Двійкові коди, що виправляють однократні помилки

Коди, що виправляють одну помилку, повинні мати мінімальну кодову відстань d_min 3. Збільшення кодової відстані досягається збільшенням числа розрядів коду n при незмінній кількості дозволених кодових комбінацій або зменшенням числа дозволених кодових комбінацій, що використовуються для передачі повідомлень, тобто збільшенням надмірності коду.

Найбільшого поширення серед двійкових кодів, що виправляють однократні помилки, одержали систематичні (лінійні, групові) блокові коди:

· Хеммінга,

· ітеративний (Елайеса),

· з багатократним повторенням,

· інверсний,

· та несистематичний код Бергера.

Систематичний код з d_min =3, який називають кодом Хеммінга, використовується для виправлення однієї або виявлення двох помилок.

Систематичний (груповий, лінійний) код довжиною n з кількістю інформаційних символів k позначають як -код. Для систематичного -коду з d_min =3 кількість перевірочних символів вибирають як найменше ціле , що відповідає умовам

. (8.1)

Як відомо, у систематичних кодах перевірочні елементи можна одержати шляхом додавання за модулем 2 визначених інформаційних елементів.

Систематичний код можна задавати твірною (породжувальною) матрицею, якій притаманні такі особливості:

– матриця має k рядків та n стовпців;

– кожний елемент матриці є або “0”, або “1”;

– кожний рядок матриці являє собою кодову комбінацію коду, що цією матрицею задається, і повинен мати не менше трьох одиниць;

– всі рядки матриці повинні бути лінійно незалежними;

– поелементна сума за модулем 2 будь-якої кількості рядків матриці (яка, до речі, завжди буде комбінацією коду) повинна мати не менше трьох одиниць.

Підібрані за даних умов вихідні комбінації, які називають базисними, записуються у вигляді матриці:

G_{n , k} =, (8.2)

де a_ji та b_jm – відповідно i- ий інформаційний та m- ий перевірочний елементи j- ої базисної кодової комбінацій.

Твірну матрицю (8.2) можна подати у вигляді двох підматриць: інформаційної (Е_k) та перевірочної (С_{r , k} ).

Інформаційну підматрицю зручно подати у канонічній формі як одиничну підматрицю розміром :

Е_k = .

Перевірочна підматриця С_{r , k} будується підбором r -розрядних двійкових послідовностей з числом одиниць у кожному рядку не менше за d_min –1=2. При цьому необхідно враховувати, що сума за модулем 2 будь-яких рядків цієї підматриці не повинна мати менше за d_min –2=1 одиниць, тобто однакові набори є неприпустимими.

Рядки у перевірочній підматриці можна міняти місцями. При цьому можна одержати декілька варіантів твірних матриць.

Твірна матриця дозволяє одержати всі кодові комбінації систематичного групового коду. Це досягається послідовним додаванням за модулем 2 рядків матриці у всіх можливих сполученнях (тобто першого і другого рядків матриці; першого і третього; першого і четвертого;...; другого і третього; другого і четвертого;...; першого, другого і третього; першого, другого і четвертого;..., нарешті усіх k рядків). Нульова комбінація дописується окремо.

Задача 8.2.1

Побудувати твірну матрицю і визначити всі комбінації двійкового систематичного (групового) коду, здатного виправляти поодинокі помилки для повідомлень.

Розв’язання. Кількість інформаційних розрядів коду . Кількість перевірочних розрядів визначається як найменше ціле , яке задовольняє нерівності ; таким значенням буде . Довжина коду . Таким чином, твірна матриця має 6 стовпців та 3 рядка, а перевірочна підматриця має 3 стовпця та 3 рядка.

Згідно з правилом побудови підматриці кількість одиниць у кожному рядку цієї підматриці повинно бути не менша за , а кодова відстань між окремими рядками цієї підматриці – не менша за . Тому, з триелементних комбінацій для підматриці вибираємо тільки ті, які задовольняють цим умовам, тобто .

За інформаційну підматрицю Е_k твірної матриці обирають одиничну підматрицю. Дописавши до неї перевірочну підматрицю, одержимо твірну матрицю систематичного коду, здатного виправляти однократні помилки,

G _6,3 = .

За допомогою одержаної твірної матриці G _6,3 визначимо всі 8 кодових комбінацій, які належать до цього систематичного коду:

