Метод распознавания параметров помехоустойчивых блочных циклических кодов по образующему полиному
Описана суть помехоустойчивого блочного циклического кодирования. Рассмотрен метод распознавания параметров такого кода при отсутствии априорной информации полным их перебором. Определено количество необходимых для этого вычислений. Показано, что использование этого метода в реальных условиях затруд...
Gespeichert in:
| Veröffentlicht in: | Кібернетика та системний аналіз |
|---|---|
| Datum: | 2021 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2021
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/190594 |
| 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: | Метод распознавания параметров помехоустойчивых блочных циклических кодов по образующему полином/ С.Н. Николаев, А.Н. Романов // Кібернетика та системний аналіз. — 2021. — Т. 57, № 1. — С. 168–177. — Бібліогр.: 26 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-190594 |
|---|---|
| record_format |
dspace |
| spelling |
Николаев, С.Н. Романов, А.Н. 2023-06-14T11:40:16Z 2023-06-14T11:40:16Z 2021 Метод распознавания параметров помехоустойчивых блочных циклических кодов по образующему полином/ С.Н. Николаев, А.Н. Романов // Кібернетика та системний аналіз. — 2021. — Т. 57, № 1. — С. 168–177. — Бібліогр.: 26 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/190594 621.391.15 Описана суть помехоустойчивого блочного циклического кодирования. Рассмотрен метод распознавания параметров такого кода при отсутствии априорной информации полным их перебором. Определено количество необходимых для этого вычислений. Показано, что использование этого метода в реальных условиях затруднительно. Исследованы известные образующие полиномы, применение которых наиболее вероятно. Сформировано множество таких полиномов и соответствующих параметров. Предложен метод распознавания параметров помехоустойчивых блочных циклических кодов среди известного множества, что позволяет значительно сократить количество необходимых вычислений. Описано суть завадостійкого блокового циклічного кодування. Розглянуто метод розпізнавання параметрів такого коду повним перебором. за відсутності апріорної інформації Визначено кількість необхідних для цього обчислень. Показано, що застосування такого методу в реальних умовах ускладнене. Досліджено відомі утворювальні поліноми, використання яких є найбільш ймовірним. Сформовано множину таких поліномів і відповідних параметрів. Запропоновано метод розпізнавання параметрів завадостійких блокових циклічних кодів серед відомої множини, що дає змогу значно скоротити кількість необхідних обчислень. The essence of the error-correcting block cyclic coding is described. A method for recognizing parameters of such a code in the absence of a priori information by a complete enumeration of parameters is considered. The amount of necessary calculation is determined. The application of the considered method in real conditions is shown to be difficult. The well-known generator polynomials whose practical use is most probable are investigated. A set of these polynomials and related parameters is generated. A method is proposed for recognizing parameters of error-correcting block cyclic codes among a known set, which can significantly reduce the amount of necessary calculation. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кібернетика та системний аналіз Програмно-технічні комплекси Метод распознавания параметров помехоустойчивых блочных циклических кодов по образующему полиному Метод розпізнавання параметрів завадостійких блокових циклічних кодів за утворювальним поліномом Error-correcting block cyclic code parameter recognition method based on generator polynomial 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 |
2021 |
| language |
Russian |
| container_title |
Кібернетика та системний аналіз |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Метод розпізнавання параметрів завадостійких блокових циклічних кодів за утворювальним поліномом Error-correcting block cyclic code parameter recognition method based on generator polynomial |
| description |
Описана суть помехоустойчивого блочного циклического кодирования. Рассмотрен метод распознавания параметров такого кода при отсутствии априорной информации полным их перебором. Определено количество необходимых для этого вычислений. Показано, что использование этого метода в реальных условиях затруднительно. Исследованы известные образующие полиномы, применение которых наиболее вероятно. Сформировано множество таких полиномов и соответствующих параметров. Предложен метод распознавания параметров помехоустойчивых блочных циклических кодов среди известного множества, что позволяет значительно сократить количество необходимых вычислений.
Описано суть завадостійкого блокового циклічного кодування. Розглянуто метод розпізнавання параметрів такого коду повним перебором. за відсутності апріорної інформації Визначено кількість необхідних для цього обчислень. Показано, що застосування такого методу в реальних умовах ускладнене. Досліджено відомі утворювальні поліноми, використання яких є найбільш ймовірним. Сформовано множину таких поліномів і відповідних параметрів. Запропоновано метод розпізнавання параметрів завадостійких блокових циклічних кодів серед відомої множини, що дає змогу значно скоротити кількість необхідних обчислень.
The essence of the error-correcting block cyclic coding is described. A method for recognizing parameters of such a code in the absence of a priori information by a complete enumeration of parameters is considered. The amount of necessary calculation is determined. The application of the considered method in real conditions is shown to be difficult. The well-known generator polynomials whose practical use is most probable are investigated. A set of these polynomials and related parameters is generated. A method is proposed for recognizing parameters of error-correcting block cyclic codes among a known set, which can significantly reduce the amount of necessary calculation.
|
| issn |
1019-5262 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/190594 |
| citation_txt |
Метод распознавания параметров помехоустойчивых блочных циклических кодов по образующему полином/ С.Н. Николаев, А.Н. Романов // Кібернетика та системний аналіз. — 2021. — Т. 57, № 1. — С. 168–177. — Бібліогр.: 26 назв. — рос. |
| work_keys_str_mv |
AT nikolaevsn metodraspoznavaniâparametrovpomehoustoičivyhbločnyhcikličeskihkodovpoobrazuûŝemupolinomu AT romanovan metodraspoznavaniâparametrovpomehoustoičivyhbločnyhcikličeskihkodovpoobrazuûŝemupolinomu AT nikolaevsn metodrozpíznavannâparametrívzavadostíikihblokovihciklíčnihkodívzautvorûvalʹnimpolínomom AT romanovan metodrozpíznavannâparametrívzavadostíikihblokovihciklíčnihkodívzautvorûvalʹnimpolínomom AT nikolaevsn errorcorrectingblockcycliccodeparameterrecognitionmethodbasedongeneratorpolynomial AT romanovan errorcorrectingblockcycliccodeparameterrecognitionmethodbasedongeneratorpolynomial |
| first_indexed |
2025-11-27T03:40:58Z |
| last_indexed |
2025-11-27T03:40:58Z |
| _version_ |
1850794863061106688 |
| fulltext |
ÓÄÊ 621.391.15
Ñ.Í. ÍÈÊÎËÀÅÂ, À.Í. ÐÎÌÀÍÎÂ
ÌÅÒÎÄ ÐÀÑÏÎÇÍÀÂÀÍÈß ÏÀÐÀÌÅÒÐÎÂ
ÏÎÌÅÕÎÓÑÒÎÉ×ÈÂÛÕ ÁËÎ×ÍÛÕ ÖÈÊËÈ×ÅÑÊÈÕ
ÊÎÄÎÂ ÏÎ ÎÁÐÀÇÓÞÙÅÌÓ ÏÎËÈÍÎÌÓ
Àííîòàöèÿ. Îïèñàíà ñóòü ïîìåõîóñòîé÷èâîãî áëî÷íîãî öèêëè÷åñêîãî êî-
äèðîâàíèÿ. Ðàññìîòðåí ìåòîä ðàñïîçíàâàíèÿ ïàðàìåòðîâ òàêîãî êîäà ïîë-
íûì ïåðåáîðîì ïðè îòñóòñòâèè àïðèîðíîé èíôîðìàöèè. Îïðåäåëåíî êîëè-
÷åñòâî íåîáõîäèìûõ äëÿ ýòîãî âû÷èñëåíèé. Ïîêàçàíî, ÷òî èñïîëüçîâàíèå
òàêîãî ìåòîäà â ðåàëüíûõ óñëîâèÿõ çàòðóäíèòåëüíî. Èññëåäîâàíû èçâåñò-
íûå îáðàçóþùèå ïîëèíîìû, ïðèìåíåíèå êîòîðûõ íàèáîëåå âåðîÿòíî.
Ñôîðìèðîâàíî ìíîæåñòâî òàêèõ ïîëèíîìîâ è ñîîòâåòñòâóþùèõ ïàðàìåò-
ðîâ. Ïðåäëîæåí ìåòîä ðàñïîçíàâàíèÿ ïàðàìåòðîâ ïîìåõîóñòîé÷èâûõ áëî÷-
íûõ öèêëè÷åñêèõ êîäîâ ñðåäè èçâåñòíîãî ìíîæåñòâà, ÷òî ïîçâîëÿåò çíà÷è-
òåëüíî ñîêðàòèòü êîëè÷åñòâî íåîáõîäèìûõ âû÷èñëåíèé.
Êëþ÷åâûå ñëîâà: áèòîâûé ïîòîê, ïîìåõîóñòîé÷èâûé áëî÷íûé öèêëè÷åñ-
êèé êîä, îáðàçóþùèé ïîëèíîì êîäà, îñòàòîê îò ïîëèíîìèàëüíîãî äåëåíèÿ,
ìàòðèöà.
ÂÂÅÄÅÍÈÅ
Äëÿ äåêîäèðîâàíèÿ äàííûõ ïî ñóùåñòâóþùèì ìåòîäàì, àëãîðèòìàì è ñòàí-
äàðòàì â ïðîãðàììíî-òåõíè÷åñêèõ êîìïëåêñàõ äîëæíû áûòü èçâåñòíû âèä
è ïàðàìåòðû êîäà [1].  ñëó÷àå îòñóòñòâèÿ òàêîé èíôîðìàöèè íåîáõîäèìî
ïðåäâàðèòåëüíî ïðîâåñòè àíàëèç áèòîâîãî ïîòîêà äëÿ èõ îïðåäåëåíèÿ [2], ÷òî
ÿâëÿåòñÿ ñëîæíîé íàó÷íî-òåõíè÷åñêîé çàäà÷åé. Òàêèå çàäà÷è, êàê ïðàâèëî, ðå-
øàþòñÿ ïðè îöåíèâàíèè õàðàêòåðèñòèê êàíàëîâ ñâÿçè, ðàäèîìîíèòîðèíãå, àíà-
ëèçå ïðîèçâîäèòåëüíîñòè ñåòåé ïåðåäà÷è äàííûõ. Îäíàêî ðàçâèòèþ ìåòîäè÷åñ-
êîãî àïïàðàòà àíàëèçà áèòîâûõ ïîòîêîâ, ïðîâîäèìîãî ïåðåä äåêîäèðîâàíèåì,
óäåëÿåòñÿ íåäîñòàòî÷íî âíèìàíèÿ [3]. Ïîä áèòîâûì ïîòîêîì (bitstream) áóäåì
ïîíèìàòü ïîòîê áèòîâ (öèôðîâîé ïîòîê) â âèäå íóëåé è åäèíèö, ïîëó÷åííûé
èç êàíàëà ñâÿçè ïîñëå äåìîäóëÿòîðà, ñîäåðæàùèé â çàêîäèðîâàííîì âèäå ñî-
îáùåíèå è îáëàäàþùèé íåêîòîðîé èçáûòî÷íîñòüþ.
Âñëåäñòâèå ýôôåêòèâíîñòè [4] íàèáîëåå ðàñïðîñòðàíåííûìè âèäàìè ïîìåõîóñ-
òîé÷èâûõ êîäîâ â ñîâðåìåííûõ ñèñòåìàõ ñâÿçè è ïåðåäà÷è äàííûõ ÿâëÿþòñÿ áëî÷íûå
è ñâåðòî÷íûå êîäû, à òàêæå èõ êîìáèíàöèè [2, 5, 6]. Ñðåäè ïîìåõîóñòîé÷èâûõ áëî÷-
íûõ êîäîâ, èñïîëüçóåìûõ íà ïðàêòèêå, ìíîãèå êîäû öèêëè÷åñêèå [7–10]. Èñêëþ÷åíèå
ñîñòàâëÿþò øèðîêî ïðèìåíÿåìûå áëàãîäàðÿ êîððåêòèðóþùèì âîçìîæíîñòÿì áëî÷-
íûå LDPC-êîäû [11], êîòîðûå â îáùåì ñëó÷àå íå ÿâëÿþòñÿ öèêëè÷åñêèìè.
Àíàëèç ðåçóëüòàòîâ èññëåäîâàíèé ïîêàçàë ðàçâèòîñòü ìåòîäè÷åñêîãî àïïà-
ðàòà àíàëèçà ñåòåâûõ ïðîòîêîëîâ ïåðåäà÷è äàííûõ è èõ öåïî÷åê íà âûñøèõ
óðîâíÿõ ìîäåëè OSI, îïåðèðóþùèõ êàäðàìè [12, 13], à òàêæå îïðåäåëåíèÿ âèäà
ìîäóëÿöèè íà ïåðâîì óðîâíå ýòîé ìîäåëè [14]. Îäíàêî ìåòîäè÷åñêèé àïïàðàò
îñòàëüíûõ àñïåêòîâ àíàëèçà áèòîâûõ ïîòîêîâ íà ïåðâîì óðîâíå èåðàðõèè ìîäå-
ëè OSI ðàçðàáîòàí íåäîñòàòî÷íî: ñóùåñòâóþò ðàçðîçíåííûå ïîäõîäû ê îïðåäåëå-
íèþ âèäà êîäà [15], àíàëèçó ïîìåõîóñòîé÷èâûõ ñâåðòî÷íûõ [15] è áëî÷íûõ
[2, 15, 16] êîäîâ. Ê èçâåñòíûì ìåòîäàì àíàëèçà áèòîâûõ ïîòîêîâ äëÿ îïðåäåëå-
íèÿ ïàðàìåòðîâ ïîìåõîóñòîé÷èâûõ áëî÷íûõ öèêëè÷åñêèõ êîäîâ îòíîñèòñÿ ìå-
òîä, èñïîëüçóþùèé êîððåëÿöèîííûå ôóíêöèè [2, 17, 18]. Åãî íåäîñòàòêîì ÿâëÿ-
åòñÿ íåîáõîäèìîñòü ïðîâåäåíèÿ çíà÷èòåëüíîãî êîëè÷åñòâà âû÷èñëåíèé äëÿ ðàñ-
ïîçíàâàíèÿ áëî÷íûõ êîäîâ áîëüøîé äëèíû [15].
168 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1
© Ñ.Í. Íèêîëàåâ, À.Í. Ðîìàíîâ, 2021
Òàêèì îáðàçîì, èññëåäîâàíèå ìåòîäîâ îïðåäåëåíèÿ ïàðàìåòðîâ ïîìåõîóñ-
òîé÷èâûõ áëî÷íûõ öèêëè÷åñêèõ êîäîâ, ñ ïîìîùüþ êîòîðûõ ïîèñê âûïîëíÿåòñÿ
çà áîëåå êîðîòêîå âðåìÿ, — àêòóàëüíàÿ çàäà÷à.  äàííîé ñòàòüå ïðåäëîæåí ìåòîä
ðàñïîçíàâàíèÿ ïàðàìåòðîâ ïîìåõîóñòîé÷èâûõ áëî÷íûõ öèêëè÷åñêèõ êîäîâ
â ìàñøòàáå ðåàëüíîãî âðåìåíè.
ÏÎÌÅÕÎÓÑÒÎÉ×ÈÂÎÅ ÁËÎ×ÍÎÅ ÖÈÊËÈ×ÅÑÊÎÅ ÊÎÄÈÐÎÂÀÍÈÅ
Îñíîâíûìè ïàðàìåòðàìè ïîìåõîóñòîé÷èâîãî áëî÷íîãî öèêëè÷åñêîãî êîäà, îä-
íîçíà÷íî îïðåäåëÿþùèìè åãî âîçìîæíîñòè ïî îáíàðóæåíèþ è èñïðàâëåíèþ
îøèáîê, ÿâëÿþòñÿ äëèíà êîäà n, êîëè÷åñòâî èíôîðìàöèîííûõ áèò k , êîëè÷åñ-
òâî ïðîâåðî÷íûõ áèò n k� , ìèíèìàëüíîå êîäîâîå ðàññòîÿíèå dmin è îáðàçóþ-
ùèé ïîëèíîì g z( ) [7–10, 16]. Ñòåïåíü îáðàçóþùåãî ïîëèíîìà ðàâíà êîëè÷åñ-
òâó ïðîâåðî÷íûõ áèòîâ.
Êàæäîå êîäîâîå ñëîâî X äëèíîé n áèò ïðåäñòàâëÿåò ñîáîé êîíêàòåíàöèþ
äâóõ ìàòðèö-âåêòîðîâ: K äëèíîé k áèò è G äëèíîé n k� áèò (ðèñ. 1),
X K G� { }, , (1)
ãäå { } — çíàê êîíêàòåíàöèè.
Èíôîðìàöèîííàÿ ÷àñòü êîäîâîãî ñëîâà ïðåäñòàâëåíà â âèäå ìàòðèöû-âåêòî-
ðà K � �( , , , )x x xk0 1 1� è ñîäåðæèò áèòû äàííûõ xi �( , )0 1 , êàê ïðàâèëî, â âèäå
êîäà ASCII (8 áèò), Unicode (16 áèò), ðåæå — â âèäå äðóãèõ êîäîâ.
Ñóòü êîäèðîâàíèÿ çàêëþ÷àåòñÿ â ôîðìèðîâàíèè ïðîâåðî÷íîé ÷àñòè êîäîâî-
ãî ñëîâà ïðè íàëè÷èè èíôîðìàöèîííîé ÷àñòè è ïðàâèëà âûïîëíåíèÿ ïðîâåðîê,
çàäàííîãî â îáðàçóþùåì ïîëèíîìå.
Ïðîâåðî÷íàÿ ÷àñòü êîäîâîãî ñëîâà G � � �( , , , )x x xk k n1 1� ñîäåðæèò ïðîâå-
ðî÷íûå áèòû xi �( , )0 1 è ïðåäñòàâëåíà â âèäå îñòàòêà îò äåëåíèÿ ñäâèíóòîé íà
n k� áèò âëåâî èíôîðìàöèîííîé ÷àñòè êîäîâîãî ñëîâà äëèíîé k, äîïîëíåííîé
ñïðàâà íóëÿìè, íà îáðàçóþùèé ïîëèíîì g z a z a zn k
n k
n k
n k( ) � � ��
�
� �
� �
1
1
� � � �� �
� �a z a z a zn k
n k
2
2
1
1
0
0
� . Ïîëèíîì g z( ) èìååò ìíîæèòåëè ïðè àðãóìåí-
òå: a0 1� ; ai �( , )0 1 , i n k� � �( , , )1 1� ; an k� �1. Âûáîð êîíêðåòíîãî çíà÷åíèÿ
ìíîæèòåëÿ ai ïðè àðãóìåíòå z i è ñîñòàâëÿåò ñóòü ïîñòðîåíèÿ îáðàçóþùåãî ïî-
ëèíîìà, îò êîòîðîãî çàâèñèò êà÷åñòâî ïîìåõîóñòîé÷èâîãî êîäà [7–10]. Íàïðè-
ìåð, ñðåäè îáðàçóþùèõ ïîëèíîìîâ 16-é ñòåïåíè äëÿ äâîè÷íûõ êîäîâ íàèáîëåå
ïðåäïî÷òèòåëüíû ñëåäóþùèå [16]:
g z z z z( ) � � � � � � �16 15 2
2 101 11000000000000101 98309 1800516 ;
g z z z z( ) � � � � � � �16 12 5
2 101 10001000000100001 69665 1102116 ;
g z z z z z( ) � � � � � � � �16 12 3
2 101 10001000000001011 69643 1100 16B ;
g z z z z z z z z z z( ) � � � � � � � � � � �16 13 12 11 10 8 6 5 2 1 100111101011001012 �
� �81253 13 6510 16D ;
g z z z z z z z z z z z( ) � � � � � � � � � � � �16 14 13 11 10 9 8 6 5 1
� � �10110111101100011 94051 16 632 10 16F .
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1 169
0 1 k � 1 k n � 1
K = (x0 , x1, … , xk�1) G = (xk , xk�1, … , xn�1)
……
Ðèñ. 1. Êîäîâîå ñëîâî X � �( , , , )x x xn0 1 1� äëèíîé n áèò
Ïðè ôèêñèðîâàííûõ ïàðàìåòðàõ n è k îñíîâíûì ïàðàìåòðîì êîäà, îïðåäåëÿ-
þùèì ïðàâèëî ôîðìèðîâàíèÿ ïðîâåðî÷íûõ áèòîâ, ÿâëÿåòñÿ îáðàçóþùèé ïîëè-
íîì g z( ). Åñëè èçâåñòåí îáðàçóþùèé ïîëèíîì êîäà, èçâåñòåí è êîä [7–10]. Ïîý-
òîìó äëÿ îòûñêàíèÿ ïàðàìåòðîâ òàêîãî ïîìåõîóñòîé÷èâîãî êîäà äîñòàòî÷íî íàé-
òè åãî îáðàçóþùèé ïîëèíîì. Äëÿ ýòîãî ìîæíî ïðèìåíèòü ìåòîä, êîòîðûé
îñíîâàí íà ïîëíîì ïåðåáîðå âñåõ âîçìîæíûõ âàðèàíòîâ.
ÐÀÑÏÎÇÍÀÂÀÍÈÅ ÏÀÐÀÌÅÒÐÎÂ ÊÎÄÀ ÏÎËÍÛÌ ÏÅÐÅÁÎÐÎÌ
Ñóòü ìåòîäà ðàñïîçíàâàíèÿ ïàðàìåòðîâ ïîìåõîóñòîé÷èâîãî áëî÷íîãî öèêëè-
÷åñêîãî êîäà ïîëíûì ïåðåáîðîì çàêëþ÷àåòñÿ â ðàçáèåíèè âñåãî àíàëèçèðóåìî-
ãî áèòîâîãî ïîòîêà Y äëèíîé M áèò íà m j ãèïîòåòè÷åñêèõ êîäîâûõ ñëîâ äëè-
íîé n j áèò êàæäîå ñ k j èíôîðìàöèîííûìè áèòàìè (ðèñ. 2) òàê, ÷òî
M m n lj j j� � , ãäå l j — îñòàòîê, â îáùåì ñëó÷àå 0 � �l nj j . Áèòîâûé ïîòîê
ðàçáèâàåòñÿ âñåãî íà J âàðèàíòîâ. Êàæäûé j-é âàðèàíò ðàçáèåíèÿ, j J� �[ ]0 1� ,
ñîîòâåòñòâóåò êîíêðåòíîìó çíà÷åíèþ äëèíû ãèïîòåòè÷åñêîãî êîäîâîãî ñëîâà n j
(îò nmin äî nmax), êîëè÷åñòâó èíôîðìàöèîííûõ áèò k j (îò kmin äî kmax),
êîëè÷åñòâó ãèïîòåòè÷åñêèõ êîäîâûõ ñëîâ m
M
n
j
j
�
�
�
�
è ñòåïåíè îáðàçóþùåãî ïî-
ëèíîìà n kj j� . Äëÿ êàæäîé ãèïîòåòè÷åñêîé äëèíû êîäîâîãî ñëîâà n j îïðåäåëÿ-
åòñÿ ìèíèìàëüíî è ìàêñèìàëüíî âîçìîæíàÿ ñòåïåíü îáðàçóþùåãî ïîëèíîìà
g n kjmin max� � è g n kjmax min� � â çàâèñèìîñòè îò ìàêñèìàëüíî kmax è ìèíè-
ìàëüíî kmin âîçìîæíîãî êîëè÷åñòâà èíôîðìàöèîííûõ áèòîâ.
Âåñü íàáîð êîäîâûõ ñëîâ, ñîñòîÿùèé èç M áèò, ïðåäñòàâëÿåòñÿ â âèäå êîí-
êàòåíàöèè êîäîâûõ ñëîâ X i (1) äëèíîé n j áèò êàæäîå (îñòàòîê îòáðàñûâàåòñÿ):
Y X X X� �{ , , , }0 1 1� m j
. (2)
 îáùåì ñëó÷àå ìàòðèöû-âåêòîðû X i èìåþò îäèíàêîâóþ äëèíó n j è íå ðàâ-
