Циклические коды. CRC и БЧХ коды

Embed Size (px)

DESCRIPTION

Циклические коды. CRC и БЧХ коды. Тихоокеанский Государственный Университет Кафедра “ Вычислительная техника ” Дисциплина “ Сети ЭВМ ” Преподаватель Шоберг А. Г. Содержание. ** Блочные и линейные коды. ** CRC код. -- CRC код. Базовые определения. -- Вычисление CRC. - PowerPoint PPT Presentation

Text of Циклические коды. CRC и БЧХ коды

. CRC .

. CRC . . ** CRC -- CRC-- -- . ** -- CRC . -- ** ** * - , .

* q . , ( 1), (q = 2).* . .

* Vk - VJ : ( ) .* - , - CRC, , - ..CRC . ** Cyclic Redundancy Code (CRC) **

* CRC , , , .

* CRC .* , , . CRC32 2-32.* , , , ; CRC.

* (, ), : 9/3=3, = 0; (9+2)/3=3, = 2.* CRC , " ". "" .

* "" . " " (eXclusive OR, - XOR), .

* CRC-:

CRC* CRC , . (W Width) , , 1001 "3", "4".

* , 1, , , , .

: 1101011011111 2 : 1. XOR , 1, . 2. XOR W , 0. * : . , .

* , , , . . * , . , , (11,7) 7- ASCII-.

* , 7- 4 (7+4=11). , .* , . . , ( , , 4):* 00000111 , 00001111. .

* s = 0x073 = 1110011 (11,7).

* * , . 2 (1, 2, 4, 8 ..).

* XOR ( ) . 11, 10, 9, 5 3. :

* , :

* :

* , , 7 (1 0) 5 (0 1). .

* N=M+C , . N+1 ( n ). =4, N=7, - : M4, M3, M2, C3, M1, C2, C1. 1, 2, 3. , 2:

* , , ( 2):

* :

* n . n , N . , . * , . , qm.* , qmm ( , D = 2qm + 1). N n- D.

* . k , k=n - log2(n+1), ( 2), k 0, 1, 4, 11, 26, 57 .., (3,1); (7,4); (15,11); (31,26); (63,57) ... . ** - - (-) , . **

* , , .

* -- () , , . . (d0 >= 5).* - .

* - , - .* - , , - P().

* n S, - k .* .

* - GF(q), q .

* , q = 2.* g(x) , n (n = 2m - 1), , , 2m.* :

((r1()) g(x) r1().

* . 2m , GF(2m) m GF(2m). (1) (0).* . 2m , GF(2m) m GF(2m). (1) (0).

* , (ra()) (ra()), :

* - - , - , .

* . * - GF(2m), - - g(x) m, n = 2m - 1. * s

* . . , . ,

* , :

* 3- 4- . .. , . .* .

* , , :

* , , .

* :

* :

* :

* - () :

* , n = 15, , :

* .** : 15- , (. . n = 15, S = 2) **

: m k m