Опираючись на твірну, матрицю можна побудувати перевірочну матрицю Н_{n , r} , яка налічує r рядків та n стовпців. Перевірочна матриця складається з двох підматриць: підматриці , яка має k стовпців та r рядків, кожний рядок якої відповідає транспонованому стовпцю перевірочної підматриці С_{r , k} твірної матриці G_{n , k} , та одиничної підматриці E_r розміром r ´ r:

. (8.3)

Перевірочна матриця (8.3) дозволяє спростити операції кодування і декодування.

Запишемо довільну кодову комбінацію коду у вигляді

V = [ a ₁ a ₂ a ₃... a_k b ₁ b ₂ b ₃ ... b_r ],

де a_i та b _m– відповідно інформаційні та перевірочні елементи.

Позиції, які зайняті одиницями у і -ому рядку підматриці D_{k , r} , визначають ті інформаційні елементи, які повинні брати участь у формуванні і -ого перевірочного елемента b_i:

b ₁ = b ₁₁ a ₁Å b ₂₁ a ₂Å... Å b_{k 1} a_k,

b ₂ = b ₁₂ a ₁Å b ₂₂ a ₂Å...Å b_{k 2} a_k, (8.4)

b_r = b _{1 r} a ₁Å b _{2 r} a ₂Å... Å b_kra_k.

Існування співвідношень (8.4), що пов’язують інформаційні та перевірочні елементи кодової комбінації, дає можливість при декодуванні виявляти та виправляти помилки в кодових комбінаціях, які можуть з’являтися через спотворення елементів у двійковому каналі під час їх передачі. Аналізуючи результати перевірки цих співвідношень у прийнятій кодовій комбінації, можна отримати певну інформацію про помилки.

Задача 8.2.2

Побудувати перевірочну матрицю двійкового систематичного коду, здатного виправляти однократні помилки з . Закодувати за допомогою одержаної перевірочної матриці комбінації первинного двійкового коду та .

Розв’язання. Для побудови перевірочної матриці систематичного коду, здатного виправляти однократні помилки, скористуємось твірною матрицею, побудованою для одержання 8 комбінацій систематичного коду у задачі 8.2.1.

Перевірочна матриця повинна мати рядки та стовпців. Вона утворюється з двох підматриць: , яка містить три стовпці і три рядки, кожний рядок якої відповідає стовпцю перевірочної підматриці твірної матриці , та одиничної підматриці . Таким чином, при

.

Перевірочні елементи, згідно матриці , можна визначити так:

b ₁ = a ₁Å a ₂;

b ₂ = a ₁Å a ₃;

b ₃ = a ₂Å a ₃.

За допомогою одержаної перевірочної матриці виконуємо кодування систематичним (груповим) кодом комбінацій первинного коду та , для чого визначаємо перевірочні елементи для заданих комбінацій. Для комбінації :

b ₁ =1Å1=0;

b ₂ =1Å1= 0;

b ₃ =1Å1= 0,

а для комбінації :

b ₁ =0Å1=1;

b ₂ =0Å1=1;

b ₃ =1Å1= 0.

Таким чином, кодові комбінації систематичного (групового) коду будуть мати вигляд: та .

Позначимо кодову комбінацію, яка пройшла через двійковий канал та підлягає декодуванню,

V ^* = [ aaa... abbb...b ],

де a та b – відповідно інформаційні та перевірочні елементи кодової комбінації на виході каналу.

Для з’ясування питання, чи відповідає кодова комбінація правилам побудови коду, отримаємо набір s_j, :

s_j = b _{1 j} a Å b _{2 j} a Å b _{3 j} a Å ... Å b_kj a Å b.

Кожний елемент s_j дає інформацію про те, задовольняють чи ні символи кодової комбінації V ^*відповідному рівнянню системи (8.4).

Набір елементів (s ₁,..., s_r) називається кодовим синдромом або пізнавачем помилок.

Якщо синдром складається з одних нулів, кодова комбінація V ^* є дозволеною, тобто задовольняє правилам побудови коду. Такий результат буде мати місце, якщо в кодовій комбінації немає помилок або конфігурація помилок є такою, що вона не може бути виявлена цим кодом. Присутність хоча б одного ненульового елемента в комбінації синдрому вказує на спотворення хоча б одного елемента у прийнятій кодовій комбінації.

Значення синдрому при однократній помилці у прийнятій кодовій комбінації збігаються із стовпцями перевірочної матриці. Порівнюючи кодовий синдром з стовпцями матриці Н_{n , r} , можна знайти місце помилки у комбінації по їх збігу. У разі помилки виправляється той розряд кодової комбінації, який відповідає порядковому номеру стовпця матриці, що збігається з синдромом.