íû ìåæäó ñîáîé, òàê êàê íàïîëíåíû ðàçíûìè âûáîðêàìè áèòîâîãî ïîòîêà
xi �( , )0 1 .
Êàæäîå ãèïîòåòè÷åñêîå êîäîâîå ñëîâî ïîëèíîìèàëüíî äåëèòñÿ íà çíà÷åíèå
ãèïîòåòè÷åñêîãî ïîëèíîìà g z( ), ïîëó÷àåìîå ïîñëåäîâàòåëüíûì èíêðåìåíòèðî-
âàíèåì íà åäèíèöó ìëàäøåãî ðàçðÿäà:
X i
g z
q z
r z
g z( )
( )
( )
( )
� � , (3)
ãäå q z( ) — ÷àñòíîå îò äåëåíèÿ; r z( ) — îñòàòîê îò äåëåíèÿ. Äåëåíèå (3) âû-
ïîëíÿåòñÿ â ïðåäåëàõ êîíêðåòíîãî ðàçáèåíèÿ j â ìàòðèöå-âåêòîðå Y (2) äëÿ
òåêóùèõ çíà÷åíèé n j , k j äëÿ êàæäîãî X i .
Åñëè r z( ) � 0, òî òàêîå ãèïîòåòè÷åñêîå êîäîâîå ñëîâî ñòàíîâèòñÿ âîçìîæíûì
êîäîâûì ñëîâîì è â ñòðîêó ìàòðèöû çàíîñÿòñÿ åãî çíà÷åíèÿ m j , n j , k j , à òàêæå òå-
êóùåå çíà÷åíèå îáðàçóþùåãî ïîëèíîìà g z( ). Åñëè äëÿ âûáðàííûõ çíà÷åíèé n j è k j
ïðîâåðåíû âñå âîçìîæíûå îáðàçóþùèå ïîëèíîìû è èñòèííûé ïîëèíîì íå íàéäåí,
170 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1
0 k j � 1 (mj � 1)n j…(mj � 1)nj + kj � 1… … n j � 1 n j … n j � k j � 1 2n j � 1… … … mj n j � 1
X0 X1
Xm � 1
j
Ðèñ. 2. Ðàçáèåíèå áèòîâîãî ïîòîêà äëèíîé M áèò íà m j ãèïîòåòè÷åñêèõ êîäîâûõ ñëîâ Xi, êàæäîå
ïî n j áèò, l j � 0
òî íà÷àëî ïîèñêà â áèòîâîì ïîòîêå äëèíîé M áèò ñäâèãàåòñÿ âïðàâî íà 1 áèò. Êîëè-
÷åñòâî áèòîâûõ ñäâèãîâ b ìîæåò ïðèíèìàòü çíà÷åíèÿ îò 0 äî n j �1. Äëÿ êàæäîãî
ïîëèíîìèàëüíîãî äåëåíèÿ, åñëè r z( ) � 0, ôîðìèðóåòñÿ ñòðîêà ìàòðèöû
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1 171
Íà÷àëî
Ôîðìèðîâàíèå
n j , k j , m j
Öèêë
ðàçáèåíèé j
îò 0 äî J � 1
Êîíåö
j :� j � 1,
öèêë j
Öèêë
ñäâèãîâ b
îò 0 äî n j � 1
Öèêë êîäîâûõ
ñëîâ �
îò 0 äî m j � 1
�: � � � 1,
öèêë �
b:� b � 1,
öèêë b
s :� 0, p:� 0,
e :� 1
Öèêë
ïîèñêà u
îò e äî s
u:� u � 1,
öèêë u
e :� s
Âûâîä
n , k , g ( z)
Öèêë
ïîèñêà f
îò 0 äî s � 1
Íåò Äà
f :� f � 1,
öèêë f
Ñ÷èòûâàíèå
ñòðîêè Ô
Äà Íåò
Öèêë
ïîëèíîìîâ i
îò 0 äî � � 1
Ôîðìèðîâàíèå
ñòðîêè Ô
i :� i � 1,
öèêë i
Ââîä nmin, nmax ,
kmin , kmax
ri (z) � 0
p:� p � 1,
s :� s � 1
Íåò Äà
�u5 � 1
h :� 1
Âûâîä
h âàðèàíòîâ
n, k, g( z)
h :� h + 1
�f 5
0
h:� 0
g i ( z)
m j
x
Ðèñ. 3. Àëãîðèòì ðàáîòû ìåòîäà ðàñïîçíàâàíèÿ ïàðàìåòðîâ ïîìåõîóñòîé÷èâûõ áëî÷íûõ öèêëè-
÷åñêèõ êîäîâ ïî îáðàçóþùåìó ïîëèíîìó ïîëíûì ïåðåáîðîì
Ô �
�
�
�
�
�
�
�
�
�
�
� � � � �
� � � � �
11 12 13 14 15
1 2 3 4 5
� � � � �
s s s s s
, (4)
ãäå � s jn1 � — äëèíà êîäîâîãî ñëîâà; � s jk2 � — êîëè÷åñòâî èíôîðìàöèîí-
íûõ áèòîâ; � s g z3 � ( ) — îáðàçóþùèé ïîëèíîì êîäà â âèäå öåëîãî ÷èñëà;
� s b4 � — áèòîâûé ñäâèã â ïðåäåëàõ ìàòðèöû-âåêòîðà Y, 0 1� � �b n j ;
� s jp m5 � / — íîðìèðîâàííîå êîëè÷åñòâî ïîäåëèâøèõñÿ íàöåëî êîäîâûõ
ñëîâ â ïðåäåëàõ ìàòðèöû-âåêòîðà Y, 0 1� �p m j/ ; s — îáùåå êîëè÷åñòâî âîç-
ìîæíûõ âàðèàíòîâ ïàðàìåòðîâ êîäà â ïðåäåëàõ âñåãî áèòîâîãî ïîòîêà èç
M áèò, ðàâíîå êîëè÷åñòâó ñòðîê ìàòðèöû Ô .
 ðåçóëüòàòå îáðàáîòêè âñåãî áèòîâîãî ïîòîêà èç M áèò çàïîëíÿåòñÿ s ñòðîê
