Исследование свойств кодов с суммированием с одним взвешенным информационным разрядом в системах функционального контроля
Рассмотрен новый класс кодов с суммированием, имеющий улучшенные характеристики обнаружения ошибок в информационных разрядах по сравнению с известными кодами с суммированием. Определены свойства полученного класса кодов, позволяющие выбрать наилучший способ кодирования при организации системы функци...
Gespeichert in:
| Veröffentlicht in: | Электронное моделирование |
|---|---|
| Datum: | 2015 |
| Hauptverfasser: | , , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2015
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/101078 |
| 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 — Т. 37, № 1. — С. 25-48. — Бібліогр.: 36 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860022877420519424 |
|---|---|
| author | Сапожников, В.В. Сапожников, Вл.В. Ефанов, Д.В. Никитин, Д.А. |
| author_facet | Сапожников, В.В. Сапожников, Вл.В. Ефанов, Д.В. Никитин, Д.А. |
| citation_txt | Исследование свойств кодов с суммированием с одним взвешенным информационным разрядом в системах функционального контроля / В.В. Сапожников, Вл.В. Сапожников, Д.В. Ефанов, Д.А. Никитин // Электронное моделирование. — 2015 — Т. 37, № 1. — С. 25-48. — Бібліогр.: 36 назв. — рос. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | Рассмотрен новый класс кодов с суммированием, имеющий улучшенные характеристики обнаружения ошибок в информационных разрядах по сравнению с известными кодами с суммированием. Определены свойства полученного класса кодов, позволяющие выбрать наилучший способ кодирования при организации системы функционального контроля. Описаны метод синтеза генераторов для новых кодов и способы упрощения схем генераторов.
Розглянуто новий клас кодів з підсумовуванням, який має покращені характеристики для виявлення похибок в інформаційних розрядах порівняно з відомими кодами з підсумовуванням. Визначено властивості отриманого класу кодів, які дають можливість обрати найкращий спосіб кодування при організуванні системи функціонального контролю. Описано метод синтезу генераторів для нових кодів та способи спрощення схем генераторів.
The new class of codes with summation with the improved characteristics of error detection in data bits in comparison with the known codes with summation is considered. Properties of the new class of codes are established, allowing the practical choosing of the best variant of coding at the organization of concurrent error detection system. A method of synthesis of generators for new codes and ways of simplification of generators schemes are described.
|
| first_indexed | 2025-12-07T16:48:38Z |
| format | Article |
| fulltext |
ÓÄÊ 681.518.5:004.052.32
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, äîêòîðà òåõí. íàóê,
Ä.Â. Åôàíîâ, êàíä. òåõí. íàóê, Ä.À. Íèêèòèí, àñïèðàíò
Ôåäåðàëüíîå ãîñóäàðñòâåííîå áþäæåòíîå
îáðàçîâàòåëüíîå ó÷ðåæäåíèå âûñøåãî ïðîôåññèîíàëüíîãî
îáðàçîâàíèÿ «Ïåòåðáóðãñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò
ïóòåé ñîîáùåíèÿ Èìïåðàòîðà Àëåêñàíäðà I»
(Ðîññèéñêàÿ Ôåäåðàöèÿ, 190031, Ñàíêò-Ïåòåðáóðã, Ìîñêîâñêèé ïð., 9,
òåë. (+7) 9117092164, (+7) (812) 4578579, e-mail: TrES-4b@yandex.ru)
Èññëåäîâàíèå ñâîéñòâ êîäîâ ñ ñóììèðîâàíèåì
ñ îäíèì âçâåøåííûì èíôîðìàöèîííûì ðàçðÿäîì
â ñèñòåìàõ ôóíêöèîíàëüíîãî êîíòðîëÿ
Ðàññìîòðåí íîâûé êëàññ êîäîâ ñ ñóììèðîâàíèåì, èìåþùèé óëó÷øåííûå õàðàêòåðèñòèêè
îáíàðóæåíèÿ îøèáîê â èíôîðìàöèîííûõ ðàçðÿäàõ ïî ñðàâíåíèþ ñ èçâåñòíûìè êîäàìè ñ
ñóììèðîâàíèåì. Îïðåäåëåíû ñâîéñòâà ïîëó÷åííîãî êëàññà êîäîâ, ïîçâîëÿþùèå âûáðàòü
íàèëó÷øèé ñïîñîá êîäèðîâàíèÿ ïðè îðãàíèçàöèè ñèñòåìû ôóíêöèîíàëüíîãî êîíòðîëÿ.
Îïèñàíû ìåòîä ñèíòåçà ãåíåðàòîðîâ äëÿ íîâûõ êîäîâ è ñïîñîáû óïðîùåíèÿ ñõåì ãåíå-
ðàòîðîâ.
Ðîçãëÿíóòî íîâèé êëàñ êîä³â ç ï³äñóìîâóâàííÿì, ÿêèé ìຠïîêðàùåí³ õàðàêòåðèñòèêè äëÿ
âèÿâëåííÿ ïîõèáîê â ³íôîðìàö³éíèõ ðîçðÿäàõ ïîð³âíÿíî ç â³äîìèìè êîäàìè ç ï³äñóìîâó-
âàííÿì. Âèçíà÷åíî âëàñòèâîñò³ îòðèìàíîãî êëàñó êîä³â, ÿê³ äàþòü ìîæëèâ³ñòü îáðàòè íàéêðà-
ùèé ñïîñ³á êîäóâàííÿ ïðè îðãàí³çóâàíí³ ñèñòåìè ôóíêö³îíàëüíîãî êîíòðîëþ. Îïèñàíî ìåòîä
ñèíòåçó ãåíåðàòîð³â äëÿ íîâèõ êîä³â òà ñïîñîáè ñïðîùåííÿ ñõåì ãåíåðàòîð³â.
Ê ë þ ÷ å â û å ñ ë î â à: ôóíêöèîíàëüíûé êîíòðîëü, íåîáíàðóæèâàåìàÿ îøèáêà, èíôîð-
ìàöèîííûå ðàçðÿäû, êîä Áåðãåðà, âçâåøåííûé êîä ñ ñóììèðîâàíèåì, ñâîéñòâà êîäîâ,
ãåíåðàòîð, òåñòåð.
Ïðè ôóíêöèîíàëüíîì êîíòðîëå ëîãè÷åñêèõ óñòðîéñòâ (ËÓ) ïðîâåðêà ïðà-
âèëüíîñòè ðàáîòû óñòðîéñòâà âûïîëíÿåòñÿ áåç îòêëþ÷åíèÿ åãî îò îáúåê-
òîâ óïðàâëåíèÿ [1—7].  ýòîì ñëó÷àå ËÓ f (x) ñíàáæàåòñÿ áëîêîì êîíò-
ðîëüíîé ëîãèêè (ÊË) g (x) è ñõåìîé ñàìîïðîâåðÿåìîãî òåñòåðà (ðèñ. 1) [8, 9].
Òàêîé ìåòîä îðãàíèçàöèè êîíòðîëÿ ïîëó÷èë íàçâàíèå ìåòîäà âû÷èñëåíèÿ
êîíòðîëüíûõ ðàçðÿäîâ, òàê êàê ïðè åãî ðåàëèçàöèè âûõîäû êîíòðîëèðóå-
ìîé ñõåìû ñòàâÿòñÿ â ñîîòâåòñòâèå èíôîðìàöèîííûì ðàçðÿäàì, à âûõîäû
áëîêà ÊË — íåêîòîðûì êîíòðîëüíûì ðàçðÿäàì [10]. Çíà÷åíèÿ êîíòðîëü-
íûõ ðàçðÿäîâ îïðåäåëÿþòñÿ èñõîäÿ èç çàðàíåå óñòàíîâëåííûõ ïðàâèë. Íà-
ïðèìåð, â ñèñòåìå êîíòðîëÿ ïî êîäó ïàðèòåòà áëîê ÊË âû÷èñëÿåò ôóíêöèþ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 1 25
�������� �
��
�
�� ���������� ��
� Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ, Ä.À. Íèêèòèí, 2015
ñëîæåíèÿ ïî ìîäóëþ äâà âñåõ èíôîðìàöèîííûõ ðàçðÿäîâ [2, 11, 12].
Ñîîòâåòñòâèå ìåæäó èíôîðìàöèîííûìè è êîíòðîëüíûìè âûõîäàìè óñòà-
íàâëèâàåòñÿ òåñòåðîì. Îò òîãî, êàêîé êîä ëåæèò â îñíîâå ïîñòðîåíèÿ
ñèñòåìû äèàãíîñòèðîâàíèÿ, çàâèñÿò ñëîæíîñòü êîíòðîëüíîãî îáîðóäîâà-
íèÿ è õàðàêòåðèñòèêè îáíàðóæåíèÿ èñêàæåíèé íà âûõîäàõ áëîêà ËÓ.
Àëüòåðíàòèâîé ìåòîäó âû÷èñëåíèÿ êîíòðîëüíûõ ðàçðÿäîâ ÿâëÿåòñÿ ìåòîä
ëîãè÷åñêîãî äîïîëíåíèÿ [13], â êîòîðîì â êà÷åñòâå îñíîâû ñèñòåìû äèàã-
íîñòèðîâàíèÿ ìîãóò áûòü óñòàíîâëåíû íåðàçäåëèìûå êîäû (íàïðèìåð, ðàâ-
íîâåñíûå èëè êîäû Àäàìàðà [14—16]) èëè âûáðàíû îñîáåííûå êëàññû ôóíê-
öèé àëãåáðû ëîãèêè (íàïðèìåð, ñàìîäâîéñòâåííûå ôóíêöèè [17]).
Ñëåäóåò çàìåòèòü, ÷òî â îáùåì ñëó÷àå êîíòðîëèðóåìîå óñòðîéñòâî
ìîæåò èìåòü m âûõîäîâ, à áëîê ÊË — k âûõîäîâ. Òîãäà ðàçäåëèìûé êîä
èìååò n = m + k ðàçðÿäîâ, m èç êîòîðûõ — èíôîðìàöèîííûå, à k — êîíòðîëü-
íûå. Òàêîé ïîäõîä ê ñèñòåìå ôóíêöèîíàëüíîãî êîíòðîëÿ ïîçâîëÿåò ðàññìàò-
ðèâàòü ñâîéñòâà èçáûòî÷íûõ êîäîâ, îïðåäåëÿÿ ïðè ýòîì ñâîéñòâà ñàìîé
ñèñòåìû êîíòðîëÿ, îáåñïå÷èâàþùèå îáíàðóæåíèå îäíîêðàòíûõ îøèáîê íà
âûõîäàõ ýëåìåíòîâ âíóòðåííåé ñòðóêòóðû êîíòðîëèðóåìûõ ËÓ.
Ñõåìû êîìïîíåíòîâ ñèñòåìû äèàãíîñòèðîâàíèÿ, áëîêîâ ËÓ, ÊË è òåñ-
òåðà, òåõíè÷åñêè ðåàëèçóþòñÿ ðàçäåëüíî. Ïîýòîìó â ëþáîé ìîìåíò âðåìå-
íè èñêàæåíèå ìîæåò âîçíèêíóòü òîëüêî â îäíîì èç áëîêîâ. Ëþáûå èñêà-
æåíèÿ â áëîêå ÊË îáíàðóæèâàþòñÿ ñõåìîé òåñòåðà, òàê êàê â ýòîì ñëó÷àå
íàðóøàåòñÿ ñîîòâåòñòâèå ìåæäó èíôîðìàöèîííûìè è êîíòðîëüíûìè ðàç-
ðÿäàìè êîäà. Òåñòåð ÿâëÿåòñÿ ñàìîïðîâåðÿåìûì [2, 10], ò.å. ëþáàÿ îäèíî÷-
íàÿ íåèñïðàâíîñòü â åãî ñòðóêòóðå îáíàðóæèâàåòñÿ, ïî êðàéíåé ìåðå, íà
îäíîì âõîäíîì âîçäåéñòâèè. Äåôåêòû âî âíóòðåííåé ñòðóêòóðå áëîêà ËÓ
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ, Ä.À. Íèêèòèí
26 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 1
x
f (x)
f2(x)
f1(x)
fm(x)
g (x)
g1(x)
g2(x)
gk(x)
Òåñòåð
z2
z1
Ðàáî÷èå âûõîäû
Ñèãíàë
êîíòðîëÿ
Èíôîðìàöèîííûå ðàçðÿäû
Êîíòðîëüíûå ðàçðÿäû
ÊË
ËÓ
. . .
.
.
.
.
.
.
.
.
.
.
.
.
Ðèñ. 1. Ñèñòåìà ôóíêöèîíàëüíîãî êîíòðîëÿ
ìîãóò ïðèâîäèòü ê èñêàæåíèÿì d âûõîäîâ (èëè èíôîðìàöèîííûõ ðàçðÿ-
äîâ) â çàâèñèìîñòè îò êîíôèãóðàöèè ñâÿçåé ìåæäó ëîãè÷åñêèìè ýëåìåíòà-
ìè êîíòðîëèðóåìîãî óñòðîéñòâà. Èíûìè ñëîâàìè, â èíôîðìàöèîííîì
âåêòîðå ìîæåò áûòü äîïóùåíà îøèáêà êðàòíîñòè d. Âîçìîæíîñòü åå èäåí-
òèôèêàöèè îïðåäåëÿåòñÿ âûáðàííûì âàðèàíòîì êîäèðîâàíèÿ íà ýòàïå
ïðîåêòèðîâàíèÿ ñèñòåìû ôóíêöèîíàëüíîãî êîíòðîëÿ.
Ïðè îðãàíèçàöèè ñèñòåìû ôóíêöèîíàëüíîãî êîíòðîëÿ ÷àñòî èñïîëü-
çóþò êîäû ñ ñóììèðîâàíèåì, èëè êîäû Áåðãåðà (S n m( , )-êîäû), âïåðâûå
îïèñàííûå â [18]. Êîíòðîëüíûé âåêòîð òàêèõ êîäîâ îáðàçóåòñÿ ïîñðåäñò-
âîì ïîäñ÷åòà åäèíè÷íûõ èíôîðìàöèîííûõ ðàçðÿäîâ (èëè âåñà r èíôîð-
ìàöèîííîãî âåêòîðà) è çàïèñè ñóììàðíîãî ÷èñëà â êîíòðîëüíûé âåêòîð.
Äàííûé êëàññ êîäîâ [19] íå îáíàðóæèâàåò äîñòàòî÷íî áîëüøîãî ÷èñëà
èñêàæåíèé â èíôîðìàöèîííûõ âåêòîðàõ. Íàïðèìåð óñòàíîâëåíî, ÷òî äëÿ
êîäîâ ñ äëèíàìè èíôîðìàöèîííûõ âåêòîðîâ m � �2 15 äîëÿ íåîáíàðóæè-
âàåìûõ èñêàæåíèé èíôîðìàöèîííûõ âåêòîðîâ îò îáùåãî ÷èñëà íåîáíàðó-
æèâàåìûõ èñêàæåíèé ïðåâûøàåò � �014, , à ïðè m = 4 èìååò ìàêñèìàëüíóþ
âåëè÷èíó � �0 225, (â ñðåäíåì áîëåå 17 % âñåõ èñêàæåíèé).
Êðîìå êîýôôèöèåíòà � äëÿ îöåíêè õàðàêòåðèñòèê îáíàðóæåíèÿ îøè-
áîê â èíôîðìàöèîííûõ âåêòîðàõ ðàçäåëèìûìè êîäàìè èñïîëüçóåòñÿ êîýô-
ôèöèåíò ýôôåêòèâíîñòè � êîäà ïðè çàäàííûõ çíà÷åíèÿõ m è k. Îí ïîêà-
çûâàåò, íàñêîëüêî ðàññìàòðèâàåìûé ðàçäåëèìûé êîä áëèæå ê îïòèìàëüíî-
ìó êîäó ïî êðèòåðèþ ìèíèìóìà îáùåãî ÷èñëà íåîáíàðóæèâàåìûõ îøèáîê
â èíôîðìàöèîííûõ ðàçðÿäàõ äëÿ äàííûõ çíà÷åíèé m è k. Îïòèìàëüíûé
êîä èìååò ðàâíîìåðíîå ðàñïðåäåëåíèå âñåõ 2m èíôîðìàöèîííûõ âåêòîðîâ
ìåæäó âñåìè 2k êîíòðîëüíûìè âåêòîðàìè. Òàêèì îáðàçîì, êîýôôèöèåíò �
îïðåäåëÿåòñÿ êàê îòíîøåíèå ÷èñëà íåîáíàðóæèâàåìûõ îøèáîê â îïòè-
ìàëüíîì êîäå ñ ñóììèðîâàíèåì äëÿ äàííûõ m è k (âåëè÷èíû N m k,
min ) ê ÷èñëó
íåîáíàðóæèâàåìûõ îøèáîê â ðàññìàòðèâàåìîì ðàçäåëèìîì êîäå (âåëè-
÷èíå N
m k,
) [20, 21]: � � N Nm k m k,
min
,
/ , ãäå N m k
m m k
,
min ( )� ��2 2 1 . ×åì áëèæå ê
åäèíèöå çíà÷åíèå �, òåì ýôôåêòèâíåå êîä ñ ñóììèðîâàíèåì ïðè çàäàííûõ
äëèíàõ èíôîðìàöèîííîãî è êîíòðîëüíîãî âåêòîðîâ.
Óìåíüøèòü ïîêàçàòåëü � è ñîîòâåòñòâåííî óâåëè÷èòü ïîêàçàòåëü �
ìîæíî íåñêîëüêèìè ñïîñîáàìè. Ïåðâûé ñïîñîá [22] ñîñòîèò â ìîäóëüíîì
ïðèíöèïå ïîäñ÷åòà âåñà èíôîðìàöèîííîãî âåêòîðà. Ïðè ýòîì ìîäóëü M
âûáèðàåòñÿ ðàâíûì 2 1k � , ãäå � k m�
log ( )2 1 — ÷èñëî êîíòðîëüíûõ ðàç-
ðÿäîâ â êëàññè÷åñêîì S n m( , )-êîäå (çàïèñü � b îçíà÷àåò öåëîå ñâåðõó îò b).
Ê ïîëó÷åííîé âåëè÷èíå äîáàâëÿåòñÿ â êà÷åñòâå ñòàðøåãî êîíòðîëüíîãî
ðàçðÿäà êîýôôèöèåíò �, ïîëó÷åííûé êàê ñóììà ïî ìîäóëþ äâà çàðàíåå
óñòàíîâëåííûõ èíôîðìàöèîííûõ ðàçðÿäîâ. Äàííûé ïîäõîä ê ïîñòðîåíèþ
ìîäèôèöèðîâàííîãî êîäà Áåðãåðà óëó÷øàåò õàðàêòåðèñòèêè, îáåñïå÷è-
Èññëåäîâàíèå ñâîéñòâ êîäîâ ñ ñóììèðîâàíèåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 1 27
âàþùèå îáíàðóæåíèå îøèáîê â èíôîðìàöèîííûõ âåêòîðàõ ïî÷òè â äâà
ðàçà. Îäíàêî íåäîñòàòêîì òàêîãî ñïîñîáà ïîñòðîåíèÿ ÿâëÿåòñÿ âîçíèêíî-
âåíèå îäíîíàïðàâëåííûõ íåîáíàðóæèâàåìûõ îøèáîê âñëåäñòâèå ìîäóëü-
íîãî ïðèíöèïà ïîäñ÷åòà âåñà èíôîðìàöèîííîãî âåêòîðà. Íà ïðàêòèêå ýòî
íàêëàäûâàåò îãðàíè÷åíèå íà âûáîð ìîäèôèöèðîâàííîãî êîäà, íàïðèìåð
ïðè îðãàíèçàöèè ñèñòåì êîíòðîëÿ êîìáèíàöèîííûõ ñõåì ñ ìîíîòîííî
íåçàâèñèìûìè âûõîäàìè [23, 24].
Äàííûé íåäîñòàòîê îòñóòñòâóåò ó âòîðîãî ñïîñîáà, ñóòü êîòîðîãî
ñîñòàâëÿåò âçâåøèâàíèå èíôîðìàöèîííûõ ðàçðÿäîâ êîäîâ [18], ò.å. êàæ-
äîìó èíôîðìàöèîííîìó ðàçðÿäó ñòàâèòñÿ â ñîîòâåòñòâèå íåêîòîðîå ïîëî-
æèòåëüíîå ÷èñëî wi (âåñ i-ãî ðàçðÿäà).  êà÷åñòâå êîíòðîëüíîãî âåêòîðà
çàïèñûâàåòñÿ äâîè÷íîå ÷èñëî, ðàâíîå ñóììàðíîìó âåñó âñåõ èíôîðìà-
öèîííûõ ðàçðÿäîâ:W x w
i
m
i i�
�
�
1
, ãäå x i — çíà÷åíèå èíôîðìàöèîííîãî ðàç-
ðÿäà. Òàêèå êîäû, êàê è êëàññè÷åñêèå êîäû ñ ñóììèðîâàíèåì, îáíàðóæè-
âàþò ëþáûå îäíîíàïðàâëåííûå èñêàæåíèÿ â èíôîðìàöèîííûõ âåêòîðàõ è
òàêæå ìîãóò ïðèìåíÿòüñÿ ïðè îðãàíèçàöèè ñèñòåì ôóíêöèîíàëüíîãî êîíò-
ðîëÿ. Âîïðîñû ñèíòåçà öèôðîâûõ ñèñòåì ñ èñïîëüçîâàíèåì âçâåøåííûõ
êîäîâ ñ ñóììèðîâàíèåì (îáîçíà÷èì èõ äàëåå êàê WS n m w w wm( , ,[ , ,..., ])1 1 -
êîäû, ãäå [ , ,..., ]w w wm1 1 — ìàññèâ âåñîâûõ êîýôôèöèåíòîâ èíôîðìàöèîí-
íûõ ðàçðÿäîâ) èññëåäîâàíû â ðàáîòàõ [25—27].
 [28] óñòàíîâëåíû ñâîéñòâà êîäîâ, â êîòîðûõ âåñ ïðèïèñûâàåòñÿ
