Error correcting code based on finite automaton and representation of numbers in the two-base numeration system

Error correcting code based on finite automaton and representation of numbers in the two-base numeration system

A new error correcting code is introduced. It combines several approaches to constructing of error correcting codes: utilizing the arithmetic properties of numbers, represented by input bit sequences, encoding by finite automaton and by simple block code. Either encoding and decoding algorithms are...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2025
1. Verfasser: Zavadskyi, I.O.
Format: Artikel
Sprache:Ukrainian
Veröffentlicht: Інститут програмних систем НАН України 2025
Schlagworte:
UDC 519.72
Online Zugang:https://pp.isofts.kiev.ua/index.php/ojs1/article/view/713
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Problems in programming

Institution

Problems in programming
id pp_isofts_kiev_ua-article-713
record_format ojs
resource_txt_mv ppisoftskievua/15/0c34fcae3a3661e3494480d4e1064e15.pdf
spelling pp_isofts_kiev_ua-article-7132025-04-09T22:22:32Z Error correcting code based on finite automaton and representation of numbers in the two-base numeration system Завадостійкий код на основі скінченного автомата та подання чисел у двобазисній системі числення Zavadskyi, I.O. UDC 519.72 УДК 519.72 A new error correcting code is introduced. It combines several approaches to constructing of error correcting codes: utilizing the arithmetic properties of numbers, represented by input bit sequences, encoding by finite automaton and by simple block code. Either encoding and decoding algorithms are presented.Prombles in programming 2014; 2-3: 205-211 Запропоновано новий метод завадостійкого кодування, що поєднує кілька підходів до побудови завадостійких кодів: з використанням арифметичних властивостей чисел, що подаються вхідними бітовими послідовностями, кодування скінченним автоматом та простим блоковим кодом. Наведено як алгоритм побудови коду, так і алгоритм декодування.Prombles in programming 2014; 2-3: 205-211 Інститут програмних систем НАН України 2025-04-09 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/713 PROBLEMS IN PROGRAMMING; No 2-3 (2014); 205-211 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2014); 205-211 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2014); 205-211 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/713/765 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution Problems in programming
baseUrl_str https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date 2025-04-09T22:22:32Z
collection OJS
language Ukrainian
topic
UDC 519.72
spellingShingle
UDC 519.72
Zavadskyi, I.O.
Error correcting code based on finite automaton and representation of numbers in the two-base numeration system
topic_facet
UDC 519.72

