Метод декодирования помехоустойчивого кода переменной длины на основе конечных автоматов
Рассмотрен алгоритм декодирования для кода, основанного на обработке информационных сообщений конечными автоматами и использовании двухбазисной системы исчисления, а также оценена его эффективность. Кроме того, описан общий алгоритм кодирования. Как кодирование, так и декодирование осуществляется с...
Gespeichert in:
| Datum: | 2015 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/124817 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Метод декодирования помехоустойчивого кода переменной длины на основе конечных автоматов / И.А. Завадский // Кибернетика и системный анализ. — 2015. — Т. 51, № 3. — С. 16-24. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-124817 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1248172025-02-09T11:37:40Z Метод декодирования помехоустойчивого кода переменной длины на основе конечных автоматов Метод декодування завадостійкого коду змінної довжини на основі скінченних автоматів The decoding method for variable rate error-correcting code based on finite automata Завадский, И.А. Кибернетика Рассмотрен алгоритм декодирования для кода, основанного на обработке информационных сообщений конечными автоматами и использовании двухбазисной системы исчисления, а также оценена его эффективность. Кроме того, описан общий алгоритм кодирования. Как кодирование, так и декодирование осуществляется с помощью двухуровневой системы: на внутреннем уровне входное сообщение представлено в виде нижнего (2,3)-кода, а на внешнем помехоустойчивые свойства этого кода усиливаются путем его преобразования конечным автоматом специального вида. При декодировании ошибки улавливаются, прежде всего, на внешнем уровне, однако если этого не происходит, результат «подчищается» на внутреннем уровне. Исследована взаимосвязь внешнего уровня рассматриваемой системы со сверточными кодами и показаны преимущества предложенного метода.. Розглянуто алгоритм декодування для коду, що базується на обробленні інформаційних повідомлень скінченними автоматами та використанні двобазисної системи числення, а також оцінено його ефективність. Крім того, розглянуто загальний алгоритм кодування. Як кодування, так і декодування здійснюється за допомогою дворівневої системи: на внутрішньому рівні вхідне повідомлення подається у вигляді нижнього (2,3)-коду, а на зовнішньому завадостійкі властивості цього коду підсилюються через його перетворення скінченним автоматом спеціального вигляду. Під час декодування помилки перехоплюються насамперед на зовнішньому рівні, але якщо цього не відбувається, результат «підчищається» на внутрішньому рівні. Досліджено взаємозв’язок зовнішнього рівня розглянутої системи зі згортковими кодами і показано переваги запропонованого методу. The decoding algorithm for the special error-correcting code is discussed and its efficiency is estimated. The code is based on information processing by finite automata and using two-base numeral system. The general encoding algorithm is also considered. Either encoding or decoding is performed by a two-level system: the input message is represented as the lower (2,3)-code on the internal level and the error correcting capabilities of this code are strengthened on the external level by its conversion using a special finite automaton. First and foremost errors are corrected on the external level; otherwise, they are erased by the internal automaton. The relation between the external level of the discussed system and convolutional codes is considered and the advantages of the proposed method are shown. 2015 Article Метод декодирования помехоустойчивого кода переменной длины на основе конечных автоматов / И.А. Завадский // Кибернетика и системный анализ. — 2015. — Т. 51, № 3. — С. 16-24. — Бібліогр.: 3 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/124817 519.725 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Завадский, И.А. Метод декодирования помехоустойчивого кода переменной длины на основе конечных автоматов Кибернетика и системный анализ |
| description |
Рассмотрен алгоритм декодирования для кода, основанного на обработке информационных сообщений конечными автоматами и использовании двухбазисной системы исчисления, а также оценена его эффективность. Кроме того, описан общий алгоритм кодирования. Как кодирование, так и декодирование осуществляется с помощью двухуровневой системы: на внутреннем уровне входное сообщение представлено в виде нижнего (2,3)-кода, а на внешнем помехоустойчивые свойства этого кода усиливаются путем его преобразования конечным автоматом специального вида. При декодировании ошибки улавливаются, прежде всего, на внешнем уровне, однако если этого не происходит, результат «подчищается» на внутреннем уровне. Исследована взаимосвязь внешнего уровня рассматриваемой системы со сверточными кодами и показаны преимущества предложенного метода.. |
| format |
Article |
| author |
Завадский, И.А. |
| author_facet |
Завадский, И.А. |
| author_sort |
Завадский, И.А. |
| title |
Метод декодирования помехоустойчивого кода переменной длины на основе конечных автоматов |
| title_short |
Метод декодирования помехоустойчивого кода переменной длины на основе конечных автоматов |
| title_full |
Метод декодирования помехоустойчивого кода переменной длины на основе конечных автоматов |
| title_fullStr |
Метод декодирования помехоустойчивого кода переменной длины на основе конечных автоматов |
| title_full_unstemmed |
Метод декодирования помехоустойчивого кода переменной длины на основе конечных автоматов |
| title_sort |
метод декодирования помехоустойчивого кода переменной длины на основе конечных автоматов |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2015 |
| topic_facet |
Кибернетика |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/124817 |
| citation_txt |
Метод декодирования помехоустойчивого кода переменной длины на основе конечных автоматов / И.А. Завадский // Кибернетика и системный анализ. — 2015. — Т. 51, № 3. — С. 16-24. — Бібліогр.: 3 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT zavadskijia metoddekodirovaniâpomehoustojčivogokodaperemennojdlinynaosnovekonečnyhavtomatov AT zavadskijia metoddekoduvannâzavadostíjkogokoduzmínnoídovžininaosnovískínčennihavtomatív AT zavadskijia thedecodingmethodforvariablerateerrorcorrectingcodebasedonfiniteautomata |
| first_indexed |
2025-11-25T21:46:27Z |
| last_indexed |
2025-11-25T21:46:27Z |
| _version_ |
1849800460483952640 |
| fulltext |
ÓÄÊ 519.725
È.À. ÇÀÂÀÄÑÊÈÉ
ÌÅÒÎÄ ÄÅÊÎÄÈÐÎÂÀÍÈß ÏÎÌÅÕÎÓÑÒÎÉ×ÈÂÎÃÎ ÊÎÄÀ
ÏÅÐÅÌÅÍÍÎÉ ÄËÈÍÛ ÍÀ ÎÑÍÎÂÅ ÊÎÍÅ×ÍÛÕ ÀÂÒÎÌÀÒÎÂ
Àííîòàöèÿ. Ðàññìîòðåí àëãîðèòì äåêîäèðîâàíèÿ äëÿ êîäà, îñíîâàííîãî íà îáðàáîòêå èí-
ôîðìàöèîííûõ ñîîáùåíèé êîíå÷íûìè àâòîìàòàìè è èñïîëüçîâàíèè äâóõáàçèñíîé ñèñòå-
ìû èñ÷èñëåíèÿ, à òàêæå îöåíåíà åãî ýôôåêòèâíîñòü. Êðîìå òîãî, îïèñàí îáùèé àëãîðèòì
êîäèðîâàíèÿ. Êàê êîäèðîâàíèå, òàê è äåêîäèðîâàíèå îñóùåñòâëÿåòñÿ ñ ïîìîùüþ äâóõ-
óðîâíåâîé ñèñòåìû: íà âíóòðåííåì óðîâíå âõîäíîå ñîîáùåíèå ïðåäñòàâëåíî â âèäå íèæ-
íåãî (2,3)-êîäà, à íà âíåøíåì ïîìåõîóñòîé÷èâûå ñâîéñòâà ýòîãî êîäà óñèëèâàþòñÿ ïóòåì
åãî ïðåîáðàçîâàíèÿ êîíå÷íûì àâòîìàòîì ñïåöèàëüíîãî âèäà. Ïðè äåêîäèðîâàíèè îøèáêè
óëàâëèâàþòñÿ, ïðåæäå âñåãî, íà âíåøíåì óðîâíå, îäíàêî åñëè ýòîãî íå ïðîèñõîäèò, ðå-
çóëüòàò «ïîä÷èùàåòñÿ» íà âíóòðåííåì óðîâíå. Èññëåäîâàíà âçàèìîñâÿçü âíåøíåãî óðîâíÿ
ðàññìàòðèâàåìîé ñèñòåìû ñî ñâåðòî÷íûìè êîäàìè è ïîêàçàíû ïðåèìóùåñòâà ïðåäëîæåí-
íîãî ìåòîäà.
Êëþ÷åâûå ñëîâà: êîíå÷íûé àâòîìàò, ïîìåõîóñòîé÷èâûé êîä, (2,3)-êîä, ñâåðòî÷íûé êîä.
ÂÂÅÄÅÍÈÅ
Ïðèíöèïû ãåíåðèðîâàíèÿ ïîìåõîóñòîé÷èâûõ êîäîâ ñ ïîìîùüþ êîíå÷íûõ àâ-
òîìàòîâ, à òàêæå äâà òàêèõ àâòîìàòà, ðàáîòà êîòîðûõ îñíîâàíà íà ðàçëè÷íûõ
ìàòåìàòè÷åñêèõ ïîäõîäàõ, îïèñàíû â [1].  äàííîé ñòàòüå ðàññìîòðåíà äâóõ-
óðîâíåâàÿ ñèñòåìà ïîìåõîóñòîé÷èâîãî êîäèðîâàíèÿ, â êîòîðîé èñïîëüçóþòñÿ
îáà àâòîìàòà, è ïðèâåäåí ìåòîä ýôôåêòèâíîãî äåêîäèðîâàíèÿ ãåíåðèðóåìîãî
ýòîé ñèñòåìîé êîäà. Ìîùíûå ïîìåõîóñòîé÷èâûå ñâîéñòâà ïðåäëîæåííîé ñèñ-
òåìû îáåñïå÷èâàþòñÿ áëàãîäàðÿ ñî÷åòàíèþ íà åå âíåøíåì è âíóòðåííåì óðîâ-
íÿõ ðàçíîðîäíûõ ïîäõîäîâ, ñîñòîÿùèõ â ãåíåðèðîâàíèè ñèìâîëîâ êîäà íà
îñíîâå íåñêîëüêèõ âõîäíûõ äâîè÷íûõ ñèìâîëîâ è âûïîëíåíèè àðèôìåòè÷åñ-
êèõ îïåðàöèé íàä áîëüøèì áëîêîì ñèìâîëîâ âõîäíîãî êîäà êàê íàä öåëûì
÷èñëîì. Ýôôåêòèâíîñòü èñïðàâëåíèÿ îøèáîê äàííîé ñèñòåìîé ñóùåñòâåííî
âûøå ïîêàçàòåëåé èçâåñòíûõ ïðîñòûõ êîäîâ òîé æå ñêîðîñòè, îñîáåííî ïðè
âûñîêîì óðîâíå øóìà â êàíàëàõ ñâÿçè (îòíîøåíèå ïîëåçíîãî ñèãíàëà ê øóìó
Eb No/ ìåíüøå 2 äÁ). Òàê, ïðè çíà÷åíèè âåëè÷èíû Eb No/ , ðàâíîì 1 äÁ, ïà-
êåòíàÿ ïîìåõîóñòîé÷èâîñòü ïðåäëîæåííîãî êîäà ïðåâûøàåò àíàëîãè÷íûé ïî-
êàçàòåëü øèðîêî èñïîëüçóåìîãî â ñèñòåìàõ ìîáèëüíîé ñâÿçè è õðàíåíèÿ äàí-
íûõ êîäà NASA (171,133) áîëåå ÷åì â 12 ðàç.
ÎÁÙÈÉ ÀËÃÎÐÈÒÌ ÊÎÄÈÐÎÂÀÍÈß
Âõîäÿùóþ äâîè÷íóþ ïîñëåäîâàòåëüíîñòü áóäåì äåëèòü íà L-áèòîâûå áëîêè.
Ê êàæäîìó áëîêó äîïèñûâàåòñÿ êîíòðîëüíàÿ ñóììà äëèíîé c áèò, èñïîëüçóþùà-
ÿñÿ ïðè äåêîäèðîâàíèè êàê êðèòåðèé åãî ïðàâèëüíîñòè. Çàòåì áëîê ïðåîáðàçóåòñÿ
â ÷èñëî èç ìíîæåñòâà N2 3, (ìíîæåñòâî ÷èñåë, âçàèìíî ïðîñòûõ ñ 2 è 3), äëÿ êîòî-
ðîãî ãåíåðèðóåòñÿ ïîìåõîóñòîé÷èâûé (2,3)-êîä àâòîìàòîì èç [1, ðèñ. 1],
è ê ýòîìó êîäó ïðèìåíÿåòñÿ àâòîìàò èç [1, ðèñ. 2].
Îïèøåì ðàáîòó àëãîðèòìà.
1. Äåëèì âõîäíóþ ïîñëåäîâàòåëüíîñòü áèòîâ íà áëîêè äëèíîé L .
2. Äîïèñûâàåì ê êàæäîìó áëîêó c-áèòîâóþ êîíòðîëüíóþ ñóììó, i-é áèò êî-
òîðîé ðàâåí ñóììå ïî ìîäóëþ 2 âñåõ áèòîâ áëîêà ñ íîìåðàìè i c( )mod .
3. Ïîëó÷åííóþ ( )L c+ -áèòîâóþ ïîñëåäîâàòåëüíîñòü ïðåîáðàçóåì â ÷èñëî èç
ìíîæåñòâà N2 3, ïî îïèñàííîìó íèæå àëãîðèòìó.
16 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 3
© È.À. Çàâàäñêèé, 2015
4. Äëÿ ýòîãî ÷èñëà ñòðîèì íèæíèé (2,3)-êîä, ïåðåïèñûâàåì ïîñëåäîâàòåëü-
íîñòü åãî ( , )D k -ãðóïï ñïðàâà íàëåâî è ïî íåé ãåíåðèðóåì ïîìåõîóñòîé÷èâûé
(2,3)-êîä ñ ïîìîùüþ âíóòðåííåãî àâòîìàòà [1, ðèñ. 1].
5. Ê ïîëó÷åííîìó íà ïðåäûäóùåì øàãå êîäó ïðèìåíÿåì àâòîìàò èç [1, ðèñ. 2].
6. Ïîìåõîóñòîé÷èâûå êîäû áëîêîâ (êîäîâûå ñëîâà) êîíêàòåíèðóåì áåç äî-
áàâëåíèÿ ðàçäåëèòåëåé.
Çàìåòèì, ÷òî ïðè èñïîëüçîâàíèè ïàêåòíîãî ïðèíöèïà ïåðåäà÷è ñîîáùåíèé,
ïðèìåíÿåìîãî âî âñåõ ñèñòåìàõ ìîáèëüíîé ñâÿçè, âåëè÷èíû L è c ìîæíî ïîäî-
áðàòü òàê, ÷òîáû êîäîâîå ñëîâî óêëàäûâàëîñü â ïàêåò (äèñïåðñèÿ äëèí êîäîâûõ
ñëîâ íåâåëèêà). Òîãäà íà øàãå 6 îïèñàííîãî àëãîðèòìà ñëåäóåò íå êîíêàòåíèðî-
âàòü êîäîâûå ñëîâà, à äîïîëíÿòü èõ íóëÿìè äî ðàçìåðà ïàêåòà. Åñëè áèòû ïåðåäà-
þòñÿ ïîòîêîì, òî äëÿ ïîâûøåíèÿ ïîìåõîóñòîé÷èâîñòè â íåêîòîðûå ôèêñèðîâàí-
íûå ïîçèöèè â êîäå íóæíî âñòàâëÿòü ìàðêåðû êîíöà êîäîâîãî ñëîâà, îïðåäåëÿþ-
ùèå, íàñêîëüêî îòêëîíÿåòñÿ äëèíà êîäîâîãî ñëîâà îò ïîçèöèè ñàìîãî ìàðêåðà.
Îäíàêî èñïîëüçîâàíèå ìàðêåðîâ äåòàëüíî ðàññìàòðèâàòü íå áóäåì, òàê êàê ïðåè-
ìóùåñòâà äàííîãî ìåòîäà êîäèðîâàíèÿ ïðîÿâëÿþòñÿ èìåííî ïðè ïàêåòíîé ïåðåäà-
÷å äàííûõ.
Îïèøåì ïîäðîáíî, êàê âûïîëíÿåòñÿ øàã 3 àëãîðèòìà (ïðåîáðàçîâàíèå ïðîèç-
âîëüíîé ïîñëåäîâàòåëüíîñòè äëèíîé M áèò â öåëîå ÷èñëî, âçàèìíî ïðîñòîå ñ 2 è 3):
1) åñëè ïîñëåäîâàòåëüíîñòü íà÷èíàåòñÿ ñ ñèìâîëà 1 è ïðåäñòàâëÿåò ñîáîé
âçàèìíî ïðîñòîå ñ 2 è 3 äâîè÷íîå ÷èñëî, ïðåîáðàçîâàíèå âûïîëíÿòü íå íóæíî;
2) äîáàâëÿåì ñèìâîë 1 ê ïîñëåäîâàòåëüíîñòè ñëåâà; åñëè ïîëó÷åíî âçàèìíî
ïðîñòîå ñ 2 è 3 ÷èñëî, òî ýòî è åñòü ðåçóëüòàò; èíà÷å ïåðåõîäèì ê øàãó 3;
3) äîáàâëÿåì ñèìâîë 1 ê ïîñëåäîâàòåëüíîñòè ñïðàâà; åñëè ïîëó÷åíî âçàèìíî
ïðîñòîå ñ 2 è 3 ÷èñëî, òî ýòî è åñòü ðåçóëüòàò; èíà÷å ïåðåõîäèì ê øàãó 4;
4) äîáàâëÿåì ñèìâîë 1 ê ïîñëåäîâàòåëüíîñòè ñïðàâà.
Îáðàòíàÿ ïðîöåäóðà ïðåîáðàçóåò ÷èñëî èç ìíîæåñòâà N2 3, âî âõîäíóþ ïî-
ñëåäîâàòåëüíîñòü áèòîâ. Îíà ìîæåò çàâåðøèòüñÿ îøèáêîé, êîòîðàÿ îçíà÷àåò, ÷òî
ýòî ÷èñëî íåëüçÿ ïîëó÷èòü â ðåçóëüòàòå ïðÿìîãî ïðåîáðàçîâàíèÿ M -áèòîâîé
ïîñëåäîâàòåëüíîñòè.
Îïèøåì îáðàòíóþ ïðîöåäóðó ïîøàãîâî:
1) åñëè áèòîâàÿ äëèíà ÷èñëà ìåíüøå M èëè áîëüøå M +3 , çàâåðøàåì ïðîöå-
äóðó ñ îøèáêîé;
2) åñëè áèòîâàÿ äëèíà ÷èñëà ðàâíà M +3 , óäàëÿåì íàèìåíåå çíà÷èìûé áèò;
åñëè ïîëó÷åííîå ÷èñëî âçàèìíî ïðîñòîå ñ 2 è 3, çàâåðøàåì ïðîöåäóðó ñ îøèáêîé;
3) åñëè áèòîâàÿ äëèíà ïîëó÷åííîãî íà ïðåäûäóùåì øàãå ÷èñëà ðàâíà M +2 ,
óäàëÿåì íàèìåíåå çíà÷èìûé áèò; åñëè ïîëó÷åííîå ÷èñëî âçàèìíî ïðîñòîå ñ 2
è 3, çàâåðøàåì ïðîöåäóðó ñ îøèáêîé;
4) åñëè áèòîâàÿ äëèíà ïîëó÷åííîãî íà ïðåäûäóùåì øàãå ÷èñëà ðàâíà M +1,
óäàëÿåì íàèáîëåå çíà÷èìûé áèò.
ÀËÃÎÐÈÒÌ ÄÅÊÎÄÈÐÎÂÀÍÈß
Äåêîäèðóþùèé àëãîðèòì âêëþ÷àåò äâà ýòàïà: ïðåîáðàçîâàíèå êîäà, ïîëó÷àå-
ìîãî íà âûõîäå âíåøíåãî àâòîìàòà [1, ðèñ. 2], â ñæàòûé (2,3)-êîä; ïîëó÷åíèå èç
ïîìåõîóñòîé÷èâîãî (2,3)-êîäà ñîîáùåíèÿ, áëèçêîãî ê èñõîäíîìó, ñ ïîìîùüþ
âíóòðåííåãî àâòîìàòà [1, ðèñ. 1]. Îäíàêî ýòè ýòàïû âûïîëíÿþòñÿ íå ïîñëåäîâà-
òåëüíî: ñæàòûé (2,3)-êîä äåêîäèðóåòñÿ ïî ìåðå åãî ãåíåðèðîâàíèÿ íà ïåðâîì
ýòàïå, ñ íåêîòîðûì çàïàçäûâàíèåì.
Ñóòü ìåòîäà èñïðàâëåíèÿ îøèáîê ñîñòîèò â ñëåäóþùåì. Åñëè ñðåäè òðåõ
áèòîâ ñ íîìåðàìè 3 1m + , 3 2m + , 3 3m + åñòü îäèí îøèáî÷íûé, ïðè îáðàáîòêå
âíåøíèì àâòîìàòîì ýòîé òðèàäû âîçíèêíåò îøèáêà, ïîñêîëüêó, êàê ïîêàçàíî
â [1], àâòîìàò áóäåò îæèäàòü òðèàäó èç ìíîæåñòâà êîäîâûõ ñëîâ À, à ñ÷èòàåò òðè-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 3 17
àäó èç ìíîæåñòâà êîäîâûõ ñëîâ Â èëè íàîáîðîò. Áóäåì ïîñëåäîâàòåëüíî ïðåäïî-
ëàãàòü, ÷òî îøèáî÷íûì ÿâëÿåòñÿ áèò 3 1 3 2m m+ +, è 3 3m + , èíâåðòèðîâàòü åãî
è çàïóñêàòü âíåøíèé àâòîìàò äàëüøå, à ê ãåíåðèðóåìîìó èì (2,3)-êîäó ïðèìå-
íÿòü âíóòðåííèé àâòîìàò. Åñëè ïðåäïîëîæåíèå îá îøèáî÷íîì áèòå âåðíî, âíåø-
íèé (à çà íèì — è âíóòðåííèé) àâòîìàò áóäåò ðàáîòàòü óñïåøíî âïëîòü äî ñëåäó-
þùåãî îøèáî÷íîãî áèòà.  ïðîòèâíîì ñëó÷àå âìåñòî îäíîé îøèáêè â òðèàäå áè-
òîâ îáðàçóåòñÿ äâå, è â ñîîòâåòñòâèè ñ äîêàçàííûìè â [1, ðàçä. 3] ñâîéñòâàìè
ñáîé â ðàáîòå âíåøíåãî àâòîìàòà ïðîèçîéäåò â îäíîé èç äâóõ ïîñëåäóþùèõ òðèàä.
Âñå òðè âàðèàíòà èñïðàâëåíèÿ îøèáîê âêëþ÷èì â ñïèñîê ïîòåíöèàëüíûõ ìåñòî-
ðàñïîëîæåíèé îøèáîê, îäíàêî âàðèàíò, â êîòîðîì àâòîìàò ïðè òîì æå êîëè÷åñòâå
èñïðàâëåíèé ïðîéäåò äàëüøå, áóäåì ñ÷èòàòü ïðåäïî÷òèòåëüíûì è ïîäëåæàùèì
äàëüíåéøåé îáðàáîòêå â ïåðâóþ î÷åðåäü. Êðîìå òîãî, ðàññìîòðèì è âêëþ÷èì
â ñïèñîê ïîòåíöèàëüíûõ ìåñòîðàñïîëîæåíèé îøèáîê òðèàäû ñ äâóìÿ èíâåðòèðî-
âàííûìè áèòàìè, ðàñïîëîæåííûå íà îäíó èëè äâå òðèàäû äî ìåñòà ñáîÿ ïðè ðàáî-
òå âíåøíåãî àâòîìàòà, è òðèàäû ñ òðåìÿ èíâåðòèðîâàííûìè áèòàìè â ìåñòå ñáîÿ.
Åñëè â ñèëó âûñîêîé ïëîòíîñòè è îñîáîé êîíôèãóðàöèè îøèáîê ñáîÿ âíåøíåãî àâ-
òîìàòà íå ïðîèçîéäåò, âûñîêà âåðîÿòíîñòü âîçíèêíîâåíèÿ îøèáêè ïðè ðàáîòå
âíóòðåííåãî àâòîìàòà.
Çàìåòèì, ÷òî àëãîðèòì äåêîäèðîâàíèÿ ïðèìåíèì è ê æåñòêîé, è ê ìÿãêîé ðå-
àëèçàöèè äåêîäåðà.  ïåðâîì ñëó÷àå ïðåäïîëàãàåòñÿ, ÷òî íà âõîä äåêîäåðà ïîñòó-
ïàþò áèòû, à âî âòîðîì — àìïëèòóäà ñèãíàëà, êîäèðóþùåãî êàæäûé áèò íà âõî-
äå äåêîäåðà. Îíà ÿâëÿåòñÿ íåïðåðûâíîé âåëè÷èíîé, ïîëó÷àåìîé â ðåçóëüòàòå íà-
ëîæåíèÿ íà óðîâåíü ïåðåäàâàåìîãî ñèãíàëà (1 — äëÿ åäèíè÷íîãî çíà÷åíèÿ áèòà
è -1 — äëÿ íóëåâîãî) àääèòèâíîãî ãàóññîâîãî áåëîãî øóìà â êàíàëå ñâÿçè. Ïðè
ìÿãêîé ðåàëèçàöèè ïîëîæèòåëüíóþ àìïëèòóäó ñèãíàëà îòîæäåñòâëÿåì ñ åäèíè÷-
íûì áèòîì, îòðèöàòåëüíóþ — ñ íóëåâûì, à òîò ôàêò, ÷òî åå çíà÷åíèÿ ìîãóò íå
áûòü öåëî÷èñëåííûìè, èñïîëüçóåòñÿ òîëüêî â îïèñàííîé íèæå îïåðàöèè ñðàâíå-
íèÿ êîððåêòèðóþùèõ êîíôèãóðàöèé, ÷òî ïîâûøàåò ïîìåõîóñòîé÷èâûå ñâîéñòâà
êîäà ïðè èñïîëüçîâàíèè ìÿãêîãî äåêîäåðà.
Ïðåäïîëîæèì, ÷òî â íåêîòîðûå áèòû êîäîâîãî ñëîâà âíåñåíû îøèáêè, ò.å.
ýòè áèòû èíâåðòèðîâàíû. Ìíîæåñòâî ïîçèöèé áèòîâ, êîòîðûå ñ÷èòàåì îøèáî÷-
íûìè, íàçîâåì ìàñêîé îøèáîê. Ïóñòü q m= +3 1— íîìåð ïåðâîãî áèòà íåêîòîðîé
òðèàäû êîäîâîãî ñëîâà, u u u= ( , , )1 K t , u u1 < <K t , — ìàñêà îøèáîê, w — ðå-
çóëüòàò äåêîäèðîâàíèÿ âíåøíèì àâòîìàòîì ÷àñòè êîäîâîãî ñëîâà, íà÷èíàþùåé-
ñÿ ñ ïåðâîãî (íàèáîëåå çíà÷èìîãî) áèòà è çàêàí÷èâàþùåéñÿ áèòîì q , â ñëó÷àå
èíâåðòèðîâàíèÿ áèòîâ, ïðèíàäëåæàùèõ ìàñêå u. Êðîìå òîãî, îáîçíà÷èì s ñîñòîÿ-
íèå âíåøíåãî àâòîìàòà, ñîîòâåòñòâóþùåå ïîëîæåíèþ ãîëîâêè q , ò.å. èíôîðìà-
öèþ êàê î ãðóïïå ñîñòîÿíèé, òàê è î íîìåðå ñîñòîÿíèÿ âíóòðè ãðóïïû. Âíåøíåé
êîððåêòèðóþùåé êîíôèãóðàöèåé íàçîâåì ÷åòâåðêó ( , , , )u w q s , âíóòðåííåé —
÷åòâåðêó ( , , , )x q a tw out1 , ãäå t w q sout = ( , , , )u — íåêîòîðàÿ âíåøíÿÿ êîððåêòèðó-
þùàÿ êîíôèãóðàöèÿ, q q1 < — êðàòíîå òðåì ÷èñëî, xw — ðåçóëüòàò äåêîäèðîâà-
íèÿ âíóòðåííèì àâòîìàòîì ÷àñòè ñëîâà w, íà÷èíàþùåéñÿ ñ ïåðâîãî áèòà è çàêàí-
÷èâàþùåéñÿ áèòîì q1, a — ñîñòîÿíèå âíóòðåííåãî àâòîìàòà, ñîîòâåòñòâóþùåå
ïîëîæåíèþ ãîëîâêè q1.
Äëÿ îïèñàíèÿ àëãîðèòìà äåêîäèðîâàíèÿ íåîáõîäèìî îïðåäåëèòü íåñêîëüêî
âñïîìîãàòåëüíûõ îïåðàöèé íàä êîððåêòèðóþùèìè êîíôèãóðàöèÿìè.
Äëÿ âíåøíåé è âíóòðåííåé êîððåêòèðóþùèõ êîíôèãóðàöèé îïðåäåëèì îïå-
ðàöèè èíêðåìåíòà. Ïóñòü t w q sout = ( , , , )u — íåêîòîðàÿ âíåøíÿÿ êîíôèãóðàöèÿ,
à âíåøíèé àâòîìàò, íà÷èíàþùèé ñ íåå ðàáîòó, îñòàíàâëèâàåòñÿ ñ îøèáêîé íà
áèòå ¢ ³q q â ñîñòîÿíèè ¢s , ãåíåðèðóÿ ïðè ýòîì ïîñëåäîâàòåëüíîñòü ¢w . Òîãäà ðå-
çóëüòàòîì èíêðåìåíòà tout + + áóäåì ñ÷èòàòü êîíôèãóðàöèþ ¢ = ¢ ¢ ¢t w q sout ( , , , )u .
Åñëè àâòîìàò äîñòèãíåò êîíöà âñåãî êîäà áåç îøèáêè, ïîëàãàåì âåëè÷èíó ¢q ðàâ-
íîé íîìåðó ïîñëåäíåãî áèòà êîäà.
18 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 3
Ðåçóëüòàòîì èíêðåìåíòà âíóòðåííåé êîíôèãóðàöèè t x q a tin w out= ( , , , )1 ñ÷è-
òàåì âíóòðåííþþ êîíôèãóðàöèþ t x q a tin w out+ + = ¢ + +( , , , )' 1 , ïîëó÷àåìóþ â ðå-
çóëüòàòå îáðàáîòêè âíóòðåííèì àâòîìàòîì, íàõîäÿùèìñÿ â ñîñòîÿíèè a , ÷àñòè
ñëîâà ¢w , âêëþ÷àþùåé áèòû ñ íîìåðàìè îò q1 äî q2 . Çäåñü ( , , , )u ¢ ¢ ¢ =w q s
= + + = + +t w q sout ( , , , )u , q q d2 3= ¢ - , ãäå d — íåêîòîðàÿ êîíñòàíòà, à xw' è ¢a —
ñîîòâåòñòâóþùèå q2 äåêîäèðîâàííàÿ ÷àñòü ñëîâà è ñîñòîÿíèå âíóòðåííåãî àâòî-
ìàòà (ðèñ. 1, à). Ïðèíöèï âûáîðà âåëè÷èíû d ïîÿñíÿåòñÿ íèæå. Èíêðåìåíò âíóò-
ðåííåé êîíôèãóðàöèè ìîæåò çàâåðøèòüñÿ îøèáêîé äî òîãî, êàê àâòîìàò ïåðåé-
äåò ê îáðàáîòêå òðèàäû, íà÷èíàþùåéñÿ ñ áèòà q2 .
Êîððåêòèðóþùèå êîíôèãóðàöèè ìîãóò ñ÷èòàòüñÿ áîëåå èëè ìåíåå óñïåøíû-
ìè: ÷åì áîëüøåå êîëè÷åñòâî áèòîâ óäàëîñü îáðàáîòàòü è ÷åì ìåíüøå áèòîâ äëÿ
ýòîãî ïðèøëîñü èíâåðòèðîâàòü (÷åì êîðî÷å ìàñêà), òåì áîëåå âåðîÿòíî, ÷òî ýëå-
ìåíòû ìàñêè ñîîòâåòñòâóþò äåéñòâèòåëüíîìó ïîëîæåíèþ îøèáîê. Ïîýòîìó ââå-
äåì îïåðàöèþ ñðàâíåíèÿ âíåøíèõ êîíôèãóðàöèé p è m , ïðåäïîëîæèâ, ÷òî â ñî-
îòâåòñòâóþùèõ èì ñëîâàõ îáðàáîòàíî q p è qm áèòîâ (ðåçóëüòàò ñðàâíåíèÿ âíóò-
ðåííèõ êîíôèãóðàöèé ñîâïàäàåò ñ ðåçóëüòàòîì ñðàâíåíèÿ âõîäÿùèõ â èõ ñîñòàâ
âíåøíèõ êîíôèãóðàöèé). Ââåäåì òàêæå ìåòðèêó (t p è tm ), êîòîðàÿ ïî-ðàçíîìó
âû÷èñëÿåòñÿ â ñëó÷àå æåñòêîé è ìÿãêîé ðåàëèçàöèè äåêîäåðà. Ïðè æåñòêîé ðåà-
ëèçàöèè âåëè÷èíà t p ðàâíà êîëè÷åñòâó áèòîâ â ìàñêå êîíôèãóðàöèè p, à ïðè ìÿã-
êîé — ñóììå ìîäóëåé èëè êâàäðàòîâ àìïëèòóä, ñîîòâåòñòâóþùèõ áèòàì ìàñêè.
 îáîèõ ñëó÷àÿõ, ÷åì ìåíüøå ìåòðèêà, òåì áîëåå ïðàâäîïîäîáíà êîððåêòèðóþ-