òîëüêî îäíîìó èíôîðìàöèîííîìó ðàçðÿäó, à âñå îñòàëüíûå ðàçðÿäû
èìåþò åäèíè÷íîå çíà÷åíèå âåñà. Ïðè ýòîì âåñ âçâåøåííîãî ðàçðÿäà âñåãäà
wi �3. Òàêîé ïîäõîä ê ïîñòðîåíèþ âçâåøåííîãî êîäà ïîçâîëÿåò ñîõðàíèòü
âñå êëþ÷åâûå õàðàêòåðèñòèêè êëàññè÷åñêîãî êîäà ñ ñóììèðîâàíèåì. Òàê,
WS n m( , ,[ , ,..., , ])1 1 1 3 -êîäû îáíàðóæèâàþò âñå îøèáêè íå÷åòíûõ êðàòíîñòåé
â èíôîðìàöèîííûõ âåêòîðàõ, à òàêæå âñå îäíîíàïðàâëåííûå îøèáêè ÷åòíûõ
êðàòíîñòåé. Ýòè êîäû èìåþò òàêîå æå ÷èñëî êîíòðîëüíûõ ðàçðÿäîâ, êàê è
êîäû Áåðãåðà, åñëè âûïîëíÿåòñÿ óñëîâèå
� m w w wm
m
�
1 2
1
2 12... .
log ( ) (1)
Ñîõðàíåíèå ÷èñëà êîíòðîëüíûõ ðàçðÿäîâ � k m�
log ( )2 1 ïîçâîëÿåò íå óñ-
ëîæíÿòü ñõåìó áëîêà ÊË â ñèñòåìå ôóíêöèîíàëüíîãî êîíòðîëÿ (ñì. ðèñ. 1).
Áóäåì ðàññìàòðèâàòü âçâåøåííûå êîäû ñ ñóììèðîâàíèåì ñ îäíèì âçâå-
øåííûì èíôîðìàöèîííûì ðàçðÿäîì áåç ó÷åòà óñëîâèÿ (1). Ïðè ýòîì íå-
êîòîðûå âçâåøåííûå êîäû ìîãóò èìåòü íà îäèí êîíòðîëüíûé ðàçðÿä
áîëüøå, ÷åì êîäû Áåðãåðà. Ðàññìîòðèì îñîáåííîñòè îáíàðóæåíèÿ èñêà-
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ, Ä.À. Íèêèòèí
28 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 1
æåíèé â èíôîðìàöèîííûõ âåêòîðàõ WS n m w w wm( , ,[ , ,..., ])1 1 -êîäàìè, ïðîÿâ-
ëÿþùèåñÿ ïðè óâåëè÷åíèè âåñà îäíîãî èíôîðìàöèîííîãî ðàçðÿäà.
Îïðåäåëåíèå ÷èñëà íåîáíàðóæèâàåìûõ îøèáîê âî âçâåøåííûõ
êîäàõ ñ ñóììèðîâàíèåì. Ðàññìîòðèì êëàññè÷åñêèé êîä ñ ñóììèðîâàíèåì
S (7, 4), à òàêæå åãî ìîäèôèêàöèþ ïðèïèñûâàíèåì ìëàäøåìó êîíòðîëüíî-
ìó ðàçðÿäó âåñîâîãî êîýôôèöèåíòà, íàïðèìåð w4 = 3 [28]. Â êîäå Áåðãåðà
êîíòðîëüíîå ñëîâî ñîîòâåòñòâóåò ñóììàðíîìó ÷èñëó åäèíè÷íûõ èíôîð-
ìàöèîííûõ ðàçðÿäîâ — èñòèííîìó âåñó r èíôîðìàöèîííîãî âåêòîðà. Âî
âçâåøåííîì êîäå çàïèñûâàåòñÿ ñóììàðíûé âåñ W åäèíè÷íûõ èíôîðìà-
öèîííûõ ðàçðÿäîâ. ×èñëà r è W â äâîè÷íîì ïðåäñòàâëåíèè åñòü êîíòðîëü-
íûå âåêòîðû êîäîâ ñ ñóììèðîâàíèåì. Ïðè ñðàâíåíèè äåñÿòè÷íûõ ýêâè-
âàëåíòîâ ÷èñåë r è W êîíòðîëüíûõ âåêòîðîâ S (7, 4) è WS ( , , [ , , , ])7 4 1 1 1 3 -
êîäîâ (òàáë. 1) âîçíèêàåò âîïðîñ: êàêàÿ ìåæäó íèìè ðàçíèöà?
 WS ( , , [ , , , ])7 4 1 1 1 3 -êîäå çíà÷åíèå ñóììàðíîãî âåñà èíôîðìàöèîí-
