計(jì)算機(jī)中的編碼

(1)二進(jìn)制、十進(jìn)制和十六進(jìn)制等常用數(shù)制及其相互轉(zhuǎn)換：

  由于計(jì)算機(jī)的存儲(chǔ)器和寄存器是兩態(tài)部件，所以各種信息在計(jì)算機(jī)中是以二進(jìn)制的方式存儲(chǔ)和計(jì)算的。數(shù)制是由基數(shù)和基數(shù)個(gè)不同的數(shù)碼組成的。
  BCD碼：十進(jìn)制的二進(jìn)制表示，

  0：0000     1：0001    2：0010   3：0011  4：0100    5：0101
6：0110     7：0111    8：1000   9：1001

十進(jìn)制的202可以表示成BCD碼為0010 0000 0010；    

十六進(jìn)制 <-> 二進(jìn)制:十六進(jìn)制表示法是用16位二進(jìn)制數(shù)字組成的,每4位二進(jìn)制數(shù)字表示一位十六進(jìn)制數(shù),十六進(jìn)制的數(shù)字表示從0-9,A,B,C,D,E,F共十六個(gè)字符.十六進(jìn)制與二進(jìn)制相互轉(zhuǎn)換就是一位十六進(jìn)制字符與四位二進(jìn)制數(shù)字的相互轉(zhuǎn)換過(guò)程.

十進(jìn)制　　<->　二進(jìn)制:十進(jìn)制向二進(jìn)制轉(zhuǎn)換分兩步進(jìn)行:首先把該數(shù)的整數(shù)部分和小數(shù)部分轉(zhuǎn)換為二進(jìn)制數(shù);然后再把這兩部分合并起來(lái)即可.十進(jìn)制的整數(shù)部分向二進(jìn)制轉(zhuǎn)換是通過(guò)對(duì)十進(jìn)制不斷的除2取余數(shù)得到，十進(jìn)制小數(shù)部分通過(guò)乘2取整的方法獲得，直到小數(shù)部分為0，所得到的整數(shù)部分就形成了二進(jìn)制編碼；同樣的，二進(jìn)制向十進(jìn)制轉(zhuǎn)換如下所示：

十進(jìn)制數(shù)N=（RnRn-1...R1R0R-1...R-m）
      = Rn *2n+Rn-1*2n-1+...+R1*2+R0+R-1*2-1...R-m*2-m

八進(jìn)制   <-> 二進(jìn)制:二進(jìn)制向八進(jìn)制轉(zhuǎn)換的方法是從小數(shù)點(diǎn)開(kāi)始分別向左右每3位二進(jìn)制數(shù)編成一組,若不夠3位 ,則小數(shù)點(diǎn)左側(cè)的最高位和右側(cè)的最低位用0補(bǔ)充,每一組用對(duì)應(yīng)的八進(jìn)制的數(shù)碼表示即可;八進(jìn)制向二進(jìn)制轉(zhuǎn)換的方法是從小數(shù)點(diǎn)開(kāi)始,把每一位八進(jìn)制的數(shù)碼轉(zhuǎn)換成對(duì)應(yīng)的3位二進(jìn)制即可.其小數(shù)點(diǎn)左側(cè)的最高位或右側(cè)的最低位的0可以省去.

(2) 計(jì)算機(jī)中的二進(jìn)制數(shù)運(yùn)算方法：

1．   定點(diǎn)數(shù)運(yùn)算：要判斷是否溢出？( )

加法：[X+Y]=（[X]補(bǔ)+[Y]補(bǔ)） MOD 2
減法：[X-Y]=（[X]補(bǔ)+[-Y]補(bǔ)）MOD 2

乘法：采用原碼比較方便，使用原碼一位乘法來(lái)求兩個(gè)定點(diǎn)數(shù)的乘積。運(yùn)算規(guī)則為：

          乘積的符號(hào)位等于乘數(shù)和被乘數(shù)的符號(hào)位進(jìn)異或；
          乘積的值等于兩數(shù)絕對(duì)值之積，即乘數(shù)和被乘數(shù)的絕對(duì)值進(jìn)行移位相加；

除法：采用原碼比較方便。運(yùn)算規(guī)則為：

商的符號(hào)位同定點(diǎn)數(shù)原碼乘法的處理方法，由兩數(shù)的符號(hào)位進(jìn)行異或
兩數(shù)的絕對(duì)值部分進(jìn)行相除。

      2．  浮點(diǎn)運(yùn)算

1) 加減法：

a)        對(duì)階
b)        尾數(shù)進(jìn)行加、減運(yùn)算
c)        規(guī)格化
d)        舍入
e)        溢出判斷
2) 乘除法：

浮點(diǎn)相乘，其積的階碼為兩數(shù)階碼相加，積的尾數(shù)為兩尾數(shù)相乘。
浮點(diǎn)數(shù)相除，其商的階碼為兩數(shù)階碼之差，商的尾數(shù)為兩尾數(shù)相除。
其結(jié)果都需要進(jìn)行規(guī)格化處理，同時(shí)還需要進(jìn)行溢出判斷。

