在計算機中迫摔，由于機器只能識別二進制數(shù)，因此泥从，鍵盤上所有數(shù)字句占、字母和符號也必須事先為它們進行二進制編碼，以便機器對它們加以識別躯嫉、存儲纱烘、處理和傳送杨拐。

下面我們來認識下計算機中的各種編碼，我打算采用四個小節(jié)的方式凹炸，分別來介紹 ASCII碼戏阅、BCD碼、漢字的編碼啤它、檢驗碼編碼和解碼 奕筐。

一、ASCII碼

ASCII碼（美國信息交換標準碼）是計算機鍵盤上輸入字符的二進制編碼变骡。

通常离赫，ASCII碼由7位二進制數(shù)碼構(gòu)成，共可為128個字符編碼塌碌，這128個字符共分為兩類：

• 圖形字符渊胸，共96個
  • 十進制數(shù)符10個
  • 大小寫英文字母52個
  • 其他字符34個
• 控制字符，共32個
  • 回車符
  • 換行符
  • 退格符
  • 設(shè)備控制符
  • 信息分隔符
  • 其他

字符0-9所對應(yīng)的ASCII碼是在其數(shù)字的基礎(chǔ)上加30H台妆，比如字符9對應(yīng)的ASCII碼為30H + 09H = 39H翎猛。

字符A對應(yīng)的ASCII碼，是在其對應(yīng)的十六進制數(shù)的基礎(chǔ)上加37H接剩，A在十六進制里面代表數(shù)字10切厘，則有37H + 0AH = 41H，由于字符A~Z的ASCII碼是順序排列的懊缺，所有任意一個大寫字母的ASCII碼都能通過字符A的ASCII碼計算出來疫稿，比如字符Z的ASCII碼比字符A的ASCII碼大25（19H），所以鹃两，字符Z所對應(yīng)的ASCII碼為41H + 19H = 5AH遗座。

小寫的字母所對應(yīng)的ASCII碼比其對應(yīng)的大寫字母的ASCII碼大32（20H），所以小寫字母a所對應(yīng)的ASCII碼為41H + 20H = 61H俊扳，由于小寫字母a~z所對應(yīng)的ASCII碼也是順序排列的途蒋，所以任意一個小寫字母的ASCII碼也可以參照字符a的ASCII碼計算出來。

在8位微型計算機中馋记，信息通常是按字節(jié)存儲和傳送的号坡，一個字節(jié)有8位。ASCII碼有7位抗果，作為一個字節(jié)還多出一位，多出的這一位是最高位奸晴，常常用作奇偶校驗冤馏，也稱為奇偶校驗位。奇偶校驗位可以用來校驗信息傳送過程中是否有錯寄啼。

二逮光、BCD碼

BCD碼是十進制數(shù)的二進制編碼代箭。

計算機對十進制數(shù)的處理過程：鍵盤上輸入的十進制數(shù)字先被替換成一個個的ASCII碼送入計算機，然后通過程序替換成BCD碼涕刚，并對BCD碼直接進行運算（也可以先把BCD碼替換成二進制碼進行運算嗡综，并把運算結(jié)果再變?yōu)?code>BCD碼），最后把BCD碼形式的輸出結(jié)果變換成ASCII碼才能在屏幕上加以顯示杜漠。

BCD碼是一種具有十進制權(quán)的二進制編碼极景。它的種類較多，常用的有8421碼驾茴、2421碼盼樟、余3碼和格雷碼。

以8421碼為例：

8421碼是BCD碼的一種锈至，因組成它的4位二進制數(shù)碼的權(quán)為8晨缴、4、2峡捡、1而得名击碗。

8421碼是一種采用4位二進制數(shù)來代表十進制數(shù)碼的代碼系統(tǒng)，在這個代碼系統(tǒng)中们拙，10組4位二進制數(shù)分別代表了0~9中的10個數(shù)字符號稍途，如下表所示：

表2.1 8421 BCD編碼表

4位二進制數(shù)字共有16種組合，其中0000B ~ 1001B為8421的基本代碼系統(tǒng)睛竣，1010B ~ 1111B未被使用晰房，稱為非法碼或冗余碼。