Задача 8.2.3

Для групового -коду, що виправляє однократні помилки, побудувати перевірочну матрицю і закодувати за її допомогою комбінацію двійкового простого коду , якщо твірна матриця має вигляд

=.

Визначити синдром для виправлення однократних помилок в комбінаціях цього коду. Показати на прикладі виправлення однократної помилки.

Розв’язання. Згідно з (8.3) перевірочна матриця для -коду буде складатись з двох підматриць: , кожний рядок якої відповідає транспонованому стовпцю перевірочної підматриці твірної матриці , та одиничної підматриці . Отже, перевірочна матриця буде мати вигляд:

.

Перевірочні елементи, згідно матриці , будуть визначатись за такими виразами:

b ₁ = a ₁Å a ₂Å a ₃;

b ₂ = a ₁Å a ₂Å a ₄;

b ₃ = a ₁Å a ₃Å a ₄.

Користуючись ними, закодуємо комбінацію , тобто визначимо перевірочні елементи:

b ₁=1Å1Å0=0;

b ₂=1Å1Å1=1;

b ₃=1Å0Å1=0;

таким чином, комбінація групового коду буде мати вигляд .

У декодері для виявлення і виправлення однократної помилки у прийнятій кодовій комбінації систематичного групового коду виконують перевірку – визначають синдром помилки. Для одержаної перевірочної матриці елементи синдрому помилки визначаються таким чином:

s ₁ = a Å a Å a Å b ;

s ₂ = a Å a Å a Å b;

s ₃ = a Å a Å a Å b.

Знайдемо і виправимо однократну помилку, наприклад, у комбінації
[ a a a a b b b ] =1001010. Для цього визначимо кодовий синдром помилки: s ₁=1Å0Å0Å0=1; s ₂=1Å0Å1Å1=1; s ₃=1Å0Å1Å0=0, тобто синдром має вигляд , що відповідає другому стовпцю перевірочної матриці . Синдром показує, що помилка знаходиться у другому розряді прийнятої кодової комбінації. Для виправлення помилки інвертуємо значення даного розряду, тобто замість “0” записуємо “1”. Виправлена кодова комбінація групового коду буде мати вигляд .

Вкорочені систематичні (групові) коди утворюються з повних кодів, при цьому одержують d_min не меншу, ніж у повного систематичного коду зі збереженням такої ж кількості перевірочних елементів, тобто .

Одержання вкороченого коду ґрунтується на тому, що через те що з загального числа 2 ^k комбінацій первинного коду, які потрібно закодувати, наприклад, систематичним (n –1, k –1)-кодом, 2 ^{k –1} комбінацій починаються з ”0”, а 2 ^{k –1} – з “1”, то і після кодування 2 ^{k –1} комбінацій систематичного групового (n, k)-коду також будуть починатися з ”0”.

