2019-408考研之組成原理筆記——第二章 （1）

•   計算機基礎知識——進制與定點、浮點運算

1. 進制與編碼
   1. 常見進制介紹
      1. 二進制：由一串0、1組成，其實際數值（以十進制數爲例）爲各位與對

應權重的乘積。例7(10) = 111(2) = 2^2+2^1+2^0；8(d)=1000(b)=2^3+0*2^2+0*2^1+0*2^0

1. 1. 1. 八進制：由0~7共8個不同的數字符號組成，可將二進制編碼中3位作爲

八進制的一位即可。例：15（10）=1111（2）=001 111（b）=17（o）

1. 1. 1. 十六進制：在十進制的基礎上將10用A表示，11用B表示……15用F

表示，其4位二進制碼與1位十六進制碼相同。例：28(10)=1 1100(b)=1C(h)=1CH

擴：二進制-Binary；八進制-Octal；十進制-Decimal；十六進制-Hexadecimal

1. 1. 進制的轉換
      1. 二進制轉八進制、十六進制——整數+小數：

以小數點爲界，左邊向左數，每3/4位一組轉爲八/十六進制，不足用0補；

       小數部分向右數，也是每3/4位一組轉爲八/十六進制，不足用0補。

       例：1011010.11011(b)=001 011 010.110 110(b)=0101 1010.1101 1000(b)=132.66(o)=

5A.D8(h)=90.84375(d)（任何進制轉十進制——將各位對應權重與數值相乘後再相加，例：0.11011(b)=1*2^-1 + 2^-2 + 0*2^-3 + 2^-4 +2^-5，其他進制類似）

1. 1. 1. 十進制轉其他進制（基數乘除法）——整數+小數：

以小數點爲界，左邊的整數部分和右邊的小數部分，對要轉換的進制（稱爲

       基數）進行除基取餘/乘基取整，再將兩部分沿小數點左右拼接得出結果。

       例：56234.789(b)轉爲十六進制，整數部分：56234/16=3514…10, 3514/16=219…10

       219/16=13…11, 13/16=0…13，對應順序就是13、11、10、10，即DBAA；小數部

       分：0.789*16=12.624->12，0.624*16=9.984->9，0.984*16=15.744->15，0.744*16~12

       注意小數部分轉換過程有誤差，一般確定一定的精度即可，故小數部分對應順序

       爲12、9、15、12，即C9FC，故轉爲十六進制爲DBAA.C9FC(h)

1. 1. 校驗碼

校驗碼是指能夠發現或能自動糾正錯誤的數據編碼，又稱檢錯糾正編碼。

原理：通過增加一些冗餘碼（在正常編碼之外的數碼）來檢驗或糾錯編碼

碼距：任意兩個合法碼字之間最少變化的二進制位數。碼距越大糾、檢錯能力越強，而且檢錯能力總大於等於糾錯能力。

1. 1. 1. 奇偶校驗碼：在原編碼上加一位校驗碼用於檢測、不能糾錯，碼距爲2。

方法：由有效數據+1位校驗位組成，校驗位取1或0可使整個校驗碼中

       「1」的個位爲奇數（奇校驗嘛）或偶數（偶校驗碼）

1. 1. 1. 漢明校驗碼：在原編碼上加入幾位校驗位（位於2的加權位中）將每個二進制數據進行分組，在某位出錯後導致其他校驗位出錯並可檢驗

糾錯理論：L-1=D+C 且D>=C.  編碼最小碼距L越大，檢測錯誤的位數D越大，糾錯的位數C越大。

步驟：1.確定漢明碼的位數：n+k<=2^k – 1（n爲有效信息的位數，k爲校驗位的位數，若要檢測兩位錯，需再增加1位校驗位，即k+1 位）；2.確定漢明碼校驗位的位置：規定校驗位Pi在漢明碼中爲2^i-1位中；3.分組：將剩下的有效位的位置寫成2進制碼，由校驗位在對應位的加權爲1對應分組；4.將每組對應位的數值與校驗位異或使其結果爲0，得校驗位數值；5.檢測與糾錯：利用校驗位和對應的信息位進行奇偶校驗，對應的數值爲對應位出錯，將該位數值取反即可

例：已知漢明碼的有效位D1-D8爲11010101，求其最終漢明校驗碼

1.確定位數：n爲8，由8+k<2^k – 1,解得k=4；2.確定校驗位位置：校驗位X1=0001=1，X2=0010=2，X3=0100=4，X4=1000=8；3.分組：將D1-D8按順序和X1-X4一起排列爲:

0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100
1	2	3	4	5	6	7	8	9	10	11，	12
X1	X2	D1	X3	D2	D3	D4	X4	D5	D6	D7	D8
X1	X2	1	X3	1	0	1	X4	0	1	0	1

分組爲X1:對應爲第4位爲1：D1、D2、D4、D5、D7；X2:對應爲第3位爲1：D1、D3、D4、D6、D7；X3:對應爲第2位爲1：D2、D3、D4、D8；X4:對應爲第1位爲1：D5、D6、D7、D8；4.得校驗碼：將X1與D1、D2、D4、D5、D7對應的數值異或（相同爲0，不同爲1）X1Å1Å1Å1Å0Å0=0，則X1=1；同理X2=1;X3=1;X4=0；故該漢明碼爲：1 1 1 1 101 0 0101(從左到右權重增加)；5.校驗：當某一位出錯如：D1=0，將X1=1與其小組數值異或，得S1=1；S2=1；S3=0；S4=0，故在0011位，即第3位（D1）處出錯，將其數值取反即爲正確。