10以上的所有十進制數(shù)至少需要2位8421碼字（即8位二進制數(shù)數(shù)字）來表示射沟，而且不應(yīng)出現(xiàn)非法碼殊者，否則就不是真正的BCD數(shù)。

1. BCD加法運算

BCD加法是指兩個BCD數(shù)按“逢十進一”原則進行相加验夯，其和也是一個BCD數(shù)猖吴。

在進行BCD加法過程中，計算機對二進制加法結(jié)果進行修正的原則是：

• 若和的低4位大于9或低4位向高4位發(fā)生了進位挥转，則低4位加6修正海蔽；
• 若高4位大于9或高4位的最高位發(fā)生進位钱烟，則高4位加6修正祷蝌。

舉例說明：48 + 69藻懒，則BCD的加法過程為：

BCD加法過程

2. BCD減法運算

與BCD加法類似卡骂，BCD減法時也要修正吴汪。

在BCD減法過程中茫经，若本位被減數(shù)大于減數(shù)（即低4位二進制數(shù)的最高位無借位）雪侥，則減法是正確的郎逃；若本位被減數(shù)小于減數(shù)，則減法時就需要借位豁护，由于BCD運算規(guī)則是借1當(dāng)作10哼凯，二進制在兩個BCD碼間的運算規(guī)則是借1當(dāng)作16，而機器是按二進制規(guī)則運算的楚里，故必須進行減6修正断部。

在BCD減法過程中，計算機對二進制運算結(jié)果修正的原則：

• 若低4位大于9或低4位向高4位有借位班缎，則低4位減6修正蝴光；
• 若高4位大于9或高4位最高位有錯位，則高4位減6修正吝梅。

舉例說明：53 - 27虱疏，則BCD的減法過程為：

BCD減法過程

所以，53 - 27 = 00100110B苏携。

note： 在計算機中做瞪，兩個數(shù)的減法被轉(zhuǎn)換成被減數(shù)的補碼加上減數(shù)相反數(shù)的補碼來完成，也就是說在計算機中不存在減法電路右冻。

三装蓬、漢字的編碼

在計算機中，每個漢字都是一個圖形纱扭，因此牍帚，計算機若要對漢字進行處理，就必須對所有漢字進行二進制編碼乳蛾，建立一個龐大的漢字庫暗赶，以便計算機進行查找。

小知識： 歷史上使用過的漢字約有60000多個肃叶，常用的漢字約有6000多個蹂随，其中，使用頻度達到90%的漢字約有2400個因惭，其余漢字的使用頻度只占10%岳锁。

1. 國標碼（GB2312）

國標碼是《信息交換用漢字編碼字符集的基本集》的簡稱，是我國國家標準總局于1981年頒布的國家標準蹦魔，編號為GB2312-80激率。

在國標碼中，共收集漢字6763個勿决，分為兩級：

1. 第一級收集漢字3755個乒躺，按拼音排序；
2. 第二級收集漢字3008個低缩，按部首排序嘉冒。

還包括了一般字符201個（間隔符、標點符號、運算符號健爬、單位符號和制表符等）、序號60個么介、數(shù)字22個娜遵、拉丁字母66個、漢語拼音符號26個壤短、漢語注音字母37等设拟。因此，連同漢字一共是7445個圖形字符久脯。

為了給7445個圖形字符編碼纳胧，國標碼采用14位二進制來給這些圖形字符編碼。14位二進制中的高7位占一個字節(jié)（最高位不用）帘撰，稱為第一字節(jié)跑慕；低7位占另一個字節(jié)（最高位不用），稱為第二字節(jié)摧找。

國標碼中的漢字和字符分為字符區(qū)和漢字區(qū)核行。

• 21H ~ 2FH（第一字節(jié)）和21H ~ 7EH（第二字節(jié)）為字符區(qū)，用于存放非漢字圖形字符蹬耘；
• 30H ~ 7EH（第一字節(jié)）和21H ~ 7EH（第二字節(jié)）為漢字區(qū)芝雪。

因此，國標碼采用4位十六進制數(shù)來表示一個漢字综苔。例如惩系，“啊”的國標碼為3021H（30H為第一字節(jié)，21H為第二字節(jié)）如筛。

2. 區(qū)位碼及漢字機內(nèi)碼

（1）區(qū)位碼