ìàòðèöû Ô, ãäå òîëüêî îäíà ñòðîêà ñîäåðæèò ïðàâèëüíûå ïàðàìåòðû êîäà (ÿâëÿ-
åòñÿ èñòèííîé). Ïî îêîí÷àíèè âñåõ èòåðàöèé ïîëèíîìèàëüíîãî äåëåíèÿ C íàé-
äåííûé ìàêñèìóì ñðåäè ýëåìåíòîâ ïÿòîãî ñòîëáöà ìàòðèöû Ô ïîçâîëÿåò îêîí÷à-
òåëüíî óñòàíîâèòü èñòèííûå ïàðàìåòðû áëî÷íîãî öèêëè÷åñêîãî êîäà, êîòîðûì
çàêîäèðîâàí áèòîâûé ïîòîê èç M áèò. Âîçìîæíû äâà ñëó÷àÿ: � s5 1� è � s5 1� .
Äëÿ ïåðâîãî ñëó÷àÿ ïðèíèìàåòñÿ ãèïîòåçà î ñîîòâåòñòâèè îáðàçóþùåãî ïîëèíî-
ìà g z( ) è ïàðàìåòðîâ n j , k j ïîìåõîóñòîé÷èâîãî áëî÷íîãî öèêëè÷åñêîãî êîäà, êî-
òîðûå ñîäåðæàòñÿ â s-é ñòðîêå ìàòðèöû Ô, èñòèííîìó ïîëèíîìó è ïîèñê ïðåêðà-
ùàåòñÿ. Äëÿ âòîðîãî ñëó÷àÿ (� s5 1� ), õàðàêòåðíîãî äëÿ ðåàëüíûõ áèòîâûõ ïîòî-
êîâ, âûïîëíÿåòñÿ ïîèñê s-é ñòðîêè ìàòðèöû Ô, äëÿ êîòîðîé � s5 ìàêñèìàëüíî
ïðèáëèæåíî ê åäèíèöå (â îáùåì ñëó÷àå äëÿ áèòîâîãî ïîòîêà èç M áèò âîçìîæíî
h âàðèàíòîâ ïàðàìåòðîâ êîäà, 0 � �h s).
Ðàññìîòðåííûé ìåòîä íàçîâåì ìåòîäîì ðàñïîçíàâàíèÿ ïàðàìåòðîâ áëî÷íûõ
öèêëè÷åñêèõ ïîìåõîóñòîé÷èâûõ êîäîâ ïî îáðàçóþùåìó ïîëèíîìó ïîëíûì ïåðå-
áîðîì. Àëãîðèòì [19, 20], îïèñûâàþùèé ðàáîòó ìåòîäà, ïðåäñòàâëåí íà ðèñ. 3.
ÎÖÅÍÊÀ ÝÔÔÅÊÒÈÂÍÎÑÒÈ ÐÀÑÏÎÇÍÀÂÀÍÈß
ÏÀÐÀÌÅÒÐÎÂ ÊÎÄÀ ÏÎËÍÛÌ ÏÅÐÅÁÎÐÎÌ
Î÷åâèäíûìè íåäîñòàòêàìè òàêîãî ìåòîäà ÿâëÿåòñÿ íåîáõîäèìîñòü ïðîâåäåíèÿ
áîëüøîãî êîëè÷åñòâà âû÷èñëåíèé è ñîîòâåòñòâåííî íèçêàÿ ñêîðîñòü ðàñïîçíàâà-
íèÿ. Ïðîàíàëèçèðîâàâ àëãîðèòì (ñì. ðèñ. 3), ïîëó÷èì ñëåäóþùèå ôîðìóëû äëÿ
îöåíêè ýôôåêòèâíîñòè îïèñàííîãî ìåòîäà. Îáùåå êîëè÷åñòâî èòåðàöèé C àëãî-
ðèòìà áåç ó÷åòà âîçìîæíîãî äîñðî÷íîãî îòûñêàíèÿ èñòèííîãî îáðàçóþùåãî
ïîëèíîìà ìîæíî ïîëó÷èòü, âûïîëíèâ öèêëû ðàçáèåíèé j, ñäâèãîâ b, êîäîâûõ
ñëîâ � è ïîëèíîìîâ i (ñì. ðèñ. 3):
C
n
nm
n n
n
n k
k k
k
�
��
�
�
�
�
�
�
�
�
�
�
�
� �
�
� �
min
max
min
max4
2
2 1 , (5)
ãäå nmin �10 — ìèíèìàëüíàÿ äëèíà êîäîâîãî ñëîâà; nmax = 32716 — ìàêñè-
ìàëüíàÿ äëèíà êîäîâîãî ñëîâà, îãðàíè÷åííàÿ âû÷èñëèòåëüíûìè âîçìîæíîñòÿ-
ìè äëÿ ÷èñåë ñ ïëàâàþùåé òî÷êîé (1,1 �104932); m — êîëè÷åñòâî ãèïîòåòè÷åñ-
êèõ êîäîâûõ ñëîâ â ïðåäåëàõ îäíîãî ðàçáèåíèÿ;
k
n n
n n
min
, , ,
, , ;
�
� �
� �
�
�
�
0 5 1 0
0 5 1 1 0
k
n n
n n
n n
max
, [ , ],
, , [ , ],
, , [ ,
�
� �
�
�
3 10 29
0 9 30 99
0 96 100 999],
, , [ , ].0 99 1000 32716n n �
�
�
�
�
�
�
�
172 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1
Êîëè÷åñòâî ðàçáèåíèé J ïðè ïîñòðîåíèè âîçìîæíûõ âàðèàíòîâ ìàòðèöû-âåê-
òîðà Y ìîæíî âû÷èñëèòü ïî ýìïèðè÷åñêîé ôîðìóëå
J
n
n n
n
�
��
�
�
�
�
4
2
min
max
. (6)
Ñëåäóåò çàìåòèòü, ÷òî ïðè ïåðåõîäå îò îäíîé èòåðàöèè àëãîðèòìà ê äðóãîé
ìíîãèå ïîëèíîìû ïîâòîðÿþòñÿ, òàê êàê èõ ñòðóêòóðà ïðè ïîëíîì ïåðåáîðå îïðå-
äåëÿåòñÿ ëèøü ñòåïåíüþ 2
n kj j�
(÷èñëîì ïðîâåðî÷íûõ áèòîâ). Ïîýòîìó îáùåå êî-
ëè÷åñòâî îáðàçóþùèõ ïîëèíîìîâ g z( ), èñïîëüçóåìûõ íà âñåõ èòåðàöèÿõ C, ñîîò-
âåòñòâóåò ÷èñëó ïðîâåðî÷íûõ áèòîâ äëÿ êàæäîãî ðàçáèåíèÿ j è åãî ìîæíî
çàïèñàòü â òàêîì âèäå:
� � � � � �� � �
�
�2 2 2 23 1 4 1 0 5 1
3
0 5
�
,
,
max
max
n i
i
n
. (7)
Ãðàôèêè çàâèñèìîñòåé êîëè÷åñòâà ðàçáèåíèé J , èòåðàöèé C è îáðàçóþùèõ
ïîëèíîìîâ � îò äëèíû êîäîâîãî ñëîâà äëÿ nmin �10 è nmax � 300, ðàññ÷èòàííûå
ïî ôîðìóëàì (5)–(7) ïðè m � 3, ïðèâåäåíû íà ðèñ. 4 è ðèñ. 5.
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1 173
Ðèñ. 4. Ãðàôèê çàâèñèìîñòè êîëè÷åñòâà ðàçáèåíèé J îò äëèíû êîäîâîãî ñëîâà n
J �103
n
Ðèñ. 5. Ãðàôèêè çàâèñèìîñòè êîëè÷åñòâà èòåðàöèé C è êîëè÷åñòâà îáðàçóþùèõ ïîëèíîìîâ � îò
äëèíû êîäîâîãî ñëîâà n
n
C , �
C
�
Ðåçóëüòàòû îöåíêè êîëè÷åñòâà ðàçáèåíèé J, èòåðàöèé C è ïîëèíîìîâ � ïî
ôîðìóëàì (5)–(7) ñâèäåòåëüñòâóþò, ÷òî îáà ïàðàìåòðà ýêñïîíåíöèàëüíî âîçðàñòàþò
ñ ðîñòîì äëèíû êîäîâîãî ñëîâà. Íàïðèìåð, äëÿ n �100, m � 3 êîëè÷åñòâî ðàçáèåíèé
J � 2298, êîëè÷åñòâî èòåðàöèé àëãîðèòìà (ôàêòè÷åñêè êîëè÷åñòâî ïîëèíîìèàëüíûõ
äåëåíèé) C � 9,89 �1017 è êîëè÷åñòâî îáðàçóþùèõ ïîëèíîìîâ � � 1,13 �1015 .  ðå-
àëüíûõ óñëîâèÿõ êîëè÷åñòâî êîäîâûõ ñëîâ m áîëüøå òðåõ, ÷òî ïðèâîäèò ê áîëüøå-
ìó óâåëè÷åíèþ êîëè÷åñòâà èòåðàöèé C . Äëÿ èçâåñòíîãî êîäà Ðèäà–Ñîëîìîíà ïðè
n � 255 [21] èìååì J �15744, C � 5,16 �1041, � � 1,7 �1038 . Î÷åâèäíî, ÷òî ïðèìåíå-
íèå ðàññìîòðåííîãî ìåòîäà â ðåàëüíûõ óñëîâèÿõ çàòðóäíèòåëüíî.
ÔÎÐÌÈÐÎÂÀÍÈÅ ÌÍÎÆÅÑÒÂÀ ÕÎÐÎØÈÕ ÎÁÐÀÇÓÞÙÈÕ ÏÎËÈÍÎÌÎÂ
Äëÿ ïðèâåäåííîãî ïðèìåðà ñî ñòåïåíüþ îáðàçóþùåãî ïîëèíîìà n k� �16 òåî-
ðåòè÷åñêè âîçìîæíî èñïîëüçîâàíèå 2 3276815 � çíà÷åíèé îáðàçóþùèõ ïîëèíî-
ìîâ (âñå íå÷åòíûå çíà÷åíèÿ îò 100000000000000012 äî 111111111111111112
âêëþ÷èòåëüíî). Î÷åâèäíî, ÷òî íå âñå ýòè çíà÷åíèÿ ðåàëüíî ïðèìåíÿþòñÿ, òàê
êàê â ñèñòåìàõ ñâÿçè è ïåðåäà÷è äàííûõ â êà÷åñòâå îáðàçóþùèõ ïîëèíîìîâ
ïîìåõîóñòîé÷èâûõ áëî÷íûõ öèêëè÷åñêèõ êîäîâ èñïîëüçóþòñÿ ëèøü èçâåñòíûå
õîðîøèå îáðàçóþùèå ïîëèíîìû, ïîçâîëÿþùèå ïîëó÷èòü ïîìåõîóñòîé÷èâûå
êîäû ñ íåîáõîäèìûìè ñâîéñòâàìè. Ïîèñê òîëüêî ñðåäè ýòèõ ïîëèíîìîâ ìî-
æåò ïîçâîëèòü çíà÷èòåëüíî ñîêðàòèòü êîëè÷åñòâî èòåðàöèé àëãîðèòìà, ïðèâå-
äåííîãî íà ðèñ. 3 [16, 19, 20].
Áûëè ïðîâåäåíû èññëåäîâàíèÿ èñïîëüçîâàíèÿ èçâåñòíûõ îáðàçóþùèõ ïîëè-
íîìîâ g z( ) íà ïðàêòèêå â áëî÷íûõ öèêëè÷åñêèõ êîäàõ è îïèñàííûõ â ôóíäàìåí-
òàëüíûõ òðóäàõ ïî òåîðèè êîäèðîâàíèÿ [1, 4, 7–10, 22–26], ïðèìåíåíèå êîòîðûõ
ÿâëÿåòñÿ íàèáîëåå âåðîÿòíûì. Îáðàçóþùèå ïîëèíîìû öåëåñîîáðàçíî èñêàòü äëÿ
ñëåäóþùèõ âèäîâ äâîè÷íûõ áëî÷íûõ öèêëè÷åñêèõ êîäîâ: Áîóçà–×îóäõóðè–Õîê-
âèíãåìà [9, 10, 23], ìàæîðèòàðíûõ M n k( , ) [22], Ãîëåÿ [22, 23], ñ ïîñòîÿííûì âå-
ñîì [24], Ôàéðà [22], Êàñàìè [8, 10], Ðèäà–Ñîëîìîíà [21], íèçêîïëîòíîñòíûõ
LDPC-êîäîâ [11, 26] è ìíîãèõ äðóãèõ [25].
Ôîðìàëüíàÿ ïîñòàíîâêà çàäà÷è èññëåäîâàíèÿ çàêëþ÷àåòñÿ â òîì, ÷òîáû çà
ñ÷åò óìåíüøåíèÿ çíà÷åíèÿ �, îïðåäåëÿåìîãî ïî ôîðìóëå (7), ñíèçèòü êîëè÷åñ-
òâî èòåðàöèé C (5), ÷òî ýêâèâàëåíòíî óìåíüøåíèþ êîëè÷åñòâà ïîëèíîìèàëüíûõ
äåëåíèé (3), è ïîñòðîèòü ìàòðèöó Ô.
Ðåçóëüòàòû ïîèñêà õîðîøèõ îáðàçóþùèõ ïîëèíîìîâ g z( ) äëÿ äëèí êîäîâ îò
nmin �10 äî nmax � 300 ïîçâîëèëè ñôîðìèðîâàòü ìíîæåñòâî � èç 600 òàêèõ ïî-
ëèíîìîâ, ñîîòâåòñòâóþùèõ èì çíà÷åíèé n è k , à òàêæå ïðåäëîæèòü ìåòîä ðàñïîç-
íàâàíèÿ ïàðàìåòðîâ ïîìåõîóñòîé÷èâûõ áëî÷íûõ öèêëè÷åñêèõ êîäîâ ïî
îáðàçóþùåìó ïîëèíîìó ñðåäè èçâåñòíîãî ìíîæåñòâà.
ÐÀÑÏÎÇÍÀÂÀÍÈÅ ÏÀÐÀÌÅÒÐÎÂ ÊÎÄÎÂ ÑÐÅÄÈ ÈÇÂÅÑÒÍÎÃÎ ÌÍÎÆÅÑÒÂÀ
Ñîêðàùåíèå êîëè÷åñòâà èòåðàöèé â óñîâåðøåíñòâîâàííîì ìåòîäå äîñòèãàåòñÿ
ïðè óñëîâèè, ÷òî â (5) âòîðîå ñóììèðîâàíèå âûïîëíÿåòñÿ ëèøü â ñëó÷àå
g z( ) �� . Ïðåäñòàâèì ìíîæåñòâî � â âèäå ìàòðèöû:
� �
�
�
�
�
�
�
�
�
�
�
� � �
� � �
11 12 13
1 2 3
� � �
d d d
, (8)
ãäå d — îáùåå êîëè÷åñòâî âîçìîæíûõ êîäîâ (d � 600); çíà÷åíèÿ � d1, � d 2 , � d 3
àíàëîãè÷íû çíà÷åíèÿì � s1, � s2 , � s3 èç âûðàæåíèÿ (4). Êîëè÷åñòâî ñòðîê d â ìàò-
ðèöå (8) â îáùåì ñëó÷àå ñóùåñòâåííî ìåíüøå, ÷åì êîëè÷åñòâî ñòðîê s â ìàòðè-
174 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1
öå (4). Ìíîæåñòâî � ðàññ÷èòàíî çàðàíåå è ïðè îá-
ðàáîòêå íå èçìåíÿåòñÿ, òîãäà êàê ìàòðèöà Ô âû÷èñ-
ëÿåòñÿ ñîãëàñíî (4).
 ïðîöåññå ïîñòðî÷íîãî çàïîëíåíèÿ ìàòðèöû Ô
