計算機中的編碼

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

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

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

十進制的202可以表示成BCD碼為0010 0000 0010；    

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

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

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

(2) 計算機中的二進制數(shù)運算方法：

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

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

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

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

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

商的符號位同定點數(shù)原碼乘法的處理方法，由兩數(shù)的符號位進行異或
兩數(shù)的絕對值部分進行相除。

      2．  浮點運算

1) 加減法：

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

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

(3) 邏輯代數(shù)的基本運算和邏輯表達式的化簡： 

    邏輯表達式就是以邏輯運算符把若干邏輯變量連接在一起表示某種關(guān)系的表達式。一個邏輯函數(shù)往往有多種不同的表達式。可以利用其本邏輯運算規(guī)律和一些常用的邏輯恒等式對邏輯表達式進行合并項、吸收項、配項、消去項等操作來化簡。

基本的邏輯運算有“與”、“或”、“非”、“異或”。

常用的邏輯運算公式：
交換律：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
  互補律：A+ A =1 A* A =0
  對合律： A =A
0-1律：0+A=A A*A=0

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

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

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

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

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

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

常用的校驗碼有3種。

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

該編碼通過增加一位校驗位來使編碼中1的個數(shù)為奇數(shù)（奇校驗）或者為偶數(shù)（偶校驗）從而使碼距變?yōu)?，來檢測數(shù)據(jù)代碼中奇數(shù)出錯的編碼。因為其利用的是編碼中1的個數(shù)的奇偶性作為依據(jù)，所以不能發(fā)現(xiàn)偶數(shù)位錯誤。

校驗位的添加方法有三種：

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

▲海明校驗碼：

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

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

概念：

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

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

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

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

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

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

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

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