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

Задача 7.2.3

Задача 7.2.2

Задача 7.2.1

Приклади розв’язання задач

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

Розв’язання. Кодова комбінація коду з перевіркою на парність буде мати вигляд: A ₁ = 11101011, а коду з простим повторенням – А ₂ = 11101011110101.

Нехай у комбінації коду з перевіркою на парність виникла однократна помилка, вектор якої Е ₁ = 00000100. Тоді сума А ₁Å Е ₁ = 11101111.

У цьому разі сума за модулем 2 елементів одержаної на приймальному боці кодової комбінації дорівнює 1, тобто непарна, що вказує на наявність у ній помилки. Надмірність коду R ₁ = 1–7/8 = 0,125.

Нехай в комбінації коду з простим повторенням вектор однократної помилки буде Е ₂=00000100000000. Тоді сума А ₂Å Е ₂= 11101111110101. Порівнюючи першу і другу частини кодової комбінації (одержуючи їх суму за модулем 2), отримаємо остачу, яка не буде дорівнювати нулю (1110111Å1110101 = 0000010), що вказує на наявність помилки у прийнятій кодовій комбінації. Надмірністькоду R ₂ = 0,5. Таким чином R ₂> R _1.

Закодувати комбінацію 01000 двійкового простого коду (k =5) двійковими кодами, що виявляють помилки: з числом одиниць у комбінації, кратним трьом, та інверсним (Бауера). Виявити однократну помилку і порівняти надмірності цих кодів.

Розв’язання. Кодова комбінація коду з числом одиниць, кратним трьом, буде мати вигляд: А ₁=0100011, а інверсного коду – А ₂=0100010111.

Нехай у комбінації коду з числом одиниць, кратним трьом, виникла однократна помилка, вектор якої Е ₁=0000100. Тоді сума А ₁Å Е ₁=0100111. У цьому разі вага одержаної кодової комбінації w ^*=4, тобто відрізняється від w =3, що вказує на наявність у ній помилки. Надмірність коду R ₁ = 1– 5 / 7=2 / 7.

Нехай у комбінації інверсного коду виникла однократна помилка, вектор якої E ₂=0000100000. Тоді сума А ₂Å Е ₂=0100110111. У декодері виконується перевірка кількості одиниць у першій половині кодової комбінації, яка дорівнює 2. Це означає, що друга половина комбінації повинна прийматися у позитиві (без інверсії). Порівнюючи першу і другу (неінвертовану) частини прийнятої кодової комбінації одержимо незбіг у чотирьох розрядах, що вказує на наявність у ній помилки. Надмірність коду R ₂ = 0,5. Таким чином R ₂ > R ₁.

Закодувати комбінацію 010101 двійкового простого коду () двійковими кодами, що виявляють помилки: з перевіркою на непарність і кореляційним. Виявити однократну помилку та порівняти надмірності цих кодів.

Розв’язання. Кодова комбінація коду з перевіркою на непарність буде мати вигляд: А ₁=0101010, а кореляційного – A ₂=011001100110.

Нехай у комбінації коду з перевіркою на непарність виникла однократна помилка, вектор якої Е ₁=0000100. Тоді сума А ₁Å Е ₁=0101110. У декодері перевіряється за модулем 2 сума елементів одержаної кодової комбінації. У цьому разі вона буде дорівнювати 0, тобто парна, що вказує на наявність в комбінації помилки. Надмірність коду.

Нехай у комбінації кореляційного коду виникла однократна помилка, вектор якої Е ₂=000010000000. Тоді сума А ₂Å Е ₂= 011011100110. Як відомо, декодування кодової комбінації у декодері ведуть тактами по два елементи у кожному такті. При цьому два елементи одного такту не повинні мати однакове значення, тобто не повинно бути сполучень 00 та 11. У даному разі у третьому такті (парі елементів) буде отримано сполучення 11, що вказує на наявність помилки у прийнятій комбінації. Надмірність коду R ₂= 0,5. Таким чином R ₂ > R ₁.

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

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

· Хеммінга,

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

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

· інверсний,

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

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

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

. (8.1)

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

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

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

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

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

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

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

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

=, (8.2)

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

Твірну матрицю (8.2) можна подати у вигляді двох підматриць: інформаційної () та перевірочної.

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

=.

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

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

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

Дата добавления: 2013-12-12