區(qū)位碼與國標碼的區(qū)別不大堡牡，它們共用一張編碼表。國標碼用4位十六進制數(shù)來表示一個漢字妙黍，區(qū)位碼是用4位十進制區(qū)號和位號來表示一個漢字悴侵。

（2）漢字機內(nèi)碼

由于國標碼每個字節(jié)的最高位都是0，與國際通用的標準ASCII碼無法區(qū)分拭嫁，因此可免，我國將每個漢字所對應(yīng)的國標碼的兩個字節(jié)的最高位分別設(shè)定為1，作為該字的機內(nèi)碼做粤。

四浇借、檢驗碼編碼和解碼

在計算機中，信息存入磁盤怕品、磁帶或其他存儲器中常常會由于某種干擾而發(fā)生錯誤妇垢，信息在傳輸過程中也會因為傳輸線路上的各種干擾而使接收端接收到的數(shù)據(jù)和發(fā)送端發(fā)送的數(shù)據(jù)不同。為了確保計算機可靠工作，人們希望計算機能對從存儲器中讀取的數(shù)據(jù)或從接收端接收到的數(shù)據(jù)自動做出判斷闯估，并加以糾錯灼舍。由此，引出了計算機對校驗碼的編碼和解碼問題涨薪。

校驗碼編碼發(fā)生在信息發(fā)送之前（或存儲）之前骑素，校驗碼解碼則在信息被接收（或讀出）后進行。也就是說：欲發(fā)送信息應(yīng)首先按照某種約定規(guī)律編碼成校驗碼刚夺，使得這些有用信息加載在校驗碼上進行傳送献丑；接收端對接收到的校驗碼按約定規(guī)律的逆規(guī)律進行解碼和還原，并在解碼過程中去發(fā)現(xiàn)和糾正因傳輸過程中的干擾所引起的錯誤碼位侠姑。

1. 奇偶校驗碼編碼

奇偶校驗碼編碼和解碼又稱為奇偶校驗创橄，是一種只有一位冗余位的校驗碼編碼方法，常用于主存校驗和信息傳送莽红。

奇偶校驗分為奇校驗和偶校驗兩種：

• 奇校驗的約定編碼規(guī)律：要求編碼后的校驗碼中1的個數(shù)（包括有效信息位和奇校驗位）為奇數(shù)妥畏；
• 偶校驗的編碼規(guī)律：要求編碼后的校驗碼中1的個數(shù)（包括有效信息位和偶校驗位）為偶數(shù)。

一個8位奇偶校驗碼安吁，有效信息位通常位于奇偶校驗碼中的低7位咖熟，一位奇偶校驗位處于校驗碼中的最高位。

對于奇偶校驗碼來說柳畔，需要知道以下幾點：

• 奇偶校驗位狀態(tài)常由發(fā)送端的奇偶校驗電路自動根據(jù)發(fā)送字節(jié)低7位中“1”的個數(shù)來確定馍管。
• 奇偶檢驗電路通常采用異或電路實現(xiàn)，如果采用偶檢驗薪韩，發(fā)送端將所有信息位經(jīng)過異或后所得的結(jié)果就是偶校驗位确沸；若采用奇校驗，所有信息位異或后取反就是奇校驗位俘陷。
• 接收端將接收到的全部信息（包括校驗信息位）進行異或運算罗捎，若采用的是偶校驗，異或運算的結(jié)果為0拉盾，則認為接收到的信息正確桨菜；若采用奇校驗，全部信息位異或后結(jié)果為1捉偏，則認為傳輸正確倒得，否則傳輸錯誤。
• 對于采用奇偶校驗的信息傳輸線路夭禽，奇偶校驗位的狀態(tài)取決于其余7位信息中“1”的奇偶性霞掺，對于偶校驗，若其他7位中“1”的個數(shù)為偶數(shù)讹躯，則奇偶校驗電路自動在校驗位上補0菩彬；若“1”的個數(shù)為奇數(shù)缠劝，則校驗位上為1，以保證所傳信息字節(jié)中“1”的個數(shù)為偶數(shù)骗灶。

例如惨恭，字符C的ASCII碼為01000011B，采用偶校驗耙旦，校驗位形成過程為：