1. 1. 1. 循環冗餘校驗碼（CRC）：在K位有效信息位後+R位校驗位

線性編碼理論：發送端通過將K位數據左移R位後與生成的多項式G做模2除，生成R位校驗碼，將K位數據和R位校驗碼一起發送出去；接收端通過生成的多項式對K+R做模2除，若能整除則爲正常，否則對應餘數確定出錯位置。

多項式與二進制轉換：多項式的最高冪次爲R，轉成二進制有R+1位；二進

制數用係數僅爲「0」或「1」的多項式表示：例：x3+x2+1對應爲1101；1011對應多項式爲：x3+x+1.

       例：有效信息碼爲：11010101，多項式G= x3+x2+1，求對應的CRC碼:

1. 確定多項式與CRC位數：G= G= x3+x2+1=1101，故CRC爲4+8=12位；
2. 左移4位補0並與多項式模2除，求4位餘數：除法關鍵：消去最高位的1，其他位作異或1，（無借位，餘數最高位爲1，商爲1，作模2減；最高位爲0，商爲0，除數右移一位）直至餘數位數小於除數，得餘數

該題1101 0101/1101，前4位相模2除，商爲1，此時餘數爲0；右移1位仍爲0，商爲0；右移1位，此時餘數爲001，不足，商爲0；右移1位，餘數0010，商爲0；繼續右移，餘數爲0101，商仍爲0，即當將信息碼與多項式相模後所得=的商爲1 0000；這時候在信息碼後補4個0計算4位校驗碼：右移一位，餘數是1010，商爲1，餘數爲111（沒有借位）；再右移一位，餘數是1110，商爲1，餘數爲0011；右移一位，商爲0，餘數0110；最後右移一位，餘數爲1100，商爲1，最終餘數爲0001.

故算的商爲1 0000 1101，確定的校驗碼爲0001

1. 將餘數置於信息碼之後，構成CRC碼，即1101 0101 0001；
2. 當接收端將所得信息碼與多項式1101進行模2除，餘數爲0則無錯；
3. 檢錯：設接收端收到信息碼爲1101 0101 0011，將其模2除，其餘數爲0010，即第2位出錯，將其取反即可

注：此題因爲隨意選擇數值，導致其多項式沒有選對，使得在數據出錯過程無法校正，但解題思路無誤；多項式的選擇應滿足：最高位和最低位爲1；當CRC碼的任何一位出錯時，做除應使餘數不爲0；不同爲出錯時，餘數應不同；對餘數作除應能使餘數構成循環

1. 1. 機器數（有符號數，最高位表示符號）

即一個數在計算機中的二進制表現形式。機器數是帶符號的，故將對應的數值稱爲機器數的真值。例：0001和1001對應的真值分別是+1和-1

當將符號和數值一起編碼存放時，表示的方法爲原碼、反碼、補碼、移碼：

1. 1. 1. 原碼：機器數的最高位表示該數的符號，其餘表示該數的絕對值

理解原碼與真值的區別：一個十進制的數+15，則在計算機中的二進制表現形式——真值：+1111，那麼原碼就是：01111；同理-15(真值-10) -> -1111(機器數) ->1 1111(原)

注意：根據定義 0 0000 和 1 0000 是兩種不同的表示，雖然都是0 (+0 -0)

1. 1. 1. 反碼：用於原碼與補碼互相轉換的過渡，正數的表現形式不變，負數將原碼絕對值部分全部按位取反

例：+15.5(d) –> 0 1111.1(原) -> 0 1111.1(反)；-15.5(d) –> 1 1111.1(原)->1 0000.0(反)

同理真值0的反碼也有兩種表示：+0(真值) ->0 0.0(反)；-0(真值) ->1 1.1(反)

1. 1. 1. 補碼：正數不變（原碼、反碼、移碼均一致），負數原碼取反碼後+1

例：+15.5(d) –> 0 1111.1(原) -> 0 1111.1(反)->0 1111.1(補)；-15.5(d) –>

1 1111.1(原)->1 0000.0(反)-> 1 0000.0(反) +1 = 1 0001.0(補) -> 再次取反1 1110.1(補的反碼)  ->1 1110.1(補的反碼)  +1 = 1 1111.1(原)得到原碼（負數的補碼取反碼+1就是原碼）

1. 1. 1. 移碼：在真值X上加一偏置值(一般爲最高位+1)，計算上移碼與補碼的符號位對應取反即可，注意移碼只能表示整數

例：+15(真)-> 0 1111(補) ->1 1111(移)；-15(真)-> 1 0001(補) ->0 0001(移)

補：階碼：用於表示小數(浮點數N=2^E ´ M)的階數E，用移碼錶示，其偏置量根據浮點數類型的不同而不同，如短浮點數中 (總位數爲32位，包括1位符號位，8位階碼，23位的尾數M) 規定階碼爲8位，故偏置量爲127

例：-100(真)-> - 110 0100(機器數)，即-1.1001´26(小數點左移6位)，該數的符號位爲1，M（即尾數）爲1100 1；確定階碼：階數E爲6，符號位爲0，若按短浮點規定，階碼爲0 000 0110 (6) + 127(0111 1111) = 128 + 5 = 1 000 0101，則該數-100以短浮點數編碼爲：1(符號位)  1 000 0101(階碼)  1100 1000 0……0（尾數，共23位）用十六進制保存爲C2E40000H。注：若階數爲負數：如此時階數爲-6，則階碼爲：1 111 1010(-6的補碼) + 0111 1111 = 0 111 1001 = 127-6 = 121.

                          總結：真值、原碼、反碼、補碼、移碼和階碼各自運算關係