äëÿ êàæäîãî çíà÷åíèÿ 2 1n k� � � � �d d1 2� èç ôîð-
ìóëû (5) è ìàòðèöû (8) îñóùåñòâëÿåòñÿ ïîäñòàíîâêà
çíà÷åíèÿ � d 3 â êà÷åñòâå äåëèòåëÿ â ôîðìóëó ïîëè-
íîìèàëüíîãî äåëåíèÿ (3). Äàëüíåéøàÿ îáðàáîòêà
âîçìîæíûõ îáðàçóþùèõ ïîëèíîìîâ, íà êîòîðûå ãè-
ïîòåòè÷åñêèå êîäîâûå ñëîâà ïîäåëèëèñü áåç îñòàòêà,
ïðîâîäèòñÿ òàê æå, êàê â ìåòîäå ïîëíîãî ïåðåáîðà.
Ïðè îòûñêàíèè èñòèííîãî îáðàçóþùåãî ïîëèíîìà
ïðîöåäóðà ìîæåò áûòü ïðåêðàùåíà.
Íà ðèñ. 6 ïîêàçàí âèäîèçìåíåííûé öèêë ïî-
ëèíîìîâ i èç ðèñ. 3, îãðàíè÷åííûé ïðåäåëàìè îò
1 äî 600, â êîòîðîì èñïîëüçóåòñÿ ïðîâåðêà g z( ) ��.
Ïðèìåíåíèå ýòîãî öèêëà â àëãîðèòìå, ïðåäñòàâ-
ëåííîì íà ðèñ. 3, ïðèâîäèò ê àëãîðèòìó, ðåàëèçó-
þùåìó ìåòîä ðàñïîçíàâàíèÿ ïàðàìåòðîâ ïîìåõî-
óñòîé÷èâûõ áëî÷íûõ öèêëè÷åñêèõ êîäîâ ïî îáðà-
çóþùåìó ïîëèíîìó ñðåäè èçâåñòíîãî ìíîæåñòâà.
Ïðèâåäåì îñíîâíûå ýëåìåíòû àëãîðèòìà, îïèñû-
âàþùåãî ðàáîòó ìåòîäà.
1. Ðàçáèåíèå áèòîâîãî ïîòîêà äëèíîé M áèò
íà J âàðèàíòîâ.
2. Öèêë áèòîâûõ ñäâèãîâ b îò 0 äî n j �1.
3. Öèêë êîäîâûõ ñëîâ � îò 0 äî m j �1.
4. Öèêë ïîëèíîìîâ i , â êîòîðîì ïîëèíîìè-
àëüíîå äåëåíèå âûïîëíÿåòñÿ ëèøü ïðè óñëîâèè
g z( ) �� .
5. Ôîðìèðîâàíèå ñòðîêè ìàòðèöû Ô.
6. Öèêë ïîèñêà u îò e äî s, â ìàòðèöå Ô êîòîðîãî íàõîäèòñÿ � s5 1� (óñëîâèå
äîñðî÷íîãî ïðåêðàùåíèÿ ïîèñêà, h �1).
7. Öèêë ïîèñêà f îò 0 äî s�1, â ìàòðèöå Ô êîòîðîãî íàõîäÿòñÿ çíà÷åíèÿ � s5 ,
ìàêñèìàëüíî ïðèáëèæåííûå ê åäèíèöå (ôîðìèðóþòñÿ h âàðèàíòîâ ïàðàìåòðîâ
êîäà). Èñòèííûé ïîëèíîì ñ÷èòàåòñÿ íàéäåííûì, åñëè îòíîøåíèå âû÷èñëåííîãî
ìàêñèìàëüíîãî çíà÷åíèÿ � s5 ê ñëåäóþùåìó ïî âåëè÷èíå çíà÷åíèþ � s5 ñîñòàâëÿ-
åò íå ìåíåå 10, èíà÷å ïðèíèìàåòñÿ ðåøåíèå î òîì, ÷òî îáðàçóþùèé ïîëèíîì íå
íàéäåí.
Î÷åâèäíî, ÷òî êîëè÷åñòâî èòåðàöèé àëãîðèòìà C (5) ïðè èñïîëüçîâàíèè ìå-
òîäà ðàñïîçíàâàíèÿ ïàðàìåòðîâ ïîìåõîóñòîé÷èâûõ áëî÷íûõ öèêëè÷åñêèõ êîäîâ
ïî îáðàçóþùåìó ïîëèíîìó ñðåäè èçâåñòíîãî ìíîæåñòâà (áåç ó÷åòà äîñðî÷íîãî
ïðåêðàùåíèÿ ïîèñêà) çíà÷èòåëüíî ñîêðàòèòñÿ.
ÇÀÊËÞ×ÅÍÈÅ
Ïðåäëîæåííûé ìåòîä ðàñïîçíàâàíèÿ ïàðàìåòðîâ ïîìåõîóñòîé÷èâûõ áëî÷íûõ
öèêëè÷åñêèõ êîäîâ, èñïîëüçóåìûõ â ñèñòåìàõ ñâÿçè è ïåðåäà÷è äàííûõ, îòëè÷à-
åòñÿ îò èçâåñòíûõ ìåòîäîâ âûïîëíåíèåì ïîèñêà ïàðàìåòðîâ ëèøü ñðåäè ìíî-
æåñòâà èçâåñòíûõ îáðàçóþùèõ ïîëèíîìîâ. Ñóùåñòâåííîå ñîêðàùåíèå âðåìåíè
âû÷èñëåíèÿ äîñòèãàåòñÿ çà ñ÷åò ïîèñêà òîëüêî ñðåäè èçâåñòíûõ õîðîøèõ îá-
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1 175
Îò öèêëà
êîäîâûõ ñëîâ �
Öèêë
ïîëèíîìîâ i
îò 1 äî 600
gi (z) � �
ÍåòÄà
Äà Íåò
Ôîðìèðîâàíèå
ñòðîêè Ô
i :� i � 1,
öèêë i
ri (z) � 0
p:� p � 1,
s:� s � 1
gi ( z)
m j
x
Ê öèêëó
êîäîâûõ ñëîâ �
Ðèñ. 6. Âèäîèçìåíåííûé öèêë ïî-
ëèíîìîâ i äëÿ ìåòîäà ðàñïîçíàâà-
íèÿ ïàðàìåòðîâ ïîìåõîóñòîé÷èâûõ
áëî÷íûõ öèêëè÷åñêèõ êîäîâ ïî îá-
ðàçóþùåìó ïîëèíîìó ñðåäè èç-
âåñòíîãî ìíîæåñòâà
ðàçóþùèõ ïîëèíîìîâ, ïðèìåíåíèå êîòîðûõ äëÿ ôîðìèðîâàíèÿ êîäîâ â ñèãíà-
ëàõ ñèñòåì ñâÿçè è ïåðåäà÷è äàííûõ íàèáîëåå âåðîÿòíî. Ïðåäïîëàãàåòñÿ, ÷òî
ïðîãðàììíûå èëè ïðîãðàììíî-àïïàðàòíûå ðåàëèçàöèè ïðåäëîæåííîãî ìåòîäà
èëè åãî ðàçíîâèäíîñòåé â ïðîãðàììíî-òåõíè÷åñêèõ êîìïëåêñàõ ïîçâîëÿò çíà-
÷èòåëüíî ïîâûñèòü ýôôåêòèâíîñòü àíàëèçà áèòîâûõ ïîòîêîâ çà ñ÷åò ðàñïîçíà-
âàíèÿ ïàðàìåòðîâ ïîìåõîóñòîé÷èâûõ áëî÷íûõ öèêëè÷åñêèõ êîäîâ, èñïîëüçóå-
ìûõ â ñèñòåìàõ ñâÿçè è ïåðåäà÷è äàííûõ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Morelos-Zaragoza R.H. The art of error correcting coding. 2nd ed. Chichester: John Wiley & Sons,
2006. 278 p.
2. Êîòþá³í Â.Þ., Ðîìàíîâ Î.Ì., Áóðëàê Ä.Þ. Îñîáëèâîñò³ âèçíà÷åííÿ ïåð³îäè÷íîñò³ ó ³íôîð-
ìàö³éí³é ïîñë³äîâíîñò³ ïðè ïðîâåäåíí³ òåõí³÷íîãî àíàë³çó ñèãíàë³â. Òåîð³ÿ òà ïðàêòèêà
ñòâîðåííÿ, ðîçâèòêó ³ çàñòîñóâàííÿ âèñîêîòåõíîëîã³÷íèõ ñèñòåì ñïåö³àëüíîãî ïðèçíà÷åííÿ
ç óðàõóâàííÿì äîñâ³äó àíòèòåðîðèñòè÷íî¿ îïåðàö³¿: òåçè äîï. XXII Âñåóêð. íàóê.-ïðàêò.
êîíô. (26–27 êâ³òíÿ 2018, Æèòîìèð). Æèòîìèð: Ʋ ³ìåí³ Ñ. Ï. Êîðîëüîâà, 2018. Ñ. 153.
3. Ðîìàíîâ Î.Ì. Îñîáëèâîñò³ ðîçðîáêè êîìïëåêñ³â àíàë³çó öèôðîâèõ ïîñë³äîâíîñòåé. Ñòâîðåí-
íÿ òà ìîäåðí³çàö³ÿ îçáðîºííÿ ³ â³éñüêîâî¿ òåõí³êè â ñó÷àñíèõ óìîâàõ: çá. òåç äîï.
17 íàóê.-òåõí. êîíô. (7–8 âåðåñíÿ 2017, ×åðí³ã³â). ×åðí³ã³â: ÄÍÂÖ ÇÑ Óêðà¿íè, 2017.
Ñ. 309–310.
4. Çóáàðåâ Þ.Á., Îâå÷êèí Ã.Â. Ïîìåõîóñòîé÷èâîå êîäèðîâàíèå â öèôðîâûõ ñèñòåìàõ ïåðåäà÷è
äàííûõ. Ýëåêòðîñâÿçü. 2008. ¹ 12. Ñ. 58–61. URL: http://mtdbest.ru/articles/obzor_dvoichnie_
kodi_2.pdf.
5. TC Synchronization and Channel Coding. Recommended Standard CCSDS 231.0-B-3. Washington:
CCSDS, 2017. 50 p. https://public.ccsds.org/Pubs/231x0b3.pdf.
6. Ñèäîðêèíà Þ.À., Øàõòàðèí Á.È., Áàëàõîíîâ Ê.À. Àíàëèç ýôôåêòèâíîñòè ñîâðåìåííûõ ïîìåõîóñ-
òîé÷èâûõ êîäîâ. Âåñòíèê ÌÃÒÓ èì. Í.Ý. Áàóìàíà. Ñåð. Ïðèáîðîñòðîåíèå. 2014. ¹ 6. Ñ. 108–116.
URL: https://cyberleninka.ru/article/n/analiz-effektivnosti-sovremennyh-pomehoustoychivyh-kodov.
7. Blahut R.E. Theory and practice of error control codes. Corr. ed. Boston: Addison-Wesley, 1983.
452 p.
8. Êàñàìè Ò., Òîêóðà Í., Èâàäàðè ¨., Èíàãàêè ß. Òåîðèÿ êîäèðîâàíèÿ. Ìîñêâà: Ìèð, 1978. 576 ñ.
9. Peterson W.W., Weldon E.J. Error-correcting codes. 2nd ed. Cambridge: MIT Press, 1972. 560 p.
10. Berlekamp E.R. Algebraic coding theory. New York: McGraw-Hill, 1968. 466 p.
11. Mostari L., Taleb-Ahmed A. High performance short-block binary regular LDPC codes. Alexandria
Engineering Journal. 2018. Vol. 57, Iss. 4. P. 2633–2639. https://doi.org/10.1016/j.aej.2017.09.016.
12. Ðîìàíîâ Î.Ì. Çàñòîñóâàííÿ àíàë³çàòîð³â ïðîòîêîë³â ïðè òåõí³÷íîìó àíàë³ç³ ñèãíàë³â ñèñòåì
çâ’ÿçêó. Ïðîáëåìè ê³áåðáåçïåêè ³íôîðìàö³éíî-òåëåêîìóí³êàö³éíèõ ñèñòåì: Ìàòåð³àëè äîï.
II íàóê.-ïðàêò. êîíô. (23–24 áåðåçíÿ 2017, Êè¿â). Ê.: ÊÍÓ ³ì. Òàðàñà Øåâ÷åíêà, 2017.
Ñ. 177–179.
13. Ìàðêèí Þ.Â. Ìåòîäû è ñðåäñòâà óãëóáëåííîãî àíàëèçà ñåòåâîãî òðàôèêà: àâòîðåô. äèñ. …
êàíä. òåõí. íàóê. Ìîñêâà: ÈÑÏ ÐÀÍ, 2017. 30 ñ. URL: https://www.ispras.ru/dcouncil/docs/diss/
2017/markin/autoref-markin-publ.pdf.
14. Âîðîáüåâà Å.È., Íåìöîâ Ð.À., ×óðàêîâ Ï.Ï. Ðàñïîçíàâàíèå âèäà ìîäóëÿöèè ñèãíàëîâ â ñèñòå-
ìàõ ðàäèîìîíèòîðèíãà. Âåñòí. Âîðîíåæ. ãîñ. òåõí. óí-òà. 2015. Ò. 11, ¹ 4. Ñ. 72–75.
15. Ðåâóöêèé Â.À. Óñòîé÷èâûå ê ìåøàþùèì ôàêòîðàì àëãîðèòìû ðàñïîçíàâàíèÿ âèäà ïîìåõîóñ-
òîé÷èâûõ êîäîâ â ðàäèîòåõíè÷åñêèõ ñèñòåìàõ: àâòîðåô. äèñ. … êàíä. òåõí. íàóê. Ðÿçàíü:
ÐÃÐÒÓ, 2013. 19 ñ.
16. Êóëÿíèöÿ Î.É., ͳêîëàºâ Ñ.Ì., Ðàòàí³í ª.Ã. Àíàë³ç öèêë³÷íèõ êîä³â ñó÷àñíèõ ñèñòåì ðàä³îçâ’ÿç-
êó ÊÕ ä³àïàçîíó. Ïðàö³ ²Ҳ ÍÒÓÓ «Êϲ». 2002. ¹ 4. Ñ. 95–98.
17. Ifeachor E.C., Jervis B.W. Digital signal processing: A practical approach. 2nd ed. Harlow; New
York: Prentice Hall, 2002. 933 p.
18. Sklar B. Digital communications: Fundamentals and applications. 2nd ed. Upper Saddle River, NJ:
Prentice Hall, 2001. 1104 p.
176 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1
19. Êóëÿíèöÿ Î.É., ͳêîëàºâ Ñ.Ì., Ïàâëþê Ñ.Â., Ðàòàí³í ª.Ã. Àëãîðèòì ïîøóêó ïàðàìåòð³â çàâà-
äîñò³éêèõ êîä³â ó ñèãíàëàõ ñèñòåì ðàä³îçâ’ÿçêó. Ïð³îðèòåòí³ íàïðÿìêè ðîçâèòêó òåëåêî-
ìóí³êàö³éíèõ ñèñòåì òà ìåðåæ ñïåö³àëüíîãî ïðèçíà÷åííÿ: òåçè äîï. ²²² íàóê.-ïðàêò. ñåì³íàðó
(8 ãðóäíÿ 2005, Êè¿â). Ê.: ²Ҳ ÍÒÓÓ «Êϲ», 2006. Ñ. 64–65.
20. ͳêîëàºâ Ñ.Ì., Ðàòàí³í ª.Ã. Àëãîðèòì ïîøóêó óòâîðþþ÷èõ ïîë³íîì³â çàâàäîñò³éêèõ êîä³â
â êîìïëåêñàõ ñïåö³àëüíîãî ïðèçíà÷åííÿ. Íàóêîâ³ ïðîáëåìè ðîçðîáêè, ìîäåðí³çàö³¿ òà çàñòî-
ñóâàííÿ ³íôîðìàö³éíî-âèì³ðþâàëüíèõ ñèñòåì êîñì³÷íîãî ³ íàçåìíîãî áàçóâàííÿ: òåçè äîï.
XV íàóê.-òåõí. êîíô. (20–21 êâ³òíÿ 2006, Æèòîìèð). Æèòîìèð: ƲÐÅ ³ì. Ñ.Ï. Êîðîëüîâà,
2006. Ñ. 173.
21. Òèïèêèí À.Ï., Ïåòðîâ Â.Â., Áàáàíèí À.Ã. Êîððåêöèÿ îøèáîê â îïòè÷åñêèõ íàêîïèòåëÿõ èí-
ôîðìàöèè. Ê.: Íàóê. äóìêà, 1990. 172 ñ.
22. Êîäèðîâàíèå èíôîðìàöèè. Äâîè÷íûå êîäû. Ïîä ðåä. Áåðåçþêà Í.Ò. Õàðüêîâ: Âèùà øê., 1978.
252 ñ.
23. Clark G.C., Cain J.B. Error-correction coding for digital communications. Applications of
communications theory. New York: Springer, 1981. 435 p. https://doi.org/10.1007/978-1-4899-2174-1.
24. Çëîòíèê Á.Ì. Ïîìåõîóñòîé÷èâûå êîäû â ñèñòåìàõ ñâÿçè. Ìîñêâà: Ðàäèî è ñâÿçü, 1989. 232 ñ.
25. Ðàõìàòêàðèåâ Ý.Ó. Àíàëèç èçáûòî÷íîñòè ïîìåõîóñòîé÷èâûõ êîäîâ. Êîäèðîâàíèå â ñëîæíûõ
ñèñòåìàõ. Ïîä ðåä. Ñàìîéëåíêî Ñ.È. Ìîñêâà: Íàóêà, 1974. Ñ. 115–153.
26. Tomlinson M., Tjhai C.J., Ambroze M.A., Ahmed M., Jibril M. Error-correction coding and
decoding. Bounds, codes, decoders, analysis and applications. Cham: Springer, 2017. 527 p.
https://doi.org/10.1007/978-3-319-51103-0.
Íàä³éøëà äî ðåäàêö³¿ 09.06.2020
Ñ.Ì. ͳêîëàºâ, Î.Ì. Ðîìàíîâ
ÌÅÒÎÄ ÐÎÇϲÇÍÀÂÀÍÍß ÏÀÐÀÌÅÒв ÇÀÂÀÄÎÑÒ²ÉÊÈÕ ÁËÎÊÎÂÈÕ ÖÈÊ˲×ÍÈÕ
ÊÎIJ ÇÀ ÓÒÂÎÐÞÂÀËÜÍÈÌ ÏÎ˲ÍÎÌÎÌ
Àíîòàö³ÿ. Îïèñàíî ñóòü çàâàäîñò³éêîãî áëîêîâîãî öèêë³÷íîãî êîäóâàííÿ.
Ðîçãëÿíóòî ìåòîä ðîçï³çíàâàííÿ ïàðàìåòð³â òàêîãî êîäó ïîâíèì ïåðåáîðîì.
çà â³äñóòíîñò³ àïð³îðíî¿ ³íôîðìàö³¿ Âèçíà÷åíî ê³ëüê³ñòü íåîáõ³äíèõ äëÿ öüî-
ãî îá÷èñëåíü. Ïîêàçàíî, ùî çàñòîñóâàííÿ òàêîãî ìåòîäó â ðåàëüíèõ óìîâàõ
óñêëàäíåíå. Äîñë³äæåíî â³äîì³ óòâîðþâàëüí³ ïîë³íîìè, âèêîðèñòàííÿ ÿêèõ º
íàéá³ëüø éìîâ³ðíèì. Ñôîðìîâàíî ìíîæèíó òàêèõ ïîë³íîì³â ³ â³äïîâ³äíèõ
ïàðàìåòð³â. Çàïðîïîíîâàíî ìåòîä ðîçï³çíàâàííÿ ïàðàìåòð³â çàâàäîñò³éêèõ
áëîêîâèõ öèêë³÷íèõ êîä³â ñåðåä â³äîìî¿ ìíîæèíè, ùî äຠçìîãó çíà÷íî
ñêîðîòèòè ê³ëüê³ñòü íåîáõ³äíèõ îá÷èñëåíü.
Êëþ÷îâ³ ñëîâà: á³òîâèé ïîò³ê, çàâàäîñò³éêèé áëîêîâèé öèêë³÷íèé êîä, óòâî-
ðþâàëüíèé ïîë³íîì êîäó, çàëèøîê â³ä ïîë³íîì³àëüíîãî ä³ëåííÿ, ìàòðèöÿ.
S.N. Nikolaev, A.N. Romanov
ERROR-CORRECTING BLOCK CYCLIC CODE PARAMETER RECOGNITION
METHOD BASED ON GENERATOR POLYNOMIAL
Abstract. The essence of the error-correcting block cyclic coding is described.
A method for recognizing parameters of such a code in the absence of a priori
information by a complete enumeration of parameters is considered. The amount
of necessary calculation is determined. The application of the considered method
in real conditions is shown to be difficult. The well-known generator
polynomials whose practical use is most probable are investigated. A set of
these polynomials and related parameters is generated. A method is proposed for
recognizing parameters of error-correcting block cyclic codes among a known
set, which can significantly reduce the amount of necessary calculation.
Keywords: bitstream, error-correcting block cyclic code, a generator polynomial
of code, remainder of polynomial division, matrix.
Íèêîëàåâ Ñåðãåé Íèêîëàåâè÷,
êàíäèäàò òåõí. íàóê, ñòàðøèé íàó÷íûé ñîòðóäíèê, íà÷àëüíèê íàó÷íî-èññëåäîâàòåëüñêîãî óïðàâëåíèÿ
Íàó÷íî-èññëåäîâàòåëüñêîãî èíñòèòóòà Ìèíèñòåðñòâà îáîðîíû Óêðàèíû, Êèåâ, e-mail: divan24@i.ua.
Ðîìàíîâ Àëåêñåé Íèêîëàåâè÷,
êàíäèäàò òåõí. íàóê, çàìåñòèòåëü íà÷àëüíèêà Íàó÷íî-èññëåäîâàòåëüñêîãî èíñòèòóòà Ìèíèñòåðñòâà
îáîðîíû Óêðàèíû ïî íàó÷íîé ðàáîòå, Êèåâ, e-mail: rolex@i.ua.
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 1 177
|