校驗位
= D? ⊕ D? ⊕ D? ⊕ D? ⊕ D? ⊕ D? ⊕ D? 
= 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 
= 1  

校驗位占D?位喉恋，最后形成含有偶檢驗位的信息編碼為11000011。
這樣母廷，接收端奇偶校驗電路只要判斷每個字節(jié)中是否有偶數(shù)個“1”（包括奇偶校驗位）就可以知道信息在傳輸中是否出錯。

奇偶校驗的缺點：

• 無法檢驗每個字節(jié)中同時發(fā)生偶數(shù)個錯碼的通信錯誤糊肤；
• 當(dāng)檢驗出錯誤時琴昆，無法確定到底是哪一位出錯。

2. 海明碼編碼

海明碼是一種既能發(fā)現(xiàn)錯誤馆揉，又能糾正錯誤的校驗碼业舍。

海明碼的碼位有（n+k）位，n為有效信息的位數(shù)升酣，k為奇偶校驗位位數(shù)舷暮。k個奇偶校驗位有2^k種組合，除采用一種組合指示信息在傳送或讀出過程中有無錯誤外噩茄，尚有（2^k - 1）種組合可以用來指示出錯的碼位下面。因此，若要能指示海明碼中任意一位是否有錯绩聘，則校驗碼的位數(shù)k必須滿足如下關(guān)系：2^k >= n+k+1沥割，由此，可以計算出n與k的關(guān)系如下表所示：

表4.2.1 有效信息位與所需校驗位的關(guān)系

在確定了n與k的值后机杜，還要進一步確定哪些位為有效信息位及哪些位作為奇偶校驗位。

海明碼規(guī)定：位號恰好等于2的權(quán)值的那些位（即：第1（ 2^0 ） 位衅谷、第2（ 2^1 ）位椒拗、第4（ 2^2 ）位、第8（ 2^3 ）位）均可用作奇偶校驗位获黔，并命名為P?蚀苛，P?，P?玷氏，P?枉阵，...，余下各位則是有效信息位预茄。

接下來兴溜，通過一個例子來說明對ASCII碼進行海明碼編碼和解碼的原理侦厚。

在對海明碼的編碼、解碼原理介紹前拙徽，先對海明碼的結(jié)構(gòu)形式簡單敘述下刨沦。

（1）海明碼的結(jié)構(gòu)形式

我們知道ASCII碼有7位有效信息位（n = 7），由上表可知膘怕，k = 4想诅，故海明碼的碼長為(n + k) = 11位。根據(jù)海明碼對奇偶校驗位位號的上述規(guī)定岛心，第1来破、2、4忘古、8位應(yīng)為奇偶校驗位徘禁，其余各位為有效信息位。其分配關(guān)系如下：

note：其中髓堪，P?送朱、P?、P?干旁、P?為奇偶校驗位驶沼；D?、D?争群、D?回怜、D?、D?换薄、D?鹉戚、D?為有效數(shù)據(jù)位；最上面一排為海明碼的位號专控。

在海明碼中抹凳，奇偶校驗位P?、P?伦腐、P?赢底、P?（海明碼位號為1、2柏蘑、4幸冻、8）負責(zé)對各有效信息位的校驗。

檢驗位和被校驗的信息位之間的關(guān)系為：海明碼的位號可看作是2^i累加（i從0開始）咳焚，例如信息位D?的海明碼位號為3 = (2^0 + 2^1)洽损，信息位D?的海明碼位號為9 = (2^0 + 2^3)。由此可以看成革半，如果信息位的海明碼位號對應(yīng)的二進制累加求和中含有2^i碑定，則該位信息位就被對應(yīng)的Pi校驗流码，所以，海明碼位號為3的D?信息位應(yīng)該被P?和P?位校驗延刘；海明碼碼號為9的D?信息位應(yīng)被P?和P?所校驗漫试。

按此關(guān)系可推出：

• P?負責(zé)對第3、5碘赖、7驾荣、9、11位的校驗普泡；
• P?負責(zé)對第3播掷、6、7撼班、10歧匈、11位的校驗；
• P?負責(zé)對第5权烧、6、7位的校驗伤溉；
• P?負責(zé)對第9般码、10、11位的校驗乱顾。

轉(zhuǎn)化成表板祝，展示如下：