íûõ ðàçðÿäîâ W îòëè÷àåòñÿ îò èñòèííîãî âåñà r òîëüêî äëÿ òåõ èíôîðìà-
öèîííûõ âåêòîðîâ, ó êîòîðûõ ìëàäøèé ðàçðÿä x4 = 1. Îòëè÷àåòñÿ îí íà
âåëè÷èíó �r w� �4 1. Òàêèõ êîäîâûõ âåêòîðîâ ïîëîâèíà.
Íà ðèñ. 2 ïðèâåäåíà òàáëè÷íàÿ ôîðìà çàäàíèÿ êîäà S (7, 4) ñ ðàçáèå-
íèåì èíôîðìàöèîííûõ âåêòîðîâ íà ãðóïïû ñ îäèíàêîâûì âåñîì r. Âñå
èíôîðìàöèîííûå âåêòîðû îäíîé ãðóïïû èìåþò îäèíàêîâûå êîíòðîëüíûå
Èññëåäîâàíèå ñâîéñòâ êîäîâ ñ ñóììèðîâàíèåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 1 29
Íîìåð
âõîäíîãî âåêòîðà
x1 x2 x3 x4 r W �r
0 0 0 0 0 0 0 0
1 0 0 0 1 1 3 2
2 0 0 1 0 1 1 0
3 0 0 1 1 2 4 2
4 0 1 0 0 1 1 0
5 0 1 0 1 2 4 2
6 0 1 1 0 2 2 0
7 0 1 1 1 3 5 2
8 1 0 0 0 1 1 0
9 1 0 0 1 2 4 2
10 1 0 1 0 2 2 0
11 1 0 1 1 3 5 2
12 1 1 0 0 2 2 0
13 1 1 0 1 3 5 2
14 1 1 1 0 3 3 0
15 1 1 1 1 4 6 2
Òàáëèöà 1
âåêòîðû, âñå ïåðåõîäû âíóòðè ãðóïïû ñîîòâåòñòâóþò íåîáíàðóæèâàåìûì
îøèáêàì. Ïðè âçâåøèâàíèè ìëàäøåãî èíôîðìàöèîííîãî ðàçðÿäà ïîëîâè-
íà âåêòîðîâ ñäâèãàåòñÿ íà �r w� � �4 1 2 ãðóïïû âïðàâî, ò.å. ïðîèñõîäèò
ïåðåðàñïðåäåëåíèå èíôîðìàöèîííûõ âåêòîðîâ îòíîñèòåëüíî êîíòðîëü-
íûõ. Ýòî ïîçâîëÿåò óïëîòíèòü òàáëèöó êîäà, ò.å. áîëåå ðàâíîìåðíî ðàñïðå-
äåëèòü èíôîðìàöèîííûå âåêòîðû îòíîñèòåëüíî êîíòðîëüíûõ.
Ïåðåìåùàåìûå ïðè ìîäèôèêàöèè èíôîðìàöèîííûå âåêòîðû ïðåäñòà-
âèì â âèäå
000 1 1
001 1 2
010 1 2
011 1 3
100 1 2
101 1 3
11
� �
� �
� �
� �
� �
� �
r
r
r
r
r
r
0 1 3
111 1 4
� �
� �
r
r
r r r r
C C C C
� � � �1 2 3 4
1 3 3 1
3
0
3
1
3
2
3
3
.
Âûäåëèâ â íèõ ïîñëåäíèé èíôîðìàöèîííûé ðàçðÿä, âèäèì, ÷òî îñòàâøèåñÿ
èíôîðìàöèîííûå ðàçðÿäû ïðèíèìàþò âñå âîçìîæíûå çíà÷åíèÿ. Íåòðóäíî
çàìåòèòü, ÷òî â îáùåì âèäå ÷èñëî ñäâèãàåìûõ âåêòîðîâ ðàâíî C m
r
�
�
1
1 .
 êàæäîé êîíòðîëüíîé ãðóïïå êîäà S (7, 4) íàõîäèòñÿ C Cm
r r� 4 èíôîð-
ìàöèîííûõ âåêòîðîâ. Ïðè âçâåøèâàíèè ìëàäøåãî êîíòðîëüíîãî ðàçðÿäà
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ, Ä.À. Íèêèòèí
30 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 1
Ðèñ. 2. Ïåðåðàñïðåäåëåíèå èíôîðìàöèîííûõ âåêòîðîâ ïðè âçâåøèâàíèè ðàçðÿäîâ (âûäå-
ëåíû ñäâèãàåìûå êîäîâûå âåêòîðû)
èç ãðóïïû ñ âåñîì r = 1, 2, ..., m âûáèðàåòñÿ C Cm
r r
�
� ��1
1
3
1 èíôîðìàöèîííûõ
âåêòîðîâ è ñäâèãàåòñÿ âïðàâî íà äâå ãðóïïû. ×èñëî èíôîðìàöèîííûõ
âåêòîðîâ â êàæäîé ãðóïïå ïîñëå ïåðåðàñïðåäåëåíèÿ ïðèâåäåíî â òàáë. 2, èç
êîòîðîé âèäíî, ÷òî ÷èñëî ïåðåõîäîâ âíóòðè êàæäîé ãðóïïû ñîñòàâëÿåò â
ñóììå 26.
Ïðîàíàëèçèðóåì ïðîöåññ ïåðåðàñïðåäåëåíèÿ â îáùåì ñëó÷àå.  êàæ-
äîé ãðóïïå r áûëî C m
r èíôîðìàöèîííûõ âåêòîðîâ. Èç âñåõ ãðóïï, êðîìå
ãðóïïû r = 0, ïåðåìåñòèëè â ãðóïïû ñ âåñîì r r wm
� �� 1ïî C m
r
�
�
1
1 âåêòîðó.
Èñõîäÿ èç ýòîãî, âñå ãðóïïû ìîæíî ðàçäåëèòü íà ÷åòûðå êàòåãîðèè:
1) ãðóïïà, îòêóäà íå çàáèðàëè è êóäà íå äîáàâëÿëè âåêòîðû — êîíò-
ðîëüíàÿ ãðóïïà r = 0;
2) ãðóïïû, îòêóäà çàáèðàëè âåêòîðû, íî êóäà èõ íå äîáàâëÿëè —
r �1 2, ,..., �r wm� �1 2 1, ,...,( );
3) ãðóïïû, îòêóäà çàáèðàëè è êóäà äîáàâëÿëè âåêòîðû èç ïðåäûäóùèõ
ãðóïï — r w w mm m�
, , ...,1 ;
4) ãðóïïû, êóäà òîëüêî ïåðåìåùàëèñü âåêòîðû — r m m m�
, , ...,1
�
��r m m wm, , ...,( )1 1 .
Îòñþäà ñëåäóåò ïðèíöèï ïîäñ÷åòà íåîáíàðóæèâàåìûõ îøèáîê â
èíôîðìàöèîííûõ âåêòîðàõ ðàññìàòðèâàåìûõ êîäîâ. Â ãðóïïàõ ñ âåñîì
r �0 è r m wm�
�( )1 ïî îäíîìó âåêòîðó — â íèõ íåîáíàðóæèâàåìûå
îøèáêè íå âîçíèêàþò. Îáùåå ÷èñëî íåîáíàðóæèâàåìûõ îøèáîê ÿâëÿåòñÿ
ñóììîé íåîáíàðóæèâàåìûõ îøèáîê îñòàâøèõñÿ òðåõ êàòåãîðèé ãðóïï:
N N N N N N N Nm m m m m m m m�
�
, , , , , , ,1 2 3 4 2 3 4, ãäå N m i, — ñóììàðíîå
÷èñëî íåîáíàðóæèâàåìûõ îøèáîê âî âñåõ ãðóïïàõ ÷åòûðåõ êàòåãîðèé
( ),N m 1 0� .
 ïåðâîé ãðóïïå íàõîäèòñÿ C m
0 âåêòîð; â ãðóïïàõ âòîðîé êàòåãîðèè —
C Cm
r
m
r� �
�
1
1 , ãäå r wm� �1 2 1, ,...,( ); â ãðóïïàõ òðåòüåé êàòåãîðèè — C Cm
r
m
r�
�
�
1
1
�
� � �C
m
r wm
1
1 1( ) , r w w mm m�
, , ...,1 ; â ãðóïïàõ ÷åòâåðòîé êàòåãîðèè —C
m
r wm
�
� � �
1
1 1( ) ,
ãäå r m m wm�
�, , ...,( )1 1 . Îòñþäà ñëåäóþò ôîðìóëû ðàñ÷åòà ÷èñëà íåîáíà-
ðóæèâàåìûõ îøèáîê ïî ãðóïïàì êàæäîé êàòåãîðèè:
N Cm m,1
0 0� � ,
Èññëåäîâàíèå ñâîéñòâ êîäîâ ñ ñóììèðîâàíèåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 1 31
Ãðóïïû êîíòðîëüíûõ âåêòîðîâ ïðè r
0 1 2 3 4 5 6 7
C4
0 C C4
1
3
0� C C4
2
3
1� C C4
3
3
2� C C4
4
3
3�
C3
0 C3
1 C3
2 C3
3
1 3 3 2 3 3 1 0
Òàáëèöà 2
N C C C Cm
r
w
m
r
m
r
m
r
m
r
m
, ( ) ( )2
1
1
1
1
1
1 1� � � �
�
�
�
�
�
�� ,
N C C C C C Cm
r w
m
m
r
m
r
m
r w
m
r
m
r
m
m
m
, ( )(3 1
1
1 1
1
1
� �
�
�
�
�
�
�
�
�
�� r wm� �1) ,
N C Cm
r m
m w
m
r w
m
r w
r m
m wm
m m
m
, ( )4
1
1
1 1
1
2
1� � �
�
�
�
�
�
�
�
�
� � C C
m
r w
m
r wm m
�
�
�
� �
1 1
1( ) . (2)
 âûðàæåíèè (2) âåðõíèé ïðåäåë ñóììèðîâàíèÿ óìåíüøåí íà åäèíèöó, òàê
