АП-97161
АНОТАЦІЯ
Документ містить опис програми, яка будує кодовікомбінації на основі циклічних кодів. Програма кодує і деко-діруетінформаційні слова. Іммітіруется робота джерела, переда-ющегоінформаційне слово, кодувальника, що кодує дане слово, каналу зв'язку ідекодувальник, виявляти і виправляти помилки в інформаційномуполінома. Програма працює за принципом приймач - джерело, так, як цереалізовано в пристроях, що передають інформацію або звичайних приводахдля зовнішніх носіїв в PC.
АП-97161
ЗМІСТ
1. Введення
.................................................. ..........................< br>............... 6
2. Постановка завдання
.................................................. ........................< br>7
3. Операції над циклічними кодами
............................................. 8
4. Принцип побудови циклічних кодів
....................................... 9
4.1. Отримання кодової комбінації додаванням залишку R (x) ...... 11
4.2. Отримання кодової комбінації множенням на який утворює поліном
.................................................. ..........................< br>.............. 14
5. Розробка схеми алгоритму
.................................................. ......... 15
6. Розробка тексту програми
.................................................. ....... 16
7. Результати роботи програми
.................................................. ..... 21
-------------------------------------------------- --------------------------< br>------------------------
Література
.................................................. ..........................< br>............ 23
Додаток № 1
.................................................. ..........................< br>... 24
Додаток № 2
.................................................. ..........................< br>... 30
§ 1 Введення
Код, в якому кодова комбінація, отримана шляхом циклічного зсувудозволеної кодової комбінації є також дозволеної кодовоїкомбінацією називається циклічним (поліноміальних, кодом з циклічниминадмірними перевірками-ЦІП).
Зрушення здійснюється справа наліво, при цьому крайній лівий символпереноситься в кінець комбінації.
Циклічний код відноситься до лінійних, блокових, коригувальних,рівномірним кодами.
У циклічних кодах кодові комбінації представляються у виглядімногочленів, що дозволяє дозволяє звести дії над кодовимикомбінаціями до дією над многочленами (використовуючи апаратполіноміальною алгебри).
Циклічні коди є різновидом систематичних кодіві тому володіють усіма їхніми властивостями. Спочатку вони були створені дляспрощення схем кодування та декодування. Їх ефекти -вність при виявленні та виправлення помилок забезпечила їм шіроеоезастосування на практиці.
Циклічні коди використовуються в ЕОМ при послідовній передачіданих.
(2 Постановка завдання
Побудувати циклічний код для передачі 31 розрядної кодової комбінаціїз виправленням одноразової помилки (n = 31, s = 1) двомаспособами.
Показати процес виявлення та виправлення одноразової помилки впереданої кодової комбінації. Скласти програму, що реалізує алгоритмкодування, декодування та виправлення помилки при передачі даних звикористанням циклічного коду.
(3 Операції над циклічними кодами
1. Зрушення справа наліво здійснюється шляхом множення полінома на x:
G (x) = x4 + x2 +1 (0010101;
G (x) (x = x5 + x3 + x (0101010.
2. Операції додавання і віднімання виконуються за модулем 2.
Вони є еквівалентність та асоціативними:
G1 (x) + G2 (x) => G3 (x);
G1 (x)-G2 (x) => G3 (x );
G2 (x) + G1 (x) => G3 (x);
Приклад:
G1 (x) = x5 + x3 + x;
G2 (x) = x4 + x3 1;
G3 (x) = G1 (x) (G2 (x) = x5 + x4 + x +1.
3. Операція поділу є звичайним поділом многочленів, тількизамість віднімання використовується додавання по модулю 2:
G1 (x) = x6 + x4 + x3;
G2 (x) = x3 + x2 +1.
x6 + x4 + x3 x3 + x2 +1
(x6 + x5 + x3 x3 + x2 x5 + x4
(x5 + x4 + x2 x2те ж у двійковому коді:
1011000 1101
(1101 1100
1100
(1101
100
Всі операції легко реалізуються апаратно на регістрах зсуву зазворотними зв'язками.
(4 Принцип побудови циклічних кодів
Ідея побудови циклічних кодів базується на використаннінепріводімих многочленів. Непріводімим називається багато-член, який неможе бять представлений у вигляді добутку многочленів нижчих ступенів
, тобто такий многочлен ділитися тільки на самого себе або на одиницю і неділитися ні на який інший многочлен. На такий многочлен ділитися беззалишку двочлен xn 1. Непріводімие багаточлени в теорії циклічних кодіввідіграють роль утворюють поліномів.
Щоб зрозуміти принцип побудови циклічного коду, множимо комбінаціюпростого k-значного коду Q (x) на Одночлен xr, а потім деліна створюючийполіном P (x), ступінь якого дорівнює r. У результаті множення Q (x) на xrступінь кожного Одночлен, що входить в Q (x), підвищена щує на r. При розподілітвори xrQ (x) на створюючий поліном виходить приватне C (x) такий жемірою, як і Q (x). Результат можна представити у вигляд
Q (x) xr R (x)
((((= C (x) + ((( , (1)
P (x) P (x)де R (x) - залишок від ділення Q (x) xr на P (x).
Приватне C (x) має таку ж ступінь, як і кодова комбінація Q (x) простогокоду, тому C (x) є кодовою комбінацією цього жпостів k-значного коду. Слід зауважити, що ступінь залишку не може бутибільше мірі утворює полінома, тобто його найвищий ступінь може бутидорівнює (r-1). Отже, найбільше число розрядів залишку R (x) неперевищує числа r.
Множачи обидві частини рівності (1) на P (x) і зробивши деякі перестановкиотримуємо:
F (x) = C (x) P (x) = Q (x) xr + R (x) (2)
Таким чином, кодова комбінація циклічного n-значного коду можебути отримана двома способами:
1) множення кодової комбінації Q (x) простого коду на Одночлен xrі додавання до цього твору залишку R (x), отриманого в результатіподілу твори Q (x) xr на який утворює полином P (x);
2) множення кодової комбінації C (x) простого k-значного на який утворюєполіном P (x).
При побудові циклічних кодів першим способом расроложеніеінформаційних символів у всіх комбінаціях строго упорядковано --вони займають k старших розрядів комбінації, а решта (nk) розрядів відводяться під контрольні.
При другому способі освіти циклічних кодів інфор -ційних і контрольні символи в комбінаціях циклічного коду не відокремленіодин від одного, що ускладнює процес декодування.
(4.1 Отримання кодової комбінації додаванням залишку R (x)
Побудувати циклічний код для передачі 31 розрядної кодовоїкомбінації з виправленням одноразової помилки (n = 31, s = 1)
Рішення.
1. Визначимо число контрольних розрядів - m: m = log2 (n +1) = log2 (31 +1) = 5.
2. Визначимо кількість інформаційних розрядів k: k = nm = 26,тобто отримали (31, 26) - код.
3. Будуємо інформаційний поліном, сответствующій інформаційномуслову довжиною k-біт:
G (x) = 00000000000000000000000101 = x2 +1.
4. Здійснюючи зсув коду вліво на m = nk = 5 розрядів тобто поліном G (x)множиться на xm: xm G (x) = (x2 +1) x5 = x7 + x5 = 0000000000000000000000010100000.
5. Вибирається створюючий многочлен-P (x) за таблицею непріводімихмногочленів. Для виправлення одиночної помилки (d0 = 3) утворює поліном
P (x) повинен бути ступеня m = nk = 5 і кількістю ненульових членів не меншемінімального кодового відстані d0 = 3. Виходячи зцього образуюшій полином P (x) дорівнює:
P (x) = x5 + x4 + x3 + x 2 +1 = 111101.
6. Визначимо залишок R (x) від ділення G (x) (xm на який утворює по-Ліном P (x) x7 + x5 x5 + x4 + x3 + x 2 1
10100000 111101 x7 + x6 + x5 + x 4 + x2 x2 + x +1 111101
111 x6 + x4 + x2
101010 x6 + x5 + x4 + x 3 + x 111101 x5 + x3 + x2 + x
101110 x5 + x4 + x3 + x 2 1
111101 x4 + x +1
10011
Залишок R (x) = x4 + x +1 = 10011.
7. Будуємо передається кодовий проліну F (x):
F (x) = xm G (x) (R (x) = x7 + x5 + x4 + x +1 = 0000000000000000000000010110011.
8. Нехай у прийнятому повідомленні сталася помилка в тридцять першомурозряді, при зтом прийняте кодове повідомлення має вигляд:
F ((x) = F (x) (E (x) = 1000000000000000000000010110011.
9. Розділемо многочлен F1 (x) соотвествующий отриманої кодової ком-комбінаціїна який утворює поліном, при цьому вага залишку (кількість одиниць в кодізалишку) повинен бути менше або дорівнює кількості помилок W (S
1000000000000000000000010110011 111101
111101
111010
111101 < p> 111000
111101
101000
111101
101010
111101
101110
111101
100110
111101
110110
111101
101100
111101
100010
111101
111110
111101
110010
111101
111111
111101
100011
111101
11110
Порівнюємо вага отриманого залишку w з числом виправляємо помилкиw> s.
10. Виробляємо циклічний зсув прийнятої кодової комбінації на одинрозряд вліво і повторюємо п.9 поки w (s.
a) 0000000000000000000000101100111 111101
111101
100011
111101
111101
111101
1 (w = s.
Складаємо по модулю 2 останнє ділене з останнім залишком:
0000000000000000000000101100111
(1
0000000000000000000000101100110
Здійснюємо зворотний зсув на 1 розряд отриманої комбінації
0000000000000000000000010110011
Відкинувши контрольні розряди, отримуємо передане інформаційної слово.
§ 4.2 Побудова кодової комбінації шляхом множення на який утворює поліном
Побудувати циклічний код для передачі 31 розрядної кодовоїкомбінації з виправленням одноразової помилки (n = 31, s = 1) шляхом множенняутворює многочлена на многочлен повного 31 розрядного коду.
Рішення.
1. Будуємо інформаційний поліном, сответствующій інформаційномуслову довжиною k-біт:
G (x) = 00000000000000000000000101 = x2 2.
2. Будуємо передається кодовий поліном
00000000000000000000000101
111101
00000000000000000000000101
00000000000000000000000101
00000000000000000000000101
00000000000000000000000101
00000000000000000000000101
0000000000000000000000011001001
3. Процес виправлення одноразової помилки аналогічний описаномув § 4.1.
(5. Розробка схеми алгоритму
Ciclic code
немає
так
немає
так
Кінець
(6. Розробка тексту програми
Для подання інформаційного слова в пам'яті використовується масив. До складу програми входить основна програма і два модулі,що реалізують алгоритм кодування і декодування інформаційних слів ідіалогу з користувачем відповідно.
Program Cyclic_Code;
Uses
Crt, _CC31, _Serv;
Var m, mm: Move_code; p: Polinom; r: Rest; i, Mainflag, From, Error: integer;
Switch: byte;
Key: boolean;begin
Repeat
Key: = true;
TextColor (11);
TextBackGround (7);
Clrscr;
SetWindow (24,10,45,14,2, 'Головне меню');
Switch: = GetMainMenuChoice; case Switch of
1: begin
About;
Readln;
Key: = False; end;
2: begin
TextColor (0);
ClrScr;
SetWindow (25,10,40,13,1, 'Утворити');
Switch: = GetSubMenuChoice; case Switch of
1: begin
TextBackGround (0);
TextColor (15);
ClrScr;
SetWindow ( 1,1,79,24,2, 'Демонстрація');
TextColor (14);
GotoXY (2,2);
Init ( m, p, r, MainFlag);
Write ( 'Інформаційний поліном');
TextColor (2); for i: = n downto 0 do begin if (i = 0 ) and (r2 [i1] = 0)) do dec (i1); if (i1 =- 1) then goto RETURN;
Kol: = n1-i1; while (Kol> 0) do begin for i: = n1 downto 1 do r2 [i]: = r2 [i-1]; dec (Kol); end;
Kol: = n1-i1; while ((Kol> 0) and (j> = 0)) do begin r2 [Kol-1]: = m2 [j]; dec (Kol); dec (j); end; if ((j =- 1) and (Kol = 0)) then begin for i: = n1 downto 0 do r2 [i]: = r2 [i] xor p2 [i]; end else flag: = Kol; end; end else if (n1 = j) then begin for i: = n1 downto 0 do begin r2 [i]: = m2 [j]; dec (j); end; for i: = n1 downto 0 do r2 [i]: = r2 [i] xor p2 [i] end else if (j0) then begin k: = n1-flag; for i: = n1 downto flag do begin m3 [k]: = r3 [i]; dec (k); end; end
else begin for i: = n1-1 downto 0 do m3 [i]: = r3 [i]; end;end;
Procedure MakeError (var m4: Move_code; var err: integer);begin
Randomize; err: = Random (n); m4 [err]: = m4 [err] xor 1;
end;
Procedure Decoder (var m6: Move_Code);var i: integer; k: byte;begin k: = 5; while (k> 0) do begin for i: = 0 to n-1 do m6 [i]: = m6 [i +1]; dec (k); end; for i: = n downto n-n1 +1 do m6 [i]: = 0;end;
Procedure BildMoveCodeMultiplication (var m7: Move_Code);var m1, m2, m3, m4, mm: Move_Code; i, j: integer;begin mm: = m7; m1: = m7; for j: = 0 to 1 do begin for i: = n downto 1 do m1 [i]: = m1 [i-1]; m1 [j]: = 0; end ; m2: = m7; for j: = 0 to 2 do begin for i: = n downto 1 do m2 [i]: = m2 [i-1]; m2 [j]: = 0; end; m3: = m7 ; for j: = 0 to 3 do begin for i: = n downto 1 do m3 [i]: = m3 [i-1]; m3 [j]: = 0; end; m4: = m7; for j: = 0 to 4 do begin for i: = n downto 1 do m4 [i]: = m4 [i-1]; m4 [j]: = 0; end; for i: = n downto 0 do m7 [i]: = mm [i] xor m1 [i] xor m2 [i] xor m3 [i] xor m4 [i];
end;
Procedure Correction (var m5: Move_code; p5: Polinom; var r5: Rest);var i, Correctflag, i1: integer;
Count, Countcarry, Carryflag: byte;
begin
Correctflag: = 0;
Countcarry: = 0; repeat for i: = n1 downto 0 do r5 [i]: = 0;
Count: = 0;
Divizion (m5, r5, p5, Correctflag); i1: = n1; while ((i1> = Correctflag) and (r5 [i1] = 0)) do dec (i1); if (((i1 = Correctflag-1) or
() (i1 = Correctflag) and (r5 [Correctflag] = 1 )){)} then m5 [0]: = m5 [0] xor r5 [Correctflag] else begin
Carryflag: = m5 [ n]; for i: = n downto 1 do m5 [i]: = m5 [i-1]; m5 [0]: = Carryflag; inc (Countcarry); end; until (((i1 = Correctflag-1) or
() (i1 = Correctflag) and (r5 [Correctflag] = 1 ));{);} while (Countcarry> 0) do begin
Carryflag: = m5 [0 ]; for i: = 0 to n-1 do m5 [i]: = m5 [i +1]; m5 [n]: = Carryflag; dec (Countcarry); end;end;end.
Додаток № 2
Процедури і функції модуля _Serv.
Unit _SERV;
Interface
Uses
Crt, Dos;
Const
EmptyBorder = 0;
SingleBorder = 1;
DoubleBorder = 2;
BorderChar: array [0 .. 2, 1 .. 6] of Char =
((# 32, # 32, # 32, # 32, # 32, # 32),
(# 218, # 196, # 191, # 179, # 192, # 217),
(# 201, # 205, # 187, # 186, # 200, # 188 ));
MaxChar = 80;
MaxLine = 25;
MenuTop = 3;
SubMenuTop = 2;
MenuLine: array [1 .. MenuTop ] of string [20] =
( 'Про програму ...',' Демонстрація' 'Вихід');
SubMenuLine: array [1 .. SubMenuTop] of string [ 20] =
( 'Додавання', 'Множенням');
Procedure SetWindow (x1, y1, x2, y2, Bord: byte; Header: string);
Procedure CursorOff;
Function GetMainMenuChoice: byte;
Function GetSubMenuChoice: byte;
Procedure About;
Implementation
Procedure SetWindow (x1, y1, x2, y2, Bord: byte; Header: string);var i: integer;begin if not ((x11) then dec (Count);
# 80: if (Count1) then dec (Count);
# 80: if (Count