表4.2.2 奇偶校驗位表

（2）海明碼的編碼原理

海明碼編碼過程在發(fā)送端一側(cè)進行，其主要任務(wù)是根據(jù)有效信息位確定P?候引、P?侯养、P?、P?的值澄干，并填入相應(yīng)海明碼的碼位上逛揩。

以字符A的ASCII碼（41H（1000001B））為例柠傍，填入海明碼的相應(yīng)位號上變?yōu)椋?/p>

確定奇偶校驗位P?、P?息尺、P?携兵、P?的值必須按表4.2.2 奇偶校驗位表進行。

編碼方法：按偶校驗或奇校驗規(guī)則統(tǒng)計相應(yīng)被校海明碼位號中“1”的個數(shù)搂誉。對于偶校驗編碼的方法是：若被校位號中“1”的個數(shù)為奇數(shù)徐紧，則相應(yīng)奇偶校驗位為“1”；若被校驗位號中“1”的個數(shù)為偶數(shù)炭懊，則相應(yīng)偶校驗位為“0”并级。

（3）海明碼的糾錯

海明碼的糾錯是在海明碼解碼過程中完成的，糾錯很簡單侮腹，只要把錯位取反就行了嘲碧。而問題的關(guān)鍵是要弄清海明碼中究竟錯在哪一位上。

海明碼的出錯指示碼E?父阻、E?愈涩、E?、E?又稱為指誤字加矛。指誤字不僅可以指出數(shù)據(jù)在讀出或傳送過程中有無錯誤履婉，而且可以指示究竟錯在哪一位上。

例如斟览，若E?E?E?E? = 0000B毁腿，則表明數(shù)據(jù)在讀出或傳送過程中沒有發(fā)生錯誤；若E?E?E?E? = 0001B苛茂，則表明海明碼的第1位（奇偶校驗位P?）有錯已烤；若E?E?E?E? = 0011B，則表明海明碼的第3位有錯妓羊。

因此胯究，海明碼解碼的主要問題可以歸結(jié)為如何求取出錯標志位E?、E?躁绸、E?及E?唐片。

出錯標志位的求取規(guī)則是按下表進行的。

表4.2.3 出錯標志位和所檢測的位號表

偶校驗解碼的方法是涨颜，若被檢測所有海明碼位號中“1”的個數(shù)為奇數(shù)费韭，則相應(yīng)出錯標志位的值為1；若被檢測所有海明碼位號中1的個數(shù)為偶數(shù)庭瑰，則相應(yīng)出錯標志位的值為0星持。

例如：若接收端接收到的字符A的海明碼中第11位錯成0，變成如下形式：

則有：

   （1）（3）（5）（7）（9）（11）
E? = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 1 
--------------------------------------------------
   （2）（3）（6）（7）（10）（11）
E? = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 1
--------------------------------------------------
   （4）（5）（6）（7）
E? = 0 ⊕ 0 ⊕ 0 ⊕ 0 = 0
--------------------------------------------------
   （8）（9）（10）（11）
E? = 1 ⊕ 0 ⊕ 0 ⊕ 0 = 1

故弹灭，指誤字為E?E?E?E? = 1011B督暂，指示第11位出錯揪垄，將它取反，則錯誤碼得到糾正逻翁。

3. 循環(huán)冗余校驗碼

循環(huán)冗余校驗碼（CRC碼）可以發(fā)現(xiàn)并糾正信息存儲或傳輸過程中連續(xù)出現(xiàn)的多位錯誤饥努，這在輔助存儲器和計算機通信方面得到了廣泛的應(yīng)用。

CRC碼是一種基于模2運算（即以按位模2相加為基礎(chǔ)的四則運算八回，運算時不考慮進位和借位）建立編碼規(guī)律的校驗碼酷愧，可以通過模2運算來建立有效信息位和校驗位之間的約定關(guān)系。

這種約定關(guān)系為：假設(shè)n是有效數(shù)據(jù)信息位位數(shù)缠诅，r是校驗位位數(shù)溶浴。則n位有效信息位與r位校驗位所拼接的數(shù)（k = n + r位長），能被某一約定的數(shù)除盡管引。

（1）CRC的編碼方法

