Помехоустойчивые коды переменной длины на основе конечных автоматов
Предложен новый метод помехоустойчивого кодирования, основанный на обработке информационных сообщений конечными автоматами и использовании двухбазисной системы исчисления. Мощные помехоустойчивые свойства обеспечиваются благодаря двухуровневой структуре кодера. На первом, внутреннем, уровне входное...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2015 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/124775 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Помехоустойчивые коды переменной длины на основе конечных автоматов / И.А. Завадский // Кибернетика и системный анализ. — 2015. — Т. 51, № 2. — С. 43-51. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-124775 |
|---|---|
| record_format |
dspace |
| spelling |
Завадский, И.А. 2017-10-05T06:20:36Z 2017-10-05T06:20:36Z 2015 Помехоустойчивые коды переменной длины на основе конечных автоматов / И.А. Завадский // Кибернетика и системный анализ. — 2015. — Т. 51, № 2. — С. 43-51. — Бібліогр.: 3 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/124775 519.725 Предложен новый метод помехоустойчивого кодирования, основанный на обработке информационных сообщений конечными автоматами и использовании двухбазисной системы исчисления. Мощные помехоустойчивые свойства обеспечиваются благодаря двухуровневой структуре кодера. На первом, внутреннем, уровне входное сообщение рассматривается как двоичное число, представляемое в двухбазисной системе исчисления в виде нижнего (2,3)-кода, характеризующегося определенной избыточностью и помехоустойчивостью. Затем помехоустойчивые свойства кода усиливаются с помощью внешнего кодирования, выполняемого конечным автоматом. Код имеет переменную длину: для различных входных сообщений одинаковой длины битовая длина генерируемых кодовых слов может различаться. Однако средняя скорость кодера, т.е. отношение битовой длины сообщения на входе к длине кодового слова, составляет 1/2. Запропоновано новий метод завадостійкого кодування, що базується на обробленні інформаційних повідомлень скінченними автоматами та використанні двобазисної системи числення. Потужні завадостійкі властивості забезпечуються завдяки дворівневій структурі кодера. На першому, внутрішньому, рівні вхідне повідомлення розглядається як двійкове число та подається в двобазисній системі числення у вигляді нижнього (2,3)-коду, який характеризується певною надлишковістю і завадостійкістю. Потім завадостійкі властивості коду посилюються за допомогою зовнішнього кодування, що виконується скінченним автоматом. Код має змінну довжину: для різних вхідних повідомлень однакової довжини бітова довжина генерованих кодових слів може різнитися. Однак середня швидкість кодера, тобто відношення бітової довжини вхідного повідомлення до довжини кодового слова, становить 1/2. A new method of error-correcting coding is proposed. It is based on information processing by finite automata and use of two-base numeral system. The two-level structure of the encoder provides powerful error-correcting capabilities. On the first, internal level, the input message is considered as a binary number represented as a low (2,3)-code that has some redundancy and error-correcting properties. The noise-resistant properties are strengthened on the external level where code is processed by special finite automaton. The code has variable length, i.e., codeword length depends not only on the length of input message but on the message content too. However, the average code rate is 1/2. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Помехоустойчивые коды переменной длины на основе конечных автоматов Завадостійкі коди змінної довжини на основі скінченних автоматів Variable length error-correcting codes based on finite automata Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Помехоустойчивые коды переменной длины на основе конечных автоматов |
| spellingShingle |
Помехоустойчивые коды переменной длины на основе конечных автоматов Завадский, И.А. Кибернетика |
| title_short |
Помехоустойчивые коды переменной длины на основе конечных автоматов |
| title_full |
Помехоустойчивые коды переменной длины на основе конечных автоматов |
| title_fullStr |
Помехоустойчивые коды переменной длины на основе конечных автоматов |
| title_full_unstemmed |
Помехоустойчивые коды переменной длины на основе конечных автоматов |
| title_sort |
помехоустойчивые коды переменной длины на основе конечных автоматов |
| author |
Завадский, И.А. |
| author_facet |
Завадский, И.А. |
| topic |
Кибернетика |
| topic_facet |
Кибернетика |
| publishDate |
2015 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Завадостійкі коди змінної довжини на основі скінченних автоматів Variable length error-correcting codes based on finite automata |
| description |
Предложен новый метод помехоустойчивого кодирования, основанный на обработке информационных сообщений конечными автоматами и использовании двухбазисной системы исчисления. Мощные помехоустойчивые свойства обеспечиваются благодаря двухуровневой структуре кодера. На первом, внутреннем, уровне входное сообщение рассматривается как двоичное число, представляемое в двухбазисной системе исчисления в виде нижнего (2,3)-кода, характеризующегося определенной избыточностью и помехоустойчивостью. Затем помехоустойчивые свойства кода усиливаются с помощью внешнего кодирования, выполняемого конечным автоматом. Код имеет переменную длину: для различных входных сообщений одинаковой длины битовая длина генерируемых кодовых слов может различаться. Однако средняя скорость кодера, т.е. отношение битовой длины сообщения на входе к длине кодового слова, составляет 1/2.
Запропоновано новий метод завадостійкого кодування, що базується на обробленні інформаційних повідомлень скінченними автоматами та використанні двобазисної системи числення. Потужні завадостійкі властивості забезпечуються завдяки дворівневій структурі кодера. На першому, внутрішньому, рівні вхідне повідомлення розглядається як двійкове число та подається в двобазисній системі числення у вигляді нижнього (2,3)-коду, який характеризується певною надлишковістю і завадостійкістю. Потім завадостійкі властивості коду посилюються за допомогою зовнішнього кодування, що виконується скінченним автоматом. Код має змінну довжину: для різних вхідних повідомлень однакової довжини бітова довжина генерованих кодових слів може різнитися. Однак середня швидкість кодера, тобто відношення бітової довжини вхідного повідомлення до довжини кодового слова, становить 1/2.
A new method of error-correcting coding is proposed. It is based on information processing by finite automata and use of two-base numeral system. The two-level structure of the encoder provides powerful error-correcting capabilities. On the first, internal level, the input message is considered as a binary number represented as a low (2,3)-code that has some redundancy and error-correcting properties. The noise-resistant properties are strengthened on the external level where code is processed by special finite automaton. The code has variable length, i.e., codeword length depends not only on the length of input message but on the message content too. However, the average code rate is 1/2.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/124775 |
| citation_txt |
Помехоустойчивые коды переменной длины на основе конечных автоматов / И.А. Завадский // Кибернетика и системный анализ. — 2015. — Т. 51, № 2. — С. 43-51. — Бібліогр.: 3 назв. — рос. |
| work_keys_str_mv |
AT zavadskiiia pomehoustoičivyekodyperemennoidlinynaosnovekonečnyhavtomatov AT zavadskiiia zavadostíikíkodizmínnoídovžininaosnovískínčennihavtomatív AT zavadskiiia variablelengtherrorcorrectingcodesbasedonfiniteautomata |
| first_indexed |
2025-11-25T22:43:40Z |
| last_indexed |
2025-11-25T22:43:40Z |
| _version_ |
1850570114489909248 |
| fulltext |
ÓÄÊ 519.725
È.À. ÇÀÂÀÄÑÊÈÉ
ÏÎÌÅÕÎÓÑÒÎÉ×ÈÂÛÅ ÊÎÄÛ ÏÅÐÅÌÅÍÍÎÉ ÄËÈÍÛ
ÍÀ ÎÑÍÎÂÅ ÊÎÍÅ×ÍÛÕ ÀÂÒÎÌÀÒÎÂ
Àííîòàöèÿ. Ïðåäëîæåí íîâûé ìåòîä ïîìåõîóñòîé÷èâîãî êîäèðîâàíèÿ, îñíîâàííûé íà
îáðàáîòêå èíôîðìàöèîííûõ ñîîáùåíèé êîíå÷íûìè àâòîìàòàìè è èñïîëüçîâàíèè äâóõáà-
çèñíîé ñèñòåìû èñ÷èñëåíèÿ. Ìîùíûå ïîìåõîóñòîé÷èâûå ñâîéñòâà îáåñïå÷èâàþòñÿ áëàãî-
äàðÿ äâóõóðîâíåâîé ñòðóêòóðå êîäåðà. Íà ïåðâîì, âíóòðåííåì, óðîâíå âõîäíîå ñîîáùå-
íèå ðàññìàòðèâàåòñÿ êàê äâîè÷íîå ÷èñëî, ïðåäñòàâëÿåìîå â äâóõáàçèñíîé ñèñòåìå èñ÷èñ-
ëåíèÿ â âèäå íèæíåãî (2,3)-êîäà, õàðàêòåðèçóþùåãîñÿ îïðåäåëåííîé èçáûòî÷íîñòüþ
è ïîìåõîóñòîé÷èâîñòüþ. Çàòåì ïîìåõîóñòîé÷èâûå ñâîéñòâà êîäà óñèëèâàþòñÿ ñ ïîìîùüþ
âíåøíåãî êîäèðîâàíèÿ, âûïîëíÿåìîãî êîíå÷íûì àâòîìàòîì. Êîä èìååò ïåðåìåííóþ äëè-
íó: äëÿ ðàçëè÷íûõ âõîäíûõ ñîîáùåíèé îäèíàêîâîé äëèíû áèòîâàÿ äëèíà ãåíåðèðóåìûõ
êîäîâûõ ñëîâ ìîæåò ðàçëè÷àòüñÿ. Îäíàêî ñðåäíÿÿ ñêîðîñòü êîäåðà, ò.å. îòíîøåíèå áèòî-
âîé äëèíû ñîîáùåíèÿ íà âõîäå ê äëèíå êîäîâîãî ñëîâà, ñîñòàâëÿåò 1/2.
Êëþ÷åâûå ñëîâà: êîíå÷íûé àâòîìàò, ïîìåõîóñòîé÷èâûé êîä, (2,3)-êîä, ñâåðòî÷íûé êîä.
ÂÂÅÄÅÍÈÅ
 òåîðèè ïîìåõîóñòîé÷èâîãî êîäèðîâàíèÿ êîíå÷íûå àâòîìàòû îáû÷íî èñïîëü-