УДК 519.72
format Article
author Zavadskyi, I.O.
author_facet Zavadskyi, I.O.
author_sort Zavadskyi, I.O.
title Error correcting code based on finite automaton and representation of numbers in the two-base numeration system
title_short Error correcting code based on finite automaton and representation of numbers in the two-base numeration system
title_full Error correcting code based on finite automaton and representation of numbers in the two-base numeration system
title_fullStr Error correcting code based on finite automaton and representation of numbers in the two-base numeration system
title_full_unstemmed Error correcting code based on finite automaton and representation of numbers in the two-base numeration system
title_sort error correcting code based on finite automaton and representation of numbers in the two-base numeration system
title_alt Завадостійкий код на основі скінченного автомата та подання чисел у двобазисній системі числення
description A new error correcting code is introduced. It combines several approaches to constructing of error correcting codes: utilizing the arithmetic properties of numbers, represented by input bit sequences, encoding by finite automaton and by simple block code. Either encoding and decoding algorithms are presented.Prombles in programming 2014; 2-3: 205-211
publisher Інститут програмних систем НАН України
publishDate 2025
url https://pp.isofts.kiev.ua/index.php/ojs1/article/view/713
work_keys_str_mv AT zavadskyiio errorcorrectingcodebasedonfiniteautomatonandrepresentationofnumbersinthetwobasenumerationsystem
AT zavadskyiio zavadostíjkijkodnaosnovískínčennogoavtomatatapodannâčiseludvobazisníjsistemíčislennâ
first_indexed 2025-07-17T09:48:01Z
last_indexed 2025-07-17T09:48:01Z
_version_ 1838409491204276224
fulltext Захист інформації © І.О. Завадський, 2014 ISSN 1727-4907. Проблеми програмування. 2014. № 2–3. Спеціальний випуск 205 УДК 519.72 ЗАВАДОСТІЙКИЙ КОД НА ОСНОВІ СКІНЧЕННОГО АВТОМАТА ТА ПОДАННЯ ЧИСЕЛ У ДВОБАЗИСНІЙ СИСТЕМІ ЧИСЛЕННЯ І.О. Завадський КНУ ім. Т. Шевченка, 03680, проспект Академіка Глушкова, 4д. Тел.: (044) 252 0927, ihorza@gmail.com Запропоновано новий метод завадостійкого кодування, що поєднує кілька підходів до побудови завадостійких кодів: з використанням арифметичних властивостей чисел, що подаються вхідними бітовими послідовностями, кодування скінченним автоматом та простим блоковим кодом. Наведено як алгоритм побудови коду, так і алгоритм декодування. A new error correcting code is introduced. It combines several approaches to constructing of error correcting codes: utilizing the arithmetic properties of numbers, represented by input bit sequences, encoding by finite automaton and by simple block code. Either encoding and decoding algorithms are presented. Вступ У теорії завадостійкого кодування скінченні автомати насамперед використовуються як засіб подання діаграм станів згорткових кодів [1]. Згортковий код швидкості l n і з пам’яттю обсягом m бітів визначається скінченним автоматом, що має 2m станів, і з кожного стану є 2l переходів. Перехід визначається l двійковими вхідними символами, які зчитує автомат. У результаті переходу автомат генерує n вихідних символів, що визначаються за n формулами, однаковими для всіх станів. Кожна з таких формул є сумою за модулем 2 деякого піднабору вхідних бітів. Як бачимо, діаграма станів згорткового коду є дуже специфічним різновидом автомату, що має задовольняти жорстким обмеженням. Головною перевагою такої структури є простота її апаратної реалізації, однак у разі програмної реалізації ця перевага не є надто суттєвою. У цій доповіді буде показано, що завадостійкі коди можна будувати на основі значно ширшого кола різновидів скінченних автоматів. Буде розглянуто приклади коду, що генерується автоматом, який не задовольняє зазначеним вище обмеженням. Зокрема вихідні символи обчислюються не як суми за модулем 2 наборів вхідних символів, а за значно складнішими формулами, у яких вхідна послідовність бітів розглядається як набір цілих чисел і над цими числами виконуються певні арифметичні операції. Якщо довжина таких чисел не перевищує 64 біти, то такі операції, як додавання чи множення фактично виконуватимуться не довше, ніж сумування певних бітів за модулем 2, оскільки сучасні комп’ютери є переважно 64-розрядними. Математичною основою розглянутих кодів є подання чисел у двобазисній системі числення з основним базисом 2 та додатковим базисом 3, яке було вперше досліджено А.В. Анісімовим [2]. 1. Нижній (2,3)-код Метод кодування на основі подання чисел у двобазисній двійково-трійковій системі описано в [2]. Йдеться про префіксні коди змінної довжини, у яких кодові слова розділяються спеціальними послідовностями- роздільниками. Цей метод має переваги порівняно з іншими методами префіксного кодування, зокрема довжина коду буде меншою, ніж у кодах Фібоначі. Обчислювальний експеримент показує, що в середньому довжина (2,3)-коду числа перевищує довжину його двійкового подання у 1,13 разів. Однак для деяких чисел довжина (2,3)-коду буде меншою за довжину двійкового подання, що дає змогу використовувати такий код для стискання даних. З іншого боку, надлишковість, яку має (2, 3)-код у середньому, дає можливість використовувати його з метою виправлення помилок, що виникають у каналах зв’язку та пристроях збереження даних. З метою підвищення завадостійкості у [3] введено модифікацію (2, 3)-коду – так званий нижній (2,3)- код, який має дещо більшу довжину, ніж код [2], але й вищу завадостійкість. Довжина нижнього (2,3)-коду перевищує довжину двійкового подання числа у 1,16 разів у середньому. Основна ідея методу кодування така. Нехай 3,2N – множина натуральних чисел, які є взаємно простими із 2 і 3, 3,2Nx , 1x  , 2[log ]n x . Тоді x можна подати у формі 1 1 32 xkn  або 1 2 32 xkn  , де 3,2Nk , xxx  13,21 },2{N і тільки в одній із цих форм. Застосовуючи аналогічний розклад до 1x , отримаємо 2x і далі будемо обчислювати 1ix з рівності 132  i kb i xx ii , поки на певній ітерації t не отримаємо 1tx або 2tx . Для однозначного декодування чисел достатньо зберігати величини ii k i nxi   ]3[log 12 і ik , які отримуємо на кожній ітерації. Справді, якщо відомі значення 1ix , i і ik , можна обчислити величину Захист інформації 206 ]3[log 12  i k i xm i , потім – iii mb  , а потім і 132  i kb i xx ii . Таким чином, під час декодування послідовність значень ix відновлюється у зворотному порядку: tx ,  , 0x , де 1tx або 2tx . Для вибору одного з двох початкових значень слід взяти до уваги, що якщо 1tx = 7 = 2 0 + 3 1 ∙ 2, то tx = 2, ib = 0, 1tk = 1, 2]3[log 12  xm k , 21   bmt . Легко показати, що 1tx = 7 – це єдиний випадок, коли 11 tk і 21  t , і єдиний випадок, коли 2tx . Тому, якщо 1tk = = 1 і 21  t , покладаємо tx = 2, а інакше – tx = 1. Нехай i kb x32  – нижнє (2, 3)-подання числа x , ]3[log2 i k xm  , bm . Величина Δ має важливу властивість: вона може набувати лише значень 0, 1 або 2, якщо 12 8 7 32  m i km x (1) і лише значень 0 або 1, якщо .232 8 7 11   m i km x (2) Якщо припустити, що x є рівномірно розподіленою на відрізку ]2;2[ 1nn випадковою величиною, то різні значення Δ траплятимуться з такими частотами: у випадку (1)   1430 iP ,   1451 P і   732 P , а у випадку (2)     2110  PP . Серед значень k з ймовірністю 2/3 траплятиметься 1, а ймовірність кожного наступного значення k буде втричі меншою за ймовірність попереднього. Нижній (2, 3)-код числа x – це послідовність блоків бітів вигляду 0…01…1, перший з яких кодує подання числа x, а наступні – подання ix на подальших ітераціях. Кількість одиниць у блоці дорівнює ik , а кількість нулів визначається величиною i . У випадку (1) значення i = 0 кодується трьома нулями, i = 1 – двома, а i = 2 – одним. У випадку (2) i = 0 кодується двома нулями, а i = 1 – одним нулем. Такий спосіб кодування обраний з огляду на вищезазначені ймовірності різних значень ik та i з метою скоротити середню довжину коду. Також з метою скорочення змінюється кодування числа 5: замість 0001 записуємо 001 (це не призводить до двозначності, адже за стандартного кодування кінцівка коду 001 ніколи не трапляється). Приклад. Побудуємо нижній (2, 3)-код числа x = 1387. 1)  821387 13 ·377, а отже, 80 b , 10 k , 3771 x . Тут 113137733 1 1 xk , 10]3[log 120  xm k , 2000  bm . 2)  72377 13 ·83, а отже, 71 b , 11 k , .832 x Тут ,2498333 1 2 xk 7]3[log 221  xm k , .0111  bm 3) 5283  + 13 ·17, а отже, 52 b , 12 k , .173 x Тут 511733 1 3 xk , 5]3[log 322  xm k , .0222  bm 4) 13217 23  , а отже, 33 b , 23 k , .14 x Тут 9133 2 4 xk , 3]3[log 323  xm k , .0333  bm У другому розкладі величина i k x3 задовольняє нерівностям (2), а в усіх інших – нерівностям (1). Тому коди нижніх (2, 3)-розкладів 1)–4) будуть такими: 01, 001, 0001, 00011. Їх конкатенація і є нижнім (2, 3)-кодом числа 1387: 01001000100011. 2. Завадостійкий нижній (2, 3)-код Якщо в каналі зв’язку, яким передається нижній (2, 3)-код, виникли перешкоди, що призвели до інвертування одного чи кількох бітів цього коду, наявність помилок у деяких випадках можна виявити за такими ознаками: 1) у випадку (2) значення  кодується більш ніж двома нулями; 2) у випадку (1) значення  кодується більш ніж трьома нулями; 3) величина m –  від’ємна. Чим довшим є кодове слово, тим вищою є ймовірність, що в разі наявності помилок виконається одна з цих ознак, а отже, факт наявності помилок буде виявлено. Також ймовірність виявлення помилок зростатиме зі зростанням їхньої кількості. У роботі [3] описано алгоритм, що дає змогу виправляти одну помилку в кодовому слові нижнього (2, 3)-коду з ймовірністю 100% і 2 помилки з ймовірністю 87,5%. Це досить низькі показники. Однак завадостійкість нижнього (2, 3)-коду можна суттєво підвищити завдяки його обробці показаним на рис. 1 скінченним автоматом. Назвемо результуючий код на виході цього автомату завадостійким нижнім (2, 3)- кодом. Захист інформації 207 Автомат має головку, яка зчитує символи нижнього (2, 3)-коду зліва направо. У автомата є 5 станів. Коли головка зчитує символи, стан автомату змінюється відповідно до зображеної на рис. 1 діаграми і у код на виході записуються символи, що відповідають виконаному переходу; ці символи вказано над стрілками переходів після скісних рисок. Стани позначено кругами. Перша цифра у кругу – це номер стану, а після неї в дужках записано символи, що розташовані перед головкою автомату, коли він перебуває у цьому стані. Автомат переходить у той чи інший стан залежно від символів, зчитаних головкою, а також деяких інших умов; ці символи та умови зазначено над стрілками переходів перед скісними рисками. Умови пов’язані з тим, що деякі переходи автомат виконує залежно від значення певної хеш-функції, застосовної до величини ix , отримуваної на кожній ітерації під час побудови нижнього (2, 3)-коду. Цією хеш-функцією може бути, наприклад 20mod)( ii xxG  . Оскільки ix – непарне число, то ця функція може набувати 10 значень. Якщо розподілити ці значення за двома множинами 1G і 2G так, що 1G ={1, 3, 5, 7, 11}, 2G ={9, 13, 15, 17, 19}, то ймовірності потрапляння значень )( ixG у кожну з цих множин будуть приблизно однаковими. Символ 1G або 2G над стрілкою переходу означає, що перехід здійснюється лише якщо поточне значення )( ixG належить множині 1G або 2G відповідно (та/або виконуються інші умови переходу). Таким чином, під час обробки нижнього коду автоматом мають обчислюватися й значення xi (або можуть використовуватися значення, отримані під час побудови нижнього (2, 3)-коду). Кожне наступне таке значення обчислюватиметься після обробки чергової групи символів 0…01…1, що кодує пару значень ( ii k, ) – її ми назвемо (Δ, k)-групою. З причин, які стануть зрозумілі з методу декодування, (  , k)-групи нижнього (2, 3)-коду мають оброблятися зображеним на рис. 1 автоматом справа наліво (проте всередині груп змінювати порядок бітів не потрібно). Щоб запобігти захаращенню зображення, переходи у стан 5 на рис. 1 не позначено. Це всі ті самі переходи, що й у стан 1, але здійснюються вони в разі виконання нерівностей (2), в той час як переходи у стан 1 – у разі виконання нерівностей (1). Оскільки і нерівності (1), і нерівності (2) не можуть виконуватися водночас, то як під час кодування, так і під час декодування завжди можна визначити однозначно, у який стан – 5 чи 1 – слід переходити. Стан 3 – особливий. Кожен із двох переходів у цей стан може виконуватися у разі зчитування не однієї певної групи символів, а двох різних груп, позначених на рис. 1 як A і В. Щоб розрізняти випадки A і В під час декодування, спосіб виходу зі стану (3) залежить від того, за якою групою символів було здійснено перехід у цей стан: A чи В. Наприклад, якщо автомат перейшов у стан 3 зі стану 2, зчитавши символи 11 (випадок A), а потім головка прочитала 0, автомат перейде зі стану 3 до стану 1 за стрілкою A & 0 і запише 00. Автомат починає роботу у стані 1, якщо величина t k xt 13  задовольняє нерівності (1), і у стані 5, якщо ця величина задовольняє нерівності (2). Перший символ коду, який завжди дорівнює 0, автомат пропускає і починає декодування з другого символу. На кожному переході автомат записує у вихідний код 3 двійкові символи, хоча з кожного стану є 4 переходи і для їхнього кодування вистачило б і двох бітів. Це зроблено з метою підвищення завадостійкості. Трійки двійкових символів, що позначають переходи з певного стану, утворюють множину слів з Хемінговою відстанню 2: {000, 011, 101, 110}. Таким чином, якщо у вихідному коді в трійку бітів з номерами 3k+1, 3k+2 і 3k+3 буде внесено 1 або 3 помилки, ця трійка вже не належатиме вказаній вище допустимій множині слів, а отже, такі трійки можна буде відразу виявити. Тоді питання полягатиме лише в тому, на якій саме позиції (чи позиціях) розташовані помилкові біти в кожній помилковій трійці. З’ясувати це дозволяє описаний у наступному розділі алгоритм ефективного перебору можливих варіантів розташування помилок. Коли автомат досягає кінця кодового слова нижнього (2, 3)-коду, можливі такі особливі випадки: 1) кодове слово закінчується символами 101, головку розміщено після символу 0, автомат перебуває у стані 1 і для останнього біту 1 переходу зі стану 1 немає. У цьому випадку до вихідного коду дописуємо справа біти 011, що означатиме символи 10 у вхідному коді і дасть змогу коректно відтворити вхідне число згідно з наведеним нижче алгоритмом декодування; 2) кодове слово закінчується символами 1001, головку розміщено після символів 10, автомат перебуває у стані 1 і для останніх символів 01 переходу зі стану 1 немає. У цьому випадку до вихідного коду дописуємо справа біти 000, що означатиме символи 010 у вхідному коді; 3) кодове слово закінчується символами 11, головку розміщено перед останнім символом 1, автомат перебуває у стані 2 і для останнього біта 1 переходу зі стану 2 немає. Тоді до вихідного коду дописуємо справа біти 011, що означатиме символи 10 у вхідному коді і перехід у стан 1; 4) автомат зупиняється у стані 3. Щоб визначити, який перехід було здійснено в цей стан: A чи В, до кодового слова дописується послідовність 000, якщо відбувся перехід A, і 011, якщо В. Ці послідовності відповідають переходам у стан 1 і, таким чином, завжди, коли автомат мав би завершувати роботу стані 3, він її завершуватиме у стані 1. Отже, фактично всі особливі випадки обробляються через дописування фіктивного нуля до нижнього (2,3)-коду. Насправді кодове слово нижнього (2, 3)-коду не може закінчуватися символом 0 і, згідно з наведеним нижче алгоритмом декодування, цей фіктивний 0 ігноруватиметься. За достатньо великої довжини вхідного кодового слова (починаючи від кількох сотень бітів) довжина завадостійкого нижнього (2, 3)-коду перевищує довжину вхідного двійкового повідомлення в 1,75 разів у Захист інформації 208 середньому. Якщо замість трійок кожен перехід кодувати парами бітів, то таке перевищення становитиме лише 1,165 разів у середньому, що майже не відрізняється від аналогічного показника для нижнього (2, 3)-коду за значно вищої завадостійкості. Рис. 1. Скінченний автомат для стискання модифікованого нижнього (2, 3)-коду Приклад. Побудуємо завадостійкий (2, 3)-код числа 1387. Його нижній (2, 3)-код було побудовано у прикладі з розділу 2 і він становить 01001000100011. Отримана при цьому послідовність значень ix становила 1387, 377, 83, 17, 1. 1. Переписуємо (  , k)-групи нижнього (2, 3)-коду справа наліво: 00011000100101. 2. Розглядаємо першу групу 00011. Тут k = 2,  = 0, і декодування починаємо з числа x = 1. xk3 = = .9132  Це число задовольняє нерівності (1), а отже автомат починає роботу зі стану 1. 3. Автомат пропускає перший символ коду і, починаючи з другого символу, зчитує групу 001, що означає перехід у стан 4. У вихідний код записуються символи 101. 4. Автомат зчитує п’ятий символ коду – 1 і переходить у стан 2. Оскільки x mod 20 = 9  2G , то перехід відбувається за умовою 1 & 2G і у вихідний код записуються символи 110. 5. Групу 00011 повністю оброблено, тому x  17. 6. Перебуваючи у стані 2, автомат зчитує символи 0001, переходить у стан 3 за умовою (В) і записує у вихідний код символи 110. 7. Групу 0001 повністю оброблено, тому x  83. 8. Перебуваючи у стані 3, автомат зчитує символ 0 і тому має перейти у стан 1 або 5. Поточна ( , k)- група – це 001, звідки отримуємо k = 1. Значення xk3 = 2498331  задовольняє нерівностям (2), і тому автомат переходить у стан 5. Цей перехід виконується за умовою B & 0, оскільки перехід у стан 3 відбувся за умовою (B). Тому автомат записує у вихідний код символи 011. Захист інформації 209 9. Перебуваючи у стані 5, автомат зчитує символи 01 і переходить у стан 2. Оскільки x mod 20 = 3  1G , то перехід відбувається за умовою 01 & 1G і у вихідний код записуються символи 101. 10. Групу 001 повністю оброблено, тому x  377. 11. Автомат зчитує символи 01 і переходить у стан 3. Оскільки x mod 20 = 17  2G , то перехід відбувається за умовою 01 & 2G (В) і у вихідний код записуються символи 101. 12. Нижній (2, 3)-код повністю оброблено, але автомат закінчив роботу у стані 3. Оскільки перехід у цей стан відбувся за умовою (В), до коду додаються символи 011. Отже, завадостійким нижнім (2, 3)-кодом числа 1387 буде послідовність 101 110 110 011 101 101 011. 3. Алгоритм кодування На вході маємо послідовність бітів, а на виході потрібно отримати завадостійкий (2, 3)-код. Вхідну двійкову послідовність будемо ділити на блоки довжиною L бітів. До кожного блоку дописуватиметься контрольна сума довжиною c бітів, потім блок перетворюватиметься на число з множини N2,3 і для нього будуватиметься завадостійкий (2, 3)-код. Контрольна сума використовуватиметься під час декодування як критерій відбору серед кількох варіантів декодованих слів потрібного. 1. Ділимо вхідну послідовність бітів на блоки довжиною L . 2. Додаємо до кожного блоку c -бітну контрольну суму, i -й біт якої може бути обчислено як суму за модулем 2 всіх бітів блоку, номери яких дорівнюють )(modqi . 3. Отриману ( cL  )-бітну послідовність перетворюємо на число з множини N2,3 за описаним далі алгоритмом. 4. Для отриманого числа будуємо нижній (2, 3)-код, переписуємо послідовність його блоків справа наліво і за нею будуємо завадостійкий (2, 3)-код. 5. Отримані завадостійкі коди блоків конкатенуються без додавання жодних роздільників. Тепер опишемо детально, як виконується крок 3 цього алгоритму: перетворення довільної послідовності довжиною M бітів на ціле число, що є взаємно простим із 2 і 3. 1. Якщо послідовність починається із символу 1 і являє собою взаємно просте з 2 і 3 двійкове число, зупиняємось. 2. Додаємо символ 1 до послідовності зліва. Якщо отримано число, яке взаємно просте з 2 і 3, зупиняємось. 3. Додаємо символ 1 до послідовності справа. Якщо отримано число, яке взаємно просте з 2 і 3, зупиняємось. 4. Додаємо символ 1 до послідовності справа. Зворотна процедура перетворює число з множини N2,3 на вхідну послідовність бітів. Вона може завершитися помилкою, яка означатиме, що це число не може бути отримане в результаті прямого перетворення M-бітної послідовності. 1. Якщо бітова довжина числа менша за M або більша за 3M , завершуємо процедуру з помилкою. 2. Якщо бітова довжина числа дорівнює 3M , видаляємо найменш значущий біт. Якщо отримане число взаємно просте з 2 і 3, завершуємо процедуру з помилкою. 3. Якщо бітова довжина отриманого на попередньому кроці числа дорівнює 2M , видаляємо найменш значущий біт. Якщо отримане число взаємно просте з 2 і 3, завершуємо процедуру з помилкою. 4. Якщо бітова довжина отриманого на попередньому кроці числа дорівнює 1M , видаляємо найбільш значущий біт. 4. Алгоритм декодування Декодувальний алгоритм застосовний до завадостійкого (2, 3)-коду, отриманого за наведеним у попередньому розділі алгоритмом. Якщо у кожну трійку бітів із номерами 23,13  mm і 33 m внесено не більше однієї помилки, цей алгоритм теоретично дає змогу виправити всі такі помилки. Однак якщо помилок буде забагато, або вони будуть скупчені, час роботи алгоритму може виявитися завеликим або може зрости ймовірність хибного виправлення – ситуації, коли за результат виправлення прийматиметься послідовність, що насправді містить помилки. Припустимо, у деякі біти кодового слова внесено помилки, тобто ці біти інвертовані. Множину позицій бітів, які ми вважаємо помилковими, називатимемо маскою помилок. Нехай 13  mq – це номер першого біта деякої тріади кодового слова, tt   ...),,...,( 11 – певна маска помилок, а x  N2,3 – результат декодування частини кодового слова, що починається з першого (найбільш значущого) біта та закінчується бітом q, у якій біти t ,...,1 інвертовано (інакше кажучи, x – це найбільше з чисел ix , отримуваних після повної обробки (Δ, k)-груп в частині слова, що містить біти з 1-го по q-й). Крім того, через a позначимо номер Захист інформації 210 стану автомата, що відповідає положенню головки q . Четвірку ),,,( aqx називатиметься коригувальною конфігурацією. Якщо після застосування маски  трійка бітів, що починається з біта q, не містить помилки, визначено операцію інкременту ),,,( aqx ++, результатом якої є конфігурація ),3,,( aqx  , де x – результат декодування частини кодового слова, що починається з першого біта та закінчується бітом 3q , після інвертування бітів, номери яких належать масці  , а a – стан автомата, що відповідає положенню головки 3q . Якщо маска v не відповідає справжньому положенню помилок у кодовому слові, операція ),,,( aqx ++ може завершитися помилкою з таких причин: 1) 4a або 5a , а частиною умови переходу, який визначається бітами 2,1,  qqq , є 1G , хоча 2)( GxG  або ж частиною умови переходу є 2G , хоча 1)( GxG  ; 2) 3a , а перехід у стан 3 відбувся зі стану 2 за умовою 01& 1G , хоча 2)( GxG  , або ж за умовою 01& 2G , хоча 1)( GxG  . Нагадаємо, що саме за значенням бітів з номерами 2,1,  qqq визначається, за якою саме умовою відбувся перехід у стан 3, під час якого було переведено головку в позицію q . Якщо для певної коригувальної конфігурації ),,,( aqx трійка бітів, що починається з позиції q , містить помилку, визначено операцію множення ),,,( aqx *. Її результатом є множина всіх можливих коригувальних конфігурацій ),,,( aqx  ++, де   – це маска, утворена з маски v додаванням одного з бітів 2,1,  qqq , і операція інкременту не завершується помилкою. Тобто щонайбільше таких конфігурацій буде 3, а якщо деякі з операцій ),,,( aqx  ++ завершуються помилкою, у множині ),,,( aqx * буде менше трьох конфігурацій. Операцію множення ),,,( aqx * визначимо також і для того випадку, коли трійка бітів, що починається з позиції q , не містить помилок. Вважатимемо, що в цьому разі результат множення збігається з результатом інкременту ),,,( aqx ++, якщо він виконується коректно, та є порожньою множиною конфігурацій, якщо інкремент завершується помилкою. Множина P всіх можливих коригувальних конфігурацій утворюється за наведеним далі ітеративним алгоритмом. 1. Утворюємо початкову множину коригувальних конфігурацій: а) оскільки автомат може починати роботу або в стані 1, або в стані 5, покладаємо )1,1,({},1 txP  * і )5,1,({},5 txP  *, де 2or1  tt xx . Як вибирати між цими двома початковими значеннями tx , описано в розділі 2. З урахуванням особливостей кодувального автомату видно, що 2tx тоді й тільки тоді, коли автомат починає роботу в стані 1 і першою трійкою бітів є 000. Якщо перша трійка бітів містить помилку, то залежно від того, який саме біт ми припускатимемо помилковим, значення tx можуть відрізнятися; б) переглядаємо всі конфігурації з множини 1P . Якщо першу (Δ, k)-групу для певної конфігурації c ще необроблено повністю, замінюємо конфігурацію p на множину конфігурацій p*. Якщо першу (Δ, k)-групу для конфігурації c оброблено повністю, видаляємо конфігурацію p із множини 1P і, якщо величина txtk 13  задовольняє нерівності (1), включаємо цю конфігурацію до результуючої множини конфігурацій P; в) процедуру, аналогічну до описаної в п. б), застосовуємо до множини 5P . У цьому разі перевіряємо відповідність значення txtk 13  нерівності (2); г) повторюємо кроки б) і в) доти, доки множини 1P і 5P не стануть порожніми. 2. Переглядаємо всі конфігурації Paqxp  ),,,( . Для кожної з них можливі такі варіанти: а) бітова довжина числа x менша за cL  . Тут L – довжина блоків, на які ділиться вхідна послідовність, а c – бітова довжина контрольної суми. У цьому випадку замінюємо конфігурацію p на множину конфігурацій p *; б) бітова довжина числа x дорівнює cL  . Тоді, можливо, x – це шукана вхідна послідовність. Щоб перевірити це, потрібно обчислити на перших L бітах x контрольну суму і порівняти її з останніми c бітами. Якщо вони збігаються, то вважаємо бітове подання x декодованою послідовністю і переходимо до декодування наступного кодового слова, що починається з біта q , якщо ні – то замінюємо p на p*. Крім того, ( cL  )-бітне число x не може бути коректно декодованим, якщо воно не взаємно просте з 2 і 3 або якщо автомат перебуває у стані 1, а попереднім станом не був стан 3. У цих випадках також замінюємо p на p* і можемо навіть не перевіряти контрольну суму; Захист інформації 211 в) бітова довжина числа x більша за cL  , але менша за 4 cL . Тоді якщо a = 1, а попереднім станом не був стан 3, конфігурацію p з множини P видаляємо, інакше застосовуємо до числа x  N2,3 описане в попередньому розділі зворотне перетворення на бітову послідовність і перевіряємо контрольну суму. Якщо всі ці процедури і перевірки завершилися успішно, вважаємо отриману послідовність шуканою і переходимо до декодування наступного числа, інакше конфігурацію p з множини P видаляємо; г) бітова довжина числа x перевищує 3 cL . У цьому випадку конфігурацію p з множини P видаляємо. 3. Повертаємося на крок 2. Цей алгоритм завжди завершуватиме свою роботу на кроці 2б) або 2в), коли ми припускатимемо, що певна коригувальна конфігурація відповідає справжньому розташуванню помилкових бітів. Висновки У запропонованому методі кодування поєднується три підходи до побудови завадостійких кодів, і всі вони мають принципово різну природу: нижній (2, 3)-код базується на арифметичних властивостях чисел, що подаються вхідними бітовими послідовностями, скінченний автомат дає змогу виявляти помилки завдяки наявності спеціальних «хибних» переходів між станами, у які можуть «завести» лише хибні значення бітів і, нарешті, точне місцезнаходження помилок визначається завдяки застосуванню одного з найпростіших блокових кодів, що кодує пари бітів трибітними кодовими словами із множини з Хемінговою відстанню 2: {000, 011, 101, 110}. Таке комбінування різнорідних підходів дає змогу досягти достатньо високої ефективності у виправленні помилок. Чисельний експеримент, у якому вхідна послідовність бітів ділилася на блоки довжиною 64 біти і довжина контрольної суми добиралася так, щоб середня швидкість коду становила 0,5 (тобто довжина кодового слова перевищувала довжину вхідної послідовності в середньому вдвічі), показав, що розглянутий вище алгоритм декодування завадостійкого (2, 3)-коду дає змогу з ймовірністю 99,8% виправляти 10 помилок у кодовому слові, у той час як, наприклад, широко відомий згортковий код NASA (171,133), що має ту саму швидкість, із зазначеною ймовірністю у кодовому слові зазначеної довжини дає змогу виправляти лише 4 помилки. Щоправда, завадостійкий (2, 3)-код має таке обмеження, що серед бітів із номерами 3m+1, 3m+2 і 3m+3 має бути не більше одного помилкового. Для усунення цього обмеження завадостійкий (2, 3)-код також може бути перетворено спеціальним скінченним автоматом, який зараз досліджується. 1. Johannesson R., Zigangirov K. Fundamentals of convolutional coding. – IEEE Press, 1999. – 400 p. 2. Anisimov A.V. Prefix Encoding by Means of the 2,3–Representation of Numbers // IEEE Transactions on Information Theory. – 2013. – Vol. 59. – N 4. – P. 2359–2374. 3. Анисимов А.В., Завадский И.А. Помехоустойчивое префиксное кодирование на основе нижнего (2,3)-представления чисел // Кибернетика и системный анализ. – 2014. – № 2. – С. 3–14.

Ähnliche Einträge