êàê â ïîñëåäíåé êîíòðîëüíîé ãðóïïå íàõîäèòñÿ îäèí âåêòîð, íå îïðåäå-
ëÿþùèé íåîáíàðóæèâàåìûõ îøèáîê. Îáùàÿ ôîðìóëà äëÿ ðàñ÷åòà ÷èñëà
íåîáíàðóæèâàåìûõ îøèáîê âî âçâåøåííûõ êîäàõ ñ ñóììèðîâàíèåì èìååò
ñëåäóþùèé âèä:
N C C C C Cm
r
w
m
r
m
r
m
r
m
r
r w
m
m
r
m
m
� � � �
�
�
�
�
�
�
�
� �
1
1
1
1
1
1 1( ) ( ) ( �
�
�C m
r
1
1
�
�
�
�
�
�
�
�
�
�
��C C C C C
m
r w
m
r
m
r
m
r w
r m
m w
m
m m
m
1 1
1
1
1
2
1)( )
1 1
1r w
m
r wm mC�
�
� �( ). (3)
Ïîëüçóÿñü ïðåäëîæåííûìè ôîðìóëàìè, ðàññ÷èòàåì çíà÷åíèå Nm äëÿ
êîäà ñ ñóììèðîâàíèåì, èìåþùåãî îäèí âçâåøåííûé èíôîðìàöèîííûé
ðàçðÿä wm = 3:
N C C C C C
r
w
m
r
m
r
m
r
m
r
r
m
4 2
1
1
1
1
1
1
1
2
41, ( ) ( ) (� � � � �
�
�
�
�
�
�
�
� � r r r rC C C� � � �� �
3
1
4 3
1 1) ( )
� � � �
� � � � �
�( ) ( ) ( ) ( )C C C C C C C C4
1
3
0
4
1
3
0
4
2
3
1
4
2
3
11 1 3 2 3 2 �12 ,
N C C C C C C
r w
m
m
r
m
r
m
r w
m
r
m
r
m
m
m
4 3 1
1
1 1
1
1, ( ) (� �
�
�
�
�
�
�
�
�
�� r wm� � �1)
� �
�
� �
�
� � � ��
r
r r r r r rC C C C C C
3
4
4 3
1
3
3
4 3
1
3
3 1( ) ( )
� �
�
�
�
�( ) ( ) ( ) (C C C C C C C C C C C4
3
3
2
3
0
4
3
3
2
3
0
4
4
3
3
3
1
4
4
31 3
3
1 1
� �C )
� �
� �2 1 3 2 8 ,
N C C C C
r m
m w
m
r w
m
r w
r
r
m
m m
4 4
1
2
1 1
5
5
3
31, ( ) (� � �
�
�
�
�
�
�
�
�� � 3
3
3
2
3
21 1 3 2 6r C C� � � � � � �) ( ) ,
N N N Nm m m4 2 3 4 12 8 6 26�
�
�, , , .
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ, Ä.À. Íèêèòèí
32 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 1
Ôîðìóëà (3) äàåò âîçìîæíîñòü îïðåäåëèòü Nm â ëþáûõ êîäàõ ñ ñóì-
ìèðîâàíèåì, ó êîòîðûõ âçâåøåí òîëüêî îäèí èíôîðìàöèîííûé ðàçðÿä. Åå
íåäîñòàòêîì ñëåäóåò ïðèçíàòü íåâîçìîæíîñòü ïîäñ÷åòà ÷èñëà íåîáíà-
ðóæèâàåìûõ îøèáîê ïî êðàòíîñòÿì.
Ñâîéñòâà âçâåøåííûõ êîäîâ ñ ñóììèðîâàíèåì. Äëÿ ðàññìàòðèâàå-
ìîãî êëàññà âçâåøåííûõ êîäîâ ñïðàâåäëèâû ñëåäóþùèå óòâåðæäåíèÿ.
Óòâåðæäåíèå 1. Ñâîéñòâà êîäà ñ ñóììèðîâàíèåì ñ îäíèì âçâåøåí-
íûì ðàçðÿäîì çàâèñÿò îò âåñà âçâåøåííîãî ðàçðÿäà, íî íå çàâèñÿò îò åãî
ìåñòîïîëîæåíèÿ â èíôîðìàöèîííîì âåêòîðå.
Äëÿ õàðàêòåðèñòèê êîäîâ èñïîëüçóþòñÿ âñå 2m èíôîðìàöèîííûõ
âåêòîðîâ, ïðè ýòîì âñå èíôîðìàöèîííûå ðàçðÿäû ïðèíèìàþò íà 2 1m�
âåêòîðàõ åäèíè÷íûå çíà÷åíèÿ è íà òàêîì æå ÷èñëå âåêòîðîâ — íóëåâûå
çíà÷åíèÿ. Âçâåøèâàíèå îäíîãî èíôîðìàöèîííîãî ðàçðÿäà âñåãäà ïðèâî-
äèò ê óâåëè÷åíèþ âåñà 2 1m� èíôîðìàöèîííûõ âåêòîðîâ íà âåëè÷èíó wi �1
(ýòî ñëåäóåò èç òîãî ôàêòà, ÷òî âåñ èìååò çíà÷åíèå òîëüêî äëÿ åäèíè÷íîãî
èíôîðìàöèîííîãî ðàçðÿäà). Ïîñêîëüêó ìåñòîïîëîæåíèå âçâåøåííîãî ðàç-
ðÿäà íå èìååò çíà÷åíèÿ, êîäû ñ ñóììèðîâàíèåì, èìåþùèå òîëüêî îäèí
âçâåøåííûé ðàçðÿä, ìîæíî îáîçíà÷èòü êàê WS n m wi( , , )-êîäû.
Óòâåðæäåíèå 2.WS n m wi( , , )-êîäû ïðè w m� èìåþò îäèíàêîâûå ðàñ-
ïðåäåëåíèÿ íåîáíàðóæèâàåìûõ îøèáîê ïî êðàòíîñòÿì.
Ïóñòü âçâåøåí òîëüêî ìëàäøèé êîíòðîëüíûé ðàçðÿä, ïðè ýòîì wi = m.
Ýòî îçíà÷àåò, ÷òî ïî ñðàâíåíèþ ñ êëàññè÷åñêèì êîäîì ñ ñóììèðîâàíèåì â
ðàñïðåäåëåíèè èíôîðìàöèîííûõ âåêòîðîâ îòíîñèòåëüíî êîíòðîëüíûõ âñå
êîäîâûå ñëîâà, èìåþùèå â êà÷åñòâå ìëàäøåãî èíôîðìàöèîííîãî ðàçðÿäà
åäèíèöó, áóäóò ñìåùåíû ïðè ðàñïðåäåëåíèè íà âåëè÷èíó m. Äàííûå êîäî-
âûå âåêòîðû ïåðåìåùàþòñÿ â ãðóïïû r + m, ãäå r — èñòèííûé âåñ èíôîð-
ìàöèîííîãî âåêòîðà. Èç ãðóïïû r = 1 ñìåùàåòñÿ îäèí êîäîâûé âåêòîð, ïå-
ðåìåùàÿñü â ãðóïïó r = 1 + m, ò.å. îí áóäåò åäèíñòâåííûì â ãðóïïå. Èç
ïîñëåäóþùèõ ãðóïï ïåðåìåùàþòñÿ ðîâíî ïî C m
r
�
�
1
1 èíôîðìàöèîííûõ âåê-
òîðîâ, êàæäûé èç êîòîðûõ çàíèìàåò ïóñòóþùóþ ãðóïïó ñ èíäåêñîì r + m.
Òàêèì îáðàçîì, ïîëîâèíà âåêòîðîâ èç òàáëèöû ðàñïðåäåëåíèÿ (òàê êàê
ìëàäøèé ðàçðÿä ðàâåí åäèíèöå ó 2 1m� âåêòîðîâ) áóäåò ïåðåìåùåíà â íî-
âûå, äî ýòîãî ïóñòûå, êîíòðîëüíûå ãðóïïû.
Äëÿ ïîäòâåðæäåíèÿ èçëîæåííîãî â òàáë. 3 è 4 ïðèâåäåíû ðàñïðåäåëå-
íèÿ èíôîðìàöèîííûõ âåêòîðîâ íà êîíòðîëüíûå ãðóïïû â êëàññè÷åñêîì
S (8, 5)-êîäå è âî âçâåøåííîì êîäå WS (9, 5, 5). Â ýòèõ òàáëèöàõ ïåðåä
êîñîé ÷åðòîé óêàçàíî çíà÷åíèå r, ïîñëå ÷åðòû — çíà÷åíèÿ ðàçðÿäîâ êîíò-
ðîëüíîãî âåêòîðà. Ïðè w mi � ïðîèçîéäåò åùå áîëüøåå ñìåùåíèå èíôîð-
ìàöèîííûõ âåêòîðîâ âïðàâî è ïîÿâÿòñÿ ïóñòûå ãðóïïû. Íàïðèìåð, åñëè
w mi �
1, òî åäèíñòâåííûé âåêòîð êîíòðîëüíîé ãðóïïû ñ âåñîì r = 1 áóäåò
Èññëåäîâàíèå ñâîéñòâ êîäîâ ñ ñóììèðîâàíèåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 1 33
ïåðåìåùåí â ãðóïïó r = 1 + m + 1 = m + 2, à ãðóïïà ñ r = 1 + m îñòàíåòñÿ
ïóñòîé. Âñå îñòàëüíûå èíôîðìàöèîííûå âåêòîðû áóäóò ñìåùåíû â ãðóï-
ïû ñ åùå áîëüøèìè íîìåðàìè. Òàêèì îáðàçîì, ðàñïðåäåëåíèÿ íåîáíàðó-
æèâàåìûõ îøèáîê âî âñåõ êîäàõ ñ w mi � áóäóò îäèíàêîâûìè. Áîëåå òîãî,
òàêèå êîäû áóäóò èìåòü ìèíèìàëüíîå çíà÷åíèå Nm äëÿ äàííîé äëèíû
èíôîðìàöèîííîãî âåêòîðà ñðåäè âñåõ WS n m wi( , , )-êîäîâ. Ýòèì îáúÿñ-
íÿåòñÿ óòâåðæäåíèå 2.
Èç óòâåðæäåíèé 1 è 2 âûòåêàåò ñëåäóþùåå óòâåðæäåíèå.
Óòâåðæäåíèå 3. Äëÿ ëþáîãî m íåçàâèñèìî îò çíà÷åíèÿ wi ñóùåñòâóåò
ðîâíî m WS n m wi( , , )-êîäîâ ñ ðàçëè÷íûìè ðàñïðåäåëåíèÿìè íåîáíàðóæè-
âàåìûõ îøèáîê ïî êðàòíîñòÿì.
ÄëÿWS n m wi( , , )-êîäîâ ñïðàâåäëèâî ñëåäóþùåå âàæíîå ñâîéñòâî.
Óòâåðæäåíèå 4. ËþáîéWS n m wi( , , )-êîä îáíàðóæèâàåò âñå îäíîíàï-
ðàâëåííûå èñêàæåíèÿ â èíôîðìàöèîííûõ âåêòîðàõ.
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ, Ä.À. Íèêèòèí
34 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 1
Êîíòðîëüíûå ãðóïïû WS (9, 5, 5)-êîäà
0 / 0000 1 / 0001 2 / 0010 3 / 0011 4 / 0100 5 / 0101 6 / 0110 7 / 0111 8 / 1000 9 / 1001
00000 00010 00110 01110 11110 00001 00011 00111 01111 11111
00100 01010 10110 00101 01011 10111
01000 01100 11010 01001 01101 11011
10000 10010 11100 10001 10011 11101
10100 10101
11000 11001
Òàáëèöà 4
Êîíòðîëüíûå ãðóïïû S (8, 5)-êîäà
0 / 000 1 / 001 2 / 010 3 / 011 4 / 100 5 / 101
00000 00001 00011 00111 11110 11111
00010 00101 01011 01111
00100 00110 01101 10111
01000 01001 01110 11011
10000 01010 10011 11101
01100 10101
10001 10110
10010 11001
10100 11010
11000 11100
Òàáëèöà 3
Èçâåñòíî, ÷òî êëàññè÷åñêèé êîä ñ ñóììèðîâàíèåì îáíàðóæèâàåò ëþ-
áûå îäíîíàïðàâëåííûå èñêàæåíèÿ, òàê êàê îäíîìó êîíòðîëüíîìó ñëîâó
ñîîòâåòñòâóþò èíôîðìàöèîííûå âåêòîðû ñ îäèíàêîâûì ÷èñëîì åäèíèö
(îäèíàêîâûì âåñîì r). Êîä ñ ñóììèðîâàíèåì ñ îäíèì âçâåøåííûì ðàçðÿ-
äîì âñåãäà èìååò â êîíòðîëüíîé ãðóïïå ñ âåñîì r èíôîðìàöèîííûå âåêòî-
ðû ñ âåñîì, ñîîòâåòñòâóþùèì íîìåðó êîíòðîëüíîé ãðóïïû èëè áîëüøèì,
÷åì íîìåð êîíòðîëüíîé ãðóïïû.  ýòîì ñëó÷àå âñå ïåðåõîäû ìåæäó
èíôîðìàöèîííûìè âåêòîðàìè îäíîé êîíòðîëüíîé ãðóïïû áóäóò ðàçíî-
íàïðàâëåííûìè.
Ñ èñïîëüçîâàíèåì ñïåöèàëüíî ðàçðàáîòàííîãî ïðîãðàììíîãî îáåñïå-
÷åíèÿ, îñíîâàííîãî íà àíàëèçå òàáëè÷íîé ôîðìû çàäàíèÿ êîäà, äëÿ
WS n m wi( , , )-êîäîâ ðàññ÷èòàíû õàðàêòåðèñòèêè îáíàðóæåíèÿ èñêàæåíèé â
èíôîðìàöèîííûõ âåêòîðàõ ïðè èõ äëèíàõ m = 3 � 20. Õàðàêòåðèñòèêè âçâå-
Èññëåäîâàíèå ñâîéñòâ êîäîâ ñ ñóììèðîâàíèåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 1 35
wi k
×èñëî íåîáíàðóæèâàåìûõ îøèáîê êðàòíîñòè d
N m � �
1 2 3 4 5 6 7 8 9
Ïðè m = 8
1 4 0 3584 0 6720 0 2240 0 70 — 12614 0,1932 0,3044
2 4 0 2688 1344 3360 2240 560 420 0 — 10612 0,1626 0,3619
3 4 0 2688 0 4480 0 1400 0 42 — 8610 0,1319 0,446
4 4 0 2688 0 3360 560 560 168 0 — 7336 0,1124 0,5234
5 4 0 2688 0 3360 0 728 0 14 — 6790 0,104 0,5655
6 4 0 2688 0 3360 0 560 28 0 — 6636 0,1017 0,5787
7 4 0 2688 0 3360 0 560 0 2 — 6610 0,1013 0,5809
8 4 0 2688 0 3360 0 560 0 0 — 6608 0,1012 0,5811
Ïðè m = 9
1 4 0 9216 0 24192 0 13440 0 1260 0 48108 0,1839 0,3299
2 4 0 7168 3584 13440 8960 4480 3360 140 112 41244 0,1576 0,3848
3 4 0 7168 0 17024 0 8960 0 812 0 33964 0,1298 0,4673
4 4 0 7168 0 13440 2240 4480 1344 140 56 28868 0,1103 0,5498
5 4 0 7168 0 13440 0 5376 0 364 0 26348 0,1007 0,6024
6 4 0 7168 0 13440 0 4480 224 140 16 25468 0,0973 0,6232
7 4 0 7168 0 13440 0 4480 0 172 0 25260 0,0965 0,6283
8 5 0 7168 0 13440 0 4480 0 140 2 25230 0,0964 0,3044
9 5 0 7168 0 13440 0 4480 0 140 0 25228 0,0964 0,3044
Òàáëèöà 5
øåííûõ êîäîâ ñ äëèíàìè èíôîðìàöèîííûõ âåêòîðîâ m = 8 è m = 9 ïðè-
âåäåíû â òàáë. 5, èç êîòîðîé âèäåí ýôôåêò âçâåøèâàíèÿ îäíîãî èíôîðìà-
öèîííîãî ðàçðÿäà, à èìåííî: íîâûå êîäû îáíàðóæèâàþò çíà÷èòåëüíî
áîëüøå èñêàæåíèé â èíôîðìàöèîííûõ âåêòîðàõ, ÷åì êëàññè÷åñêèå êîäû
Áåðãåðà.
 ðåçóëüòàòå àíàëèçà òàáëèö õàðàêòåðèñòèê êîäîâ ñ ñóììèðîâàíèåì
îïðåäåëåíû ñëåäóþùèå ñâîéñòâà WS n m wi( , , )-êîäîâ:
1. Ñ óâåëè÷åíèåì âåñà wi çíà÷åíèå Nm â èíôîðìàöèîííûõ âåêòîðàõ
óìåíüøàåòñÿ, äîñòèãàÿ ìèíèìóìà äëÿ çàäàííîãî çíà÷åíèÿ m ïðè wi = m.
2. Åñëè wi — íå÷åòíîå ÷èñëî, òî êîä ñ ñóììèðîâàíèåì íå èìååò íåîá-
íàðóæèâàåìûõ èñêàæåíèé íå÷åòíîé êðàòíîñòè [29].
3. Äëÿ çàäàííîãî çíà÷åíèÿ m âñå âçâåøåííûå êîäû ñ ÷åòíûìè çíà-
÷åíèÿìè wi èìåþò îäèíàêîâîå ÷èñëî èñêàæåíèé ÷åòíûõ êðàòíîñòåé d.
4. Âçâåøåííûé êîä ñ ñóììèðîâàíèåì WS n m wi( , , ) îáíàðóæèâàåò ëþ-
áûå èñêàæåíèÿ íå÷åòíîé êðàòíîñòè ïðè wi = m.
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ, Ä.À. Íèêèòèí
36 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 1
m
×èñëî íåîáíàðóæèâàåìûõ îøèáîê
â êîäàõ ñ ñóììèðîâàíèåì �
×èñëî äâóêðàòíûõ
íåîáíàðóæèâàåìûõ îøèáîê â êîäàõ
ñ ñóììèðîâàíèåì �2
S n m( , ) WS n m m( , , ) S n m( , ) WS n m wi( , , )
3 12 4 3 12 4 3
4 54 24 2,25 48 24 2
5 220 108 2,037 160 96 1,667
6 860 440 1,955 480 320 1,5
7 3304 1720 1,921 1344 960 1,4
8 12614 6608 1,909 3584 2688 1,333
9 48108 25228 1,907 9216 7168 1,286
10 183732 96216 1,91 23040 18432 1,25
11 703384 367464 1,914 56320 46080 1,222
12 2700060 1406768 1,919 135168 112640 1,2
13 10392408 5400120 1,924 319488 270336 1,182
14 40100216 20784816 1,929 745472 638976 1,167
15 155084752 80200432 1,934 1720320 1490944 1,154
16 601014854 310169504 1,938 3932160 3440640 1,143
17 2333475148 1202029708 1,941 8912896 7864320 1,133
18 9074873156 4666950296 1,944 20054016 17825792 1,125
19 35344739512 18149746312 1,947 44826624 40108032 1,118
20 137845480244 70689479024 1,95 99614720 89653248 1,111
Òàáëèöà 6
5. Ó âçâåøåííûõ êîäîâ ñ ñóììèðîâàíèåì ñ îäíèì âçâåøåííûì èíôîð-
ìàöèîííûì ðàçðÿäîì ïðè äàííîì çíà÷åíèè m âñåãäà îäèíàêîâîå ÷èñëî íåîá-
íàðóæèâàåìûõ îøèáîê ÷åòíûõ êðàòíîñòåé, â ÷àñòíîñòè ïðè w di � , âñå êîäû
èìåþò îäèíàêîâîå ÷èñëî äâóêðàòíûõ íåîáíàðóæèâàåìûõ èñêàæåíèé.
6. Âñå êîäû, êðîìå êîäà ñ wi �2, îáíàðóæèâàþò ëþáûå èñêàæåíèÿ
êðàòíîñòè d = 3.
7. Åñëè m — íå÷åòíîå, òî êîäû ñ íå÷åòíûìè çíà÷åíèÿìè wi íå èìåþò
íåîáíàðóæèâàåìûõ îøèáîê ìàêñèìàëüíîé êðàòíîñòè d m� ; åñëè m — ÷åò-
íîå, òî êîäû ñ ÷åòíûìè çíà÷åíèÿìè wi íå èìåþò íåîáíàðóæèâàåìûõ îøè-
áîê ìàêñèìàëüíîé êðàòíîñòè d m� .
8. Äëÿ êîäîâ, íå óäîâëåòâîðÿþùèõ ñâîéñòâó 7, ïðè çàäàííîì çíà÷åíèè
m ñ óâåëè÷åíèåì çíà÷åíèÿ wi ÷èñëî íåîáíàðóæèâàåìûõ èñêàæåíèé êðàò-
íîñòè d m� óìåíüøàåòñÿ, äîñòèãàÿ ìèíèìóìà (Nm = 2) ïðè w mi � �1.
9. Êîä ìàêñèìàëüíî ýôôåêòèâåí äëÿ çàäàííîé äëèíû èíôîðìàöèîí-
íîãî âåêòîðà, åñëè ÷èñëî êîíòðîëüíûõ ðàçðÿäîâ â íåì � k m�
log ( )2 1 è
âûïîëíÿåòñÿ óñëîâèå
i
m
i
kw
�
� � �
1
2 1.
 òàáë. 6 ïðèâåäåíû çíà÷åíèÿ ÷èñëà íåîáíàðóæèâàåìûõ îøèáîê èí-