çóþòñÿ äëÿ ïðåäñòàâëåíèÿ äèàãðàìì ñîñòîÿíèé ñâåðòî÷íûõ êîäîâ. Ýòî àâòîìà-
òû ñïåöèàëüíîãî âèäà, óäîâëåòâîðÿþùèå æåñòêèì îãðàíè÷åíèÿì íà êîëè÷åñ-
òâî ñîñòîÿíèé, ïåðåõîäîâ èç êàæäîãî ñîñòîÿíèÿ è äð. Îäíàêî íà ñàìîì äåëå
ïîìåõîóñòîé÷èâûå êîäû ìîæíî ñòðîèòü íà îñíîâå ãîðàçäî áîëåå øèðîêîãî
êëàññà êîíå÷íûõ àâòîìàòîâ, äâà èç êîòîðûõ ïðèâåäåíû â äàííîé ñòàòüå.
Îáùàÿ èäåÿ êîäèðîâàíèÿ ñ ïîìîùüþ êîíå÷íîãî àâòîìàòà ñîñòîèò â òîì, ÷òî
àâòîìàò ìåíÿåò ñîñòîÿíèÿ â çàâèñèìîñòè îò ñ÷èòàííûõ ñèìâîëîâ êîäèðóåìîãî
ñëîâà è çàïèñûâàåò ïðè ýòîì íåêîòîðûå ñèìâîëû â ðåçóëüòèðóþùèé êîä.
Èçáûòî÷íîñòü êîäà íà âûõîäå àâòîìàòà, à çíà÷èò, è åãî ïîòåíöèàëüíàÿ ïîìå-
õîóñòîé÷èâîñòü, îáåñïå÷èâàåòñÿ áëàãîäàðÿ òîìó, ÷òî àâòîìàò ìîæåò çàïèñû-
âàòü áîëüøå ñèìâîëîâ, ÷åì ñ÷èòûâàåò, à òàêæå èìåòü «òóïèêîâûå» ñîñòîÿíèÿ
èëè «îøèáî÷íûå» ïåðåõîäû, â êîòîðûõ îí íèêîãäà íå îêàæåòñÿ ïðè äåêîäèðî-
âàíèè êîððåêòíî ïåðåäàííîãî êîäîâîãî ñëîâà, îäíàêî ìîæåò ïîïàñòü â ñëó÷àå
èíâåðòèðîâàíèÿ íåêîòîðûõ åãî áèòîâ.
Óñëîâèÿ, ïðè âûïîëíåíèè êîòîðûõ àâòîìàò îñóùåñòâëÿåò òîò èëè èíîé ïåðå-
õîä, ìîãóò áûòü çíà÷èòåëüíî ñëîæíåå, ÷åì ïðîâåðêà ñîîòâåòñòâèÿ íåñêîëüêèõ ñ÷è-
òàííûõ àâòîìàòîì ñèìâîëîâ îïðåäåëåííîìó ýòàëîííîìó çíà÷åíèþ.  ÷àñòíîñòè, áè-
òîâàÿ ïîñëåäîâàòåëüíîñòü íà âõîäå àâòîìàòà ìîæåò èíòåðïðåòèðîâàòüñÿ êàê öåëîå
÷èñëî, àðèôìåòè÷åñêèå ñâîéñòâà êîòîðîãî îïðåäåëÿþò ïîñëåäîâàòåëüíîñòü ïåðåõî-
äîâ. Òàêîé ïîäõîä èñïîëüçîâàí íà ïåðâîì, âíóòðåííåì, óðîâíå îïèñàííîé â äàííîé
ñòàòüå äâóõóðîâíåâîé ñèñòåìû êîäèðîâàíèÿ: âõîäíîå ñîîáùåíèå ðàññìàòðèâàåòñÿ
êàê äâîè÷íîå ÷èñëî è ïðåäñòàâëÿåòñÿ â äâóõáàçèñíîé ñèñòåìå èñ÷èñëåíèÿ â âèäå òàê
íàçûâàåìîãî (2,3)-êîäà, îáëàäàþùåãî îïðåäåëåííîé èçáûòî÷íîñòüþ è ïîìåõîóñòîé-
÷èâîñòüþ. Çàòåì ñïåöèàëüíûé êîíå÷íûé àâòîìàò âûïîëíÿåò âíåøíåå êîäèðîâàíèå,
óñèëèâàþùåå ïîìåõîóñòîé÷èâûå ñâîéñòâà. Âûñîêàÿ ïîìåõîóñòîé÷èâîñòü îáåñïå÷è-
âàåòñÿ èìåííî áëàãîäàðÿ ñî÷åòàíèþ íà âíåøíåì è âíóòðåííåì óðîâíÿõ ðàçíîðîä-
íûõ ïîäõîäîâ, ñîñòîÿùèõ â ãåíåðèðîâàíèè ñèìâîëîâ êîäà íà îñíîâå íåñêîëüêèõ
âõîäíûõ äâîè÷íûõ ñèìâîëîâ è ðåçóëüòàòà àðèôìåòè÷åñêèõ îïåðàöèé íàä áîëüøèì
áëîêîì ñèìâîëîâ âõîäíîãî êîäà êàê íàä öåëûì ÷èñëîì.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 2 43
© È.À. Çàâàäñêèé, 2015
Êîä èìååò ïåðåìåííóþ äëèíó, ò.å. äëÿ ðàçëè÷íûõ âõîäíûõ èíôîðìàöèîí-
íûõ ñîîáùåíèé îäèíàêîâîé äëèíû áèòîâàÿ äëèíà ãåíåðèðóåìûõ êîäîâûõ ñëîâ
ìîæåò ðàçëè÷àòüñÿ. Îäíàêî ñðåäíåå îòíîøåíèå áèòîâîé äëèíû ñîîáùåíèÿ íà
âõîäå ê äëèíå êîäîâîãî ñëîâà ñîñòàâëÿåò 1/2.
ÂÍÓÒÐÅÍÍÅÅ ÊÎÄÈÐÎÂÀÍÈÅ
 îñíîâå âíóòðåííåãî êîäèðîâàíèÿ ëåæèò íèæíèé (2,3)-êîä öåëûõ ÷èñåë. Âïåð-