待編碼的有效信息以多項式M(x)表示士败，將M(x)左移r位得到多項式M(x) × x^r，使低r位二進制位全為零褥伴，以便與隨后得到的r位校驗位相拼接谅将。

使用多項式M(x) × x^r除以生成多項式G(x)，求得的余數(shù)即為校驗位重慢。為了得到r位余數(shù)（校驗位）饥臂，G(x)必須是r + 1位的。

將r位余數(shù)R(x)與左移r位的M(x) × x^r相加伤锚，就得到n + r位的CRC碼擅笔。

（2）模2運算

模2運算：不考慮借位和進位的運算志衣。

• 模2加減
  可用異或門實習(xí)屯援，即：

0 + 0 = 0;
0 + 1 = 1;
1 + 0 = 1;
1 + 1 = 0;
0 - 0 = 0;
0 - 1 = 1;
1 - 0 = 1;
1 - 1 = 0;

• 模2乘法
  用模2加求部分積之和。
• 模2除法
  用模2減求部分余數(shù)念脯，每上一位商狞洋，部分余數(shù)要減少一位，上商規(guī)則是：余數(shù)最高位為1绿店，就商1吉懊，否則商0。當(dāng)部分余數(shù)的位數(shù)小于除數(shù)時假勿，該余數(shù)為最后余數(shù)借嗽。

舉例說明：設(shè)四位有效信息位是1100，選用生成多項式G(x) = 1011转培，求有效信息位1100的CRC編碼恶导。

（1）將有效信息位1100表示為多項式M(x)

M(x) = x3 + x2 = 1100

（2）M(x)左移3位，得M(x) × x3 

M(x) × x3 = x? + x? = 1100000

（3）用r + 1位的生成多項式G(x)浸须，對M(x) × x3作模2除

M(x) × x3      1100000                    010
----------- = --------------- = 1110 + --------------
G(x)             1011                     1011

（4）M(x) × x3與r位余數(shù)R(x)做模2加惨寿，即可求得它的CRC碼

M(x) × x3 + R(x) = 1100000 + 010 = 1100010

（3）CRC的譯碼及糾錯

CRC碼傳輸?shù)侥繕瞬考r邦泄，用約定的多項式G(x)對收到的CRC碼進行“模2除”，若余數(shù)為0裂垦，則表明該CRC校驗碼正確顺囊，否則表明有錯，不同的出錯位蕉拢，其余數(shù)是不同的特碳，由余數(shù)指出是哪一位出了錯然后加以糾正。

表4.3.1 G(x) = 1011時企量，CRC碼出錯模式表

由上表可知测萎，若CRC碼有一位出錯，用G(x)作“模2除”運算届巩，則得到一個不為零的余數(shù)硅瞧，若對余數(shù)補零，繼續(xù)作“模2除”運算恕汇，會得到一個結(jié)果：各次余數(shù)會按上表中的順序循環(huán)腕唧。

例如，第一位N?出錯瘾英，余數(shù)將為1枣接，補零后再除，得到余數(shù)為010缺谴，以后依次為100但惶、011、……湿蛔，反復(fù)循環(huán)膀曾。這就是循環(huán)碼的由來，利用這個特性正好可以來糾錯阳啥。

當(dāng)余數(shù)不為零時添谊，一邊對余數(shù)補零繼續(xù)作“模2除”運算，一邊將被檢測的CRC碼循環(huán)左移察迟。由上表可知斩狱，當(dāng)出現(xiàn)余數(shù)為101時，出錯位也移到了N?位扎瓶，可通過“異或門”將它們糾正后所踊，再在下次移位時送回N?，然后繼續(xù)移位概荷，直至移滿一個循環(huán)秕岛，就得到一個糾正后的碼字。

（4）關(guān)于生成多項式

不是任何一個（r + 1）位多項式都能作為生成多項式，從檢錯瓣蛀、糾錯的要求來看陆蟆，生成多項式應(yīng)滿足下列要求：

• 任何一位發(fā)生錯誤，都應(yīng)使余數(shù)不為零惋增；
• 不同位發(fā)生錯誤叠殷，都應(yīng)使余數(shù)不同；
• 對余數(shù)補零诈皿，繼續(xù)作“模2除”林束，應(yīng)使余數(shù)循環(huán)。