(3) 邏輯代數(shù)的基本運(yùn)算和邏輯表達(dá)式的化簡(jiǎn)： 

    邏輯表達(dá)式就是以邏輯運(yùn)算符把若干邏輯變量連接在一起表示某種關(guān)系的表達(dá)式。一個(gè)邏輯函數(shù)往往有多種不同的表達(dá)式?？梢岳闷浔具壿嬤\(yùn)算規(guī)律和一些常用的邏輯恒等式對(duì)邏輯表達(dá)式進(jìn)行合并項(xiàng)、吸收項(xiàng)、配項(xiàng)、消去項(xiàng)等操作來(lái)化簡(jiǎn)。

基本的邏輯運(yùn)算有“與”、“或”、“非”、“異或”。

常用的邏輯運(yùn)算公式：
交換律：A+B=B+A  A*B=B*A
結(jié)合律：A+（B+C）=（A+B）+C
分配律：A*（B+C）=A*B+A*C  A+（B*C）=（A+B）*（A+C）
    反演律：A+B= A * B
重疊律：A+A=A A*A=A
  互補(bǔ)律：A+ A =1 A* A =0
  對(duì)合律： A =A
0-1律：0+A=A A*A=0

(4) 定點(diǎn)數(shù)與浮點(diǎn)數(shù)的機(jī)內(nèi)表示：

  定點(diǎn)數(shù)的表示方法：
1.      定點(diǎn)整數(shù)：（符號(hào)位）（最高數(shù)據(jù)位）。。。（最低數(shù)據(jù)位）
2.      定點(diǎn)小數(shù)：（符號(hào)位）小數(shù)點(diǎn)（最高數(shù)據(jù)位）。。。（最低數(shù)據(jù)位）
浮點(diǎn)數(shù)表示方法：
 浮點(diǎn)數(shù)編碼：符號(hào)位-階碼-尾數(shù)，階碼由移碼表示，尾數(shù)由補(bǔ)碼或原碼表示；
 規(guī)格化處理：以純小數(shù)表示尾數(shù)，分為原碼和補(bǔ)碼；#p#

(5) 原碼、補(bǔ)碼、反碼、移碼 ；

   數(shù)值數(shù)據(jù)的機(jī)器內(nèi)表示形式稱為機(jī)器碼，機(jī)器碼所代表的數(shù)值為該機(jī)器碼的真值。
原碼表示：[X]=X或2n-1-X；+0和-0的表示不同；（定點(diǎn)整數(shù)）
          [X]=X或1-X；                              （定點(diǎn)小數(shù)）
          +0=00000000     -0=10000000            (2的n次方-1個(gè)編碼)
補(bǔ)碼表示：[X]=X或2n+X；                      （定點(diǎn)整數(shù)）
          [X]=X或2+X；                              （定點(diǎn)小數(shù)）
          0的編碼唯一；00000000                 (2的n次方個(gè)編碼)
          -1=10000000 (小數(shù))                 -1=11111111（整數(shù)）
反碼表示：[X]=X或(2n-1)+X；                （定點(diǎn)整數(shù)）
          [X]=X或(2-2-n+1)+X          （定點(diǎn)小數(shù)）
          +0=00000000        -0=11111111        (2的n次方-1個(gè)編碼)
移碼表示：[X]=X或2¬¬¬¬¬¬¬的(n-1)次方+X；0表示方法唯一10000000    (定點(diǎn)整數(shù))
          [X]=1+X；                                  （定點(diǎn)小數(shù)）
         0的編碼唯一：10000000                  (2的n次方個(gè)編碼)

(6) ASCII碼及漢字編碼等常用的編碼 ：  
   ASCII碼采用7bit編碼， 共有128種編碼；表示128個(gè)不同的字符；計(jì)算機(jī)里存儲(chǔ)和傳送單位通常使用Byte，所以7位的ASCII碼也用一個(gè)字節(jié)來(lái)表示，最高一位沒(méi)有用，通常也添0，也可以把它作為校驗(yàn)位或用來(lái)擴(kuò)展字符集。
   EBCDIC碼采用8bit編碼，共有256個(gè)編碼，表示256個(gè)不同字符；
   漢字編碼：
1.      數(shù)字編碼：每個(gè)漢字分配一個(gè)數(shù)字碼，用以代表漢字；
2.      拼音碼：用每個(gè)漢字的漢語(yǔ)拼音符號(hào)作為漢字的輸入編碼；
3.      字形碼：以漢字的形狀特點(diǎn)編碼，例如五筆字型編碼
漢字存儲(chǔ)：以內(nèi)碼形式存放，以連續(xù)兩個(gè)字節(jié)表示，兩個(gè)字節(jié)的最高位均為1，漢字的內(nèi)碼是在計(jì)算機(jī)內(nèi)處理漢字信息時(shí)采用的機(jī)內(nèi)代碼，把漢字的輸入編碼稱為外碼。
漢字輸出：漢字的點(diǎn)陣字型碼，點(diǎn)陣的密度決定了漢字的美觀程度，漢字需要大量的存儲(chǔ)空間，例如16*16點(diǎn)陣，每個(gè)漢字要占用16*16=32Byte

  (7) 數(shù)據(jù)校驗(yàn)碼：計(jì)算機(jī)在存儲(chǔ)和傳送數(shù)據(jù)過(guò)程中，為了保證數(shù)據(jù)的準(zhǔn)確性，一般都要進(jìn)行數(shù)據(jù)校驗(yàn)和糾錯(cuò)。通常使用校驗(yàn)碼的方法來(lái)檢測(cè)數(shù)據(jù)是否出錯(cuò)。其基本思想是把數(shù)據(jù)可能出現(xiàn)的編碼區(qū)分為合法編碼和錯(cuò)誤編碼。