ùàÿ êîíôèãóðàöèÿ.
Ïîëàãàåì, ÷òî åñëè p m> , òî êîíôèãóðàöèÿ p õóæå êîíôèãóðàöèè m è èç íèõ
äâóõ â ïåðâóþ î÷åðåäü äàëüíåéøåé îáðàáîòêå ïîäëåæèò êîíôèãóðàöèÿ m. Èòàê,
îïåðàöèÿ p m> âûïîëíÿåòñÿ ñëåäóþùèì îáðàçîì (ïîðÿäîê âûïîëíåíèÿ
ñðàâíåíèé ñóùåñòâåí):
1) åñëè q qp m< è t tp m> , ðåçóëüòàò èñòèííûé;
2) åñëè q qp m> è t tp m< , ðåçóëüòàò ëîæíûé;
3) äëÿ æåñòêîé ðåàëèçàöèè: åñëè q q t t t tp m m p m p< - - - -12 4 2( ) ( ) , ðåçóëü-
òàò èñòèííûé; äëÿ ìÿãêîé ðåàëèçàöèè: åñëè t tp m< è q q t tp m m p< - - -20( )
- -8 2( )t tm p , ðåçóëüòàò èñòèííûé;
4) äëÿ æåñòêîé ðåàëèçàöèè: åñëè q q t t t tm p p m p m< - - - -12 4 2( ) ( ) , ðåçóëüòàò
ëîæíûé; äëÿ ìÿãêîé ðåàëèçàöèè: åñëè t tp m> è q q t t t tm p p m p m< - - - -20 8 2( ) ( ) ,
ðåçóëüòàò ëîæíûé;
5) åñëè t tp m> , ðåçóëüòàò èñòèííûé;
6) åñëè t tp m< , ðåçóëüòàò ëîæíûé;
7) åñëè íè îäíî èç óñëîâèé 1)–6) íå âûïîëíÿåòñÿ, ðåçóëüòàò ëîæíûé.
Òàêèì îáðàçîì, ïðåæäå âñåãî ïðîâåðÿåòñÿ ÿâíîå ïðåèìóùåñòâî îäíîé êîíôè-
ãóðàöèè íàä äðóãîé: è ìåòðèêà ìåíüøå, è êîëè÷åñòâî îáðàáîòàííûõ áèòîâ áîëüøå.
Åñëè æå, íàïðèìåð, ìåòðèêà â êîíôèãóðàöèè p ìåíüøå, îäíàêî è êîëè÷åñòâî îáðà-
áîòàííûõ áèòîâ ìåíüøå, òî ðåçóëüòàò çàâèñèò îò çíà÷åíèÿ ýâðèñòè÷åñêîé ôóíêöèè,
èñïîëüçîâàííîé â ïï. 3) è 4). Åñëè â êîíôèãóðàöèÿõ ðàâíû è ìåòðèêè, è êîëè÷åñòâà
îáðàáîòàííûõ áèòîâ, òî êîíôèãóðàöèè ðàâíîöåííû è äëÿ îïðåäåëåííîñòè ñ÷èòàåì
ðåçóëüòàò îïåðàöèè èõ ñðàâíåíèÿ ëîæíûì.
Ïóñòü t — íåêîòîðàÿ êîíôèãóðàöèÿ, à P — ñïèñîê êîððåêòèðóþùèõ êîíôèãó-
ðàöèé. Ââåäåì îïåðàöèþ ïîïîëíåíèÿ ñïèñêà P t+ , â ðåçóëüòàòå êîòîðîé êîíôèãó-
ðàöèÿ t âñòàâëÿåòñÿ â ñïèñîê P ïåðåä òàêîé áëèæàéøåé ê íà÷àëó ñïèñêà êîíôèãó-
ðàöèåé p, ÷òî p t> , à åñëè òàêîé êîíôèãóðàöèè íåò — òî â êîíåö ñïèñêà. Ôîðìè-
ðîâàíèå ñïèñêà ÷åðåç îïåðàöèè ïîïîëíåíèÿ ãàðàíòèðóåò åãî óïîðÿäî÷åííîñòü ïî
âîçðàñòàíèþ, ò.å. â âåðøèíå ñïèñêà âñåãäà áóäåò íàõîäèòüñÿ «íàèëó÷øàÿ» êîíôè-
ãóðàöèÿ, ïîäëåæàùàÿ äàëüíåéøåé îáðàáîòêå â ïåðâóþ î÷åðåäü.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 3 19
Äëÿ âíóòðåííåé êîíôèãóðàöèè tin ââåäåì îïåðàöèþ ïðîâåðêè check tin( ) ,
îïðåäåëÿþùóþ, ãåíåðèðóåò ëè âíóòðåííèé àâòîìàò, íà÷èíàþùèé ðàáîòó â ýòîé
êîíôèãóðàöèè, ÷èñëî x* , êîòîðîå ïðîõîäèò âñå ïðîâåðêè íà ñîîòâåòñòâèå âõîäÿ-
ùåé áèòîâîé ïîñëåäîâàòåëüíîñòè, à èìåííî:
— ÷èñëî x* áåç îøèáêè ïðåîáðàçóåòñÿ èç ìíîæåñòâà N2 3, âî âõîäíóþ ïî-
ñëåäîâàòåëüíîñòü äëèíîé L c+ áèòîâ;
— êîíòðîëüíàÿ ñóììà, âû÷èñëåííàÿ íà ïåðâûõ L áèòàõ ïîëó÷åííîé ïîñëåäî-
âàòåëüíîñòè, ñîâïàäàåò ñ ïîñëåäíèìè c áèòàìè.
Ðåçóëüòàò îïåðàöèè check tin( ) ÿâëÿåòñÿ èñòèííûì, åñëè óäîâëåòâîðÿþùåå òà-
êèì óñëîâèÿì ÷èñëî x* ïîëó÷åíî äî îáðàáîòêè áèòà ¢q (ò.å. ïîçèöèè èç ñîîòâåò-
ñòâóþùåé âíåøíåé êîíôèãóðàöèè t w q sout + + = ¢ ¢ ¢( , , , )u ) è äî âîçíèêíîâåíèÿ
îøèáêè â ðàáîòå âíóòðåííåãî àâòîìàòà (ðèñ. 1, á).
Ââåäåì òàêæå îïåðàöèþ ïîïîëíåíèÿ ìàñêè îøèáîê, êîòîðóþ îáîçíà÷èì
ñèìâîëîì +. Åå ëåâûì îïåðàíäîì áóäåò âíóòðåííÿÿ êîíôèãóðàöèÿ, à ïðàâûì —
íîìåð áèòà, äîáàâëÿåìîãî ê ìàñêå îøèáîê: ¢ ¬ +t t kin in . Çíà÷åíèÿ ïàðàìåòðîâ
êîíôèãóðàöèè ¢tin ñîâïàäàþò ñî çíà÷åíèÿìè ïàðàìåòðîâ êîíôèãóðàöèè tin , çà òåì
èñêëþ÷åíèåì, ÷òî ìàñêà îøèáîê âõîäÿùåé â åå ñîñòàâ âíåøíåé êîíôèãóðàöèè
äîïîëíÿåòñÿ áèòîì k.
Êðîìå òîãî, ââåäåì îïåðàöèþ îòêàòà âíóòðåííåé êîíôèãóðàöèè íà êðàòíîå
òðåì êîëè÷åñòâî áèòîâ: ¢ ¬t rollback t din in( , )3 . Åñëè t x q a tin w out= ( , , , )1 , òî â êîí-
ôèãóðàöèè ¢ = ¢ - ¢ ¢t x q d a tin out( , , , )1 3 ãîëîâêà âíóòðåííåãî àâòîìàòà íàõîäèòñÿ
â ïîçèöèè q d1 3- , ñîñòîÿíèå âíóòðåííåãî àâòîìàòà ¢a è ðåçóëüòèðóþùåå ÷èñëî ¢x
ñîîòâåòñòâóþò ýòîìó ïîëîæåíèþ ãîëîâêè, à âñå ïàðàìåòðû âíåøíåé êîíôèãóðà-
öèè ¢tout — ïîçèöèè q d1 3- ãîëîâêè âíåøíåãî àâòîìàòà.
Îïèøåì àëãîðèòì äåêîäèðîâàíèÿ, èñïðàâëÿþùèé îøèáêè.
1. Ôîðìèðóåì íà÷àëüíûå êîíôèãóðàöèè: âíåøíþþ tout ¬ ( , '' '' , , , ){} { }1 1 1
è âíóòðåííþþ t tin out¬ ( '' '' , , , )1 1 . Âî âíåøíåé êîíôèãóðàöèè ìíîæåñòâî îøè-
áîê è ðåçóëüòèðóþùàÿ ñòðîêà ïóñòûå, ãîëîâêà àâòîìàòà ðàñïîëîæåíà íà ïåðâîì
(ñàìîì ñòàðøåì) áèòå, à ñàì àâòîìàò íàõîäèòñÿ â ïåðâîì ñîñòîÿíèè ïåðâîé ãðóï-
ïû; âî âíóòðåííåé — âõîäíàÿ ñòðîêà ïóñòàÿ, ãîëîâêà ðàñïîëîæåíà íà ïåðâîì
áèòå, à àâòîìàò íàõîäèòñÿ â ïåðâîì ñîñòîÿíèè. Ôîðìèðóåì òàêæå ñïèñîê äîïóñ-
òèìûõ âíóòðåííèõ êîíôèãóðàöèé Pin , ñîñòîÿùèé ñíà÷àëà èç îäíîé íà÷àëüíîé
êîíôèãóðàöèè: P tin in¬ { } .
2. Ïóñòü h — ïåðâûé ýëåìåíò ñïèñêà äîïóñòèìûõ âíóòðåííèõ êîíôèãóðà-
öèé. Âûïîëíÿåì ïðèñâàèâàíèå t hin ¬ è èñêëþ÷àåì h èç ñïèñêà.
3. Îñóùåñòâèì îïåðàöèþ èíêðåìåíòà âíóòðåííåé êîíôèãóðàöèè: ¢ ¬ + + =t tin in
= - ¢ + + = ¢ ¢ ¢( , , , ) ( , , , )x q d a t x q a tw out out' 1 23 . Ñíà÷àëà âûïîëíÿåòñÿ èíêðåìåíò ñî-
îòâåòñòâóþùåé âíåøíåé êîíôèãóðàöèè tout + +, â ðåçóëüòàòå êîòîðîãî âíåøíèé
àâòîìàò îñòàíàâëèâàåòñÿ â ïîçèöèè q1, ãåíåðèðóÿ íà âûõîäå ñëîâî ¢w , çàòåì îíî
îáðàáàòûâàåòñÿ âíóòðåííèì àâòîìàòîì. Íèæå îáúÿñíÿåòñÿ ïðèíöèï âûáîðà âå-
20 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 3
tout tout ++
tin tin ++
tout
tin check(tin)
tout ++
Êîíåö êîäîâîãî ñëîâà
3d
Ðèñ. 1. Ïîëîæåíèå ãîëîâêè àâòîìàòà äî è ïîñëå îïåðàöèé èíêðåìåíòà (à) è ïðîâåðêè (á);
çàøòðèõîâàíû òðèàäû áèòîâ, â êîòîðûõ ïðîèñõîäèò ñáîé
à á
ëè÷èíû d . Çàìåòèì, ÷òî åå îïòèìàëüíûì çíà÷åíèåì ÿâëÿåòñÿ 2, ò.å. âíóòðåííèé
àâòîìàò äîëæåí îñòàíàâëèâàòüñÿ íà äâå òðèàäû ðàíüøå òîé ïîçèöèè, ãäå îñòàíî-
âèëñÿ âíåøíèé àâòîìàò. Åñëè îïåðàöèÿ tin + + çàâåðøèëàñü îøèáêîé äî äîñòèæå-
íèÿ ãîëîâêîé âíóòðåííåãî àâòîìàòà ïîçèöèè q d1 3- è ñïèñîê Pin íå ïóñòîé, âîç-
âðàùàåìñÿ ê øàãó 2, èíà÷å ïåðåõîäèì ê øàãó 4.
4. Âûïîëíÿåì ïðîâåðêó âíóòðåííåé êîíôèãóðàöèè, ïîëó÷åííîé â ðåçóëüòàòå
èíêðåìåíòà: check tin( )¢ . Åñëè ýòà îïåðàöèÿ âîçâðàùàåò èñòèííîå çíà÷åíèå, ãåíå-
ðèðóÿ ÷èñëî x* , òî x* ñ÷èòàåì ðåçóëüòàòîì äåêîäèðîâàíèÿ êîäîâîãî ñëîâà. Îñòà-
åòñÿ ïðèìåíèòü ê ýòîìó ÷èñëó îáðàòíîå ïðåîáðàçîâàíèå èç ìíîæåñòâà N2 3, è îò-
áðîñèòü áèòû êîíòðîëüíîé ñóììû. Åñëè ðåçóëüòàò check tin( )¢ íå ÿâëÿåòñÿ èñòèí-
íûì, ïåðåõîäèì ê øàãó 5.
5. Ïðåäïîëàãàåì, ÷òî ñáîé â ðàáîòå âíåøíåãî àâòîìàòà âûçâàí åäèíè÷íîé
îøèáêîé â òðèàäå áèòîâ ñ íîìåðàìè q q q1 1 11 2, ,+ + . Äëÿ çíà÷åíèé i = 0 1 2, , âû-
ïîëíÿåì îïåðàöèþ äîáàâëåíèÿ áèòà ê ìàñêå: ¢¢ ¬ ¢ + +t t q iin in ( )1 è ïîïîëíÿåì ñïè-
ñîê äîïóñòèìûõ âíóòðåííèõ êîíôèãóðàöèé: P P tin in in¬ + ¢¢ .
6. Ïðåäïîëàãàåì, ÷òî ñáîé â ðàáîòå âíåøíåãî àâòîìàòà â òðèàäå, íà÷èíàþ-
ùåéñÿ ñ ïîçèöèè q1, âûçâàí äâîéíîé îøèáêîé â îäíîé èç äâóõ ïðåäøåñòâóþùèõ
òðèàä. Âûïîëíÿåì îòêàò êîíôèãóðàöèè ¢tin íà øåñòü áèòîâ è ê ìàñêå ïîëó÷åííîé
êîíôèãóðàöèè äîáàâëÿåì âñå âîçìîæíûå ïàðû áèòîâ i è k, ïðèíàäëåæàùèõ îä-
íîé òðèàäå áèòîâ è íàõîäÿùèõñÿ â äèàïàçîíå îò q1 6- äî q1 1- âêëþ÷èòåëüíî:
¢¢ ¬ ¢ + +t rollback t i kin in( , )6 . Ïîïîëíÿåì ñïèñîê äîïóñòèìûõ âíóòðåííèõ êîíôèãó-
ðàöèé êîíôèãóðàöèåé ¢¢tin : P P tin in in¬ + ¢¢ .
7. Ïðåäïîëàãàåì, ÷òî âñå áèòû â òðèàäå, íà÷èíàþùåéñÿ ñ ïîçèöèè q1, ñîäåð-
æàò îøèáêè: ¢¢ ¬ ¢ + + + + +t t q q qin in 1 1 11 2( ) ( ) . Äîïîëíÿåì ñïèñîê äîïóñòèìûõ
âíóòðåííèõ êîíôèãóðàöèé êîíôèãóðàöèåé ¢¢tin .
8. Âîçâðàùàåìñÿ ê øàãó 2.
Íàëè÷èå «çàçîðà» â 3 6d = áèò ìåæäó òî÷êàìè îêîí÷àíèÿ èíêðåìåíòà âíåøíåé
è âíóòðåííåé êîíôèãóðàöèé (øàã 3) îáúÿñíÿåòñÿ âîçìîæíîñòüþ îòêàòà, âûïîëíÿå-
ìîãî íà øàãå 6. Åñëè îñòàíîâêà âíåøíåãî àâòîìàòà â ïîçèöèè q1 ñâÿçàíà ñ äâîéíîé
îøèáêîé â îäíîé èç ïðåäûäóùèõ äâóõ òðèàä, íåëüçÿ «òðåáîâàòü» îò âíóòðåííåãî
àâòîìàòà áåçîøèáî÷íîé îáðàáîòêè áèòîâ ñ íîìåðàìè q q1 16 1- -, ,K .
Äàëåå îáúÿñíèì, äëÿ ÷åãî íà øàãå 4 àëãîðèòìà êîäèðîâàíèÿ ( , )D k -ãðóïïû
ïåðåïèñûâàëèñü ñïðàâà íàëåâî. Òàê êàê äåêîäèðîâàíèå íèæíåãî (2,3)-êîäà íà÷è-
íàåòñÿ ñ âåëè÷èíû xt =1 èëè xt = 2, ( , )D k -ãðóïïà, ïîëó÷àåìàÿ ïðè êîäèðîâàíèè
ïîñëåäíåé, äîëæíà îáðàáàòûâàòüñÿ ïðè äåêîäèðîâàíèè ïåðâîé. Åñëè áû ïîðÿäîê
ãðóïï íå èçìåíÿëñÿ, ïîçèöèÿ òàêîé ( , )D k -ãðóïïû áûëà áû íåèçâåñòíîé,
ïîñêîëüêó äëèíà êîäîâîãî ñëîâà ÿâëÿåòñÿ ïåðåìåííîé âåëè÷èíîé.
ÑÂßÇÜ ÂÍÅØÍÅÃÎ ÀÂÒÎÌÀÒÀ ÑÎ ÑÂÅÐÒÎ×ÍÛÌÈ ÊÎÄÀÌÈ
Ñâåðòî÷íûé êîä ñêîðîñòè l n/ ñ ïàìÿòüþ m áèò ìîæíî ïðåäñòàâèòü â âèäå êîíå÷-
íîãî àâòîìàòà ñ 2m ñîñòîÿíèÿìè è 2 l ïåðåõîäàìè èç êàæäîãî ñîñòîÿíèÿ [3]. Ïåðå-
õîä âûáèðàåòñÿ èñõîäÿ èç çíà÷åíèÿ l äâîè÷íûõ âõîäÿùèõ ñèìâîëîâ, êîòîðûå
ñ÷èòûâàåò àâòîìàò. Ïðè ïåðåõîäå àâòîìàò ãåíåðèðóåò n ñèìâîëîâ âûõîäíîãî
êîäà, îïðåäåëÿåìûõ n ôîðìóëàìè, îäèíàêîâûìè äëÿ âñåõ ñîñòîÿíèé. Êàæäàÿ
ôîðìóëà ïðåäñòàâëÿåò ñîáîé ñóììó ïî ìîäóëþ 2 íåêîòîðîãî ïîäíàáîðà âõîä-
íûõ áèòîâ. Ìàêñèìàëüíàÿ ðàçíîñòü â ýòèõ ôîðìóëàõ ìåæäó íîìåðàìè áèòîâ ñî-
ñòàâëÿåò m. Òàêèì îáðàçîì, äèàãðàììà ñîñòîÿíèé ñâåðòî÷íîãî êîäà — ñïåöè-
ôè÷åñêàÿ ðàçíîâèäíîñòü êîíå÷íîãî àâòîìàòà, êîòîðàÿ äîëæíà óäîâëåòâîðÿòü
æåñòêèì îãðàíè÷åíèÿì, îäíàêî èçîáðàæåííûé â [1, ðèñ. 2] àâòîìàò ýòèì îãðà-
íè÷åíèÿì óäîâëåòâîðÿåò. Åñëè îòîæäåñòâëÿòü åãî ñ äèàãðàììîé ñîñòîÿíèé
ñâåðòî÷íîãî êîäà, òî ýòî äîëæåí áûòü êîä ñêîðîñòè 2/3 c ïàìÿòüþ 4. Òåì íå
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 3 21
ìåíåå, êàê ïîêàçàíî äàëåå, äàííûé àâòîìàò îïðåäåëÿåò ñâåðòî÷íûé êîä ñêî-
ðîñòè 2/3 ñ ïàìÿòüþ 8. Ðàçëè÷èå ìåæäó êîäàìè ñ ïàìÿòüþ 4 è 8 ñóùåñòâåííî,
òàê êàê è ýôôåêòèâíîñòü, è ñëîæíîñòü äåêîäèðîâàíèÿ ïðè èñïîëüçîâàíèè íàè-
áîëåå ðàñïðîñòðàíåííîãî ìåòîäà Âèòåðáè ðàñòåò ñ óâåëè÷åíèåì ïàìÿòè êîäà
ýêñïîíåíöèàëüíî. Êîä, ãåíåðèðóåìûé ðàññìàòðèâàåìûì àâòîìàòîì, îáëàäàåò
ïàìÿòüþ 8, îäíàêî ìîæåò áûòü äåêîäèðîâàí àëãîðèòìîì ñ òîé æå âðåìåííîé
ñëîæíîñòüþ, ÷òî è êîä ïàìÿòè 4.
Èòàê, âûâåäåì ôîðìóëû, ïîçâîëÿþùèå èíòåðïðåòèðîâàòü âíåøíèé àâòîìàò
êàê ñâåðòî÷íûé êîä. Ïóñòü x x1 0 — ñèìâîëû, ñ÷èòàííûå àâòîìàòîì íà íåêîòîðîé
èòåðàöèè (x x x x3 2 5 4, è ò.ä. — ñèìâîëû, ñ÷èòàííûå íà ïðåäûäóùèõ èòåðàöèÿõ),
y y y2 1 0 — ñèìâîëû, çàïèñûâàåìûå ïðè ïîñëåäóþùåì ïåðåõîäå, k0 — áèò, îïðå-
äåëÿþùèé òèï êîäèðîâêè: k0 0= äëÿ êîäèðîâêè À è k0 1= äëÿ êîäèðîâêè B. Êàê
âèäíî èç òàáë. 1, ïðèâåäåííîé â [1],
y x k2 1 0= Å ,
y x k1 0 0= Å , (1)
y x x k0 0 1 0= Å Å .
Åñëè ðàññìàòðèâàòü íîìåð ãðóïïû ñîñòîÿíèé è íîìåð ñîñòîÿíèÿ âíóòðè ãðóï-
ïû êàê äâîè÷íûå äâóõáèòîâûå ÷èñëà g g1 0 è s s1 0 ñîîòâåòñòâåííî, òî, êàê âèä-
íî èç ðèñ. 2 â [1],
k s g0 0 1= Å è â îáùåì ñëó÷àå k s gi i i2 2 2 1= Å + , (2)
g g1 0 = s s3 2 è â îáùåì ñëó÷àå g g s si i i i2 1 2 2 3 2 2+ + += . (3)
Ðàññìîòðèì âòîðîé è ïîñëåäíèé ñòîëáöû òàáë. 1 â [1], îïðåäåëÿþùèå çàâèñè-
ìîñòü ìåæäó ñ÷èòàííûì ÷èñëîì (ïðåäïîëîæèì, ÷òî ýòî ÷èñëî x x3 2 ) è ñîñòîÿ-
íèåì àâòîìàòà íà ñëåäóþùåé èòåðàöèè (s s1 0 ). Ôîðìóëà, ñâÿçûâàþùàÿ äàííûå
÷èñëà, çàâèñèò îò çíà÷åíèÿ áèòà g2 , ò.å. îò ÷åòíîñòè íîìåðà ãðóïïû ñîñòîÿ-
íèé. Â òàáë. 1, ïðèâåäåííîé â äàííîé ðàáîòå, îòîáðàæåíà çàâèñèìîñòü ìåæäó
ìëàäøèì áèòîì g2 íîìåðà ãðóïïû ñîñòîÿíèé, ñ÷èòàííûì ÷èñëîì x x3 2 è ñî-
ñòîÿíèåì âíóòðè ãðóïïû íà ñëåäóþùåé èòåðàöèè s s1 0 .
Òàêèì îáðàçîì,
s x0 2 1= Å è â îáùåì ñëó÷àå s xi i2 2 2 1= Å+ , (4)
s x x g1 2 3 2= Å Å è â îáùåì ñëó÷àå s x x gi i i i2 1 2 2 2 3 2 2+ + + += Å Å . (5)
Èç ïîñëåäíåãî ðàâåíñòâà, ñ ó÷åòîì ôîðìóëû (3), ïîëó÷àåì s x x s1 2 3 4= Å Å .
Âûðàçèâ s4 ïî ôîðìóëå (4), ïîëó÷èì s x x x1 2 3 6 1= Å Å Å , à çíà÷èò,
s x x x3 4 5 8 1= Å Å Å . Â ñîîòâåòñòâèè ñ ôîðìóëîé (3) ïîñëåäíåå âûðàæåíèå
ðàâíî g1. Ó÷èòûâàÿ ñîîòíîøåíèå (4), èç (2)
ïîëó÷àåì k x x x x0 2 4 5 8= Å Å Å . Ïîäñòàâëÿÿ
ýòî âûðàæåíèå â ôîðìóëû (1), èìååì
y x x x x x2 1 2 4 5 8= Å Å Å Å ,
y x x x x x1 0 2 4 5 8= Å Å Å Å ,
y x x x x x x0 0 1 2 4 5 8= Å Å Å Å Å .
Äàííûå ôîðìóëû îïðåäåëÿþò íåñèñòåìàòè÷åñ-
êèé ñâåðòî÷íûé êîä ñêîðîñòè 2/3 ñ ïàìÿòüþ 8
è ïîðîæäàþùåé ìàòðèöåé
22 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 3
Ò à á ë è ö à 1
g2 x x3 2 s s1 0
0
00 01
01 10
10 11
11 00
1
00 11
01 00
10 01
11 10
1 1
1 1
2 2 2
2 4 2 4 2 4
+ +
+ + + + + + + +
æ
è
ç
ç
ö
ø
÷
÷
D D D
D D D D D D D D D
,
÷òî â îáùåïðèíÿòîé äëÿ ñâåðòî÷íûõ êîäîâ çàïèñè ïîëèíîìîâ â âîñüìåðè÷íîé
ôîðìå ñîîòâåòñòâóåò ìàòðèöå
11 10 11
26 27 27
æ
è
ç
ö
ø
÷ .
ÑÐÀÂÍÈÒÅËÜÍÛÉ ÀÍÀËÈÇ ÝÔÔÅÊÒÈÂÍÎÑÒÈ ÊÎÄÎÂ
Ðàññìîòðåííûé ïîìåõîóñòîé÷èâûé êîä ÿâëÿåòñÿ äâóõóðîâíåâûì, ïðè÷åì íà
ðàçíûõ óðîâíÿõ ðåàëèçîâàíû ïðèíöèïèàëüíî ðàçëè÷íûå ìàòåìàòè÷åñêèå ïîä-
õîäû, ñî÷åòàíèå êîòîðûõ äàåò âîçìîæíîñòü äîñòè÷ü âûñîêîé ïîìåõîóñòîé÷è-
âîñòè. Íà ðèñ. 2 ïðèâåäåíû ãðàôèêè, èëëþñòðèðóþùèå ýôôåêòèâíîñòü îïèñàí-
íîãî ìåòîäà ïî ñðàâíåíèþ ñ íàèáîëåå èçâåñòíûì ñâåðòî÷íûì êîäîì NASA
(171,133) ñêîðîñòè 1/2, ò.å. òàêîé æå, êàê è ñðåäíÿÿ ñêîðîñòü ïðåäëîæåííîãî
êîäà. Êàê âèäíî, äàííûé êîä îáåñïå÷èâàåò ñóùåñòâåííî áîëåå íèçêèé óðîâåíü
îøèáîê â ïàêåòàõ (Frame Error Rate — FER). Ýòà âåëè÷èíà èçìåðÿåòñÿ êàê îò-
íîøåíèå êîëè÷åñòâà ïàêåòîâ ñ îøèáêàìè ê îáùåìó êîëè÷åñòâó ïåðåäàííûõ
ïàêåòîâ. Äëÿ ìîäåëèðîâàíèÿ âûáðàí êàíàë ñâÿçè ñ àääèòèâíûì ãàóññîâûì áå-
ëûì øóìîì (AWGN), ïî êîòîðîìó ïåðåäàþòñÿ ïàêåòû ñî ñðåäíåé äëèíîé
100 áèò, ÷òî ñîîòâåòñòâóåò 50-áèòîâîìó ïàêåòó íà âõîäå êàíàëà ñâÿçè ïðè
6-áèòîâîé êîíòðîëüíîé ñóììå.
Ïðèìåíåíèå òîëüêî âíåøíåãî êîäèðîâàíèÿ ïîçâîëèëî áû èñïðàâëÿòü òàê íà-
çûâàåìûé ìåëêèé äîæäü îøèáîê, ò.å. îøèáêè, ðàñïîëîæåííûå îòíîñèòåëüíî äà-
ëåêî îäíà îò äðóãîé. Èç îïèñàíèÿ ïðèâåäåííûõ â [1] ìåòîäîâ èñïðàâëåíèÿ îøè-
áîê ñëåäóåò, ÷òî åäèíè÷íûå è òðîéíûå îøèáêè â òðèàäàõ áóäóò èñïðàâëåíû ñ âå-
ðîÿòíîñòüþ 100 %, åñëè ïîñëå òðèàäû ñ îøèáêàìè ñëåäóåò äâå òðèàäû áåç
îøèáîê. Òàêæå ñ âåðîÿòíîñòüþ 100 % áóäóò èñïðàâëåíû äâîéíûå îøèáêè
â òðèàäàõ, ïîñëå êîòîðûõ ñëåäóåò øåñòü òðèàä áåç îøèáîê.
Êîìáèíèðîâàíèå âíåøíåãî êîäèðîâàíèÿ ñ âíóòðåííèì ïîçâîëÿåò óñïåøíî èñ-
ïðàâëÿòü çíà÷èòåëüíî áîëåå ïëîòíûå êîíôèãóðàöèè îøèáîê. Îäíàêî â ýòîì ñëó÷àå
îïðåäåëèòü òåîðåòè÷åñêè âñå âàðèàíòû êîäîâûõ ïîñëåäîâàòåëüíîñòåé, èñïðàâëÿå-
ìûõ ñ âåðîÿòíîñòüþ 100 %, íå ïðåäñòàâëÿåòñÿ âîçìîæíûì è ïðè íåêîòîðûõ ñëîæ-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 3 23
Ðèñ. 2. Ãðàôèêè âåðîÿòíîñòè îøèáêè â ïàêåòå äëÿ ïîìåõîóñòîé÷èâîñòè êîäà NASA(171,133) (1)
è ïðåäëîæåííîãî êîäà (2)
1 1,5 2 2,5 3 3,5 Eb No/ , äÁ
12
1
0,1
0,01
0,001
0,0001
FER
íûõ êîíôèãóðàöèÿõ îøèáîê àëãîðèòì äåêîäèðîâàíèÿ ìîæåò íå ñðàáàòûâàòü. Î íà-
ëè÷èè òàêîé êîíôèãóðàöèè îøèáîê ñâèäåòåëüñòâóåò, ïðåæäå âñåãî, äëèòåëüíîå
âðåìÿ ðàáîòû àëãîðèòìà. Ïîýòîìó åñëè êîëè÷åñòâî èòåðàöèé ïðåâûøàåò íåêîòî-
ðîå ïðåäîïðåäåëåííîå, çàâèñÿùåå îò èíòåíñèâíîñòè ïîìåõ â êàíàëå ñâÿçè, ÷èñëî
(äëÿ íåèçâåñòíîãî óðîâíÿ ïîìåõ ïîëàãàåì åãî ðàâíûì 200), òî ðàáîòó àëãîðèòìà
íàä êîäîâûì ñëîâîì ñëåäóåò îñòàíîâèòü, íå âíîñÿ â íåãî íèêàêèõ èçìåíåíèé. Ýòî
îáúÿñíÿåòñÿ òåì, ÷òî åñëè âðåìÿ ðàáîòû àëãîðèòìà äåêîäèðîâàíèÿ ñòàíîâèòñÿ íå-
äîïóñòèìî áîëüøèì, îí ñ âûñîêîé âåðîÿòíîñòüþ â èòîãå íàéäåò ÷èñëî x* , ïðîõî-
äÿùåå âñå ïðîâåðêè, íî îòëè÷àþùååñÿ îò çàêîäèðîâàííîãî ÷èñëà, ò.å. âíåñåò äî-
ïîëíèòåëüíûå îøèáêè âî âõîäíîå ñîîáùåíèå.
ÇÀÊËÞ×ÅÍÈÅ
Ïîñêîëüêó âíåøíèé êîä, ïî ñóòè, ñâåðòî÷íûé, â öåëÿõ ïîâûøåíèÿ áûñòðîäåé-
ñòâèÿ ìîæíî áûëî áû ïðîâîäèòü âíåøíåå äåêîäèðîâàíèå ïî ìåòîäó Âèòåð-
áè [3], à âíóòðåííèé (2,3)-êîä èñïîëüçîâàòü äëÿ îòñåâà êîíôèãóðàöèé îøèáîê
òîëüêî â òîì ñëó÷àå, åñëè ðåçóëüòàò, ïîëó÷åííûé ñ ïîìîùüþ ìåòîäà Âèòåðáè,
íå ïðîõîäèò ïðîâåðîê íà ñîîòâåòñòâèå âõîäÿùåé áèòîâîé ïîñëåäîâàòåëüíîñòè.
Îäíàêî ìåòîä Âèòåðáè õîðîøî ðàáîòàåò ëèøü ïðè íèçêîé çàøóìëåííîñòè êà-
íàëà, à ïðåèìóùåñòâà ðàññìîòðåííîãî ïîäõîäà ïðîÿâëÿþòñÿ, ïðåæäå âñåãî,
ïðè âûñîêîì óðîâíå øóìà. Áîëåå òîãî, ðîëü âíóòðåííåãî êîäèðîâàíèÿ ïðè òà-
êîì ïîäõîäå íèâåëèðóåòñÿ è ïîìåõîóñòîé÷èâîñòü êîäà â öåëîì îêàçûâàåòñÿ
ñóùåñòâåííî íèæå.
Îïèñàííûé â äàííîé ñòàòüå àëãîðèòì ìîæíî ðàññìàòðèâàòü êàê áàçîâûé.
Åãî ìîæíî óëó÷øèòü ïóòåì èññëåäîâàíèÿ äîïîëíèòåëüíûõ êîíôèãóðàöèé îøè-
áîê: íàïðèìåð, âñåõ êîíôèãóðàöèé, â êîòîðûõ äâå ñîñåäíèå òðèàäû ñîäåðæàò
îøèáêè. Ýòî íåñêîëüêî óâåëè÷èâàåò âðåìÿ ðàáîòû àëãîðèòìà, îäíàêî ïîâûøàåò
åãî ïîìåõîóñòîé÷èâîñòü.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ç à â à ä ñ ê è é È . À . Ïîìåõîóñòîé÷èâûå êîäû ïåðåìåííîé äëèíû íà îñíîâå êîíå÷íûõ àâòîìà-
òîâ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2015. — 51, ¹ 2. — Ñ. 43–51.
2. À í è ñ è ì î â À .  . , Ç à â à ä ñ ê è é È . À . Ïîìåõîóñòîé÷èâîå ïðåôèêñíîå êîäèðîâàíèå íà
îñíîâå íèæíåãî (2,3)-ïðåäñòàâëåíèÿ ÷èñåë // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2014. — 50,
¹ 2. — Ñ. 3–14.
3. J o h a n n e s s o n R . , Z i g a n g i r o v K . Fundamentals of convolutional coding. — New York:
IEEE Press, 1999. — 400 p.
Ïîñòóïèëà 23.04.2014
24 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 3
|