1.3.2 Побудова циклічного надлишкового коду 7,4

Побудова циклічних надлишкових кодів CRC утворюється в периферійних мікроконтролерних системах шляхом множення визначених комбінацій С(х) (рядків одиничної діагональної матриці Е_к) на утворюючий поліном Р(х) відповідного ступеню (у нашому випадку Х³+Х+1) з метою контролю правильності передачі в системі.

C(x)*x^r

P(x)

=

Q(x)

+

R(x) (9)

P(x)

C(x)-кодова комбінація (code combination);

д

Q(x)-приватне (quotient);

е:

R(x)- залишок (remainder);

P(x)-поліном, що не приводться (permanence numerous);

Після деяких перетворень вираз (9) набуде вигляду (10):

C(x)*x^r

=

Q(x)*P(x)

+

R(x)

C(x)*x^r

=

Q(x)*P(x)

+

R(x)

C(x)*x^r

=

Q(x)*P(x) (10)

+

R(x)

F(x)

=

Вирази (9) та (10) сприяють утворенню пакетів 7,4: поряд з кожною кодовою комбінацією С(х) розміщаються решти від ділення, які і є перевірочними бітами R. (див. табл.1). Таки чином, спочатку утворюється матриця G_n,k, що народжує перші к пакетів.

Для побудови матриці G_n,k маємо наступні вхідні дані:

P(x)=x³+x+1 (P(x)=1011); n=7; k=4; C₁(x)=0001; C₂(x)=0010; C₃(x)=0100; C₃(x)=1000;

r=n-k=7-4=3;

Ступінь кожного рядку C матриці Е підвищується на ступінь поліному, що не приводиться і результат ділиться на поліном, що не приводиться Р(х). Залишок від ділення R є рядками під матриці R_r, _k

0001*1000

1011

=

C₁(x)*x^r

P(x)

R₁(x) = 011

0010*1000

1011

=

C₂(x)*x^r

P(x)

R₂(x) = 110

0100*1000

1011

=

C₃(x)*x^r

P(x)

R₃(x) =111

1000*1000

1011

=

C₄(x)*x^r

P(x)

R₄(x) = 101

Таблиця 3 - Розділений циклічний надлишковий код 7,4 (пакети 7,4)

№	П акети 7,4		W Gn,k ay creation
	Інформаційні біти	Перевірочні біти
1	1000	101	1
2	0100	111	2
3	0010	110	3
4	0001	011	4
5	1100	010	1+2
6	1010	011	1+3
7	1001	110	1+4
8	0110	001	2+3
9	0101	100	2+4
10	0011	101	3+4
11	1110	100	1+2+3
12	1011	000	1+3+4
13	0111	010	2+3+4
14	1101	001	1+2+4
15	1111	111	1+2+3+4
16	0000	000	All combination

Перші чотири рядки таблиці 1 містять матрицю, що народжує, G_n,k , рядки 5-16 - добудовані істинні інформаційні пакети. Якщо поділити на поліном, що не приводиться, любий істинний пакет з таблиці 1, то отримаємо залишок R=0. Це є ознакою передачі інформації без помилок.

Візьмемо пакет №7 (див. табл..1) і поділимо на поліном P(x)=1011.

Якщо внести помилку (наприклад у біт №3) і здійснити перевірку наявності помилок в отриманому пакеті шляхом ділення його на поліном, що не приводиться, отримаємо:

Як видно залишок від ділення не рівний 0 (R=011). Тож трапилася помилка.