使用校驗(yàn)碼來(lái)查錯(cuò)，涉及到一個(gè)重要概念——碼距。它是指一個(gè)編碼系統(tǒng)中任意兩個(gè)合法編碼之間至少有多少個(gè)二進(jìn)制位不同。碼距為1的編碼是不能發(fā)現(xiàn)錯(cuò)誤的。

常用的校驗(yàn)碼有3種。

▲奇偶校驗(yàn)碼：不能發(fā)現(xiàn)偶數(shù)位錯(cuò)誤

該編碼通過(guò)增加一位校驗(yàn)位來(lái)使編碼中1的個(gè)數(shù)為奇數(shù)（奇校驗(yàn)）或者為偶數(shù)（偶校驗(yàn)）從而使碼距變?yōu)?，來(lái)檢測(cè)數(shù)據(jù)代碼中奇數(shù)出錯(cuò)的編碼。因?yàn)槠淅玫氖蔷幋a中1的個(gè)數(shù)的奇偶性作為依據(jù)，所以不能發(fā)現(xiàn)偶數(shù)位錯(cuò)誤。

校驗(yàn)位的添加方法有三種：

          水平奇偶校驗(yàn)碼：對(duì)每個(gè)數(shù)據(jù)的編碼添加校驗(yàn)位
          垂直奇偶校驗(yàn)碼：對(duì)一組數(shù)據(jù)的相同位添加一個(gè)校驗(yàn)位；
          水平垂直奇偶校驗(yàn)碼：先對(duì)一組數(shù)據(jù)垂直校驗(yàn)，所得結(jié)果再添加一位水平校驗(yàn)位；

▲海明校驗(yàn)碼：

也是利用奇偶性來(lái)檢錯(cuò)和糾錯(cuò)，通過(guò)在數(shù)據(jù)之間插入k個(gè)校驗(yàn)位，擴(kuò)大數(shù)據(jù)編碼的碼距，從而有能力檢測(cè)出n位錯(cuò)，并能糾正1位或n位錯(cuò)。

▲循環(huán)校驗(yàn)碼（CRC）校驗(yàn)碼：采用模2運(yùn)算，可檢測(cè)所有等于、小于校驗(yàn)位長(zhǎng)度的突發(fā)錯(cuò)，利用生成多項(xiàng)式為k個(gè)數(shù)據(jù)位產(chǎn)生r個(gè)校驗(yàn)位進(jìn)行編碼，其編碼長(zhǎng)度為n=k+rk,又稱為（n，k）碼，生成的多項(xiàng)式與被校驗(yàn)的數(shù)據(jù)無(wú)關(guān)。

概念：

編碼效率=（log2（碼字?jǐn)?shù)））/總位數(shù)：

例題：在無(wú)線電通信中常采用7中取3定比碼，它規(guī)定碼字長(zhǎng)為7位，并且其中總有且僅有3個(gè)“1”。這種碼的編碼效率為 ；35=
舉一個(gè)例子：關(guān)于二進(jìn)制的編碼的考試題目

根據(jù)“冗余校驗(yàn)”的思想，碼距可用來(lái)判斷使校驗(yàn)碼制冗余的程度，并估價(jià)其查錯(cuò)、糾錯(cuò)能力。“8421”碼的碼距為A ，因而它B 。若一組海明（Hamming）碼有效信息位k=4，校驗(yàn)位r=3，則其碼距為C ，用它能夠發(fā)現(xiàn)D位錯(cuò)，并可糾正E位錯(cuò)。

 A、C、D、E：    ①0         ②1         ③2         ④3         ⑤4         ⑥7

 B：  ①能發(fā)現(xiàn)1位錯(cuò)   ②能糾正1位錯(cuò)   ③能發(fā)現(xiàn)并糾正1位錯(cuò)   ④不能查錯(cuò)、糾錯(cuò)

    本題主要考查數(shù)據(jù)校驗(yàn)方法的相關(guān)知識(shí)。

    在這部分知識(shí)點(diǎn)中有個(gè)很重要的概念——碼距。碼距是指一個(gè)編碼系統(tǒng)中任意兩個(gè)合法編 

    這里有個(gè)定理，即若一種校驗(yàn)碼合法碼字集的碼矩為2d+1，則它能夠發(fā)現(xiàn)2d位錯(cuò)，并能糾正d位錯(cuò)
　A: 2   B: 4  C: 4  D: 3  E: 2