âûå (2,3)-êîäèðîâàíèå áûëî îïèñàíî â [1], à íèæíèé (2,3)-êîä, ìåòîäû åãî ïî-
ñòðîåíèÿ è ïîìåõîóñòîé÷èâûå ñâîéñòâà èññëåäîâàíû â [2]. Ïðèâåäåì îñíîâíûå
îïðåäåëåíèÿ. Ïóñòü N2 3, — ìíîæåñòâî íàòóðàëüíûõ ÷èñåë, âçàèìíî ïðîñòûõ ñ 2
è 3, x ÎN2 3, , x >1, ë ûn x= log 2 . Òîãäà x ìîæíî ïðåäñòàâèòü â ôîðìå
2 31
1
n k
x
- + èëè 2 32
1
n k
x
- + , ãäå k ÎN, x x x1 2 3 1Î <N , , , è òîëüêî â îäíîé èç
ýòèõ ôîðì. Ðàñêëàäûâàÿ àíàëîãè÷íûì îáðàçîì x1, ïîëó÷àåì x2 è äàëåå áóäåì âû-
÷èñëÿòü xi+1 èç óðàâíåíèÿ x xi
n k
i
i i= + +2 3 1, ïîêà íà íåêîòîðîé èòåðàöèè íå ïîëó-
÷èì xi =1 èëè xi = 2. Äëÿ îäíîçíà÷íîãî äåêîäèðîâàíèÿ ÷èñåë äîñòàòî÷íî çàïîìè-
íàòü âû÷èñëÿåìûå íà êàæäîé èòåðàöèè âåëè÷èíû D i
k
i i
i x n=ë ûlog 2 3 - è k i .
Ïðè äåêîäèðîâàíèè ïîñëåäîâàòåëüíîñòü çíà÷åíèé xi âîññòàíàâëèâàåòñÿ â îá-
ðàòíîì ïîðÿäêå: x xt , ,K 0 , ãäå xt =1èëè xt = 2 . Âûáîð îäíîãî èç äâóõ âîçìîæíûõ
íà÷àëüíûõ çíà÷åíèé xt îïðåäåëÿåòñÿ òåì ôàêòîì, ÷òî åñëè xt- = = + ×1
0 17 2 3 2, òî
x b kt i t= = =-2 0 11, , , m x
k= =ë ûlog 2 13 2, D t- =1 m b- = 2. Ëåãêî ïîêàçàòü, ÷òî
xt- =1 7 — åäèíñòâåííûé ñëó÷àé, êîãäà k t- =1 1, D t- =1 2 , è åäèíñòâåííûé ñëó-
÷àé, êîãäà xt = 2. Ïîýòîìó, åñëè k t- =1 1è D t- =1 2, ïîëàãàåì xt = 2, èíà÷å xt =1.
Ïóñòü 2 3 1
b k
x+ — íèæíåå ðàçëîæåíèå ÷èñëà x , D = -ë ûlog 2 13k
x b. Ïîêà-
æåì, ÷òî D ìîæåò ïðèíèìàòü òîëüêî çíà÷åíèÿ 0, 1 èëè 2, åñëè
2 3
7
8
21
1m k m
x< £ + ,
(1)
è òîëüêî çíà÷åíèÿ 0 èëè 1, åñëè
7
8
2 3 21
1
1m k m
x
+ +< < .
(2)
Íèæíèé (2,3)-êîä ÷èñëà x — ïîñëåäîâàòåëüíîñòü áèòîâûõ ãðóïï âèäà
0 01 1¼ ¼ , ïåðâàÿ èç êîòîðûõ êîäèðóåò (2,3)-ðàçëîæåíèå ÷èñëà x, à ïîñëåäóþùèå —
ðàçëîæåíèÿ xi íà äàëüíåéøèõ èòåðàöèÿõ. Êîëè÷åñòâî åäèíèö â ãðóïïå ðàâíî k i ,
à êîëè÷åñòâî íóëåé îïðåäåëÿåòñÿ âåëè÷èíîé D i .  ñëó÷àå (1) çíà÷åíèå D i = 0 êîäè-
ðóåòñÿ òðåìÿ íóëÿìè, D i =1 — äâóìÿ, D i = 2 — îäíèì íóëåì, à â ñëó÷àå (2) D i = 0
êîäèðóåòñÿ äâóìÿ íóëÿìè, D i =1 — îäíèì íóëåì. Òàêîé ñïîñîá êîäèðîâàíèÿ âû-
áðàí â öåëÿõ ñîêðàùåíèÿ ñðåäíåé äëèíû êîäà.
Çàìåòèì, ÷òî óðîâåíü ïîìåõîóñòîé÷èâîñòè íèæíåãî (2,3)-êîäà íåäîñòàòî÷åí
äëÿ ïðàêòè÷åñêîãî ïðèìåíåíèÿ áåç ñî÷åòàíèÿ ñ äðóãèìè ìåòîäàìè êîäèðîâàíèÿ.
Îäíàêî ïîìåõîóñòîé÷èâîñòü ìîæíî ñóùåñòâåííî ïîâûñèòü, ïðåîáðàçîâàâ íèæ-
íèé (2,3)-êîä ñ ïîìîùüþ èçîáðàæåííîãî íà ðèñ. 1 êîíå÷íîãî àâòîìàòà. Àâòîìàò
èìååò òðè ñîñòîÿíèÿ, îáîçíà÷åííûõ êðóæêàìè. Ïåðâàÿ öèôðà â êðóæêå — íîìåð
ñîñòîÿíèÿ, à ïîä íåé â ñêîáêàõ çàïèñàíû ñèìâîëû, ðàñïîëîæåííûå ïåðåä ãîëîâ-
êîé àâòîìàòà, êîãäà îí ïðåáûâàåò â ýòîì ñîñòîÿíèè.
44 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 2
Ïåðâûé ñèìâîë êîäà, âñåãäà ðàâíûé 0, àâòîìàò ïðîïóñêàåò è íà÷èíàåò êîäè-
ðîâàíèå â ñîñòîÿíèè 1 ñî âòîðîãî ñèìâîëà è ñî çíà÷åíèÿ xt =1 èëè xt = 2, ïðèí-
öèï âûáîðà êîòîðîãî îïèñàí âûøå. Àâòîìàò ïåðåõîäèò â òî èëè èíîå ñîñòîÿíèå
â ñîîòâåòñòâèè ñ ðèñ. 1 â çàâèñèìîñòè îò òîãî, êàêèå ñèìâîëû ñ÷èòûâàåò ãîëîâêà,
à òàêæå îò íåêîòîðûõ äðóãèõ óñëîâèé; ýòè ñèìâîëû è óñëîâèÿ çàïèñàíû âîçëå
ñòðåëîê ïåðåõîäîâ ïåðåä êîñîé ÷åðòîé. Ïîñëå êîñîé ÷åðòû óêàçàíû ñèìâîëû, êî-
òîðûå àâòîìàò çàïèñûâàåò â êîä íà âûõîäå ïðè êàæäîì ïåðåõîäå. Òàê êàê èç êàæ-
äîãî ñîñòîÿíèÿ åñòü ÷åòûðå ïåðåõîäà, äëÿ èäåíòèôèêàöèè ïåðåõîäà â ðåçóëüòè-
ðóþùèé êîä äîñòàòî÷íî çàïèñàòü äâà áèòà.
Óïîìÿíóòûå âûøå óñëîâèÿ ïåðåõîäîâ ìîãóò áûòü äâóõ òèïîâ. Âî-ïåðâûõ, ýòî
óñëîâèÿ, ñâÿçàííûå ñ òåì, ÷òî íåêîòîðûå ïåðåõîäû àâòîìàò âûïîëíÿåò â çàâèñèìîñ-
òè îò çíà÷åíèÿ õåø-ôóíêöèè, àðãóìåíòîì êîòîðîé ÿâëÿåòñÿ âû÷èñëÿåìàÿ íà êàæäîé
èòåðàöèè âåëè÷èíà xi . Òàêîé õåø-ôóíêöèåé ìîæåò áûòü, íàïðèìåð,
G x xi i( ) mod= 20 . Ïîñêîëüêó xi — íå÷åòíîå ÷èñëî, ýòà ôóíêöèÿ ìîæåò ïðèíèìàòü
äåñÿòü çíà÷åíèé. Åñëè ðàñïðåäåëèòü èõ ïî äâóì ìíîæåñòâàì G1 è G2 òàê, ÷òî
G G1 21 3 5 7 11 9 13 15 17 19= ={ } { }, , , , , , , , , , òî âåðîÿòíîñòè ïîïàäàíèÿ çíà÷åíèé G xi( )
â êàæäîå èç ýòèõ ìíîæåñòâ áóäóò ïðèáëèçèòåëüíî îäèíàêîâûìè. Ñèìâîë G1 èëè G2
âîçëå ñòðåëêè ïåðåõîäà îçíà÷àåò, ÷òî ïåðåõîä îñóùåñòâëÿåòñÿ, òîëüêî åñëè òåêóùåå
çíà÷åíèå G xi( ) ïðèíàäëåæèò ìíîæåñòâó G1 èëè G2 ñîîòâåòñòâåííî (è/èëè âûïîëíÿ-
þòñÿ äðóãèå óñëîâèÿ ïåðåõîäà). Âî-âòîðûõ, óñëîâèåì ìîæåò áûòü âûïîëíåíèå íåðà-
âåíñòâ (1) èëè (2) äëÿ âåëè÷èíû 3k
ix . Ýòè óñëîâèÿ íà ðèñ. 1 îáîçíà÷åíû êàê (1) è (2).
Ðàññìîòðèì, íàïðèìåð, ïåðåõîä èç ñîñòîÿíèÿ 1 â ñîñòîÿíèå 2, îáîçíà÷åííûé
êàê ( )& ( )& & /1 01 2 01 101Ú G . Ýòî îçíà÷àåò, ÷òî àâòîìàò âûïîëíèò ïåðåõîä, åñëè:
â ñëó÷àå (1) ñ÷èòàíû ñèìâîëû 01 èëè â ñëó÷àå (2) ñ÷èòàíû ñèìâîëû 01 è âåëè÷è-
íà G xi( ) ïðèíàäëåæèò ìíîæåñòâó G1.
Òàêèì îáðàçîì, ïðè îáðàáîòêå àâòîìàòîì íèæíåãî (2,3)-êîäà äîëæíû âû-
÷èñëÿòüñÿ òàêæå è çíà÷åíèÿ xi (èëè ìîãóò èñïîëüçîâàòüñÿ çíà÷åíèÿ, ïîëó÷åííûå
ïðè ïîñòðîåíèè íèæíåãî (2,3)-êîäà). Êàæäîå ñëåäóþùåå òàêîå çíà÷åíèå áóäåò
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 2 45
2
(1)
1
1
(À
)
Ú
0
0
0
1
(B
)
/
1
0
À
&
1
/
1
0
10 /11
À & 0 / 00
B & 0 / 01
1&G1 / 00
0
1
&
G
1(
À
)
Ú
0
1
&
G
2
(B
)
/
0
1 B
&
1
/
1
1
1
(10)
3
(1)
1&G2 / 01
(1)&01Ú(2)&01&G1 / 10
001Ú(2)&01&G2 / 11
0
0
1
&
G
1
(À
)
Ú
0
0
1
&
G
2
(B
)
/
0
0
Ðèñ. 1. Ñõåìà êîíå÷íîãî àâòîìàòà, ãåíåðèðóþùåãî ïîìåõîóñòîé÷èâûé íèæíèé (2,3)-êîä
âû÷èñëÿòüñÿ ïîñëå îáðàáîòêè àâòîìàòîì î÷åðåäíîé ãðóïïû ñèìâîëîâ 0 01 1¼ ¼ ,
êîäèðóþùåé ïàðó çíà÷åíèé ( , )D i ik , — íàçîâåì åå ( , )D k -ãðóïïîé. Ïî ïðè÷èíàì,
êîòîðûå ïîíÿòíû èç îïèñàíèÿ ìåòîäà äåêîäèðîâàíèÿ, ( , )D k -ãðóïïû íèæíåãî
(2,3)-êîäà äîëæíû îáðàáàòûâàòüñÿ èçîáðàæåííûì íà ðèñ. 1 àâòîìàòîì ñïðàâà íà-
ëåâî (îäíàêî ïîðÿäîê îáðàáîòêè áèòîâ âíóòðè ãðóïï èçìåíÿòü íå íóæíî).
Ñîñòîÿíèå 3 — îñîáîå. Êàæäûé ïåðåõîä â ýòî ñîñòîÿíèå ìîæåò âûïîëíÿòüñÿ
ïðè ñ÷èòûâàíèè íå îäíîé îïðåäåëåííîé ãðóïïû ñèìâîëîâ, à äâóõ ðàçëè÷íûõ
ãðóïï, îáîçíà÷åííûõ íà ðèñ. 1 êàê A è Â. Ñïîñîá âûõîäà èç ñîñòîÿíèÿ 3 çàâèñèò îò
òîãî, â ñîîòâåòñòâèè ñ êàêèì óñëîâèåì áûë îñóùåñòâëåí ïåðåõîä â ýòî ñîñòîÿíèå:
A èëè Â. Íàïðèìåð, åñëè àâòîìàò ïåðåøåë â ñîñòîÿíèå 3 èç ñîñòîÿíèÿ 2, ñ÷èòàâ
ñèìâîëû 11 (óñëîâèå A), à çàòåì ãîëîâêà ñ÷èòàëà 0, àâòîìàò ïåðåéäåò èç ñîñòîÿ-
íèÿ 3 â ñîñòîÿíèå 1 ïî ñòðåëêå A&0 è çàïèøåò ñèìâîëû 00.
Êîãäà àâòîìàò çàêàí÷èâàåò êîäèðîâàòü âõîäÿùóþ áèòîâóþ ïîñëåäîâàòåëü-
íîñòü, âîçìîæíû ñëåäóþùèå ñëó÷àè:
1) àâòîìàò îñòàíîâèëñÿ â ñîñòîÿíèè 3, òîãäà îí äîëæåí äîïèñàòü ê êîäîâîìó
ñëîâó ñïðàâà îäèí áèò, îïðåäåëÿþùèé, â ñîîòâåòñòâèè ñ êàêèì óñëîâèåì, A èëè B,
áûë âûïîëíåí ïåðåõîä â ýòî ñîñòîÿíèå;
2) êîäîâîå ñëîâî îêàí÷èâàåòñÿ ñèìâîëàìè 11, ãîëîâêà ðàçìåùåíà ïåðåä ïî-
ñëåäíèì ñèìâîëîì 1, àâòîìàò íàõîäèòñÿ â ñîñòîÿíèè 2 è äëÿ ïîñëåäíåãî åäèíè÷-
íîãî áèòà ïåðåõîä èç ñîñòîÿíèÿ 2 íå ïðåäóñìîòðåí, òîãäà ê êîäîâîìó ñëîâó ñëåäó-
åò äîïèñàòü ñïðàâà ñèìâîëû 11, ÷òî ñîîòâåòñòâóåò ñèìâîëàì 10 â èñõîäíîì êîäå
è ïåðåõîäó â ñîñòîÿíèå 1; ïðè äåêîäèðîâàíèè ïîñëåäíèé íóëåâîé áèò êîäîâîãî
ñëîâà áóäåò ïðîèãíîðèðîâàí, òàê êàê îíî ñîñòîèò èç 0 01 1¼ ¼ -ãðóïï è íå ìîæåò
îêàí÷èâàòüñÿ íóëåì.
Óñëîâèÿ ïåðåõîäîâ ìåæäó ñîñòîÿíèÿìè ñôîðìóëèðîâàíû ñ ó÷åòîì óêàçàí-
íûõ â [2] âåðîÿòíîñòåé ðàçëè÷íûõ çíà÷åíèé D òàê, ÷òîáû âñå ïåðåõîäû èç êàæäî-
ãî ñîñòîÿíèÿ áûëè êàê ìîæíî áîëåå ðàâíîâåðîÿòíûìè. Ýòî ïîçâîëÿåò óìåíüøèòü
äëèíó êîäà, êîòîðàÿ â ðåçóëüòàòå ïðåâûøàåò äëèíó äâîè÷íîãî ïðåäñòàâëåíèÿ
÷èñëà â 1,25 ðàç â ñðåäíåì. Ââèäó íåáîëüøîãî óâåëè÷åíèÿ äëèíû ïðè ñóùåñòâåí-
íîì âîçðàñòàíèè ïîìåõîóñòîé÷èâîñòè ïîëó÷àåìûé íà âûõîäå àâòîìàòà êîä íàçû-
âàåòñÿ ñæàòûì (2,3)-êîäîì.
Ïðè äåêîäèðîâàíèè ñ÷èòûâàþòñÿ ïàðû áèòîâ èç ñæàòîãî (2,3)-êîäà, âûïîëíÿ-
þòñÿ ñîîòâåòñòâóþùèå èì ïåðåõîäû è âû÷èñëÿþòñÿ çíà÷åíèÿ x xt , ,K 0 . Åñëè íåêî-
òîðûé áèò êîäà âñëåäñòâèå ïîìåõ â êàíàëå ñâÿçè áóäåò èíâåðòèðîâàí, òî íà îäíîì
èç ïåðåõîäîâ, âûïîëíÿþùèõñÿ âñêîðå ïîñëå îáðàáîòêè ýòîãî áèòà, ñ áîëüøîé âåðî-
ÿòíîñòüþ çíà÷åíèå õåø-ôóíêöèè G xi( ) ìîæåò ïðèíàäëåæàòü ìíîæåñòâó G1, õîòÿ ñî-
ãëàñíî êîäèðîâêå îíî äîëæíî ïðèíàäëåæàòü ìíîæåñòâó G2 , ëèáî íàîáîðîò. Òàêàÿ
ñèòóàöèÿ ïîçâîëÿåò âûÿâëÿòü îøèáêè â êîäå, ÷òî îáåñïå÷èâàåò îïðåäåëåííóþ åãî
ïîìåõîóñòîé÷èâîñòü, êîòîðàÿ ñóùåñòâåííî âûøå ïîìåõîóñòîé÷èâîñòè îïèñàííîãî
â [2] íèæíåãî (2,3)-êîäà.
ÂÍÅØÍÅÅ ÊÎÄÈÐÎÂÀÍÈÅ
Åñëè ðàññìîòðåòü ïîäðîáíåå ïîìåõîóñòîé÷èâûå ñâîéñòâà ñæàòîãî (2,3)-êîäà,
òî îêàæåòñÿ, ÷òî îí ïîçâîëÿåò ñ âûñîêîé âåðîÿòíîñòüþ îáíàðóæèâàòü ôàêò íà-
ëè÷èÿ îøèáîê â êîäîâîì ñëîâå, íî äàåò ìàëî èíôîðìàöèè î òîì, â êàêèõ
èìåííî áèòàõ ïðîèçîøëè îøèáêè, à çíà÷èò, è âîçìîæíîñòåé äëÿ èñïðàâëåíèÿ
îøèáîê. Ýòî âïîëíå åñòåñòâåííî äëÿ âûñîêîñêîðîñòíîãî ìåòîäà êîäèðîâàíèÿ,
â êîòîðîì îòíîøåíèå äëèíû äâîè÷íîé ïîñëåäîâàòåëüíîñòè ê ñðåäíåé äëèíå
êîäîâîãî ñëîâà ñîñòàâëÿåò 0,8. ×òîáû èìåòü âîçìîæíîñòü îáíàðóæèâàòü ïîçè-
öèè îøèáî÷íûõ áèòîâ, ñëåäóåò ìîäèôèöèðîâàòü êîä, ñíèçèâ, â ÷àñòíîñòè, åãî
ñêîðîñòü. Íàïðèìåð, â èçîáðàæåííîì íà ðèñ. 1 àâòîìàòå ïåðåõîäû ìîæíî êî-
äèðîâàòü íå äâóìÿ, à òðåìÿ áèòàìè, âûáèðàÿ òðîéêè áèòîâ èç ìíîæåñòâà òðè-
46 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 2
àä ñ õåììèíãîâûì ðàññòîÿíèåì 2, òàêîãî êàê { , , , }000 011 101 110 . Ñêîðîñòü
êîäà â ýòîì ñëó÷àå óìåíüøèòñÿ â ïîëòîðà ðàçà. Åñëè â êàæäîé òðèàäå áèòîâ
èìååòñÿ íå áîëåå îäíîé îøèáêè, òî âñå òðèàäû ñ îøèáî÷íûìè áèòàìè ìîæíî
âûÿâèòü ñðàçó. Çàòåì ñ ïîìîùüþ ïåðåáîðíîãî àëãîðèòìà îïðåäåëÿåòñÿ, êàêèå
èìåííî áèòû ýòèõ òðèàä ñîäåðæàò îøèáêè. Ïîäîáíûé ïîäõîä îïèñàí â [3].
Åãî ãëàâíûì íåäîñòàòêîì ÿâëÿåòñÿ îãðàíè÷åíèå, ñâÿçàííîå ñ íàëè÷èåì íå áî-
ëåå îäíîé îøèáêè â êàæäîé òðèàäå. Äàëåå îïèøåì êîíå÷íûé àâòîìàò, êîòî-
ðûé òàêæå îáðàáàòûâàåò ñæàòûé (2,3)-êîä è óìåíüøàåò åãî ñêîðîñòü â ïîëòîðà
ðàçà, îäíàêî ëèøåí ýòîãî íåäîñòàòêà.
Àâòîìàò ñ÷èòûâàåò ïàðû áèòîâ ñæàòîãî íèæíåãî (2,3)-êîäà, îñóùåñòâëÿåò
ïåðåõîäû ìåæäó ñîñòîÿíèÿìè è çàïèñûâàåò ïðè ýòîì â ðåçóëüòèðóþùèé êîä òðè-
àäû áèòîâ. Îí èìååò 16 ñîñòîÿíèé, îáúåäèíåííûõ â ÷åòûðå ãðóïïû ïî ÷åòûðå ñî-
ñòîÿíèÿ â êàæäîé (ðèñ. 2). Òðèàäû, çàïèñûâàåìûå àâòîìàòîì, ïðèíàäëåæàò ê îä-
íîìó èç ìíîæåñòâ: A = { , , , }000 011 101 110 èëè B = { , , , }111 100 010 001 , â çàâèñè-
ìîñòè îò òîãî, èç êàêîãî ñîñòîÿíèÿ îñóùåñòâëÿåòñÿ ïåðåõîä. Ýòè ìíîæåñòâà
áóäåì íàçûâàòü òàêæå êîäèðîâêàìè À è Â. Íà ðèñ. 2 ìíîæåñòâî òðèàä, ñîîòâåò-
ñòâóþùåå ïåðåõîäó, óêàçàíî âîçëå ñòðåëêè ïåðåõîäà (áóêâà À èëè Â). Â öåëîì
ðàáîòà àâòîìàòà íà ýòîì ðèñóíêå ïðåäñòàâëåíà â ñîêðàùåííîì âèäå, òàê êàê íà
ñàìîì äåëå êàæäîé ñòðåëêå ïåðåõîäà ñîîòâåòñòâóþò ÷åòûðå ïåðåõîäà, âåäóùèõ
âî âñå ñîñòîÿíèÿ òîé ãðóïïû, íà êîòîðóþ óêàçûâàåò ñòðåëêà.
Êàê âèäíî èç ðèñ. 2, íîìåð ãðóïïû ñîñòîÿíèé íà ñëåäóþùåé èòåðàöèè ðàâåí
íîìåðó ñîñòîÿíèÿ âíóòðè ãðóïïû íà òåêóùåé èòåðàöèè, à ñ÷èòûâàåìûå àâòîìà-
òîì ïàðû ñèìâîëîâ ñæàòîãî (2,3)-êîäà îïðåäåëÿþò, âî-ïåðâûõ, êàêîé èìåííî
ýëåìåíò ìíîæåñòâà À èëè Â áóäåò çàïèñàí â êîä íà âûõîäå, âî-âòîðûõ, â êàêîå ñî-
ñòîÿíèå âíóòðè ãðóïïû ñîñòîÿíèé ïåðåéäåò àâòîìàò. Ýòà âçàèìîñâÿçü îòðàæåíà
â òàáë. 1. Íîìåð ñîñòîÿíèÿ âíóòðè ãðóïïû ðàâåí çíà÷åíèþ îäíîé èç ôóíêöèé —
( ) modx +1 4 ëèáî ( ) modx +3 4 , ãäå x — äâóõðàçðÿäíîå äâîè÷íîå ÷èñëî, áèòû êî-
òîðîãî ñ÷èòàíû àâòîìàòîì. Åñëè ïðèìåíÿåòñÿ ïåðâàÿ èç ýòèõ ôóíêöèé, òî ñòðåë-
êà ñîîòâåòñòâóþùåãî ïåðåõîäà íà ðèñ. 2 îáîçíà÷åíà öèôðîé 1 ïîñëå ñèìâîëà À
èëè B, åñëè âòîðàÿ — òî öèôðîé 3.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 2 47
Ò à á ë è ö à 1. Ïåðåõîäû ïðè âíåøíåì êîäèðîâàíèè
Òèï êîäèðîâêè Ñ÷èòàííûå ñèìâîëû Çàïèñûâàåìûå ñèìâîëû
Íîâîå ñîñòîÿíèå
(x — ñ÷èòàííîå
äâóõáèòîâîå ÷èñëî)
A1
00 000
( ) modx + 1 4
01 011
10 101
11 110
A3
00 000
( ) modx + 3 4
01 011
10 101
11 110
B1
00 111
( ) modx + 1 4
01 100
10 010
11 001
B3
00 111
( ) modx + 3 4
01 100
10 010
11 001
Êàê êîäèðîâàíèå, òàê è äåêîäèðîâàíèå àâòîìàò íà÷èíàåò â ïåðâîì ñîñòîÿ-
íèè ïåðâîé ãðóïïû è çàêàí÷èâàåò ñ îêîí÷àíèåì îáðàáîòêè ïîäàþùåãîñÿ íà âõîä
èíôîðìàöèîííîãî ñîîáùåíèÿ. Äîêàæåì íåêîòîðûå ñâîéñòâà àâòîìàòà,
ñóùåñòâåííûå ñ òî÷êè çðåíèÿ èññëåäîâàíèÿ åãî ïîìåõîóñòîé÷èâîñòè.
Çàìåòèì, ÷òî åñòü äâà ñïîñîáà ðàñïðåäåëåíèÿ êîäèðîâîê â ãðóïïàõ ñîñòîÿ-
íèé: â ãðóïïàõ 1 è 2 ñîñòîÿíèÿì 1, 2, 3, 4 ñîîòâåòñòâóþò êîäèðîâêè A B A B, , , ,
à â ãðóïïàõ 3, 4 — êîäèðîâêè B A B A, , , . Ïîýòîìó ãðóïïû 1 è 2 íàçîâåì îáúåäè-
íåíèåì ABAB, à ãðóïïû 3 è 4 — îáúåäèíåíèåì BABA . Ïðîàíàëèçèðîâàâ ðèñ. 2,
îòìåòèì ñëåäóþùåå ñâîéñòâî ðàññìàòðèâàåìîãî àâòîìàòà.
Ñâîéñòâî 1. Åñëè äâóì ðàçëè÷íûì ñîñòîÿíèÿì îäíîé ãðóïïû ñîîòâåòñòâóþò
îäèíàêîâûå êîäèðîâêè, òî èç îäíîãî òàêîãî ñîñòîÿíèÿ ïåðåõîäû îñóùåñòâëÿþòñÿ
â ãðóïïó îáúåäèíåíèÿ BABA , à èç äðóãîãî — â ãðóïïó îáúåäèíåíèÿ ABAB.
×òîáû äîêàçàòü åùå îäíî âàæíîå ñâîéñòâî àâòîìàòà, ââåäåì ôóíêöèþ
S s g( , , )u , çíà÷åíèå êîòîðîé ðàâíî íîìåðó ñîñòîÿíèÿ àâòîìàòà âíóòðè ãðóïïû íà
ñëåäóþùåé èòåðàöèè, åñëè íà òåêóùåé èòåðàöèè àâòîìàò íàõîäèëñÿ â ñîñòîÿíèè
s ãðóïïû g è ñ÷èòàë äâóõáèòîâîå ÷èñëî u. Òàê êàê âñåì ñîñòîÿíèÿì êàæäîé ãðóï-
ïû ñîïîñòàâëåíà îäíà è òà æå ôóíêöèÿ ïåðåõîäà ñîñòîÿíèé âèäà ( ) modx c+ 4, òî,
åñëè s è q — äâà ðàçëè÷íûõ ñîñòîÿíèÿ èç îäíîé ãðóïïû g, âûïîëíÿåòñÿ ðàâåí-
ñòâî ( ( , , ) ( , , )) mod ( ) modS s g S q g s qu u- = -4 4 . Åñëè ïðè ýòîì s è q — ñîñòîÿ-
íèÿ ñ îäèíàêîâûìè êîäèðîâêàìè, òî ( ) (mod )s q- = 2 4 (ðèñ. 2), à çíà÷èò,
è ( ( , , ) ( , , )) (mod )S s g S q gu u- = 2 4 . Ñîñòîÿíèÿì, íîìåðà êîòîðûõ îòëè÷àþòñÿ íà 2,
â îáúåäèíåíèÿõ BABA è ABAB ñîîòâåòñòâóþò ðàçëè÷íûå êîäèðîâêè, ïîýòîìó
ñ ó÷åòîì ñâîéñòâà 1 ïîëó÷àåì ñëåäóþùåå ñâîéñòâî.
Ñâîéñòâî 2. Åñëè s è q — ðàçëè÷íûå ñîñòîÿíèÿ ñ îäèíàêîâûìè êîäèðîâêà-
ìè, ïðèíàäëåæàùèå ãðóïïàì îäíîãî îáúåäèíåíèÿ, òî äëÿ ëþáîãî ñ÷èòàííîãî àâ-
òîìàòîì çíà÷åíèÿ u ïåðåõîäû èç ñîñòîÿíèé S s g( , , )u è S q g( , , )u èìåþò ðàçëè÷-
íûå êîäèðîâêè.
48 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 2
1 2 3 4
1 2 3 4
1
2
3
4
1
2
3
4
A1
A3
B1
A1
B1
A3
B3
B3
B1
A1
B1
A1 A3
B3
A3
B3
2
1
3
4
Ðèñ. 2. Îáùàÿ ñõåìà àâòîìàòà, âûïîëíÿþùåãî âíåøíåå êîäèðîâàíèå
Åñëè â êîäîâîì ñëîâå âîçíèêàþò îøèáêè, îíè ïðèâîäÿò ê ñáîÿì: ñèòóàöèÿì,
êîãäà âî âðåìÿ äåêîäèðîâàíèÿ àâòîìàò íàõîäèòñÿ â ñîñòîÿíèè, êîòîðîìó ñîîòâåò-
ñòâóåò ìíîæåñòâî êîäîâûõ ñëîâ A, îäíàêî ñ÷èòûâàåò êîäîâîå ñëîâî èç ìíîæåñò-
âà B, ëèáî íàîáîðîò. Âçàèìîñâÿçü ìåæäó ìåñòîì âîçíèêíîâåíèÿ îøèáêè è ìåñ-
òîì ñáîÿ îïðåäåëÿåòñÿ ñëåäóþùèìè ñâîéñòâàìè.
Ñâîéñòâî 3. Åñëè òðèàäà t ñîäåðæèò îäíó èëè òðè îøèáêè, à ïðè ïåðåõîäå
ê íåé àâòîìàò íàõîäèëñÿ â ïðàâèëüíîì ñîñòîÿíèè, ñáîé ïðîèçîéäåò ïðè îáðàáîò-
êå òðèàäû t.
Ñâîéñòâî 4. Åñëè òðèàäà t ñîäåðæèò äâå îøèáêè, ïðè ïåðåõîäå ê íåé àâòî-
ìàò íàõîäèëñÿ â ïðàâèëüíîì ñîñòîÿíèè è òðèàäû t +1, t +2 îøèáîê íå ñîäåðæàò,
òî ñáîé ïðîèçîéäåò ïðè îáðàáîòêå òðèàäû t +1 èëè t +2.
Ñâîéñòâî 3 ñëåäóåò íåïîñðåäñòâåííî èç ïîñòðîåíèÿ ìíîæåñòâ À è Â, à ñâîé-
ñòâî 4 òðåáóåò äîêàçàòåëüñòâà.
Ïóñòü g g gt t t, ,+ +1 2 è s s st t t, ,+ +1 2 — ãðóïïû è âíóòðèãðóïïîâûå ñîñòîÿíèÿ
àâòîìàòà, ñîîòâåòñòâóþùèå òðèàäàì t, t +1 è t +2 â ñëó÷àå îòñóòñòâèÿ îøèáîê
â òðèàäå t, à ¢ ¢ ¢+ +g g gt t t, ,1 2 è ¢ ¢ ¢+ +s s st t t, ,1 2 — ñîîòâåòñòâóþùèå ãðóïïû è ñîñòîÿ-
íèÿ â ñëó÷àå äâóõ îøèáîê â òðèàäå t. Äâå îøèáêè â îäíîé òðèàäå ïðåîáðàçóþò åå
â äðóãîé ýëåìåíò òîãî æå êîäîâîãî ìíîæåñòâà (A èëè B). Ïîýòîìó ïðè äâóõ
îøèáêàõ â òðèàäå t ñáîé ïðÿìî â íåé íå âîçíèêíåò è ïîñëå åå îáðàáîòêè àâòîìàò
ïåðåéäåò â òó æå ãðóïïó, ÷òî è â ñëó÷àå îòñóòñòâèÿ îøèáîê â ýòîé òðèàäå, îäíàêî
â äðóãîå åå ñîñòîÿíèå, ò.å. g gt t+ += ¢1 1, íî s st t+ +¹ ¢1 1. Îáîçíà÷èì E s( ) ôóíêöèþ,
âîçâðàùàþùóþ òèï êîäèðîâêè (À èëè Â) äëÿ ïåðåõîäîâ èç ñîñòîÿíèÿ s. Âåðîÿò-
íîñòü òîãî, ÷òî E s E st t( ) ( )¢ ¹+ +1 1 , ñîñòàâëÿåò 2 3/ , è â ýòîì ñëó÷àå ñáîé ïðîèçîé-
äåò ïðè îáðàáîòêå òðèàäû t +1. Åñëè E s E st t( ) ( )¢ =+ +1 1 , òî òðèàäà t +1 áóäåò îáðà-
áîòàíà áåç ñáîÿ, íî â ñîîòâåòñòâèè ñî ñâîéñòâîì 2 ñáîé âîçíèêíåò ïðè îáðàáîòêå
òðèàäû t +2. Ñâîéñòâî 4 äîêàçàíî.
Èç ñâîéñòâ 3 è 4 ñëåäóåò ïðîñòîé ìåòîä îïðåäåëåíèÿ íîìåðîâ áèòîâ ñ îøèá-
êàìè, åñëè â ïîñëåäîâàòåëüíûõ òðåõ òðèàäàõ èìååòñÿ íå áîëåå îäíîé îøèáêè.
À èìåííî, åñëè ïðè äåêîäèðîâàíèè íåêîòîðîé òðèàäû t ïðîèçîøåë ñáîé, ïðåäïî-
ëàãàåì íàëè÷èå îøèáêè â êàæäîì áèòå ýòîé òðèàäû è èíâåðòèðóåì ýòîò áèò. Åñëè
ïðåäïîëîæåíèå íåâåðíî, òî âñëåäñòâèå èíâåðòèðîâàíèÿ ñîçäàäèì â òðèàäå t âòî-
ðóþ îøèáêó è ñáîé ïðîèçîéäåò ïðè îáðàáîòêå òðèàä t +1 èëè t +2. Åñëè ïðåäïîëî-
æåíèå âåðíî, òî èñïðàâèì îøèáêó â òðèàäå t è òîãäà òðèàäû t +1èëè t +2 áóäóò îá-
ðàáîòàíû áåç ñáîÿ. Ìåòîä òàêæå áóäåò äåéñòâåííûì, åñëè â ïåðâîé èç òðåõ ïîñëåäî-
âàòåëüíûõ òðèàä âñå òðè áèòà îøèáî÷íû, à â äâóõ äðóãèõ òðèàäàõ îøèáîê íåò.
×òîáû îïðåäåëÿòü îøèáî÷íûå áèòû â òðèàäàõ ñ äâóìÿ îøèáêàìè, íåîáõîäè-
ìî ðàññìîòðåòü åùå íåêîòîðûå ñâîéñòâà êîäèðóþùåãî êîíå÷íîãî àâòîìàòà. Ñëåäó-
þùåå ñâîéñòâî âûòåêàåò íåïîñðåäñòâåííî èç ïîñòðîåíèÿ ôóíêöèè, îïðåäåëÿþùåé
âíóòðèãðóïïîâîå ñîñòîÿíèå íà ñëåäóþùåé èòåðàöèè (ñì. âòîðîé è ïîñëåäíèé
ñòîëáöû òàáë. 1).
Ñâîéñòâî 5. Êàêîâû áû íè áûëè ðàçëè÷íûå ñîñòîÿíèÿ s è q àâòîìàòà (ò.å. ðàç-
ëè÷àþùèåñÿ ëèáî ãðóïïîé, ëèáî âíóòðèãðóïïîâûì íîìåðîì), åñëè àâòîìàò ñ÷èòû-
âàåò â ýòèõ ñîñòîÿíèÿõ îäèíàêîâûå ñèìâîëû, òî â ðåçóëüòàòå ëèáî â îäíîì èç ñîñòî-
ÿíèé ïðîèñõîäèò ñáîé, ëèáî àâòîìàò ïåðåõîäèò íà ñëåäóþùåé èòåðàöèè â ñîñòîÿíèÿ
ñ îäèíàêîâûìè èëè îòëè÷àþùèìèñÿ íà 2 (mod )4 âíóòðèãðóïïîâûìè íîìåðàìè.
Òåïåðü äîêàæåì áîëåå îáùåå âàæíîå ñâîéñòâî.
Ñâîéñòâî 6. Åñëè äâà ýêçåìïëÿðà àâòîìàòà íà íåêîòîðîé èòåðàöèè t íàõî-
äÿòñÿ â ðàçëè÷íûõ (ò.å. ðàçëè÷àþùèõñÿ ëèáî ãðóïïîé, ëèáî âíóòðèãðóïïîâûì
íîìåðîì) ñîñòîÿíèÿõ st è ¢st è íà èòåðàöèÿõ t – t +3 ñ÷èòûâàþò îäèíàêîâûå ñèì-
âîëû, òî íà îäíîé èç èòåðàöèé t – t +3 â ðàáîòå îäíîãî èç àâòîìàòîâ ïðîèçîéäåò
ñáîé.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 2 49
Äåéñòâèòåëüíî, åñëè E s E s( ) ( )¹ ¢ , òî ñáîé ïðîèñõîäèò íåïîñðåäñòâåííî
â òðèàäå t . Åñëè E s E s( ) ( )= ¢ , òî â ñîîòâåòñòâèè ñî ñâîéñòâîì 5 st+ =1
= ¢ ±+st 1 2 4(mod ) ëèáî s st t+ += ¢1 1. Åñëè g t+1 è ¢+g t 1 — ãðóïïû ðàçëè÷íûõ îáúåäè-
íåíèé, òî E s E st t( ) ( )+ +¹ ¢1 1 è ñáîé ïðîèñõîäèò â òðèàäå t +1. Åñëè g t+1 è ¢+g t 1 —
ãðóïïû îäíîãî îáúåäèíåíèÿ è s st t+ += ¢ ±1 1 2 4(mod ) , òî g t+ 2 è ¢+g t 2 áóäóò ãðóï-
ïàìè ðàçëè÷íûõ îáúåäèíåíèé è ñáîé ïðîèçîéäåò â òðèàäå t +2. Íàêîíåö, åñëè
g t+1 è ¢+g t 1 — ãðóïïû îäíîãî îáúåäèíåíèÿ è s st t+ += ¢1 1, òî g gt t+ +¹ ¢1 1,
g gt t+ += ¢2 2 è c s c st t( ) ( )+ +¹ ¢1 1 , ãäå c s( ) — êîíñòàíòà â ôîðìóëå ( ) modx c+ 4, ïî
êîòîðîé âû÷èñëÿåòñÿ íîâîå ñîñòîÿíèå àâòîìàòà (ñì. ïîñëåäíèé ñòîëáåö òàáë. 1).
Ýòî îçíà÷àåò, ÷òî st+ 2 è ¢+st 2 — ñîñòîÿíèÿ îäíîé ãðóïïû, ïðè÷åì
s st t+ += ¢ ±2 2 2 4(mod ). Ïîýòîìó â ñîîòâåòñòâèè ñî ñâîéñòâîì 1 g t+ 3 , ¢+g t 3 áóäóò
ãðóïïàìè ðàçëè÷íûõ îáúåäèíåíèé è ñáîé ïðîèçîéäåò â òðèàäå t +3 . Ñâîéñòâî 6
äîêàçàíî.
Äàëåå îáîçíà÷èì s è g âíóòðèãðóïïîâûå ñîñòîÿíèÿ è ãðóïïû, â êîòîðûõ íà-
õîäèòñÿ àâòîìàò â ñëó÷àå îòñóòñòâèÿ îøèáîê, à ¢s è ¢g — ïðè èõ íàëè÷èè.
Ñâîéñòâî 7. Åñëè â òðèàäàõ t è t +1 ñîäåðæèòñÿ õîòÿ áû îäíà îøèáêà, ïðè
ïåðåõîäå ê òðèàäå t àâòîìàò íàõîäèëñÿ â ïðàâèëüíîì ñîñòîÿíèè, à â òðèàäàõ t è
t +1 íå ïðîèñõîäèò ñáîÿ, òî s st t+ +¹ ¢2 2 èëè g gt t+ +¹ ¢2 2 .
Ïîñêîëüêó ïðè ïåðåõîäå ê òðèàäå t àâòîìàò íàõîäèëñÿ â ïðàâèëüíîì ñîñòîÿ-
íèè, s st t= ¢ . Çàìåòèì, ÷òî îøèáêà â íåêîòîðîé òðèàäå p ïðèâîäèò ê èçìåíåíèþ
çíà÷åíèÿ sp+1, íî íå g p+1. Ïîýòîìó åñëè â òðèàäå t ñîäåðæàòñÿ îøèáêè, òî íåçà-
âèñèìî îò èõ íàëè÷èÿ â òðèàäå t +1 áóäåò âûïîëíÿòüñÿ íåðàâåíñòâî s st t+ +¹ ¢1 1,
à çíà÷èò, g gt t+ +¹ ¢2 2 . Åñëè â òðèàäå t íåò îøèáîê, íî îíè åñòü â òðèàäå t +1, òî
î÷åâèäíî, s st t+ +¹ ¢2 2 . Ñâîéñòâî 7 äîêàçàíî.
Ñâîéñòâî 8. Åñëè òðèàäû t è t +2 ñîäåðæàò îøèáêè, à òðèàäà t +1 íå ñîäåð-
æèò, ïðè ïåðåõîäå ê òðèàäå t àâòîìàò íàõîäèëñÿ â ïðàâèëüíîì ñîñòîÿíèè è â òðè-
àäàõ t , t +1 è t +2 íå ïðîèñõîäèò ñáîÿ, òî g gt t+ +¹ ¢3 3 .
Òàê êàê s st t= ¢ , òî g gt t+ += ¢1 1 è, ïîñêîëüêó îáà àâòîìàòà ñ÷èòûâàþò íà èòåðà-
öèè t +1îäèíàêîâûå ñèìâîëû, áóäåò âûïîëíÿòüñÿ ðàâåíñòâî s st t+ += ¢2 2 . Ïîýòîìó
îøèáêè â òðèàäå t +2 ïðèâåäóò åñëè íå ê ñáîþ â íåé, òî ê âûïîëíåíèþ íåðàâåí-
ñòâà g gt t+ +¹ ¢3 3 . Ñâîéñòâî 8 äîêàçàíî.
Îñíîâûâàÿñü íà ñâîéñòâàõ 4, 6–8, îïèøåì ìåòîä, êîòîðûé ïðè âîçíèêíîâå-
íèè ñáîÿ â ðàáîòå àâòîìàòà ïîçâîëÿåò óçíàòü, íå ïðèâåëà ëè ê ñáîþ äâîéíàÿ
îøèáêà â íåêîòîðîé òðèàäå, è, åñëè ýòî òàê, îïðåäåëèòü äâà îøèáî÷íûõ áèòà.
Ïðåäïîëàãàåì, ÷òî ñáîé ïðîèçîøåë â òðèàäå t , à òðèàäû t +1– t + 4 îøèáîê íå ñî-
äåðæàò. Ñîãëàñíî ñâîéñòâó 4 ñáîé â òðèàäå t ìîæåò ñâèäåòåëüñòâîâàòü î íàëè÷èè
äâîéíîé îøèáêè â òðèàäå t -1 ëèáî t -2. Ïîýòîìó ñëåäóåò ðàññìîòðåòü âñå øåñòü
âîçìîæíûõ êîìáèíàöèé îøèáî÷íûõ áèòîâ, ñîîòâåòñòâóþùèõ îäíîé äâîéíîé
îøèáêå â òðèàäå t -1 ëèáî t -2. Åñëè èíâåðòèðîâàíèå áèòîâ â ñîîòâåòñòâèè ñ îä-
íîé èç êîìáèíàöèé ïîçâîëèò àâòîìàòó îáðàáîòàòü áåç ñáîåâ òðèàäû t– t + 4, òî
ýòî è åñòü èñêîìàÿ êîìáèíàöèÿ îøèáî÷íûõ áèòîâ, èíà÷å ñëåäóåò ñäåëàòü âûâîä,
÷òî ñáîé â òðèàäå t âûçâàí åäèíè÷íîé èëè òðîéíîé îøèáêîé íåïîñðåäñòâåííî
â ýòîé òðèàäå.
×òîáû ïîêàçàòü äîñòîâåðíîñòü ïðèâåäåííîãî ìåòîäà, ðàññìîòðèì ðàáîòó àâ-
òîìàòà ïðè âñåõ âîçìîæíûõ ëîæíûõ ïðåäïîëîæåíèÿõ î òîì, êàêèå äâà áèòà
îøèáî÷íû.
· Åñëè ïðåäïîëàãàåì íàëè÷èå äâîéíîé îøèáêè â òîé òðèàäå, ãäå îíà äåé-
ñòâèòåëüíî èìååò ìåñòî, íî â äðóãèõ áèòàõ, òî ïîñëå èíâåðòèðîâàíèÿ áèòîâ, êî-
òîðûå ïîñ÷èòàëè îøèáî÷íûìè, äâîéíàÿ îøèáêà â ýòîé òðèàäå îñòàíåòñÿ, à â ñëå-
äóþùèõ äâóõ òðèàäàõ ñîãëàñíî ñâîéñòâó 4 ïðîèçîéäåò ñáîé.
50 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 2
· Åñëè ïðåäïîëàãàåì íàëè÷èå äâîéíîé îøèáêè â òðèàäå t -1, à íà ñàìîì
äåëå îíà èìååò ìåñòî â òðèàäå t -2 ëèáî íàîáîðîò, òî ïîñëå èíâåðòèðîâàíèÿ áèòîâ
îáå òðèàäû, t -1 è t -2, áóäóò ñîäåðæàòü îøèáêè, à çíà÷èò, ñîãëàñíî ñâîéñòâó 7 ñî-
ñòîÿíèå àâòîìàòà â òðèàäå t áóäåò îòëè÷àòüñÿ îò òîãî, â êîòîðîì áû îí ïðåáûâàë,
åñëè áû îøèáîê íå áûëî. Èç ýòîãî, â ñîîòâåòñòâèè ñî ñâîéñòâîì 6, ñëåäóåò, ÷òî
ïðè îáðàáîòêå òðèàä t– t +3 ïðîèçîéäåò ñáîé.
· Åñëè ïðåäïîëàãàåì íàëè÷èå äâîéíîé îøèáêè â òðèàäå t -1, à íà ñàìîì
äåëå ñáîé âûçâàí åäèíè÷íîé èëè òðîéíîé îøèáêîé â òðèàäå t, òî ïîñëå èíâåðòè-
ðîâàíèÿ áèòîâ îøèáêè áóäåò ñîäåðæàòü êàê òðèàäà t -1, òàê è òðèàäà t. Ïîýòîìó
ñîãëàñíî ñâîéñòâó 7 ñîñòîÿíèå àâòîìàòà â òðèàäå t +1 áóäåò îòëè÷àòüñÿ îò òîãî,
â êîòîðîì áû îí ïðåáûâàë, åñëè áû îøèáîê íå áûëî. Èç ýòîãî, â ñîîòâåòñòâèè ñî
ñâîéñòâîì 6, ñëåäóåò, ÷òî ïðè îáðàáîòêå òðèàä t +1– t + 4 ïðîèçîéäåò ñáîé.
· Åñëè ïðåäïîëàãàåì íàëè÷èå äâîéíîé îøèáêè â òðèàäå t -2, à íà ñàìîì
äåëå ñáîé âûçâàí åäèíè÷íîé èëè òðîéíîé îøèáêîé â òðèàäå t, òî ïîñëå èíâåðòè-
ðîâàíèÿ áèòîâ îøèáêè áóäóò ñîäåðæàòü òðèàäû t -2 è t, íî íå òðèàäà t -1. Òîãäà
ñîãëàñíî ñâîéñòâó 8 ñîñòîÿíèå àâòîìàòà â òðèàäå t +1 áóäåò îòëè÷àòüñÿ îò òîãî,
â êîòîðîì áû îí ïðåáûâàë, åñëè áû îøèáîê íå áûëî. Èç ýòîãî, â ñîîòâåòñòâèè ñî
ñâîéñòâîì 6, ñëåäóåò, ÷òî ïðè îáðàáîòêå òðèàä t +1– t + 4 ïðîèçîéäåò ñáîé.
ÇÀÊËÞ×ÅÍÈÅ
Îïèñàííàÿ äâóõóðîâíåâàÿ ñòðóêòóðà êîäèðóþùåãî óñòðîéñòâà ïðåäïîëàãàåò
è äâóõóðîâíåâîå äåêîäèðîâàíèå, âûïîëíÿþùååñÿ ñíà÷àëà ñ ïîìîùüþ âíåøíå-
ãî àâòîìàòà, à çàòåì — âíóòðåííåãî. Äëÿ âíåøíåãî àâòîìàòà äîëæåí áûòü
ïðèìåíåí ïåðåáîðíûé àëãîðèòì ïîèñêà ïîçèöèé îøèáî÷íûõ áèòîâ. Êàê âèäíî
èç èçëîæåííîãî âûøå, òàêîé àëãîðèòì ïîçâîëèò îïðåäåëÿòü ïîçèöèè îøèáî÷-
íûõ áèòîâ â òåõ ñëó÷àÿõ, êîãäà òðèàäà áèòîâ t ñîäåðæèò îäèí èëè òðè îøè-
áî÷íûõ áèòà, à â òðèàäàõ t +1 è t +2 îøèáîê íåò, ëèáî êîãäà òðèàäà áèòîâ t
ñîäåðæèò äâà îøèáî÷íûõ áèòà, à â òðèàäàõ t +1– t + 4 îøèáîê íåò. Ïðè áîëåå
ñëîæíûõ êîìáèíàöèÿõ îøèáî÷íûõ áèòîâ ëîæíûå ïðåäïîëîæåíèÿ îá èõ ïîçè-
öèÿõ áóäóò îòñåèâàòüñÿ ñ ïîìîùüþ âíóòðåííåãî àâòîìàòà. Èññëåäîâàíèå ïî-
äîáíîãî ìåòîäà äåêîäèðîâàíèÿ ïðîäîëæàåòñÿ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. A n i s i m o v A . V . Prefix encoding by means of the 2,3-representation of numbers // IEEE Trans. Inform.
Theory. — 2013. — 59, N 4. — P. 2359–2374.
2. À í è ñ è ì î â À .  . , Ç à â à ä ñ ê è é È . À . Ïîìåõîóñòîé÷èâîå ïðåôèêñíîå êîäèðîâàíèå íà îñíîâå
íèæíåãî (2,3)-ïðåäñòàâëåíèÿ ÷èñåë // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2014. — 50, ¹ 2. —
Ñ. 3–14.
3. A n i s i m o v A . V . , Z a v a d s k y i I . O . Forward error correcting codes by means of the two-base
(2,3)-numeration system // IEEE Intern. Black Sea Conf. on Communications and Networking. — Chisinau,
2014. — P. 107–111.
Ïîñòóïèëà 23.04.2014
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 2 51
|