ôîðìàöèîííûõ âåêòîðîâ â êëàññè÷åñêèõ êîäàõ Áåðãåðà è âçâåøåííûõ
êîäàõ ñ w mi � , ìàêñèìàëüíî ýôôåêòèâíî îáíàðóæèâàþùèõ îøèáêè â
èíôîðìàöèîííûõ âåêòîðàõ. Çíà÷åíèÿ � ïîêàçûâàþò, âî ñêîëüêî ðàç áîëü-
øå îøèáîê îáíàðóæèâàåò âçâåøåííûé êîä â èíôîðìàöèîííûõ âåêòîðàõ.
Èç ðèñ. 3 âèäíî, ÷òî âåëè÷èíà � ïðàêòè÷åñêè äëÿ âñåõ âçâåøåííûõ êîäîâ
áëèçêà ê çíà÷åíèþ � = 2 è èìååò ìèíèìóì ïðè m = 9.
Èññëåäîâàíèå ñâîéñòâ êîäîâ ñ ñóììèðîâàíèåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 1 37
Ðèñ. 3. Ãðàôèê çàâèñèìîñòè âåëè÷èíû � îò äëèíû èíôîðìàöèîííîãî âåêòîðà
 òàáë. 7 ïðèâåäåíû ðåçóëüòàòû ñðàâíåíèÿ êîäîâ S n m( , ) èWS n m m( , , )