Будемо ці 2 ^{k –1} комбінацій розглядати як новий груповий код. Тоді, якщо вони належать вихідному (-коду, d_min нового коду буде не меншою, ніж d_min вихідного. Нульовий символ на початку вихідної кодової комбінації зберігається і після кодування її груповим (n, k)-кодом. Зрозуміло, що він не впливає на утворення перевірочних елементів групового коду і його можна відкинути. При цьому одержимо груповий -код, тобто код, що містить n –1 елементів, з яких k– 1 інформаційних та r – перевірочних.

Вкорочений груповий код легко одержати з повного (n, k)-коду, який поданий у вигляді твірної матриці G_{n , k} розміру (k ´ n) вигляду (8.2), шляхом виключення з матриці першого рядка і першого стовпця. У результаті цього одержимо твірну матрицю G_{n– 1, k– 1} нового вкороченого коду розмірності (k –1)´(n –1), що утворює 2 ^{k– 1} комбінацій вкороченого коду. Для одержання перевірочної матриці H_{n –1, r} вкороченого коду досить виключити перший стовпець з матриці H_{n , r} відповідного повного коду.

Після вкорочення на один символ групового -коду можна одержати вкорочений -код тощо.

Наведена вище інтерпретація коду Хеммінга ґрунтується на сучасних уявленнях про цей код як різновид лінійних кодів. Згідно з цією теорією можна побудувати не менше, ніж n!/ r! різноманітних лінійних кодів, що мають d_min =3, тобто кодів Хеммінга. Кожен із цих кодів задається однією із перестановок стовпців перевірочної матриці. Всі ці коди еквівалентні за корегувальною здатністю; відрізняються вони розташуванням перевірочних символів, співвідношеннями, яким відповідають символи, та, звичайно, наборами кодових комбінацій.

Код, запропонований Р.В.Хеммінгом ще до формування теорії лінійних кодів, – це один із варіантів вищеозначених кодів, для якого перевірочна матриця будується так, що i -ий стовпець її є двійковим поданням числа і. За такою умовою кодовий синдром, у разі виникнення однократної помилки, буде двійковим поданням номера спотвореного розряду кодової комбінації. Перевірочні розряди в такому коді розташовані на позиціях з номерами ; перевірочні розряди розміщуються між інформаційними. Такий код називається традиційним кодом Хеммінга.

Задача 8.2.4

Закодувати традиційним двійковим кодом Хеммінга комбінацію двійкового простого коду і показати на прикладі процес виправлення будь-якої однократної помилки. Визначити надмірність коду.

Розв’язання. Згідно із співвідношенням (8.1) при кількість перевірочних елементів , ; довжина коду . Перевірочні елементи будуть розташовані на позиціях (див. правила побудови перевірочної матриці коду Хеммінга). Побудуємо перевірочну матрицю коду Хеммінга розмірами рядків та стовпців:

b ₁ b ₂ a ₁ b ₃ a ₂ a ₃ a ₄ b ₄ a ₅

Під матрицею для полегшення процесу кодування записана у загальному вигляді кодова комбінація, де через a_i та b_j позначені інформаційні та перевірочні елементи відповідно. Користуючись побудованою перевірочною матрицею , визначимо значення перевірочних елементів для [ a ₁ a ₂ a ₃ a ₄ a ₅]=10110:

b ₁= a ₁Å a ₂Å a ₄Å a ₅=1Å0Å1Å0=0;

b ₂= a ₁Å a ₃Å a ₄=1Å1Å1=1;

b ₃= a ₂Å a ₃Å a ₄=0Å1Å1=0;

b ₄ = a ₅=0.

Кодова комбінація традиційного коду Хеммінга буде мати вигляд: .

Виконаємо декодування одержаної кодової комбінації з виправленням однократної помилки. Припустимо, що при передачі сталося спотворення і замість була прийнята кодова комбінація 011001000.

Для виявлення і виправлення помилки у декодері виконують перевірки на парність з урахуванням перевірочних елементів, тобто знаходять синдром помилки згідно перевірочній матриці :

s ₁= b ₁Å a ₁ Å a ₂Å a ₄Å a ₅=0 Å1Å0Å0Å0=1;

s ₂= b ₂Å a ₁Å a ₃Å a ₄=1Å1Å1Å0=1;

s ₃= b ₃Å a ₂ a ₃Å a ₄=0Å0Å1Å0=1;

s ₄= b ₄Å a ₅=0Å0=0.

Маємо синдром . Таким чином, визначаємо, що спотворено елемент із порядковим номером 0111₂=7₁₀, тобто елемент a _4. Виправляємо його за допомогою інверсії та одержуємо правильну кодову комбінацію – .

Надмірність коду .

Розширений код Хеммінга використовується, головним чином, для виявлення помилок. Цей код має кодову відстань d_min = 4 і забезпечує виявлення одно-, дво- і трикратних помилок завдяки введенню додаткового перевірочного елемента b ₀, який одержують за допомогою перевірки кодової комбінації коду Хеммінга на парність. При цьому перевірочний елемент, який розміщується, як правило, на початку кодової комбінації, дорівнює “0” при парній кількості одиниць у кодовій комбінації і “1” – при непарній.

Декодування розширеного коду Хеммінга виконують у зворотній послідовності: спершу виконують загальну перевірку прийнятої кодової комбінації на парність, а потім – перевірку кодової комбінації без b ₀. При цьому можуть виникнути ситуації, які показані у таблиці 8.1.

Таблиця 8.1

Кратність помилки	Перевірка на парність(b 0)	Кодовий синдром
Помилка відсутня	= 0	=
Однократна помилка	= 1
Двократна помилка	= 0
Трикратна помилка	= 1	=

Для одержання вкорочених кодів Хеммінга з d_min = 3 або 4 керуються правилами, що були викладені при побудові вкорочених систематичних кодів.

Код з багатократним повторенням (з повторенням без інверсії) є роздільним лінійним кодом. Код містить k інформаційних та mk перевірочних елементів, де m – число повторень первинної кодової комбінації. У цьому коді кожні k перевірочних елементів є просто повтореннями інформаційних елементів

b_j = b_{j + k} = b_{j + 2 k} = … = b_{j +(m –1) k} = a_j, j = 1... k.

Кодова відстань коду з багатократним повторенням d_min = m +1, тому при m ³2 код здатен не тільки виявляти, але і виправляти помилки. Процедура виявлення помилок у прийнятій кодовій комбінації полягає у порівнянні однойменних інформаційних і перевірочних розрядів. Їх незбіг говорить про наявність помилок у прийнятій комбінації. При виправленні помилок у комбінації застосовується мажоритарний принцип виправлення для кожного інформаційного елемента, тобто "голосування за більшістю", коли за істинне значення приймається те, яке частіше зустрічається у цьому інформаційному і відповідних йому перевірочних елементах. Код дозволяє виправляти всі помилки кратності від 1 до цілої частини числа m /2 та деякі помилки більш високої кратності у залежності від розміщення помилок у комбінації.

Надмірність коду .

Задача 8.2.5

Закодувати кодову комбінацію двійкового простого коду двійковим кодом з багатократним повторенням, здатним виправляти однократні помилки. Виправити будь-яку однократну помилку та визначити надмірність коду.

Розв’язання. Число повторень при виправленні однієї помилки визначається з виразу d_min = m +1. Кодова відстань при виправленні однократної помилки повинна бути не менша за d_min =3, тому m = d_min –1=3–1=2. Кодова комбінація коду з багатократним повторенням буде мати вигляд: 011010110101101.

Покажемо процес з багатократним повторенням якщо виникла однократна помилка, вектор якої . Тоді прийнята кодова комбінація буде мати вигляд: .

У декодері прийнята кодова комбінація розбивається на три частини по 5 елементів у кожній і виконується порозрядне їх порівняння:

01101,

у результаті якого виявляється помилка у п’ятому розряді. Застосувавши “голосування за більшістю”, можна виправити цю помилку. Виправлена комбінація двійкового первинного коду буде мати вигляд 01101.

Надмірність коду .

Ітеративні коди (коди Елайеса), якщо вони орієнтовані на виправлення однократних помилок, являють собою, як правило, двомірні лінійні коди з кодуванням рядків і стовпців завадостійкими кодами з перевіркою на парність. Такі ітеративні коди мають мінімальну кодову відстань d_min =4 і у режимі виправлення помилок дозволяють виправити будь-які однократні помилки і деякі помилки більшої кратності.

Рекомендується на практиці використовувати коди з числом перевірочних елементів 8, 9 та 16. Для коду з використовують блок інформаційних елементів розмірами (з k ₁=3 рядками та k ₂ = 4 стовпцями). При цьому число інформаційних елементів k = k ₁´ k ₂ = 3´4 =12, число перевірочних – r =8, n =20. Для коду з r =9 беруть k = k ₁´ k ₂ =4´4=16, n = 25; для коду з r =16: або k = k ₁´ k ₂=8´7=56, n =72 або k = k ₁´ k ₂=7´8=56, n =72.

При виправленні помилки у декодері визначають рядок і стовпець, для яких не виконуються умови парності. Спотворений інформаційний елемент, розташований на місці перетину рядка і стовпця, для яких не виконується перевірка на парність, інвертується.

Надмірність двомірних ітеративних кодів:

для ;

для ;

для .

Задача 8.2.6

Закодувати ітеративним кодом (Елайеса), що виправляє однократні помилки, комбінацію двійкового первинного коду з інформаційними елементами. Виправити будь-яку однократну помилку та визначити надмірність коду.

Розв’язання. Розбиваємо комбінацію первинного коду на три частини, записуємо у вигляді матриці з трьома рядками та робимо перевірку на парність елементів кожного рядка і кожного стовпця, дописуючи перевірочні елементи:

Таким чином отримали кодовий двовимірний масив (комбінацію) ітеративного коду з перевірками на парність, який має мінімальну кодову відстань d_min =2´2=4 (добуток мінімальних кодових відстаней кодів, якими захищаються рядки та стовпці). У лінію (канал) зв’язку передаються послідовно рядок за рядком двійкові елементи отриманого масиву: 01100101110101010001. Довжина цієї комбінації , вона містить інформаційних та перевірочних елементів.

Припустімо, що при передачі у результаті спотворень виникла помилка і на приймач прийшла комбінація 01100101010101010001. При декодуванні у декодері прийняту двійкову послідовність знову записують у вигляді матриці, структура якої співпадає зі структурою масиву після кодування, і виконують перевірку на парність кожного рядка і кожного стовпця цієї матриці:

Помилка знаходиться на перетині рядка та стовпця, які мають непарну кількість одиниць. В даному випадку це другий рядок та четвертий стовпець. Для виправлення помилки цей елемент інвертуємо, тобто замість прийнятого “0” записуємо “1”. Тоді виправлена інформаційна частина комбінації буде мати вигляд , що збігається із комбінацією первинного коду, яка підлягала кодуванню.

Надмірність коду .

Несистематичний код Бергера є найбільш поширеним з несистематичних кодів. У такому коді перевірочні елементи, які дописуються у кінці первинної кодової комбінації, – це інвертований запис двійкового числа, яке дорівнює сумі вагів тих елементів інформаційної частини кодової комбінації, на яких розташовані одиниці. При цьому число перевірочних елементів визначається як найменше ціле, яке задовольняє нерівності r ³ log ₂, де w_i – вага i -ого інформаційного елемента первинної кодової комбінації, яка кодується кодом Бергера, а ваги елементів первинної комбінації повинні приймати такі значення, починаючи з першого (старшого) розряду: 3,5,6,7,9,10,11,12,13,14,15,17,18 тощо, тобто всі числа, крім тих, які дорівнюють значенням числа 2 у будь-якій цілій додатній степені (2⁰,2¹,2²,...). Так наприклад, при k = 8 маємо log ₂= log ₂ (3+5+6+7+9+10+11+12) = log ₂63 =5,977, тобто r = 6. Таким чином перевірочна частина кодової комбінації буде мати 6 розрядів.

Для виправлення помилки в декодері підраховується сума S ^* вагів тих інформаційних розрядів прийнятої кодової комбінації, на яких розташовані одиниці. Далі інвертуються перевірочні розряди прийнятої кодової комбінації; отримане двійкове число переводиться у десяткове і віднімається від обчисленої суми S ^*. Якщо в інформаційній частині кодової комбінації є однократна помилка, то модуль різниці буде збігатись із вагою спотвореного розряду; для виправлення помилки відповідний інформаційний розряд потрібно інвертувати.

Надмірність коду .

Задача 8.2.7

Закодувати несистематичним кодом Бергера, що виправляє однократні помилки, комбінацію двійкового первинного коду з . Виправити будь-яку однократну помилку та визначити надмірність коду.

Розв’язання. Для побудови коду Бергера визначимо кількість перевірочних елементів з виразу

r log ₂= log ₂(3+5+6+7+9) = log ₂30=4,907, тобто r =5.

Далі визначимо сумарну вагу комбінації первинного коду, для чого треба додати послідовно вагу першого, третього, четвертого і п’ятого розрядів, одержане десяткове число записати у двійковій формі п’ятьма двійковими розрядами, інвертувати його і дописати до комбінації первинного коду: , ; тоді комбінація коду Бергера буде мати вигляд 1011100110. Таким чином комбінація складається з двох частин: інформаційної (перші 5 елементів) і перевірочної (6...10 елементи).

Зробимо припущення, що при передачі по лінії зв’язку в результаті дії завад у кодовій комбінації виникає помилка і на приймач надходить комбінація 1001100110. Для виявлення помилки у декодері спочатку виконуються такі ж операції, що і у кодері, тобто визначається сума вагів тих інформаційних елементів, на місцях яких розташовані “1”: ; це число записується у двійковій формі п’ятьма розрядами та інвертується . Перевірочна частина прийнятої комбінації і обчислена у декодері не збігаються, що вказує на наявність помилки у прийнятій кодовій комбінації. Далі для виправлення помилки інвертується двійковий запис перевірочної частини прийнятої кодової комбінації, одержане двійкове число переводиться у десяткову форму (воно дорівнює 25) і від нього віднімається обчислене число . Маємо ; це свідчить про те, що у прийнятій кодовій комбінації був спотворений третій елемент, оскільки саме йому відповідає вага . Виправлення виконується інвертуванням спотвореного елемента у прийнятій комбінації. Таким чином, правильний запис первинної комбінації має вигляд: .

Надмірність коду .

Висновки

Дата добавления: 2014-01-11; Просмотров: 6172; Нарушение авторских прав?; Мы поможем в написании вашей работы!