ïî ÷èñëó íåîáíàðóæèâàåìûõ èñêàæåíèé ÷åòíîé êðàòíîñòè ïðè m = 8 è m = 9.
Âåëè÷èíà � îïðåäåëÿåò îòíîøåíèå ÷èñëà íåîáíàðóæèâàåìûõ îøèáîê ïî
êðàòíîñòÿì d â S n m( , ) è WS n m m( , , )-êîäàõ. Êàê âèäíî èç òàáë. 7, âçâåøåí-
íûå êîäû ïðåâîñõîäÿò êëàññè÷åñêèå êîäû ñ ñóììèðîâàíèåì ïî ñïîñîá-
íîñòè îáíàðóæåíèÿ îøèáîê ëþáûõ ÷åòíûõ êðàòíîñòåé. Òàêàÿ çàâèñèìîñòü
ñîõðàíÿåòñÿ è ïðè äðóãèõ çíà÷åíèÿõ m. Ñëåäîâàòåëüíî, ìîæíî ñ÷èòàòü, ÷òî
äëÿ ëþáîãî çíà÷åíèÿ m âåëè÷èíà � â êîäàõ S n m( , ) è WS n m m( , , ) óâåëè-
÷èâàåòñÿ ñ óâåëè÷åíèåì çíà÷åíèÿ d. Ýòî îçíà÷àåò, ÷òî âçâåøåííûå êîäû ñ
ñóììèðîâàíèåì ìàêñèìàëüíî ýôôåêòèâíû â îáëàñòè îáíàðóæåíèÿ îøè-
áîê áîëüøèõ êðàòíîñòåé.
Ñîãëàñíî ñâîéñòâó 3 âñå WS n m wi( , , )-êîäû èìåþò îäèíàêîâîå ÷èñëî
íåîáíàðóæèâàåìûõ äâóêðàòíûõ èñêàæåíèé èíôîðìàöèîííûõ ðàçðÿäîâ.
Âåëè÷èíà �2 â òàáë. 6 îïðåäåëÿåò çíà÷åíèå îòíîøåíèÿ ÷èñëà íåîáíàðóæè-
âàåìûõ äâóêðàòíûõ îøèáîê â S n m( , )-êîäàõ ê àíàëîãè÷íîé âåëè÷èíå â
WS n m wi( , , )-êîäàõ. Êàê âèäíî èç òàáë. 6, ñ óâåëè÷åíèåì äëèíû èíôîð-
ìàöèîííîãî âåêòîðà ÷èñëî íåîáíàðóæèâàåìûõ îøèáîê êðàòíîñòè d = 2 â
êëàññè÷åñêèõ è âçâåøåííûõ êîäàõ ñòàíîâèòñÿ ïî÷òè îäèíàêîâûì.
Èçâåñòíî [19], ÷òî äîëÿ íåîáíàðóæèâàåìûõ èñêàæåíèé ÷åòíîé êðàò-
íîñòè d îò îáùåãî ÷èñëà èñêàæåíèé äàííîé êðàòíîñòè äëÿ ëþáîãî êîäà
Áåðãåðà ÿâëÿåòñÿ ïîñòîÿííîé âåëè÷èíîé:
�d
d
d
dC� �2 2/ . (4)
Èç ôîðìóëû (4) ñëåäóåò, ÷òî ëþáîé êîä Áåðãåðà íå îáíàðóæèâàåò 50%
äâóêðàòíûõ èñêàæåíèé. Ñëåäóåò çàìåòèòü, ÷òîWS n m wi( , , )-êîäû íå îáíà-
ðóæèâàþò ìåíüøåå ÷èñëî äâóêðàòíûõ èñêàæåíèé â èíôîðìàöèîííûõ ðàç-
ðÿäàõ (ñì. òàáë. 6).  äèàïàçîíå m = 3 � 20 âåëè÷èíà�d èçìåíÿåòñÿ â ïðåäåëàõ
îò 0,167 äî 0,45. Ñ óâåëè÷åíèåì äëèíû m äîëÿ äâóêðàòíûõ íåîáíàðóæèâàå-
ìûõ èñêàæåíèé ïðèáëèæàåòñÿ ê âåëè÷èíå äëÿ êîäà Áåðãåðà �d �05, .
Òåñòåð âçâåøåííîãî êîäà ñ ñóììèðîâàíèåì (ðèñ. 4, à) ñòðóêòóðíî
ïîäðàçäåëÿåòñÿ íà ãåíåðàòîð êîíòðîëüíûõ ðàçðÿäîâ G è êîìïàðàòîð TRC.
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ, Ä.À. Íèêèòèí
38 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 1
×èñëî íåîáíàðóæèâàåìûõ
îøèáîê êðàòíîñòè d
m = 8 m = 9
wi � 1 wi � 8 � wi � 1 wi � 9 �
2 3584 2688 1,333 9216 7168 1,286
4 6720 3360 2 24192 13440 1,8
6 2240 560 4 13440 4480 3
8 70 0 — 1260 140 9
Òàáëèöà 7
Ãåíåðàòîð ïî çíà÷åíèÿì âûõîäîâ áëîêà îñíîâíîé ëîãèêè âû÷èñëÿåò çíà-
÷åíèÿ êîíòðîëüíûõ ðàçðÿäîâ �g1, �g 2, …, �g k , à êîìïàðàòîð âûïîëíÿåò ñðàâ-
íåíèå ïîëó÷åííûõ ôóíêöèé ñ ôóíêöèÿìè, âû÷èñëåííûìè â áëîêå ÊË, g1,
g 2, …, g k (ïîñëåäíèå ïðåäâàðèòåëüíî èíâåðòèðóþòñÿ). Åñëè îòñóòñòâóþò
íåèñïðàâíîñòè, â áëîêå îñíîâíîé ëîãèêè óñòàíàâëèâàåòñÿ ñëåäóþùåå
ñîîòâåòñòâèå: � �g gj j . Ýòî ïîçâîëÿåò ñòðîèòü êîìïàðàòîð â âèäå êàñêàä-
íîãî ñîåäèíåíèÿ ìîäóëåé ñðàâíåíèÿ ïàðàôàçíûõ ñèãíàëîâ TRC (two-rail
checker) [3, 8]. Òåñòåð ñíàáæåí äâóìÿ âûõîäàìè, z1 è z2, êîòîðûå ïðèíè-
ìàþò íåïàðàôàçíûå çíà÷åíèÿ 00 èëè 11 â ñëó÷àå íàëè÷èÿ äåôåêòà â ñèñ-
òåìå ôóíêöèîíàëüíîãî êîíòðîëÿ [10].
Ñèíòåç ãåíåðàòîðîâ êîäîâ ñ ñóììèðîâàíèåì óäîáíî îñóùåñòâëÿòü,
èñïîëüçóÿ ìîäóëè ïîëíûõ ñóììàòîðîâ FA è ïîëóñóììàòîðîâ HA [30, 31].
Ïðè ýòîì ãåíåðàòîð óäîáíî ðàçäåëèòü íà òðè áëîêà (ðèñ. 4, á). Â ôóíêöèè
áëîêà G1 âõîäèò ïîëó÷åíèå ñóììû âåñà m – 1 íåâçâåøåííûõ èíôîðìà-
öèîííûõ ðàçðÿäîâ (áåç ïîòåðè îáùíîñòè ïðåäïîëîæèì, ÷òî âçâåøåí
ïîñëåäíèé èíôîðìàöèîííûé ðàçðÿä), âûðàæåííîãî äâîè÷íûì ÷èñëîì a =
= < a1 a2 … at >. Òàêîé áëîê ìîæåò áûòü ðåàëèçîâàí êàê ãåíåðàòîð èç-
âåñòíîãî êîäà Áåðãåðà ñ m – 1 èíôîðìàöèîííûì ðàçðÿäîì. Áëîê G2 ÿâëÿåò-
ñÿ ïðåîáðàçîâàòåëåì âåñà wi âçâåøåííîãî èíôîðìàöèîííîãî ðàçðÿäà â
äâîè÷íîå ÷èñëî b = < b1 b2 … br >. Áëîê G3 ñóììèðóåò äâà äâîè÷íûõ ÷èñëà,
a è b, òàê ÷òî íà åãî âûõîäàõ ôîðìèðóåòñÿ êîíòðîëüíûé âåêòîð.
Ðàññìîòðèì ïðîöåäóðó ñèíòåçà ãåíåðàòîðà íà ïðèìåðå WS (10, 6, 4)-
êîäà. Áëîê G1 ôîðìèðóåò ñóììó âåñîâ ïÿòè åäèíè÷íûõ èíôîðìàöèîííûõ
ðàçðÿäîâ è ñîîòâåòñòâóþùåå åé äâîè÷íîå òðåõðàçðÿäîå ÷èñëî a = < a1 a2 a3 >.
Âûõîäû áëîêà G2 îïðåäåëÿþò äâîè÷íîå ÷èñëî b = < b1 b2 b3 >, ñòàðøèé
Èññëåäîâàíèå ñâîéñòâ êîäîâ ñ ñóììèðîâàíèåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 1 39
f2f1
G
1g�
2g�
kg�
fm
TRC
g
1
g
2
gk
z1 z2
f2 f
1
fm fm –1
G1G2
G3
1g� 2g� kg�
a1 a2 at b1 b2 br
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . . . . .
à á
Ðèñ. 4. Ñòðóêòóðíûå ñõåìû òåñòåðà (à) è ãåíåðàòîðà êîíòðîëüíûõ âåêòîðîâ WS n m wi( , , )-
êîäîâ (á)
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ, Ä.À. Íèêèòèí
40 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 1
HA
1 1
2 1
FA
1 1
2 1
1
HA
1 1
2 1
FA
2 2
4 2
2
f1f4 f2f5 f3
11 010
0 1 01
0 1
10 1 00
10
a1 a2 a3
G1
f6
b3b2b1
1 0 0
G2
HA
1 1
2 1
FA
2 2
4 2
2
0 1
10 0 10
1
FA
4 4
8 4
4
0
01 0
10
g'1 g'2 g'3 g'4
G3
G2
a3b3a2a1b1 b2
HA
1 1
2 1
FA
1 1
2 1
1
HA
1 1
2 1
FA
2 2
4 2
2
f1f4 f2f5 f3
11 010
0 1 01
0 1
10 1 00
10
a1 a2 a3
G1
HA
1 1
2 1
FA
2 2
4 2
2
0 1
10 0 10
1
FA
4 4
8 4
4
0
01 0
10
g '1 g'2 g '3 g'4
G3
b1=f6
a3b3a2a1b1 b2
b3=0b2=0
à
â
HA
1 1
2 1
FA
1 1
2 1
1
HA
1 1
2 1
FA
2 2
4 2
2
f1f4 f2f5 f3
11 010
0 1 01
0 1
10 1 00
10
a1 a2 a3
G 1
11
HA
4 4
8 4
4
01
10
g �
1
g �
2
g �
3 g '
4
á
f6
Ðèñ. 5. Íåîïòèìèçèðîâàííàÿ (à) è óïðî-
ùåííàÿ (á, â) ñõåìû ñòðóêòóðû ãåíåðà-
òîðà WS (10, 6, 4)-êîäà: á — äî îïòèìè-
çàöèè; â — ïîñëå îïòèìèçàöèè
ðàçðÿä êîòîðîãî ðàâåí çíà÷åíèþ âçâåøåííîãî èíôîðìàöèîííîãî ðàçðÿäà,
à ìëàäøèå ðàçðÿäû ðàâíû íóëþ (ñëîæíîñòü áëîêà G2 ôàêòè÷åñêè ðàâíà
íóëþ). Áëîê G3 ñóììèðóåò ÷èñëà a è b. Íà ðèñ. 5, à, ïðåäñòàâëåíà ïîëó-
÷åííàÿ ñòðóêòóðà ãåíåðàòîðà WS (10, 6, 4)-êîäà è óñòàíîâëåíû ñèãíàëû
êàæäîé ëèíèè ñõåìû ïðè ãåíåðàöèè êîíòðîëüíîãî ñëîâà äëÿ èíôîðìà-
öèîííîãî âåêòîðà < 101101 >.
Îïòèìèçàöèÿ ñòðóêòóðû ãåíåðàòîðà âîçìîæíà, òàê êàê äâîè÷íîå ÷èñ-
ëî, ðàâíîå âåñó âçâåøåííîãî èíôîðìàöèîííîãî ðàçðÿäà, â íåêîòîðûõ ïî-
çèöèÿõ èìååò íóëåâûå çíà÷åíèÿ.  ïðîöåññå îïòèìèçàöèè ñòðóêòóðû ãåíå-
ðàòîðà (ðèñ. 5, á) áëîê G1 îñòàåòñÿ íåèçìåííûì, áëîê G2 óäàëÿåòñÿ è çà-
ìåíÿåòñÿ ââîäàìè ðàçðÿäîâ äâîè÷íîãî ÷èñëà b, áëîê G3 óïðîùàåòñÿ ñ
èñïîëüçîâàíèåì íóëåâûõ ðàçðÿäîâ äâîè÷íîãî ÷èñëà b (ðèñ. 5, â). Ãåíåðàòîð
êëàññè÷åñêîãî êîäà Áåðãåðà S (9, 6) ïîñòðîåí íà îñíîâå òðåõ ïîëíûõ ñóì-
ìàòîðîâ è îäíîãî ïîëóñóììàòîðà. Ïîëó÷åííûé â ðåçóëüòàòå îïòèìèçàöèè
ãåíåðàòîð WS (10, 6, 4)-êîäà ñîäåðæèò äâà ïîëíûõ ñóììàòîðà è òðè ïîëó-
ñóììàòîðà.
Îöåíèì ãåíåðàòîðû êîäîâ ñ ñóììèðîâàíèåì ïî ñëîæíîñòè — ÷èñëó
âõîäîâ âíóòðåííèõ ëîãè÷åñêèõ ýëåìåíòîâ [10]. Èçâåñòíî, ÷òî ñëîæíîñòü
ïîëíîãî ñóììàòîðà îïðåäåëÿåòñÿ âåëè÷èíîé LFA = 21, à ïîëóñóììàòîðà —
LHA = 8. Òîãäà ñëîæíîñòü ãåíåðàòîðà S (9, 6)-êîäà ñîñòàâëÿåò L1 = 71, à WS (10,
6, 4)-êîäà — L2 = 66. Îòñþäà ñëåäóåò, ÷òî â íåêîòîðûõ ñëó÷àÿõ ãåíåðàòîðû
âçâåøåííûõ êîäîâ ïîëó÷àþòñÿ áîëåå ïðîñòûìè, ÷åì ãåíåðàòîðû êëàññè-
÷åñêèõ êîäîâ ñ ñóììèðîâàíèåì ïðè îäèíàêîâîé äëèíå èíôîðìàöèîííîãî
âåêòîðà. Îäíàêî âûèãðûø â ñëîæíîñòè ïðè ýòîì íåáîëüøîé âñëåäñòâèå
ñëîæíîñòè êîìïàðàòîðà. Íàïðèìåð, çíàÿ, ÷òî ñëîæíîñòü îäíîãî ìîäóëÿ
TRC ñîñòàâëÿåò LTRC = 12 è ïðè ðåàëèçàöèè êîìïàðàòîðà äëÿ òðåõ êîíò-
ðîëüíûõ ðàçðÿäîâ òðåáóåòñÿ äâà ìîäóëÿ TRC, à äëÿ ÷åòûðåõ êîíòðîëüíûõ
ðàçðÿäîâ — òðè ìîäóëÿ TRC [10], çàêëþ÷àåì, ÷òî êîìïàðàòîð êîäà S (9, 6)
èìååò ñëîæíîñòü L3 = 24, à âçâåøåííîãî êîäà WS (10, 6, 4) — L4 = 36. Òàêèì
îáðàçîì, ïîëíûé òåñòåð êîäà Áåðãåðà èìååò ñëîæíîñòü, ðàâíóþ 95, à
âçâåøåííîãî êîäà — 102.
Ðåçóëüòàòû àíàëèçà ñòðóêòóð ãåíåðàòîðîâ WS n m wi( , , )-êîäîâ ñâèäå-
òåëüñòâóþò î òîì, ÷òî íàèáîëåå ïðîñòûå ãåíåðàòîðû ïîëó÷àþòñÿ äëÿ êî-
äîâ ñ ÷åòíûì çíà÷åíèåì wi. Ïðè ýòîì ñ óâåëè÷åíèåì âåñà óìåíüøàåòñÿ è
ñëîæíîñòü òåõíè÷åñêîé ðåàëèçàöèè ãåíåðàòîðà. Òàêèì îáðàçîì, ñïðàâåä-
ëèâî ñëåäóþùåå óòâåðæäåíèå.
Óòâåðæäåíèå 5. Åñëè âåñ èíôîðìàöèîííîãî ðàçðÿäà WS n m wi( , , )-
êîäà åñòü ñòåïåíü ÷èñëà äâà, òî ãåíåðàòîð òàêîãî êîäà èìååò ìèíèìàëüíóþ
ñëîæíîñòü.
Òåñòåð ïîäîáíûõ êîäîâ òàêæå ÿâëÿåòñÿ ìàêñèìàëüíî ïðîñòûì. Â òàáë.
8 ïðèâåäåíû âåëè÷èíû, õàðàêòåðèçóþùèå ñëîæíîñòü òåñòåðîâ âçâåøåí-
Èññëåäîâàíèå ñâîéñòâ êîäîâ ñ ñóììèðîâàíèåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 1 41
íûõ êîäîâ ïðè m = 8 è m = 9, à òàêæå ñëîæíîñòü ãåíåðàòîðîâ è êîìïàðàòî-
ðîâ. Çíà÷åíèÿ �L è � ñîîòâåòñòâåííî îïðåäåëÿþò âûèãðûø â ñëîæíîñòè ïî
ñðàâíåíèþ ñ òåñòåðîì êëàññè÷åñêîãî êîäà Áåðãåðà äëÿ çàäàííîé äëèíû
èíôîðìàöèîííîãî âåêòîðà è îòíîøåíèå ñëîæíîñòè òåñòåðà êîäà Áåðãåðà ê
ñëîæíîñòè òåñòåðà WS n m wi( , , )-êîäà. Ïðè m = 8 â áîëüøèíñòâå ñëó÷àåâ
óäàåòñÿ ïîëó÷èòü ìåíåå ñëîæíûé òåñòåð, ÷åì òåñòåð êîäà ñ ñóììèðîâàíèåì.
Ëþáîé òåñòåð âçâåøåííîãî êîäà ïðè m = 9 ñëîæíåå òåñòåðà êëàññè÷åñêîãî
êîäà Áåðãåðà, îäíàêî íåçíà÷èòåëüíî (â ñðåäíåì íà 12,3 %).
Íà îñíîâàíèè óòâåðæäåíèé 2 è 3 ìîæíî åùå áîëåå óïðîñòèòü òåñòåð
WS n m wi( , , )-êîäà. Ïóñòü m = 6. Ïîñòàâèì çàäà÷ó ïîëó÷èòü ìàêñèìàëüíî
ïðîñòóþ ñòðóêòóðó òåñòåðà äëÿ òàêîãî êîäà. Ñëîæíîñòü ãåíåðàòîðà êîäà
Áåðãåðà ñ m = 5 èíôîðìàöèîííûìè ðàçðÿäàìè ðàâíà 58. Ïðè ýòîì íà åãî
âûõîäàõ ôîðìèðóåòñÿ òðåõðàçðÿäíîå ÷èñëî a = < a1 a2 a3 >. Âûáåðåì
çíà÷åíèå wi òàêîå, ÷òîáû îíî âñåãäà äàâàëî ÷èñëî ñ òðåìÿ íóëåâûìè
ìëàäøèìè ðàçðÿäàìè, ò.å. b = < b1 0 0 0 > èëè wi = 8. Ïðè ñëîæåíèè ÷èñåë a
è b íå òðåáóåòñÿ äîïîëíèòåëüíîãî îáîðóäîâàíèÿ: ÷èñëî b1 áóäåò ñòàðøèì
ðàçðÿäîì â ñóììå a + b = < b1 a1 a2 a3 >. Òåñòåð òàêîãî êîäà ìàêñèìàëüíî
ïðîñò. Àíàëîãè÷íî ìîæíî ñôîðìóëèðîâàòü ñëåäóþùåå óòâåðæäåíèå.
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ, Ä.À. Íèêèòèí
42 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 1
m wi k Ãåíåðàòîð Êîìïàðàòîð Òåñòåð �L �
8 1 4 140 36 176 0 1
8 2 4 115 36 151 �25 0,858
8 3 4 136 36 172 �4 0,977
8 4 4 109 36 145 �31 0,824
8 5 4 138 36 161 �2 0,989
8 6 4 130 36 153 �10 0,943
8 7 4 151 36 187 11 1,063
8 8 4 101 36 137 �39 0,778
9 1 4 153 36 189 0 1
9 2 4 162 36 198 9 1,048
9 3 4 183 36 219 30 1,159
9 4 4 154 36 190 1 1,005
9 5 4 183 36 219 30 1,159
9 6 4 175 36 211 22 1,116
9 7 4 196 36 232 43 1,228
9 8 5 148 48 196 7 1,037
9 9 5 185 48 233 44 1,233
Òàáëèöà 8
Óòâåðæäåíèå 6. Äëÿ ëþáîãî ãåíåðàòîðàWS n m wi( , , )-êîäà ìîæíî ïî-
ëó÷èòü íàèáîëåå ïðîñòóþ òåõíè÷åñêóþ ðåàëèçàöèþ ïîäáîðîì âåñà âçâå-
øåííîãî èíôîðìàöèîííîãî ðàçðÿäà, ïðè ýòîì � wi
m�2 2log
.
Ñëîæíîñòü ïîëó÷àåìîãî ãåíåðàòîðàWS n m wi( , , )-êîäà ïðè � wi
m�2 2log
áóäåò ðàâíà ñëîæíîñòè ãåíåðàòîðà êîäà Áåðãåðà ñ m – 1 èíôîðìàöèîííûì
ðàçðÿäîì.
Óòâåðæäåíèå 6, îñíîâàííîå íà ñâîéñòâåWS n m wi( , , )-êîäîâ, äàåò âîçìîæ-
íîñòü ñèíòåçèðîâàòü òåñòåðû âçâåøåííûõ êîäîâ ñ ìèíèìàëüíîé ñëîæíîñòüþ.
Îïèñàííûé ïðîöåññ ñèíòåçà òåñòåðîâWS n m wi( , , )-êîäîâ íà îñíîâå ñòàíäàðò-
íûõ ìîäóëåé ãåíåðàòîðîâ êîäîâ Áåðãåðà ñ m – 1 èíôîðìàöèîííûì ðàçðÿäîì è
ñóììàòîðà äâîè÷íûõ ÷èñåë ÿâëÿåòñÿ ïðîñòûì è â íåêîòîðûõ ñëó÷àÿõ äàåò
âîçìîæíîñòü ïîëó÷èòü òåñòåðû ñ ìåíåå ñëîæíîé ñòðóêòóðîé ïî ñðàâíåíèþ ñî
ñòðóêòóðàìè òåñòåðîâ êëàññè÷åñêèõ êîäîâ ñ ñóììèðîâàíèåì.
Âûâîäû
Èñïîëüçóÿ òàáëèöû õàðàêòåðèñòèê âçâåøåííûõ êîäîâ ñ ñóììèðîâàíèåì, à
òàêæå óñòàíîâëåííûå äëÿ äàííûõ êîäîâ ñâîéñòâà îáíàðóæåíèÿ îøèáîê â
èíôîðìàöèîííûõ âåêòîðàõ, ìîæíî âûáèðàòü îïòèìàëüíûé âàðèàíò êîäè-
ðîâàíèÿ ñ ó÷åòîì îñîáåííîñòåé êîíòðîëèðóåìîãî ËÓ f (x).
Ëþáîé WS n m wi( , , )-êîä îáëàäàåò âàæíîé îñîáåííîñòüþ: îí îáíàðó-
æèâàåò ëþáûå îäíîíàïðàâëåííûå èñêàæåíèÿ â èíôîðìàöèîííûõ ðàçðÿäàõ
(ñì. óòâåðæäåíèå 4). Íàïðèìåð, ìîäóëüíûå è ìîäóëüíî-ìîäèôèöèðîâàííûå
êîäû [20—22, 33—35] íå ïîçâîëÿþò îáíàðóæèâàòü 100 % îäíîíàïðàâëåí-
íûõ íåîáíàðóæèâàåìûõ îøèáîê â èíôîðìàöèîííûõ âåêòîðàõ. Ëþáîé
WS n m wi( , , )-êîä ìîæåò áûòü ïðèìåíåí äëÿ ïîñòðîåíèÿ ñèñòåìû ôóíê-
öèîíàëüíîãî êîíòðîëÿ ïðîèçâîëüíîé êîìáèíàöèîííîé ñõåìû, êîòîðàÿ ëåãêî
ïðåîáðàçóåòñÿ â ñõåìó ñ ìîíîòîííî íåçàâèñèìûìè âûõîäàìè [2, 23, 24, 36].
Òàêèì îáðàçîì, ïðè ïîñòðîåíèè ñèñòåìû ôóíêöèîíàëüíîãî êîíòðîëÿ êîìáè-
íàöèîííîé ñõåìû ìîæåò áûòü ïðèìåíåíWS n m wi( , , )-êîä, îáëàäàþùèé îñíî-
âíûìè ñâîéñòâàìè êîäà Áåðãåðà, íî èìåþùèé ëó÷øèå õàðàêòåðèñòèêè îá-
íàðóæåíèÿ èñêàæåíèé â èíôîðìàöèîííûõ ðàçðÿäàõ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. McCluskey E.J. Logic Design Principles: With Emphasis on Testable Semicustom Circuits. —
N.J.: Prentice Hall PTR, 1986. — 549 p.
2. Ñîãîìîíÿí Å.Ñ., Ñëàáàêîâ Å.Â. Ñàìîïðîâåðÿåìûå óñòðîéñòâà è îòêàçîóñòîé÷èâûå
ñèñòåìû. — Ì. : Ðàäèî è ñâÿçü, 1989. — 208 ñ.
3. Lala P.K. Self-Checking and Fault-Tolerant Digital Design. — San Francisco: Morgan
Kaufmann Publishers, 2001. — 216 p.
4. Nicolaidis M., Zorian Y. On-Line Testing for VLSI — À Compendium of Approaches // Journal
of Electronic Testing: Theory and Applications. — 1998. — Vol. 12. — ¹ 2. — P. 7—20.
Èññëåäîâàíèå ñâîéñòâ êîäîâ ñ ñóììèðîâàíèåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 1 43
5. G��îessel M., Ocheretny V., Sogomonyan E., Marienfeld D. New Methods of Concurrent
Checking: Edition 1. — Dordrecht: Springer Science+Business Media B.V., 2008. — 184 p.
6. Ubar R., Raik J., Vierhaus H.-T. Design and Test Technology for Dependable Systems-on-Chip
(Premier Reference Source) // Information Science Reference, Hershey — New York, IGI
Global, 2011. — 578 p.
7. Wang L-T., Stroud C.E., Touba N.A. System-on-Chip Test Architectures: Nanometer Design
for Testability. — Morgan Kaufmann Publishers, 2008. — 856 p.
8. Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications. —
John Wiley & Sons, 2006. — 720 p.
9. Dutta A., Touba N.A. Synthesis of Non-Intrusive Concurrent Error Detection Using an Even
Error Detection Function // International test conf. (ITC). — 2005. — P. 1059—1066.
10. Ñàïîæíèêîâ Â.Â., Ñàïîæíèêîâ Âë.Â. Ñàìîïðîâåðÿåìûå äèñêðåòíûå óñòðîéñòâà. —
ÑÏá: Ýíåðãîàòîìèçäàò, 1992. — 224 ñ.
11. Àêñåíîâà Ã.Ï. Íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ ïîñòðîåíèÿ ïîëíîñòüþ ïðîâå-
ðÿåìûõ ñõåì ñâåðòêè ïî ìîäóëþ 2 // Àâòîìàòèêà è òåëåìåõàíèêà. — 1979. — ¹ 9. —
Ñ. 126—135.
12. Richter M., Goessel M. Concurrent Checking With Split-Parity Codes // Proc. of the 15th
IEEE International On-Line Testing Symposium (IOLTS). — Portugal, Sesimbra-Lisabon,
June 24—26, 2009. — P. 159—163.
13. Ñàïîæíèêîâ Â.Â., Ñàïîæíèêîâ Âë.Â., Äìèòðèåâ À.Â. è äð. Îðãàíèçàöèÿ ôóíêöèî-
íàëüíîãî êîíòðîëÿ êîìáèíàöèîííûõ ñõåì ìåòîäîì ëîãè÷åñêîãî äîïîëíåíèÿ //
Ýëåêòðîí. ìîäåëèðîâàíèå. — 2002. — 24, ¹ 6. — Ñ. 52—66.
14. Ïàðõîìåíêî Ï.Ï., Ñîãîìîíÿí Å.Ñ. Îñíîâû òåõíè÷åñêîé äèàãíîñòèêè (îïòèìèçàöèÿ
àëãîðèòìîâ äèàãíîñòèðîâàíèÿ, àïïàðàòóðíûå ñðåäñòâà). — Ì. : Ýíåðãîàòîìèçäàò,
1981. — 320 ñ.
15. Ðîìàùåíêî À.Å., Ðóìÿíöåâ À.Þ., Øåíü À. Çàìåòêè ïî òåîðèè êîäèðîâàíèÿ. — Ì.:
Èçä-âî ÌÖÍÌÎ, 2011. — 80 ñ.
16. Ìàòðîñîâà À.Þ., Áóòîðèíà Í.Á., ßêèìîâà Í.Î. Ñèíòåç äåòåêòîðîâ ðàâíîâåñíûõ
êîäîâ ñ èñïîëüçîâàíèåì ìîíîòîííûõ ôóíêöèé // Èçâ. ÂÓÇ. Ôèçèêà. — 2013. — 56,
¹ 9/2. — Ñ. 171—173.
17. øññåëü Ì., Ìîðîçîâ À.À., Ñàïîæíèêîâ Â.Â., Ñàïîæíèêîâ Âë.Â. Ïîñòðîåíèå ñàìîïðî-
âåðÿåìûõ êîìáèíàöèîííûõ ñõåì íà îñíîâå ñâîéñòâ ñàìîäâîéñòâåííûõ ôóíêöèé //
Àâòîìàòèêà è òåëåìåõàíèêà. — 2000. — ¹ 2. — Ñ. 151—163.
18. Berger J.M. A Note on Error Detection Codes for Asymmetric Channels // Information and
Control. — 1961. — Vol. 4, Issue 1. — P. 68—73.
19. Åôàíîâ Ä.Â., Ñàïîæíèêîâ Â.Â., Ñàïîæíèêîâ Âë.Â. Î ñâîéñòâàõ êîäà ñ ñóììèðîâàíèåì
â ñõåìàõ ôóíêöèîíàëüíîãî êîíòðîëÿ // Àâòîìàòèêà è òåëåìåõàíèêà. — 2010. — ¹ 6. —
Ñ. 155—162.
20. Áëþäîâ À.À., Åôàíîâ Ä.Â., Ñàïîæíèêîâ Â.Â., Ñàïîæíèêîâ Âë.Â. Ïîñòðîåíèå ìîäèôè-
öèðîâàííîãî êîäà Áåðãåðà ñ ìèíèìàëüíûì ÷èñëîì íåîáíàðóæèâàåìûõ îøèáîê èíôîðìà-
öèîííûõ ðàçðÿäîâ // Ýëåêòðîí. ìîäåëèðîâàíèå. — 2012. — 34, ¹ 6. — Ñ. 17—29.
21. Efanov D., Sapozhnikov V., Sapozhnikov Vl., Blyudov A. On the Problem of Selection of
Code with Summation for Combinational Circuit Test Organization // Proc. of 11th IEEE
East-West Design & Test Symposium (EWDTS`2013). — Rostov-on-Don, Russia, Septem-
ber 27—30, 2013. — Ð. 261—266.
22. Blyudov A., Efanov D., Sapozhnikov V., Sapozhnikov Vl. Properties of Code with Sum-
mation for Logical Circuit Test Organization // Proc. of the 10th IEEE East-West De-
sign & Test Symposium (EWDTS`2012). — Kharkov, Ukraine, September 14—17, 2012. —
P. 114—117.
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ, Ä.À. Íèêèòèí
44 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 1
23. Ñàïîæíèêîâ Â.Â., Ñàïîæíèêîâ Âë.Â., øññåëü Ì., Ìîðîçîâ À.À. Ìåòîä ïîñòðîåíèÿ
êîìáèíàöèîííûõ ñàìîïðîâåðÿåìûõ óñòðîéñòâ ñ îáíàðóæåíèåì âñåõ îäèíî÷íûõ íå-
èñïðàâíîñòåé // Ýëåêòðîí. ìîäåëèðîâàíèå. — 1998. — 20, ¹6. — Ñ. 70—80.
24. Morosow A., Saposhnikov V.V., Saposhnikov Vl.V., Goessel M. Self-Checking Combi-
national Circuits with Unidirectionally Independent Outputs // VLSI Design. — 1998. — Vol. 5,
Issue 4. — P. 333—345.
25. Das D., Touba N.A. Weight-Based Codes and Their Application to Concurrent Error Detec-
tion of Multilevel Circuits // Proc. of the 17th IEEE VLSI Test Symposium. — USA, CA,
Dana Point, April 25—29, 1999. — P. 370—376.
26. Ghosh S., Lai K.W., Jone W.B., Chang S.C. Scan Chain Fault Identification Using Weight-
Based Codes for SoC Circuits // Proc. of the 13th Asian Test Symposium. — Taiwan,
Kenting, November 15—17, 2004. — P. 210—215.
27. Das D., Touba N.A., Seuring M., Gossel M. Low Cost Concurrent Error Detection Based on
Modulo Weight-Based Codes // Proc. of the 6th IEEE International On-Line Testing Work-
shop (IOLTW). — Spain, Palma de Mallorca, July 3—5, 2000. — P. 171—176.
28. Ñàïîæíèêîâ Â.Â., Ñàïîæíèêîâ Âë.Â., Åôàíîâ Ä.Â, Íèêèòèí Ä.À. Ìåòîä ïîñòðîåíèÿ
êîäà Áåðãåðà ñ ïîâûøåííîé ýôôåêòèâíîñòüþ îáíàðóæåíèÿ îøèáîê â èíôîðìàöèîí-
íûõ ðàçðÿäàõ // Ýëåêòðîí. ìîäåëèðîâàíèå. — 2013. — 35, ¹ 4. — Ñ. 21—34.
29. Ñàïîæíèêîâ Â.Â., Ñàïîæíèêîâ Âë.Â., Åôàíîâ Ä.Â. Âçâåøåííûå êîäû ñ ñóììèðîâà-
íèåì äëÿ îðãàíèçàöèè êîíòðîëÿ ëîãè÷åñêèõ óñòðîéñòâ // Òàì æå. — 2014. — 36, ¹ 1. —
Ñ. 59—80.
30. Marouf M.A., Friedman A.D. Design of Self-Checking Checkers for Berger Codes // Proc.
of the 8th Annual Intern. Conf. on Fault-Tolerant Computing, Toulouse. — France, 1978. —
P. 179—183.
31. Piestrak S.J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes. —
Wroc�aw: Oficyna Wydawnicza Politechniki Wroc�avskiej, 1995. — 111 p.
32. Yang S. Logic Synthesis and Optimization Benchmarks User Guide: Version 3.0 / Technical
Report Microelectronics Center of North Carolina, P.O. Box 12889, Research Triangle Park,
NC 27709, January 15, 1991. — 44 p.
33. Bose B., Lin D.J. Systematic Unidirectional Error-Detection Codes // IEEE Trans. Comput. —
1985. — Vol. C-34. — P. 1026—1032.
34. Áëþäîâ À.À., Åôàíîâ Ä.Â., Ñàïîæíèêîâ Â.Â., Ñàïîæíèêîâ Âë.Â. Êîäû ñ ñóììèðîâà-
íèåì äëÿ îðãàíèçàöèè êîíòðîëÿ êîìáèíàöèîííûõ ñõåì // Àâòîìàòèêà è òåëåìåõàíèêà. —
2013. — ¹ 6. — Ñ. 153—164.
35. Áëþäîâ À.À., Åôàíîâ Ä.Â., Ñàïîæíèêîâ Â.Â., Ñàïîæíèêîâ Âë.Â. Î êîäàõ ñ ñóììèðîâà-
íèåì åäèíè÷íûõ ðàçðÿäîâ â ñèñòåìàõ ôóíêöèîíàëüíîãî êîíòðîëÿ // Òàì æå. — 2014. —
¹ 8. — Ñ. 131—145.
36. Ìàòðîñîâà À.Þ., Îñòàíèí Ñ.À., Ñèíãõ Â. Îáíàðóæåíèå íåñóùåñòâåííûõ ïóòåé ëîãè-
÷åñêèõ ñõåì íà îñíîâå ñîâìåñòíîãî àíàëèçà È-ÈËÈ äåðåâüåâ è SSBDD-ãðàôîâ // Òàì
æå. — 2013. — ¹ 7. — Ñ. 126—142.
V.V. Sapozhnikov, Vl.V. Sapozhnikov, D.V. Efanov, D.A. Nikitin
RESEARCH OF PROPERTIES OF CODES WITH SUMMATION WITH
ONE WEIGHTED DATA BIT IN CONCURRENT ERROR DETECTION SYSTEMS
The new class of codes with summation with the improved characteristics of error detection in
data bits in comparison with the known codes with summation is considered. Properties of the
new class of codes are established, allowing the practical choosing of the best variant of coding at
Èññëåäîâàíèå ñâîéñòâ êîäîâ ñ ñóììèðîâàíèåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 1 45
the organization of concurrent error detection system. A method of synthesis of generators for
new codes and ways of simplification of generators schemes are described.
K e y w o r d s: concurrent error detection, undetectable error, data bits, Berger code, weight-
based code with summation, code properties, generator, checker.
REFERENCE
1. McCluskey E.J. Logic Design Principles: With Emphasis on Testable Semicustom Circuits. —
N.J.: Prentice Hall PTR, 1986. –– 549 p.
2. Sogomonyan E.S., Slabakov E.V. Self-Checking Devices and Fault-Tolerant Systems. —
Moscow.: Radio and Telecommunication, 1989. — 208 p. (in Russian).
3. Lala P.K. Self-Checking and Fault-Tolerant Digital Design. — San Francisco: Morgan
Kaufmann Publishers, 2001. — 216 p.
4. Nicolaidis M., Zorian Y. On-Line Testing for VLSI — À Compendium of Approaches // Journal
of Electronic Testing: Theory and Applications. — 1998. — Vol. 12, No 2. — P. 7—20.
5. G��îessel M., Ocherethy V., Sogomonyan E., Marienfield D. New Methods of Concurrent
Checking: Edition 1. — Dordrecht: Springer Science+Business Media, 2008. – 184 p.
6. Ubar R., Raik J., Vierhaus H.-T. Design and Test Technology for Dependable Systems-
on-Chip (Premier Reference Source) // Information Science Reference, Hershey — New
York: IGI Global, 2011. — 578 p.
7. Wang L-T., Stroud C.E., Touba N.A. System-on-Chip Test Architectures: Nanometer De-
sign for Testability. — Morgan Kaufmann Publishers, 2008. — 856 p.
8. Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications. —
John Wiley & Sons, 2006. — 720 p.
9. Dutta A., Touba N.A. Synthesis of Non-Intrusive Concurrent Error Detection Using an Even
Error Detection Function // International Test Conf. (ITC). — 2005. — P. 1059—1066.
10. Sapozhnikov V.V., Sapozhnikov Vl.V. Self-Checking Discrete Devices. — St.-Petersburg:
Energoatomizdat, 1992. — 224 p. (in Russian).
11. Aksjonova G.P. Necessary and Sufficient Conditions for the Construction of a Fully Testable
Circuits Convolution on Modulo 2 // Automation and Remote Control. — 1979. — Nî 9. —
P. 126—135 (in Russian).
12. Richter M., Goessel M. Concurrent Checking With Split-Parity Codes // Proc. of the 15th
IEEE International On-Line Testing Symposium (IOLTS). — Portugal, Sesimbra-Lisabon,
June 24—26, 2009. — P. 159—163.
13. Saposhnikov V.V., Saposhnikov Vl.V., Dmitriev A.V. et al. Organization of Concurrent Error
Detection Systems for Combinational Circuits by the Method of Logic Complement // Elec-
tronic Modeling. — 2002. — Vol. 24, No 6. — P. 52—66 (in Russian).
14. Parkhomenko P.P., Sogomonyan E.S. Technical Diagnosis Fundamentals (Diagnostic Algo-
ritm Optimization, Apparatus Means). — Moscow: Energoatomizdat, 1981. — 320 p. (in
Russian).
15. Romaschenko A.E., Rumyantsev A.Yu., Shen A. Notes in Coding Theory. – Moscow: MTsNMO,
2011. — 80 p. (in Russian).
16. Matrosova A.Yu., Butorina N.B., Yakimova, N.O. Checker Design Based on Monotonous
Function Implementation // Proc. Higher Educ. Inst., Physics. — 2013. — Vol. 56, No 9/2. —
P. 171—173 (in Russian).
17. G��îessel M., Morozov A.A., Sapozhnikov V.V., Sapozhnikov Vl.V. Synthesis of Self-Checking
Combinational Circuits Based on Self-Dual Functions // Automation and Remote Control. —
2000. — No 2. — P. 151—163 (in Russian).
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ, Ä.À. Íèêèòèí
46 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 1
18. Berger J.M. A Note on Error Detection Codes for Asymmetric Channels // Information and
Control. — 1961. — Vol. 4, Iss. 1. — P. 68—73.
19. Efanov D.V., Saposhnikov V.V., Saposhnikov Vl.V. On Summation Code Properties in Func-
tional Control Circuits // Automation and Remote Control. — 2010. — No 6. — P. 155—162
(in Russian).
20. Blyudov A.A., Efanov D.V., Saposhnikov V.V., Saposhnikov Vl.V. Formation of the Berger
Modified Code with Minimum Number of Undetectable Errors of Informational Bits // Elec-
tronic Modeling. — 2012. — Vol. 34, No 6. — P. 17—29 (in Russian).
21. Efanov D., Sapozhnikov V., Sapozhnikov Vl., Blyudov A. On the Problem of Selection of
Code with Summation for Combinational Circuit Test Organization // Proc. of 11th IEEE
East-West Design & Test Symposium (EWDTS`2013). — Rostov-on-Don, Russia, Sep-
tember 27—30, 2013. — P. 261—266.
22. Blyudov A., Efanov D., Sapozhnikov V., Sapozhnikov Vl. Properties of Code with Summation
for Logical Circuit Test Organization // Proc. of the 10th IEEE East-West Design & Test
Symposium (EWDTS`2012). — Kharkov, Ukraine, September 14—17, 2012. — P. 114—
117.
23. Sapozhnikov V.V., Sapozhnikov Vl.V., G��îessel M., Morozov A.A. Method of Construction of
Combinational Self-Checking Devices With Detection of All Single Faults // Electronic
Modeling. — 1998. — Vol. 20, No 6. — P. 70—80 (in Russian).
24. Morosow A., Saposhnikov V.V., Saposhnikov Vl.V., Goessel M. Self-Checking Combinatio-
nal Circuits with Unidirectionally Independent Outputs // VLSI Design. — 1998. — Vol. 5,
Iss. 4. — P. 333—345.
25. Das D., Touba N.A. (1999) Weight-Based Codes and Their Application to Concurrent Error
Detection of Multilevel Circuits // Proc. of the 17th IEEE VLSI Test Symposium. — USA,
CA, Dana Point, April 25—29, 1999. — P. 370—376.
26. Ghosh S., Lai K.W., Jone W.B., Chang S.C. Scan Chain Fault Identification Using Weight-
Based Codes for SoC Circuits // Proc. of the 13th Asian Test Symposium. — Taiwan,
Kenting, November 15—17, 2004. — P. 210—215.
27. Das D., Touba N.A., Seuring M., Gossel M. Low Cost Concurrent Error Detection Based on
Modulo Weight-Based Codes // Proc. of the 6th IEEE International On-Line Testing Work-
shop (IOLTW). — Spain, Palma de Mallorca, July 3—5, 2000. — P. 171—176.
28. Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V., Nikitin D.A. Method of Constructing the
Berger Code with High Error Detecting Efficiency in Information Bits // Electronic Mode-
ling. — 2013. — Vol. 35, No 4. — P. 21—34 (in Russian).
29. Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Weight-Based Codes with Summation
for Checking of Digital Devices Organization // Ibid. — 2014. — Vol. 36, No 1. — P. 59—
80 (in Russian).
30. Marouf M.A., Friedman D. Design of Self-Checking Checkers for Berger Codes // Proc. of
the 8th Annual Intern. Conf. on Fault-Tolerant Computing. — Toulouse. — France, 1978. —
P. 179—183.
31. Piestrak S.J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes. —
Wroc�aw: Oficyna Wydawnicza Politechniki Wroc�avskiej, 1995. — 111 p.
32. Yang S. Logic Synthesis and Optimization Benchmarks User Guide: Version 3.0 / Technical
Report Microelectronics Center of North Carolina, P.O. Box 12889, Research Triangle Park,
NC 27709, January, 15, 1991. — 44 p.
33. Bose B., Lin D.J. Systematic Unidirectional Error-Detection Codes // IEEE Trans. Comput. —
1985. — Vol. C-34. — P. 1026—1032.
Èññëåäîâàíèå ñâîéñòâ êîäîâ ñ ñóììèðîâàíèåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 1 47
34. Blyudov A.A., Efanov D.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Summation Codes for Or-
ganization of Control of Combinational Circuits // Automation and Remote Control. —
2013. — No 6. — P. 153—164 (in Russian).
35. Blyudov A.A., Efanov D.V., Sapozhnikov V.V., Sapozhnikov Vl.V. On Codes with Sum-
mation of Data Bits in Concurrent Error Detection Systems // Ibid. — 2014. — No 8. — P. 131—
145 (in Russian).
36. Matrosova A.Yu., Ostanin S.A., Singh V. Detection of False Paths in Logical Circuits by Joint
Analysis of the AND/OR Trees and SSBDD-Graphs // Ibid. — 2013. — No 7. — P. 126—
142 (in Russian).
Ïîñòóïèëà 04.09.14
ÑÀÏÎÆÍÈÊÎÂ Âàëåðèé Âëàäèìèðîâè÷, ä-ð òåõí. íàóê, ïðîôåññîð êàôåäðû «Àâòîìàòèêà è
òåëåìåõàíèêà íà æåëåçíûõ äîðîãàõ» Ïåòåðáóðãñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà ïóòåé
ñîîáùåíèÿ.  1963 ã. îêîí÷èë Ëåíèíãðàäñêèé èíñòèòóò èíæåíåðîâ æåëåçíîäîðîæíîãî òðàíñ-
ïîðòà. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — íàäåæíîñòíûé ñèíòåç äèñêðåòíûõ óñòðîéñòâ,
ñèíòåç áåçîïàñíûõ ñèñòåì, ñèíòåç ñàìîïðîâåðÿåìûõ ñõåì, òåõíè÷åñêàÿ äèàãíîñòèêà äèñê-
ðåòíûõ ñèñòåì.
ÑÀÏÎÆÍÈÊÎÂ Âëàäèìèð Âëàäèìèðîâè÷, ä-ð òåõí. íàóê, çàâ. êàôåäðîé «Àâòîìàòèêà è
òåëåìåõàíèêà íà æåëåçíûõ äîðîãàõ» Ïåòåðáóðãñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà ïóòåé
ñîîáùåíèÿ.  1963 ã. îêîí÷èë Ëåíèíãðàäñêèé èíñòèòóò èíæåíåðîâ æåëåçíîäîðîæíîãî òðàíñ-
ïîðòà. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — íàäåæíîñòíûé ñèíòåç äèñêðåòíûõ óñòðîéñòâ,
ñèíòåç áåçîïàñíûõ ñèñòåì, ñèíòåç ñàìîïðîâåðÿåìûõ ñõåì, òåõíè÷åñêàÿ äèàãíîñòèêà äèñê-
ðåòíûõ ñèñòåì.
ÅÔÀÍÎÂ Äìèòðèé Âèêòîðîâè÷, êàíä. òåõí. íàóê, äîöåíò êàôåäðû «Àâòîìàòèêà è òåëå-
ìåõàíèêà íà æåëåçíûõ äîðîãàõ» Ïåòåðáóðãñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà ïóòåé ñîîá-
ùåíèÿ, êîòîðûé îêîí÷èë â 2007 ã. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — äèñêðåòíàÿ ìàòåìàòèêà,
íàäåæíîñòü è òåõíè÷åñêàÿ äèàãíîñòèêà äèñêðåòíûõ ñèñòåì.
ÍÈÊÈÒÈÍ Äìèòðèé Àëåêñàíäðîâè÷, àñïèðàíò êàôåäðû «Àâòîìàòèêà è òåëåìåõàíèêà íà
æåëåçíûõ äîðîãàõ» Ïåòåðáóðãñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà ïóòåé ñîîáùåíèÿ. Â 2014 ã.
îêîí÷èë Ñàíêò-Ïåòåðáóðãñêèé ãîñóäàðñòâåííûé ïîëèòåõíè÷åñêèé óíèâåðñèòåò. Îáëàñòü
íàó÷íûõ èññëåäîâàíèé — äèñêðåòíàÿ ìàòåìàòèêà, ïðîãðàììèðîâàíèå è ìîäåëèðîâàíèå.
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ, Ä.À. Íèêèòèí
48 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 1
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 1 49
|
| id | nasplib_isofts_kiev_ua-123456789-101078 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-12-07T16:48:38Z |
| publishDate | 2015 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Сапожников, В.В. Сапожников, Вл.В. Ефанов, Д.В. Никитин, Д.А. 2016-05-30T18:01:38Z 2016-05-30T18:01:38Z 2015 Исследование свойств кодов с суммированием с одним взвешенным информационным разрядом в системах функционального контроля / В.В. Сапожников, Вл.В. Сапожников, Д.В. Ефанов, Д.А. Никитин // Электронное моделирование. — 2015 — Т. 37, № 1. — С. 25-48. — Бібліогр.: 36 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101078 681.518.5:004.052.32 Рассмотрен новый класс кодов с суммированием, имеющий улучшенные характеристики обнаружения ошибок в информационных разрядах по сравнению с известными кодами с суммированием. Определены свойства полученного класса кодов, позволяющие выбрать наилучший способ кодирования при организации системы функционального контроля. Описаны метод синтеза генераторов для новых кодов и способы упрощения схем генераторов. Розглянуто новий клас кодів з підсумовуванням, який має покращені характеристики для виявлення похибок в інформаційних розрядах порівняно з відомими кодами з підсумовуванням. Визначено властивості отриманого класу кодів, які дають можливість обрати найкращий спосіб кодування при організуванні системи функціонального контролю. Описано метод синтезу генераторів для нових кодів та способи спрощення схем генераторів. The new class of codes with summation with the improved characteristics of error detection in data bits in comparison with the known codes with summation is considered. Properties of the new class of codes are established, allowing the practical choosing of the best variant of coding at the organization of concurrent error detection system. A method of synthesis of generators for new codes and ways of simplification of generators schemes are described. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Вычислительные процессы и системы Исследование свойств кодов с суммированием с одним взвешенным информационным разрядом в системах функционального контроля Research of properties of codes with summation with one weighted data bit in concurrent error detection systems Article published earlier |
| spellingShingle | Исследование свойств кодов с суммированием с одним взвешенным информационным разрядом в системах функционального контроля Сапожников, В.В. Сапожников, Вл.В. Ефанов, Д.В. Никитин, Д.А. Вычислительные процессы и системы |
| title | Исследование свойств кодов с суммированием с одним взвешенным информационным разрядом в системах функционального контроля |
| title_alt | Research of properties of codes with summation with one weighted data bit in concurrent error detection systems |
| title_full | Исследование свойств кодов с суммированием с одним взвешенным информационным разрядом в системах функционального контроля |
| title_fullStr | Исследование свойств кодов с суммированием с одним взвешенным информационным разрядом в системах функционального контроля |
| title_full_unstemmed | Исследование свойств кодов с суммированием с одним взвешенным информационным разрядом в системах функционального контроля |
| title_short | Исследование свойств кодов с суммированием с одним взвешенным информационным разрядом в системах функционального контроля |
| title_sort | исследование свойств кодов с суммированием с одним взвешенным информационным разрядом в системах функционального контроля |
| topic | Вычислительные процессы и системы |
| topic_facet | Вычислительные процессы и системы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/101078 |
| work_keys_str_mv | AT sapožnikovvv issledovaniesvoistvkodovssummirovaniemsodnimvzvešennyminformacionnymrazrâdomvsistemahfunkcionalʹnogokontrolâ AT sapožnikovvlv issledovaniesvoistvkodovssummirovaniemsodnimvzvešennyminformacionnymrazrâdomvsistemahfunkcionalʹnogokontrolâ AT efanovdv issledovaniesvoistvkodovssummirovaniemsodnimvzvešennyminformacionnymrazrâdomvsistemahfunkcionalʹnogokontrolâ AT nikitinda issledovaniesvoistvkodovssummirovaniemsodnimvzvešennyminformacionnymrazrâdomvsistemahfunkcionalʹnogokontrolâ AT sapožnikovvv researchofpropertiesofcodeswithsummationwithoneweighteddatabitinconcurrenterrordetectionsystems AT sapožnikovvlv researchofpropertiesofcodeswithsummationwithoneweighteddatabitinconcurrenterrordetectionsystems AT efanovdv researchofpropertiesofcodeswithsummationwithoneweighteddatabitinconcurrenterrordetectionsystems AT nikitinda researchofpropertiesofcodeswithsummationwithoneweighteddatabitinconcurrenterrordetectionsystems |