Взвешенные коды с суммированием для организации контроля логических устройств
Приведены результаты исследований кодов с суммированием взвешенных информационных разрядов при сохранении числа контрольных разрядов таким же, как у классических кодов Бергера. Определены классы кодов, которые обладают основными свойствами кодов Бергера и имеют наименьшее среди известных кодов число...
Saved in:
| Published in: | Электронное моделирование |
|---|---|
| Date: | 2014 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2014
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/100986 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Взвешенные коды с суммированием для организации контроля логических устройств / В.В. Сапожников, Вл.В. Сапожников, Д.В. Ефанов // Электронное моделирование. — 2014 — Т. 36, № 1. — С. 59-80. — Бібліогр.: 25 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859594280772829184 |
|---|---|
| author | Сапожников, В.В. Сапожников, Вл.В. Ефанов, Д.В. |
| author_facet | Сапожников, В.В. Сапожников, Вл.В. Ефанов, Д.В. |
| citation_txt | Взвешенные коды с суммированием для организации контроля логических устройств / В.В. Сапожников, Вл.В. Сапожников, Д.В. Ефанов // Электронное моделирование. — 2014 — Т. 36, № 1. — С. 59-80. — Бібліогр.: 25 назв. — рос. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | Приведены результаты исследований кодов с суммированием взвешенных информационных разрядов при сохранении числа контрольных разрядов таким же, как у классических кодов Бергера. Определены классы кодов, которые обладают основными свойствами кодов Бергера и имеют наименьшее среди известных кодов число необнаруживаемых ошибок в информационных разрядах.
Наведено результати досліджень кодів з підсумовуванням зважених інформаційних розрядів при зберіганні числа контрольних розрядів таким, як у класичних кодів Бергера. Визначено класи кодів з основними властивостями кодів Бергера, які мають найменше серед відомих кодів число похибок, що не визначаються, в інформаційних розрядах.
The paper presents the results of studying the codes with summation of the weighted data bits under the condition of preservation of the number of check bits, similar to the classical Berger codes. Classes of codes which possess the main properties of the Berger codes and have the least number of undetectable errors in data bits (among known codes) are defined.
|
| first_indexed | 2025-11-27T18:25:56Z |
| format | Article |
| fulltext |
ÓÄÊ 681.518.5
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, äîêòîðà òåõí. íàóê,
Ä.Â. Åôàíîâ, êàíä. òåõí. íàóê
Ôåäåðàëüíîå ãîñóäàðñòâåííîå áþäæåòíîå
îáðàçîâàòåëüíîå ó÷ðåæäåíèå âûñøåãî ïðîôåññèîíàëüíîãî
îáðàçîâàíèÿ «Ïåòåðáóðãñêèé ãîñóäàðñòâåííûé
óíèâåðñèòåò ïóòåé ñîîáùåíèÿ»,
(Ðîññèéñêàÿ Ôåäåðàöèÿ, 190031, Ñàíêò-Ïåòåðáóðã, Ìîñêîâñêèé ïð., 9,
òåë. (+7) 9117092164, (+7) (812) 4578579, e-mail: TrES-4b@yandex.ru)
Âçâåøåííûå êîäû ñ ñóììèðîâàíèåì
äëÿ îðãàíèçàöèè êîíòðîëÿ ëîãè÷åñêèõ óñòðîéñòâ
Ïðèâåäåíû ðåçóëüòàòû èññëåäîâàíèé êîäîâ ñ ñóììèðîâàíèåì âçâåøåííûõ èíôîðìàöèîí-
íûõ ðàçðÿäîâ ïðè ñîõðàíåíèè ÷èñëà êîíòðîëüíûõ ðàçðÿäîâ òàêèì æå, êàê ó êëàññè÷åñêèõ
êîäîâ Áåðãåðà. Îïðåäåëåíû êëàññû êîäîâ, êîòîðûå îáëàäàþò îñíîâíûìè ñâîéñòâàìè êî-
äîâ Áåðãåðà è èìåþò íàèìåíüøåå ñðåäè èçâåñòíûõ êîäîâ ÷èñëî íåîáíàðóæèâàåìûõ îøè-
áîê â èíôîðìàöèîííûõ ðàçðÿäàõ.
Íàâåäåíî ðåçóëüòàòè äîñë³äæåíü êîä³â ç ï³äñóìîâóâàííÿì çâàæåíèõ ³íôîðìàö³éíèõ ðîç-
ðÿä³â ïðè çáåð³ãàíí³ ÷èñëà êîíòðîëüíèõ ðîçðÿä³â òàêèì, ÿê ó êëàñè÷íèõ êîä³â Áåðãåðà.
Âèçíà÷åíî êëàñè êîä³â ç îñíîâíèìè âëàñòèâîñòÿìè êîä³â Áåðãåðà, ÿê³ ìàþòü íàéìåíøå
ñåðåä â³äîìèõ êîä³â ÷èñëî ïîõèáîê, ùî íå âèçíà÷àþòüñÿ, â ³íôîðìàö³éíèõ ðîçðÿäàõ.
Ê ë þ ÷ å â û å ñ ë î â à: ôóíêöèîíàëüíûé êîíòðîëü, íåîáíàðóæèâàåìàÿ îøèáêà, âåñ èíôîð-
ìàöèîííîãî ðàçðÿäà, êîä Áåðãåðà, âçâåøåííûé êîä ñ ñóììèðîâàíèåì, òåñòåð, ãåíåðàòîð.
Êîäû ñ ñóììèðîâàíèåì ïðåäñòàâëÿþò ñîáîé ðàçäåëèìûå êîäû, â êîòîðûõ
êîíòðîëüíûå ðàçðÿäû âû÷èñëÿþòñÿ ïî çíà÷åíèÿì èíôîðìàöèîííûõ ðàç-
ðÿäîâ ñîãëàñíî çàðàíåå óñòàíîâëåííûì ïðàâèëàì [1] è ýôôåêòèâíî ïðèìå-
íÿþòñÿ ïðè ïåðåäà÷å è îáðàáîòêå äàííûõ, à òàêæå ïðè ïðîåêòèðîâàíèè
ñèñòåì òåõíè÷åñêîãî äèàãíîñòèðîâàíèÿ óñòðîéñòâ àâòîìàòèêè [2, 3].
Êîäû ñ ñóììèðîâàíèåì èñïîëüçóþòñÿ, íàïðèìåð, ïðè ïîñòðîåíèè ñèñ-
òåì ôóíêöèîíàëüíîãî êîíòðîëÿ ëîãè÷åñêèõ óñòðîéñòâ ìåòîäîì âû÷èñëå-
íèÿ êîíòðîëüíûõ ðàçðÿäîâ (ðèñ. 1) [4—7]. Â òàêîé ñèñòåìå êîíòðîëè-
ðóåìîå óñòðîéñòâî f x( ), äëÿ îïðåäåëåíèÿ åãî òåõíè÷åñêîãî ñîñòîÿíèÿ â
ïðîèçâîëüíûé ìîìåíò âðåìåíè, ñíàáæàåòñÿ ñïåöèàëèçèðîâàííûì êîíò-
ðîëüíûì îáîðóäîâàíèåì, âêëþ÷àþùèì â ñåáÿ áëîê äîïîëíèòåëüíîé ëîãè-
êè g x( ) è ñõåìó òåñòåðà. Âõîäû áëîêà f x( ) îäíîâðåìåííî ÿâëÿþòñÿ è
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 59
���������
�
��������
� �������
� Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ, 2014
âõîäàìè áëîêà g (x). Ïðè ïîÿâëåíèè íà íèõ îïðåäåëåííîãî âõîäíîãî âåê-
òîðà� �x x x i1 2 ... íà ðàáî÷èõ âûõîäàõ áëîêà f x( ) ôîðìèðóåòñÿ íåêîòîðûé
èíôîðìàöèîííûé âåêòîð, à íà êîíòðîëüíûõ âûõîäàõ áëîêà g x( ) — ñîîò-
âåòñòâóþùèé åìó êîíòðîëüíûé âåêòîð. Ïðè íàëè÷èè ñáîåâ âî âíóòðåí-
íåé ñòðóêòóðå áëîêà f x( ) äàííîå ñîîòâåòñòâèå íàðóøàåòñÿ. Ïðèíàäëåæ-
íîñòü ôîðìèðóåìîãî íà âûõîäàõ áëîêîâ f x( ) è g x( ) êîäîâîãî âåêòîðà
� �f f f g g gm k1 2 1 2... ... çàðàíåå âûáðàííîìó êîäó ñ ñóììèðîâàíèåì îïðå-
äåëÿåòñÿ ñàìîïðîâåðÿåìûì òåñòåðîì. Ïîä ñàìîïðîâåðÿåìîñòüþ ñèñòåìû
êîíòðîëÿ ïîäðàçóìåâàåòñÿ âîçìîæíîñòü ñèãíàëèçàöèè òåñòåðîì î íàëè÷èè
ëþáîãî äåôåêòà ñèñòåìû ôóíêöèîíàëüíîãî êîíòðîëÿ (îòêàçà ëþáîãî èç åå
áëîêîâ) õîòÿ áû íà îäíîì âõîäíîì íàáîðå � �x x x i1 2 ... .  ýòîì ñëó÷àå
êîíòðîëüíûå âûõîäû òåñòåðà ïðèíèìàþò íåïàðàôàçíûå çíà÷åíèÿ <00>
èëè <11>.
Èäåÿ êîíòðîëÿ ñîñòîèò â ñëåäóþùåì. Òåñòåð ïî çíà÷åíèÿì ðàçðÿäîâ
èíôîðìàöèîííîãî âåêòîðà � �f f f m1 2 ... âû÷èñëÿåò êîíòðîëüíûé âåêòîð
� � � � �g g g k1 2 ... , à çàòåì âûïîëíÿåò åãî ñðàâíåíèå ñ àíàëîãè÷íûì êîíòðîëüíûì
âåêòîðîì� �g g g k1 2 ... , ñôîðìèðîâàííûì áëîêîì äîïîëíèòåëüíîé ëîãèêè ïî
çíà÷åíèÿì âõîäîâ. Íåñîîòâåòñòâèå õîòÿ áû â îäíîì êîíòðîëüíîì ðàçðÿäå
ÿâëÿåòñÿ ïðèçíàêîì íàëè÷èÿ äåôåêòà â áëîêå îñíîâíîé ëîãèêè f x( ).
 ïðàêòè÷åñêèõ çàäà÷àõ ñèñòåìà ôóíêöèîíàëüíîãî êîíòðîëÿ äîëæíà
óäîâëåòâîðÿòü òðåáîâàíèþ îáíàðóæåíèÿ ëþáûõ îäèíî÷íûõ íåèñïðàâíîñ-
òåé â áëîêå îñíîâíîé ëîãèêè f x( ). Íî òàê êàê ñâÿçè ìåæäó ëîãè÷åñêèìè
ýëåìåíòàìè âî âíóòðåííåé ñòðóêòóðå óñòðîéñòâà f x( ) ìîãóò áûòü ðàç-
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ
60 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
f (x)
f 2
f1
fm
g (x)
g 1
g2
gk
Ðàáî÷èå
âûõîäû
x1
x2
xi
Òåñòåð Êîíòðîëüíûå
âûõîäûz2
z 1
f 1
f
2
fm
gkg2g1
fmf
2
f
1
Êîíòðîëüíîå
îáîðóäîâàíèå
Âåêòîð êîäà ñ
ñóììèðîâàíèåì
..
.
..
.
... ...
..
.
..
...
.
..
.
Ðèñ. 1. Ñèñòåìà ôóíêöèîíàëüíîãî êîíòðîëÿ
ëè÷íûìè, òî è îäèíî÷íûé äåôåêò ìîæåò ðàñïðîñòðàíÿòüñÿ îäíîâðåìåííî
íà íåñêîëüêî âûõîäîâ, èñêàæàÿ â ïðîöåññå ôóíêöèîíèðîâàíèÿ ñèñòåìû
êîíòðîëÿ èíôîðìàöèîííûé âåêòîð çàðàíåå âûáðàííîãî êîäà ñ ñóììèðî-
âàíèåì. Ïîñêîëüêó â ñòðóêòóðå, èçîáðàæåííîé íà ðèñ. 1, íåâîçìîæíî
îäíîâðåìåííîå èñêàæåíèå âûõîäîâ îáîèõ áëîêîâ, f x( ) è g x( ), ÷òî íå-
ïîñðåäñòâåííî ñëåäóåò èç èñõîäíîãî äîïóùåíèÿ ïðè ðàçäåëüíîé ðåàëèçàöèè
ëîãè÷åñêèõ áëîêîâ, ìîæíî ðàññìàòðèâàòü îñîáåííîñòè êîíêðåòíî âûáðàííî-
ãî êîäà ñ ñóììèðîâàíèåì íà ñëó÷àé ïîòåíöèàëüíîãî âîçíèêíîâåíèÿ èñêàæå-
íèé â èíôîðìàöèîííîì âåêòîðå ïðè áåçîøèáî÷íîñòè êîíòðîëüíîãî.
Ïðàâèëà ïîñòðîåíèÿ êîäà ñ ñóììèðîâàíèåì îïðåäåëÿþò äâà îñíîâíûõ
êðèòåðèÿ ñèñòåìû ôóíêöèîíàëüíîãî êîíòðîëÿ: õàðàêòåðèñòèêè ïî îáíàðó-
æåíèþ îøèáîê â áëîêå f x( ) è ñëîæíîñòü êîíòðîëüíîãî îáîðóäîâàíèÿ.
Çàäà÷à âûáîðà êîäà ñîñòîèò â îáåñïå÷åíèè îáíàðóæåíèÿ ëþáûõ îäèíî÷-
íûõ äåôåêòîâ â áëîêå f x( ) ïðè ìèíèìàëüíîé ñëîæíîñòè êîíòðîëüíîãî
îáîðóäîâàíèÿ. Ñëåäóåò òàêæå çàìåòèòü, ÷òî ïðè ýòîì íà âõîäàõ òåñòåðà â
ïðîöåññå ðàáîòû ñèñòåìû ôóíêöèîíàëüíîãî êîíòðîëÿ äîëæíû ôîðìèðî-
âàòüñÿ âñå ïðîâåðî÷íûå âîçäåéñòâèÿ.
Êîäû ñ ñóììèðîâàíèåì â ñèñòåìàõ ôóíêöèîíàëüíîãî êîíòðîëÿ.
×àñòî ñèñòåìó ôóíêöèîíàëüíîãî êîíòðîëÿ îðãàíèçóþò ïî êëàññè÷åñêèì
êîäàì ñ ñóììèðîâàíèåì (êîäàì Áåðãåðà [1]), â êîòîðûõ êîíòðîëüíûé âåê-
òîð ÿâëÿåòñÿ äâîè÷íûì îòîáðàæåíèåì ÷èñëà åäèíè÷íûõ ðàçðÿäîâ â èí-
ôîðìàöèîííîì âåêòîðå (âåñà r èíôîðìàöèîííîãî âåêòîðà). Ââåäåì ñëå-
äóþùèå îáîçíà÷åíèÿ: m — äëèíà èíôîðìàöèîííîãî âåêòîðà (èëè ÷èñëî
âûõîäîâ áëîêà f x( )); k — äëèíà êîíòðîëüíîãî âåêòîðà (èëè ÷èñëî âûõîäîâ
áëîêà g (x)); n = m + k — äëèíà âåêòîðà êîäà ñ ñóììèðîâàíèåì. Êîä Áåðãå-
ðà, èñõîäÿ èç ýòîãî, îáîçíà÷èì S (n, m).
Ñèñòåìà ôóíêöèîíàëüíîãî êîíòðîëÿ, ïîñòðîåííàÿ ïî S n m( , )-êîäó,
âêëþ÷àåò â ñåáÿ áëîê g x( ), èìåþùèé � �k m� log ( )2 1 âûõîäîâ (çàïèñü � �b
îçíà÷àåò öåëîå ñâåðõó îò b). Êîäîì S (n, m) îáíàðóæèâàåòñÿ ëþáàÿ îøèáêà
èíôîðìàöèîííîãî âåêòîðà, íàðóøàþùàÿ åãî âåñ, à ê íåîáíàðóæèâàåìûì
îòíîñÿòñÿ òîëüêî ðàçíîíàïðàâëåííûå èñêàæåíèÿ ÷åòíîãî ÷èñëà èíôîðìà-
öèîííûõ ðàçðÿäîâ (÷åòíîé êðàòíîñòè d), ñîäåðæàùèå ãðóïïû èñêàæåíèé
{0
1, 1
0}. Óñòàíîâëåíî [8], ÷òî äëÿ ëþáîãî êîäà Áåðãåðà äîëÿ íåîáíà-
ðóæèâàåìûõ èñêàæåíèé äàííîé êðàòíîñòè îò îáùåãî ÷èñëà èñêàæåíèé
äàííîé êðàòíîñòè â íåçàâèñèìîñòè îò äëèíû èíôîðìàöèîííîãî âåêòîðà
ÿâëÿåòñÿ ïîñòîÿííîé âåëè÷èíîé:
�d
d
d
dC� �2 2/ . (1)
Êîä S n m( , ) îáëàäàåò îòíîñèòåëüíî íèçêèìè âîçìîæíîñòÿìè ïî îáíàðó-
æåíèþ îøèáîê â èíôîðìàöèîííûõ âåêòîðàõ â îáëàñòè ìàëîé êðàòíîñòè, à
Âçâåøåííûå êîäû ñ ñóììèðîâàíèåì äëÿ îðãàíèçàöèè êîíòðîëÿ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 61
èìåííî íå îáíàðóæèâàåò 50 % äâóêðàòíûõ èñêàæåíèé, 37,5 % ÷åòûðåõ-
êðàòíûõ è 31,25 % øåñòèêðàòíûõ èñêàæåíèé.
 ðàáîòàõ [9—12] ïðåäëîæåíû ñïîñîáû óëó÷øåíèÿ õàðàêòåðèñòèê ïî
îáíàðóæåíèþ îøèáîê êëàññè÷åñêèìè êîäàìè Áåðãåðà ïðè ñîõðàíåíèè è
ñíèæåíèè èçáûòî÷íîñòè êîäà êàê ãëàâíîé õàðàêòåðèñòèêè, âëèÿþùåé íà
ñëîæíîñòü êîíòðîëüíîãî îáîðóäîâàíèÿ â ñèñòåìå äèàãíîñòèðîâàíèÿ.
Ïðîñòåéøèì ñïîñîáîì ñíèæåíèÿ ñëîæíîñòè ÿâëÿåòñÿ ïðèìåíåíèå ìî-
äóëüíîãî ïðèíöèïà ïîäñ÷åòà âåñà èíôîðìàöèîííîãî âåêòîðà [13, 14]. Ïðè
ýòîì ìîäóëü âûáèðàåòñÿ èç äèàïàçîíà � �M
m
�
2 2 21 2 1 12, ,...,
log ( )
[10]. Êîäû,
ïîëó÷åííûå äàííûì ñïîñîáîì, íàçûâàþòñÿ ìîäóëüíûìè êîäàìè ñ ñóììè-
ðîâàíèåì è îáîçíà÷àþòñÿ êàê SM n m( , )-êîäû, ãäå M — ìîäóëü ïîäñ÷åòà
âåñà èíôîðìàöèîííîãî âåêòîðà. ×åì ìåíüøå ìîäóëü ïîäñ÷åòà, òåì íèæå
âîçìîæíîñòè ïî îáíàðóæåíèþ îøèáîê â èíôîðìàöèîííûõ ðàçðÿäàõ êîäà
ñ ñóììèðîâàíèåì, íî òåì ìåíüøå ñëîæíîñòü êîíòðîëüíîãî îáîðóäîâàíèÿ.
Èíòåðåñíî, ÷òî äëÿ ìîäóëüíûõ êîäîâ ñ ñóììèðîâàíèåì ñâîéñòâî ïîñ-
òîÿíñòâà äîëè íåîáíàðóæèâàåìûõ îøèáîê êðàòíîñòè d îò îáùåãî ÷èñëà
îøèáîê òîé æå êðàòíîñòè ñîõðàíÿåòñÿ [12].
 ðàáîòå [11] ðàññìîòðåíî ñåìåéñòâî ìîäèôèöèðîâàííûõ êîäîâ Áåð-
ãåðà ñ ÷èñëîì êîíòðîëüíûõ ðàçðÿäîâ � �k m� log ( )2 1 è ñ óëó÷øåííûìè
ñâîéñòâàìè ïî îáíàðóæåíèþ îøèáîê â èíôîðìàöèîííûõ âåêòîðàõ ïî
ñðàâíåíèþ ñ êëàññè÷åñêèìè êîäàìè ñ ñóììèðîâàíèåì. Ïðè ýòîì àëãîðèòì
ìîäèôèêàöèè êîäîâ Áåðãåðà ìîæåò áûòü ïðèìåíåí òàêæå è ê ëþáîìó
SM n m( , )-êîäó, ÷òî ïîçâîëèò ïîëó÷èòü ñåìåéñòâî ìîäóëüíî-ìîäèôèöèðî-
âàííûõ êîäîâ ñ ñóììèðîâàíèåì ñ óëó÷øåííûìè õàðàêòåðèñòèêàìè ïî îáíàðó-
æåíèþ îøèáîê â èíôîðìàöèîííûõ âåêòîðàõ ïî ñðàâíåíèþ ñ ñîîòâåòñòâóþ-
ùèìè SM n m( , )-êîäàìè [15].
Äðóãèì ñïîñîáîì ïîâûøåíèÿ ýôôåêòèâíîñòè SM n m( , )-êîäà ÿâëÿåòñÿ
âçâåøèâàíèå èíôîðìàöèîííûõ ðàçðÿäîâ è çàïèñü â êà÷åñòâå êîíòðîëüíîãî
âåêòîðà ñóììû âåñîâ åäèíè÷íûõ èíôîðìàöèîííûõ ðàçðÿäîâ [1, 16 — 19]:
W x w
i
m
i i�
�
�
1
,
ãäå xi — çíà÷åíèå èíôîðìàöèîííîãî ðàçðÿäà (0 èëè 1); wi — åãî âåñ. Ïðè
ýòîì äëèíà êîíòðîëüíîãî âåêòîðà ñóùåñòâåííî çàâèñèò îò çíà÷åíèé âåñîâ
èíôîðìàöèîííûõ ðàçðÿäîâ.  ñëó÷àå, åñëè âåñà èíôîðìàöèîííûõ ðàçðÿ-
äîâ óäîâëåòâîðÿþò íåðàâåíñòâó
� �m w w wm
m� � �
1 2
1
2 12...
log ( )
, (2)
òî ÷èñëî êîíòðîëüíûõ ðàçðÿäîâ âçâåøåííîãî êîäà íå ïðåâûøàåò àíàëîãè÷-
íîãî ïîêàçàòåëÿ êîäà Áåðãåðà. ×àñòíûé ñëó÷àé òàêèõ êîäîâ è èõ ñâîéñòâà
îïèñàíû â [20].
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ
62 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
Íåðàâåíñòâî (2) íàêëàäûâàåò îãðàíè÷åíèÿ íà çíà÷åíèÿ âåñîâûõ êîýô-
ôèöèåíòîâ wi. Íàïðèìåð, ïðè m = 7 íåëüçÿ ïîñòðîèòü âçâåøåííûé êîä ñ
òàêèì æå, êàê ó êîäà Áåðãåðà, ÷èñëîì êîíòðîëüíûõ ðàçðÿäîâ, òàê êàê
� �2 1 72 7 1log ( ) � � , è âçâåøèâàíèå ëþáîãî èíôîðìàöèîííîãî ðàçðÿäà ïðè-
âåäåò ê óâåëè÷åíèþ ÷èñëà êîíòðîëüíûõ ðàçðÿäîâ.
Ðåçóëüòàòû èññëåäîâàíèé ñâèäåòåëüñòâóþò î òîì, ÷òî â çàâèñèìîñòè
îò âûáðàííûõ âåñîâ èíôîðìàöèîííûõ ðàçðÿäîâ íàõîäÿòñÿ è ðàñïðåäå-
ëåíèÿ íåîáíàðóæèâàåìûõ îøèáîê ïî êðàòíîñòÿì. Äàëåå ðàññìîòðèì îñî-
áåííîñòè âçâåøåííûõ êîäîâ ñ ñóììèðîâàíèåì, óäîâëåòâîðÿþùèõ óñëî-
âèþ (2). Îïðåäåëèì ïðîñòîå ñîîòíîøåíèå âåñîâûõ êîýôôèöèåíòîâ èíôîð-
ìàöèîííûõ ðàçðÿäîâ, âûáîð êîòîðûõ ïîçâîëÿåò ïîëó÷àòü êîäû ñ âîçìîæ-
íîñòüþ îáíàðóæåíèÿ ëþáûõ îøèáîê íå÷åòíûõ êðàòíîñòåé è ëþáûõ îäíî-
íàïðàâëåííûõ èñêàæåíèé ÷åòíûõ êðàòíîñòåé.
Âçâåøåííûå êîäû ñ ñóììèðîâàíèåì â ñèñòåìàõ ôóíêöèîíàëüíîãî
êîíòðîëÿ. Îáîçíà÷èì âçâåøåííûé êîä Áåðãåðà WS (n, m, [w1, w2, …, wm]),
ãäå [w1, w2, …, wm] — ìàññèâ âåñîâûõ êîýôôèöèåíòîâ ñîîòâåòñòâóþùèõ
èíôîðìàöèîííûõ ðàçðÿäîâ. Äëÿ ðåøåíèÿ çàäà÷è ôóíêöèîíàëüíîãî êîíò-
ðîëÿ áóäåì âûáèðàòü âåñîâûå êîýôôèöèåíòû èíôîðìàöèîííûõ ðàçðÿäîâ â
ñîîòâåòñòâèè ñ (2). Ðàññìîòðèì S (7, 4)-êîä (èëè WS (7, 4, [1, 1, 1, 1])-êîä) è
êîä ñ åäèíñòâåííûì âçâåøåííûì ðàçðÿäîì, íàïðèìåð ìëàäøèì ðàçðÿäîì
ïðè w4 = 3, ò.å. WS (7, 4, [1, 1, 1, 3])-êîä (òàáë. 1).
Îøèáêà â êîäå áóäåò íåîáíàðóæèâàåìîé òîãäà è òîëüêî òîãäà, êîãäà
îíà èñêàçèò èíôîðìàöèîííûé âåêòîð ñ ñîîòâåòñòâóþùèì åìó ñóììàðíûì
âåñîì è ïåðåâåäåò åãî â èíôîðìàöèîííûé âåêòîð ñ òàêèì æå ñóììàðíûì
âåñîì. Ðàñïðåäåëåíèå èíôîðìàöèîííûõ âåêòîðîâ íà ãðóïïû êîíòðîëüíûõ
âåêòîðîâ îäíîçíà÷íî õàðàêòåðèçóåò è ðàñïðåäåëåíèÿ íåîáíàðóæèâàåìûõ
îøèáîê â êîäå ñ ñóììèðîâàíèåì. Íà ðèñ. 2 ïîêàçàíî ðàñïðåäåëåíèå èíôîð-
ìàöèîííûõ âåêòîðîâ S (7, 4)-êîäà è ïðèíöèï èõ ïåðåðàñïðåäåëåíèÿ ïðè
âçâåøèâàíèè ìëàäøåãî êîíòðîëüíîãî ðàçðÿäà, ò.å. ïåðåõîä ê ðàñïðåäå-
ëåíèþ èíôîðìàöèîííûõ âåêòîðîâ WS (7, 4, [1, 1, 1, 3])-êîäà. ×åì ðàâíî-
ìåðíåå ðàñïðåäåëåíèå èíôîðìàöèîííûõ âåêòîðîâ íà ãðóïïû êîíòðîëüíûõ
âåêòîðîâ, òåì ìåíüøå îøèáîê â êîäå íå îáíàðóæèâàåòñÿ [11].
Êîä ñ ñóììèðîâàíèåì ñ çàäàííûìè çíà÷åíèÿìè m è k íàçûâàåòñÿ
îïòèìàëüíûì îòíîñèòåëüíî îáùåãî ÷èñëà íåîáíàðóæèâàåìûõ îøèáîê
èíôîðìàöèîííûõ ðàçðÿäîâ, åñëè îí èìååò ðàâíîìåðíîå ðàñïðåäåëåíèå
âñåõ èíôîðìàöèîííûõ âåêòîðîâ íà 2k êîíòðîëüíûå ãðóïïû [11]. ×èñëî
íåîáíàðóæèâàåìûõ îøèáîê â îïòèìàëüíîì êîäå ìèíèìàëüíî: N m
min �
� ��2 2 1m m k( ).
Ýôôåêòèâíîñòü ëþáîãî êîäà ñ ñóììèðîâàíèåì ìîæíî ñðàâíèòü ñ ýô-
ôåêòèâíîñòüþ îïòèìàëüíîãî êîäà ïðè çàäàííûõ çíà÷åíèÿõ m è k. Êîýô-
Âçâåøåííûå êîäû ñ ñóììèðîâàíèåì äëÿ îðãàíèçàöèè êîíòðîëÿ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 63
ôèöèåíò ýôôåêòèâíîñòè � îïðåäåëÿåòñÿ êàê îòíîøåíèå ÷èñëà íåîáíàðó-
æèâàåìûõ îøèáîê â îïòèìàëüíîì êîäå N m
min ê îáùåìó ÷èñëó íåîáíàðó-
æèâàåìûõ îøèáîê â ðàññìàòðèâàåìîì êîäå Nm [11]:
� � N Nm m
min / . (3)
Êîä S (7, 4) èìååò ýôôåêòèâíîñòü � = 0,2963. Èç ðèñ. 2 âèäíî, ÷òî
ïåðåðàñïðåäåëåíèå èíôîðìàöèîííûõ âåêòîðîâ äëÿ êîäà ñ ñóììèðîâàíèåì
S (7, 4) ïðèâîäèò ê óìåíüøåíèþ èõ ÷èñëà â êîíòðîëüíûõ ãðóïïàõ è áîëåå
ðàâíîìåðíîìó ðàñïðåäåëåíèþ íà ãðóïïû (òàáë. 2). Ïðè ýòîì óìåíüøàåòñÿ
è ÷èñëî íåîáíàðóæèâàåìûõ îøèáîê. Òàê, â êîäå S (7, 4) Nm = 54 íåîá-
íàðóæèâàåìûõ îøèáêè (48 äâóêðàòíûõ è 6 ÷åòûðåõêðàòíûõ), à âî âçâå-
øåííîì WS (7, 4, [1, 1, 1, 3])-êîäå, ïîëó÷åííîì ïîñëå ïåðåðàñïðåäåëåíèÿ
âåêòîðîâ, — Nm = 26 íåîáíàðóæèâàåìûõ îøèáîê (24 äâóêðàòíûõ è 2
÷åòûðåõêðàòíûõ). Ñîãëàñíî (3) ýôôåêòèâíîñòü âçâåøåííîãî êîäà ñîñòàâ-
ëÿåò � = 0,6154, ÷òî áîëåå ÷åì âäâîå âûøå ýôôåêòèâíîñòè êëàññè÷åñ-
êîãî S (7,4)-êîäà.
Åñëè âåñ îäíîãî èç èíôîðìàöèîííûõ ðàçðÿäîâ áóäåò wi = 4, òî ïîëó÷èì
åùå áîëåå áëèçêîå ê îïòèìàëüíîìó ïåðåðàñïðåäåëåíèå èíôîðìàöèîííûõ
âåêòîðîâ îòíîñèòåëüíî êîíòðîëüíûõ (ñì. òàáë. 2). Îäíàêî äàëüíåéøåå óâåëè-
÷åíèå âåñà ïðèâåäåò ê óâåëè÷åíèþ ÷èñëà êîíòðîëüíûõ ðàçðÿäîâ â êîäå.
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ
64 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
Íîìåð êîäîâîãî
ñëîâà
Èíôîðìàöèîííûå ðàçðÿäû
âçâåøåííûõ êîäîâ ïðè m = 4
Êîíòðîëüíûå ðàçðÿäû
x1 x2 x3 x4 WS ( , ,[ , , , ])7 4 1111 WS ( , ,[ , , , ])7 4 111 3
0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 1 0 0 1 0 1 1
2 0 0 1 0 0 0 1 0 0 1
3 0 0 1 1 0 1 0 1 0 0
4 0 1 0 0 0 0 1 0 0 1
5 0 1 0 1 0 1 0 1 0 0
6 0 1 1 0 0 1 0 0 1 0
7 0 1 1 1 0 1 1 1 0 1
8 1 0 0 0 0 0 1 0 0 1
9 1 0 0 1 0 1 0 1 0 0
10 1 0 1 0 0 1 0 0 1 0
11 1 0 1 1 0 1 1 1 0 1
12 1 1 0 0 0 1 0 0 1 0
13 1 1 0 1 0 1 1 1 0 1
14 1 1 1 0 0 1 1 0 1 1
15 1 1 1 1 1 0 0 1 1 0
Òàáëèöà 1
 òàáë. 3 ïðèâåäåíû ðàñïðåäåëåíèÿ íåîáíàðóæèâàåìûõ îøèáîê âî
âñåõ âçâåøåííûõ êîäàõ WS (7, 4, [w1, w2, w3, w4]) ïðè m = 4, óäîâëåò-
âîðÿþùèõ óñëîâèþ (2). Âñå ýòè êîäû ïîìåõîóñòîé÷èâû (îáíàðóæèâàþò
âñå îäèíî÷íûå èñêàæåíèÿ), íî êàæäûé èç íèõ èìååò ðàçëè÷íûå ðàñïðå-
äåëåíèÿ íåîáíàðóæèâàåìûõ îøèáîê è ðàçëè÷íóþ ýôôåêòèâíîñòü. Íåêîòî-
ðûå êîäû îáíàðóæèâàþò âñå îøèáêè íå÷åòíîé êðàòíîñòè, êàê è êëàññè-
÷åñêèé êîä ñ ñóììèðîâàíèåì, ïðèâåäåííûé â ïåðâîé ñòðîêå òàáë. 3. Ëþ-
áîé èç ïðèâåäåííûõ âçâåøåííûõ êîäîâ áîëåå ýôôåêòèâåí, ÷åì S (7, 4)-
êîä. Èõ ìîæíî ñðàâíèòü ñ ìîäèôèöèðîâàííûìè êîäàìè Áåðãåðà RS (7, 4, 1)
è RS (7, 4, 2), ïðèíöèï ïîñòðîåíèÿ êîòîðûõ îïèñàí â [9—11].
Èç òàáë. 3 âèäíî, ÷òî ìîäèôèöèðîâàííûå êîäû Áåðãåðà ïðè m = 4 ïî
ñðàâíåíèþ ñ äðóãèìè êîäàìè ñ ñóììèðîâàíèåì èìåþò áîëåå âûñîêóþ
ýôôåêòèâíîñòü îáíàðóæåíèÿ èñêàæåíèé â èíôîðìàöèîííûõ âåêòîðàõ.
Ïðè ýòîì RS (7, 4, 2)-êîä íå îáíàðóæèâàåò äâå îäíîíàïðàâëåííûå îøèáêè.
Ñ óâåëè÷åíèåì çíà÷åíèÿ m ÷èñëî îäíîíàïðàâëåííûõ íåîáíàðóæèâàåìûõ
îøèáîê ó ìîäèôèöèðîâàííûõ êîäîâ Áåðãåðà óâåëè÷èâàåòñÿ, à âçâåøåííûå
êîäû îáíàðóæèâàþò âñå îäíîíàïðàâëåííûå îøèáêè [1].
Âçâåøèâàÿ èíôîðìàöèîííûå ðàçðÿäû, ìîæíî ïîëó÷èòü áîëüøîå ðàçíî-
îáðàçèå êîäîâ ñ ñóììèðîâàíèåì ñ ðàçëè÷íûìè ðàñïðåäåëåíèÿìè íåîáíàðóæè-
âàåìûõ îøèáîê, ïðèãîäíûõ äëÿ ðåøåíèÿ çàäà÷ òåõíè÷åñêîé äèàãíîñòèêè.
Íåêîòîðûå ñâîéñòâà âçâåøåííûõ êîäîâ ñ ñóììèðîâàíèåì ïî îáíà-
ðóæåíèþ îøèáîê â ñèñòåìàõ ôóíêöèîíàëüíîãî êîíòðîëÿ. Ïðè óâåëè-
÷åíèè çíà÷åíèÿ m è ôèêñèðîâàííîì k ÷èñëî ðàçëè÷íûõ âàðèàíòîâ âçâåøè-
âàíèÿ èíôîðìàöèîííûõ ðàçðÿäîâ óìåíüøàåòñÿ, òàê êàê ÷èñëî èíôîðìà-
öèîííûõ ðàçðÿäîâ ïðèáëèæàåòñÿ ê âåëè÷èíå 2 1k � (ñì. (2)).  òàáë. 4 ïðè-
Âçâåøåííûå êîäû ñ ñóììèðîâàíèåì äëÿ îðãàíèçàöèè êîíòðîëÿ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 65
000 001 010 011 100 101 110 111
0000 0001
0010
0100
1000
0111
1011
1101
1110
1111
0110
1001
1010
1100
0011
0101
Ðèñ. 2. Ïåðåðàñïðåäåëåíèå èíôîðìàöèîííûõ âåêòîðîâ
âåäåíî ÷èñëî ðàçëè÷íûõ âçâåøåííûõ êîäîâ ñ ñóììèðîâàíèåì â çàâèñè-
ìîñòè îò çíà÷åíèÿ m, èìåþùèõ òàêóþ æå äëèíó êîíòðîëüíîãî âåêòîðà, êàê
è êîäû Áåðãåðà.
Ñ ïîìîùüþ ðàçðàáîòàííîãî ïðîãðàììíîãî îáåñïå÷åíèÿ, ðåàëèçóþ-
ùåãî àëãîðèòì ïîäñ÷åòà ÷èñëà íåîáíàðóæèâàåìûõ îøèáîê ïî êðàòíîñòÿì
(îí îñíîâàí íà òàáëè÷íîé ôîðìå çàäàíèÿ êîäîâ), ïîëó÷åíû ðàñïðåäåëåíèÿ
íåîáíàðóæèâàåìûõ îøèáîê äëÿ âñåõ âçâåøåííûõ êîäîâ ñ ÷èñëîì êîíò-
ðîëüíûõ ðàçðÿäîâ, îïðåäåëÿåìûõ ïî ôîðìóëå � �k m� log ( )2 1 , è äëèíîé
èíôîðìàöèîííîãî âåêòîðà m = 2 � 20.
 òàáë. 5 ïðèâåäåíû ðàñïðåäåëåíèÿ íåîáíàðóæèâàåìûõ îøèáîê èí-
ôîðìàöèîííûõ ðàçðÿäîâ âî âñåõ WS (14, 10, [w1, w2, …, w10])-êîäàõ. Â ïåð-
âîé ñòðîêå ïðåäñòàâëåí êëàññè÷åñêèé êîä Áåðãåðà, ýôôåêòèâíîñòü êîòî-
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ
66 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
Êîä
×èñëî íåîáíàðóæèâàåìûõ
îøèáîê êðàòíîñòè d
×èñëî îäíîíàïðàâëåííûõ
íåîáíàðóæèâàåìûõ îøèáîê
êðàòíîñòè d N m �
1 2 3 4 1 2 3 4
WS ( , ,[ , , , ])7 4 1 1 1 1 0 48 0 6 0 0 0 0 54 0,2963
WS ( , ,[ , , , ])7 4 1 1 1 2 0 24 12 0 0 0 0 0 36 0,4444
WS ( , ,[ , , , ])7 4 1 1 1 3 0 24 0 2 0 0 0 0 26 0,6154
WS ( , ,[ , , , ])7 4 1 1 1 4 0 24 0 0 0 0 0 0 24 0,6667
WS ( , ,[ , , , ])7 4 11 2 2 0 16 8 4 0 0 0 0 28 0,5714
WS ( , ,[ , , , ])7 4 11 2 3 0 8 12 0 0 0 0 0 20 0,8
RS ( , , )7 4 1 0 24 0 0 0 0 0 0 24 0,6667
RS ( , , )7 4 2 0 16 0 8 0 0 0 2 24 0,6667
Òàáëèöà 3
Èíôîðìàöèîííûå âåêòîðû
000 001 010 011 100 101 110 111
Äëÿ êîäà WS (7, 4, [1, 1, 1, 3])
0000 0010 0110 0001 0011 0111 1111
0100 1010 1110 0101 1011
1000 1100 1001 1101
Äëÿ êîäà WS (7, 4, [1, 1, 1, 4])
0000 0010 0110 1110 0001 0011 0111 1111
0100 1010 0101 1011
1000 1100 1001 1101
Òàáëèöà 2
ðîãî � = 0,3511. Íàèáîëüøóþ ýôôåêòèâíîñòü, � = 0,69, èìååò âçâåøåííûé
êîä WS (14, 10, [1, 1, 1, 1, 1, 1, 1, 1, 2, 5]), ÷òî â 1,965 ðàçà áîëüøå, ÷åì ó
êëàññè÷åñêîãî êîäà ñ ñóììèðîâàíèåì.
Àíàëèç òàáëèö äëÿ ðàññìàòðèâàåìîãî êëàññà âçâåøåííûõ êîäîâ ñ
ñóììèðîâàíèåì ïîçâîëÿåò óñòàíîâèòü ðÿä ñâîéñòâ íîâûõ êîäîâ, èìåþùèõ
çíà÷åíèå äëÿ ïðàêòè÷åñêîé çàäà÷è âûáîðà êîäà ïðè îðãàíèçàöèè ñèñòåì
ôóíêöèîíàëüíîãî êîíòðîëÿ.
Ñâîéñòâî 1. Ëþáîé âçâåøåííûé êîä èìååò ìåíüøåå îáùåå ÷èñëî
íåîáíàðóæèâàåìûõ îøèáîê, ÷åì êëàññè÷åñêèé êîä ñ ñóììèðîâàíèåì ïðè
òåõ æå äëèíàõ èíôîðìàöèîííûõ è êîíòðîëüíûõ âåêòîðîâ.
Äàííîå ñâîéñòâî ñëåäóåò èç ñðàâíåíèÿ âåëè÷èí Nm â òàáë. 5.
Îáîçíà÷èì � ðàçíèöó ìåæäó ìàêñèìàëüíûì çíà÷åíèåì âåñà äëÿ äàííîãî
çíà÷åíèÿ m (îíî ðàâíî âåðõíåé ãðàíèöå 2 1k � ) è ìàêñèìàëüíûì çíà÷åíèåì
ñóììàðíîãî âåñà èíôîðìàöèîííîãî âåêòîðà W x wi i
i
m
max �
�
�
1
. Ñïðàâåäëèâî
ñëåäóþùåå óòâåðæäåíèå.
Ñâîéñòâî 2. Ëþáîé âçâåøåííûé êîä îáíàðóæèâàåò âñå îøèáêè ìàê-
ñèìàëüíîé êðàòíîñòè d = m, åñëè âåëè÷èíà � � � �
�
�( )2 1
1
k
i i
i
m
x w åñòü ÷åò-
íîå ÷èñëî.
Âçâåøåííûå êîäû ñ ñóììèðîâàíèåì äëÿ îðãàíèçàöèè êîíòðîëÿ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 67
m k
Ñóììàðíûé âåñ
×èñëî âçâåøåííûõ êîäîâ
ñ ñóììèðîâàíèåì
Ìèíèìàëüíûé Ìàêñèìàëüíûé
2 2 2 3 2
3 2 3 3 1
4 3 4 7 7
5 3 5 7 4
6 3 6 7 2
7 3 7 7 1
8 4 8 15 45
9 4 9 15 30
10 4 10 15 19
11 4 11 15 12
12 4 12 15 7
13 4 13 15 4
14 4 14 15 2
15 4 15 15 1
Òàáëèöà 4
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ
68 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
Â
åñ
î
â
û
å
ê
î
ýô
ô
è
ö
è
åí
òû
ð
àç
ð
ÿ
ä
î
â
W
m
ax
×
è
ñë
î
í
åî
á
í
àð
ó
æ
è
â
àå
ì
û
õ
î
ø
è
á
î
ê
ê
ð
àò
í
î
ñò
è
d
N
m
�
1
2
3
4
5
6
7
8
9
1
0
[1
,1
,1
,1
,1
,1
,1
,1
,1
,1
]
1
0
0
2
3
0
4
0
0
8
0
6
4
0
0
6
7
2
0
0
0
1
2
6
0
0
0
2
5
2
1
8
3
7
3
2
0
,3
5
[1
,1
,1
,1
,1
,1
,1
,1
,1
,2
]
1
1
0
1
8
4
3
2
9
2
1
6
4
8
3
8
4
3
2
2
5
6
2
6
8
8
0
2
0
1
6
0
2
5
2
0
2
0
1
6
0
1
5
9
8
6
4
0
,4
0
[1
,1
,1
,1
,1
,1
,1
,1
,2
,2
]
1
2
0
1
4
8
4
8
1
4
3
3
6
3
4
0
4
8
3
5
8
4
0
2
4
6
4
0
1
3
4
4
0
6
1
0
4
4
4
8
1
9
6
1
4
3
9
0
0
0
,4
4
[1
,1
,1
,1
,1
,1
,1
,1
,1
,3
]
1
2
0
1
8
4
3
2
0
5
9
1
3
6
0
4
7
0
4
0
0
8
5
6
8
0
1
6
8
1
3
3
3
4
4
0
,4
8
[1
,1
,1
,1
,1
,1
,1
,2
,2
,2
]
1
3
0
1
2
2
8
8
1
6
1
2
8
2
9
5
6
8
3
0
9
1
2
2
5
7
6
0
1
1
7
6
0
4
3
6
8
1
2
8
8
0
1
3
2
0
7
2
0
,4
8
[1
,1
,1
,1
,1
,1
,1
,1
,2
,3
]
1
3
0
1
4
3
3
6
9
2
1
6
3
4
0
4
8
2
8
6
7
2
1
7
9
2
0
1
6
5
7
6
1
6
2
4
1
5
6
8
0
1
2
3
9
6
0
0
,5
2
[1
,1
,1
,1
,1
,1
,1
,1
,1
,4
]
1
3
0
1
8
4
3
2
0
4
8
3
8
4
8
0
6
4
2
6
8
8
0
8
0
6
4
2
5
2
0
1
0
0
8
0
1
1
3
3
5
2
0
,5
6
[1
,1
,1
,1
,1
,1
,2
,2
,2
,2
]
1
4
0
1
0
7
5
2
1
5
3
6
0
2
9
1
8
4
2
6
8
8
0
2
3
3
6
0
1
2
4
8
0
3
8
8
8
7
3
6
1
6
8
1
2
2
8
0
8
0
,5
2
[1
,1
,1
,1
,1
,1
,1
,2
,2
,3
]
1
4
0
1
1
2
6
4
1
4
3
3
6
2
4
1
9
2
3
1
3
6
0
1
9
0
4
0
1
0
7
5
2
4
9
8
4
3
3
6
1
5
6
1
1
6
4
2
0
0
,5
5
[1
,1
,1
,1
,1
,1
,1
,1
,3
,3
]
1
4
0
1
4
8
4
8
0
4
8
3
8
4
0
4
0
3
2
0
0
7
4
7
2
0
1
5
6
1
1
1
3
8
0
0
,5
7
[1
,1
,1
,1
,1
,1
,1
,1
,2
,4
]
1
4
0
1
4
3
3
6
7
1
6
8
3
0
4
6
4
2
2
4
0
0
1
7
9
2
0
9
4
0
8
3
8
6
4
3
3
6
1
2
8
1
0
6
0
2
4
0
,6
0
[1
,1
,1
,1
,1
,1
,1
,1
,1
,5
]
1
4
0
1
8
4
3
2
0
4
8
3
8
4
0
3
0
9
1
2
0
4
5
3
6
0
7
2
1
0
2
3
3
6
0
,6
3
[1
,1
,1
,1
,1
,2
,2
,2
,2
,2
]
1
5
0
1
0
2
4
0
1
2
8
0
0
2
9
4
4
0
2
5
6
0
0
2
0
8
0
0
1
1
2
0
0
4
4
0
0
8
0
0
0
1
1
5
2
8
0
0
,5
5
[1
,1
,1
,1
,1
,1
,2
,2
,2
,3
]
1
5
0
9
2
1
6
1
6
1
2
8
2
2
1
4
4
2
7
0
7
2
2
0
9
6
0
9
9
6
8
3
5
0
4
1
0
9
6
0
1
1
0
0
8
8
0
,5
0
[1
,1
,1
,1
,1
,1
,1
,2
,3
,3
]
1
5
0
1
1
2
6
4
8
9
6
0
2
7
7
7
6
2
5
0
8
8
1
5
6
8
0
1
4
1
1
2
1
5
1
2
1
3
4
4
0
1
0
5
7
3
6
0
,6
1
[1
,1
,1
,1
,1
,1
,1
,2
,2
,4
]
1
5
0
1
1
2
6
4
1
1
0
0
8
2
4
1
9
2
2
2
8
4
8
1
9
0
4
0
8
5
1
2
3
2
4
8
8
9
6
0
1
0
1
0
0
8
0
,6
3
[1
,1
,1
,1
,1
,1
,1
,1
,3
,4
]
1
5
0
1
4
3
3
6
2
0
4
8
3
4
0
4
8
1
5
2
3
2
1
7
9
2
0
1
1
6
4
8
1
6
2
4
1
2
6
4
0
9
8
1
2
0
0
,6
5
[1
,1
,1
,1
,1
,1
,1
,1
,2
,5
]
1
5
0
1
4
3
3
6
7
1
6
8
2
6
8
8
0
2
1
5
0
4
1
0
7
5
2
1
1
2
0
0
7
5
8
9
2
8
0
9
3
4
9
6
0
,6
0
[1
,1
,1
,1
,1
,1
,1
,1
,1
,6
]
1
5
0
1
8
4
3
2
0
4
8
3
8
4
0
2
6
8
8
0
1
3
4
4
2
5
2
0
2
8
8
0
9
7
8
4
8
0
,6
5
Ò
à
á
ëö
à
5
Ñâîéñòâî 2 òàêæå âûòåêàåò èç òàáë. 5: âñå êîäû ñ ÷åòíûìè çíà÷åíèÿìè
� îáíàðóæèâàþò ëþáûå èñêàæåíèÿ êðàòíîñòè d = m. Ýòî êîäû ñ Wmax = 11,
13, 15.
 òàáë. 6 ïðåäñòàâëåíû õàðàêòåðèñòèêè íàèáîëåå ýôôåêòèâíûõ
WS (n, m, [w1, w2, ..., wm])-êîäîâ ñ çàäàííûìè ïàðàìåòðàìè äëèí èíôîðìà-
öèîííûõ è êîíòðîëüíûõ âåêòîðîâ.  íåêîòîðûõ ñëó÷àÿõ âçâåøåííûé êîä îá-
íàðóæèâàåò áîëåå ÷åì â äâà ðàçà áîëüøå îøèáîê èíôîðìàöèîííûõ ðàç-
ðÿäîâ, ÷åì êîä Áåðãåðà.  ñòðîêàõ 1, 5, 13 òàáë. 6 çàïèñàíû êîäû Áåðãåðà,
òàê êàê âçâåøèâàíèå èíôîðìàöèîííûõ ðàçðÿäîâ ïðèâîäèò ê íàðóøåíèþ
óñëîâèÿ (2).
 ðåçóëüòàòå èññëåäîâàíèé óñòàíîâëåíî, ÷òî ñóùåñòâóåò ïðîñòîå ñîîò-
íîøåíèå âåñîâ èíôîðìàöèîííûõ ðàçðÿäîâ, ïðè êîòîðîì êîä îáíàðóæè-
âàåò ëþáûå îøèáêè íå÷åòíûõ êðàòíîñòåé, à òàêæå âñå îäíîíàïðàâëåííûå
îøèáêè ÷åòíûõ êðàòíîñòåé â èíôîðìàöèîííûõ âåêòîðàõ. Ïîäîáíûìè
ñâîéñòâàìè îáëàäàåò è êëàññè÷åñêèé êîä Áåðãåðà.
Íà ðèñ. 2. âèäíî íå òîëüêî áîëåå ðàâíîìåðíîå ðàñïðåäåëåíèå èíôîð-
ìàöèîííûõ âåêòîðîâ íà êîíòðîëüíûå ãðóïïû, íî è î÷åâèäåí ñäâèã âåêòî-
ðîâ ïðè âçâåøèâàíèè èíôîðìàöèîííîãî ðàçðÿäà. Ïðè ýòîì èíôîðìàöèîí-
íûå âåêòîðû ñ îäèíàêîâûì ïî ÷åòíîñòè ÷èñëîì åäèíèö ïîïàäàþò â îäíó
ãðóïïó, ÷òî ïîçâîëÿåò ñîõðàíèòü ñòðóêòóðó íåîáíàðóæèâàåìûõ îøèáîê:
âçâåøåííûé êîä WS (7, 4, [1, 1, 1, 3]) òàêæå îáíàðóæèâàåò âñå îøèáêè íå-
÷åòíîé êðàòíîñòè, êàê è WS (7, 4, [1, 1, 1, 1])-êîä.
Âçâåøåííûå êîäû ñ ñóììèðîâàíèåì äëÿ îðãàíèçàöèè êîíòðîëÿ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 69
Íîìåð
ñòðîêè
m k
Âåñîâûå êîýôôèöèåíòû
ðàçðÿäîâ
Nm N m
min
�
Óâåëè÷åíèå
ýôôåêòèâíîñòè
îòíîñèòåëüíî
S (n,m)-êîäà
1 3 2 [1,1,1] 12 8 0,66667 1
2 4 3 [1,1,1,4] 24 16 0,66667 2,25
3 5 3 [1,1,1,1,3] 124 96 0,77419 1,77
4 6 3 [1,1,1,1,1,2] 680 448 0,65882 1,26
5 7 3 [1,1,1,1,1,1,1] 3304 1920 0,58111 1
6 8 4 [1,1,1,1,1,1,6,3] 4764 3840 0,80605 2,65
7 9 4 [1,1,1,1,1,1,1,5,3] 21588 15872 0,73522 2,23
8 10 4 [1,1,1,1,1,1,1,1,5,2] 93496 64512 0,69 1,97
9 11 4 [1,1,1,1,1,1,1,1,1,1,5] 398472 260096 0,65273 1,77
10 12 4 [1,1,1,1,1,1,1,1,1,1,1,4] 1747856 1044480 0,59758 1,54
11 13 4 [1,1,1,1,1,1,1,1,1,1,1,1,3] 8015128 4186112 0,52228 1,3
12 14 4 [1,1,1,1,1,1,1,1,1,1,1,1,1,2] 36237136 16760832 0,46253 1,11
13 15 4 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] 155084752 67076096 0,43251 1
Òàáëèöà 6
Äëÿ ëþáûõ WS (n, m, [w1, w2, …, wm])-êîäîâ ñïðàâåäëèâî ñëåäóþùåå
ñâîéñòâî.
Òåîðåìà. Âçâåøåííûé êîä ñ ñóììèðîâàíèåì îáíàðóæèâàåò ëþáûå
îøèáêè íå÷åòíûõ êðàòíîñòåé è âñå îäíîíàïðàâëåííûå îøèáêè ÷åòíûõ
êðàòíîñòåé, åñëè âñå âåñà åãî èíôîðìàöèîííûõ ðàçðÿäîâ ÿâëÿþòñÿ íå÷åò-
íûìè ÷èñëàìè.
Ä î ê à ç à ò å ë ü ñ ò â î. Äëÿ äîêàçàòåëüñòâà îòñóòñòâèÿ íåîáíàðó-
æèâàåìûõ îøèáîê íå÷åòíîé êðàòíîñòè íåîáõîäèìî ïîêàçàòü, ÷òî îäíîìó
êîíòðîëüíîìó âåêòîðó ñîîòâåòñòâóþò èíôîðìàöèîííûå âåêòîðû ñ îäèíà-
êîâûì ïî ÷åòíîñòè ñóììàðíûì âåñîì.
Ðàññìîòðèì âçâåøåííûé êîä ñ ñóììèðîâàíèåì WS (n,m,[w1,w2, …,wm])
ñ äëèíîé èíôîðìàöèîííîãî âåêòîðà, ðàâíîé m. Ïóñòü ó ýòîãî êîäà âñå
èíôîðìàöèîííûå ðàçðÿäû, êðîìå îäíîãî, èìåþò âåñ wi = 1, à îäèí èíôîð-
ìàöèîííûé ðàçðÿä — íå÷åòíûé âåñ wm. Âñå èíôîðìàöèîííûå âåêòîðû äàí-
íîãî êîäà ìîæíî ðàçáèòü íà äâå ãðóïïû, < ~ ~ … ~ 0 > è < ~ ~ … ~ 1 >, ãäå
ïîñëåäíèé ðàçðÿä èìååò âåñ wm.
Îáîçíà÷èì r1 = r âåñ èíôîðìàöèîííîãî âåêòîðà < ~ ~ … ~ 1 > íåâçâå-
øåííîãî êîäà. Òîãäà âåêòîð < ~ ~ … ~ 0 > áóäåò èìåòü âåñ r0 = r �1. Ñ
ó÷åòîì ýòîãî èíôîðìàöèîííûå âåêòîðû WS n m w w wm( , . [ , ,..., ])1 2 -êîäà áó-
äóò èìåòü ñóììàðíûé âåñ ëèáî W0 = r – 1, ëèáî W 1 = r – 1 + wi. Åñëè r —
÷åòíîå ÷èñëî, òî ÷èñëî W0 ÿâëÿåòñÿ íå÷åòíûì, à W1 — ÷èñëîì ÷åòíûì, â
ñèëó òîãî, ÷òî ÷èñëà r – 1 è wi — íå÷åòíûå. Íàïðîòèâ, åñëè r — íå÷åòíîå, òî
÷èñëî W0 ÿâëÿåòñÿ ÷åòíûì, à W1 — íå÷åòíûì, â ñèëó òîãî, ÷òî ÷èñëî r –1 —
÷åòíîå, à wi — íå÷åòíîå.
Äîïóñòèì òåïåðü, ÷òî äâà èíôîðìàöèîííûõ ðàçðÿäà èìåþò íå÷åòíûå
çíà÷åíèÿ âåñîâ, wm è wm – 1, à îñòàëüíûå m – 2 èíôîðìàöèîííûõ ðàçðÿäà
èìåþò âåñà wi = 1. Âñå èíôîðìàöèîííûå âåêòîðû äåëÿòñÿ íà ÷åòûðå
êàòåãîðèè, < ~ ~ ... ...~ 0 0 >, < ~ ~ ... ~ 0 1 >, < ~ ~ ... ~ 1 0 > è < ~ ~ ... ~ 1 1 >,
ãäå ïîñëåäíèå äâà ðàçðÿäà — ýòî ñîîòâåòñòâåííî ðàçðÿäû ñ âåñàìè wm – 1 è
wm. Ðàññóæäàÿ, êàê è ðàíåå, çàìåòèì, ÷òî ñóììàðíûå âåñà íåâçâåøåííûõ
èíôîðìàöèîííûõ âåêòîðîâ ðàâíû: r r11 � , r r01 1� � , r r10 1� � , r r00 2� � .
Ïîñëå âçâåøèâàíèÿ ïîëó÷àåì
W r w wi i
11
12� � � , W r wi
01 1� � , W r wi
10
11� � � , W r00 � .
Ïóñòü òåïåðü r — ÷åòíîå, òîãäàW 11 è W00 — òàêæå ÷åòíûå, à W01 è W10 —
íå÷åòíûå, ò.å. íå èçìåíèëè ñâîåé ÷åòíîñòè ïðè âçâåøèâàíèè; ïóñòü r —
íå÷åòíîå, òîãäà W11 è W00 ÿâëÿþòñÿ íå÷åòíûìè, à W01 è W10 — ÷åòíûìè, ò.å.
òàêæå íå èçìåíèëè ñâîåé ÷åòíîñòè ïðè âçâåøèâàíèè.
Ïðè âçâåøèâàíèè îäíîãî èíôîðìàöèîííîãî ðàçðÿäà ÷èñëî ãðóïï âåê-
òîðîâ ðàâíî äâóì, ïðè âçâåøèâàíèè äâóõ èíôîðìàöèîííûõ ðàçðÿäîâ ÷èñ-
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ
70 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
ëî ãðóïï âåêòîðîâ ðàâíî 2 � 2 = 4. Ïðè êàæäîì äîáàâëåíèè îäíîãî âçâåøåí-
íîãî ðàçðÿäà ÷èñëî ðàññìàòðèâàåìûõ ãðóïï óâåëè÷èâàåòñÿ â äâà ðàçà: ïðè
k âçâåøåííûõ ðàçðÿäàõ îíî ðàâíî 2k . ×åòíîñòü âåêòîðîâ ïðè âçâåøèâàíèè
íå ìåíÿåòñÿ ïî ñðàâíåíèþ ñ âåêòîðàìè êîäà ñ íåâçâåøåííûìè ðàçðÿäàìè.
Òàêèì îáðàçîì, åñëè îäèí èëè äâà ðàçðÿäà âçâåøåíû è ïðè ýòîì èìåþò
íå÷åòíûå çíà÷åíèÿ âåñîâûõ êîýôôèöèåíòîâ ðàçðÿäîâ, òî ÷åòíîñòü âåñà
èíôîðìàöèîííîãî âåêòîðà ñîõðàíÿåòñÿ. Îøèáêè, ïåðåâîäÿùèå èíôîðìà-
öèîííûå âåêòîðû ñ îäèíàêîâûìè êîíòðîëüíûìè âåêòîðàìè äðóã â äðóãà,
ÿâëÿþòñÿ íåîáíàðóæèâàåìûìè. Ïîñêîëüêó ÷åòíîñòü ñîõðàíèëàñü, ýòè
îøèáêè ÿâëÿþòñÿ îøèáêàìè ÷åòíûõ êðàòíîñòåé. Àíàëîãè÷íûå ðåçóëüòàòû
ïîëó÷åíû è ïðè àíàëèçå èíôîðìàöèîííûõ âåêòîðîâ ñ áîëüøèì ÷èñëîì
íå÷åòíûõ âåñîâûõ êîýôôèöèåíòîâ.
Ñâîéñòâî ðàçíîíàïðàâëåííîñòè íåîáíàðóæèâàåìûõ îøèáîê âûòåêàåò
èç òîãî, ÷òî ïðè âçâåøèâàíèè èíôîðìàöèîííûõ âåêòîðîâ ïðîèñõîäèò óâå-
ëè÷åíèå ñóììàðíîãî âåñà, ò.å. ñìåùåíèå çíà÷åíèÿ èñòèííîãî âåñà â áîëü-
øóþ ñòîðîíó. Â ãðóïïó ñ âåñîì r, ñîîòâåòñòâóþùèì âåñó íåâçâåøåííîãî
êîäà, íèêîãäà íå ïîïàäåò èíôîðìàöèîííûé âåêòîð âçâåøåííîãî êîäà ñ
áîëüøèì çíà÷åíèåì âåñà. Òåîðåìà äîêàçàíà.
Ñëåäóåò çàìåòèòü, ÷òî äàííàÿ òåîðåìà ñïðàâåäëèâà äëÿ ëþáûõ âçâå-
øåííûõ êîäîâ ñ ñóììèðîâàíèåì, äëÿ êîòîðûõ ñóììàðíîå çíà÷åíèå âåñà íå
îáÿçàòåëüíî ðàâíî 2 1k � .
Äëÿ ïðèìåðà ðàññìîòðèì ðàñïðåäåëåíèå èíôîðìàöèîííûõ âåêòîðîâ
êîäà WS (8,5, [1,1,1,1,3]) îòíîñèòåëüíî êîíòðîëüíûõ âåêòîðîâ [20]. Èç
òàáë. 7 âèäíî, ÷òî ëþáîé ïåðåõîä âíóòðè êîíòðîëüíîé ãðóïïû — ýòî èñêà-
æåíèå ÷åòíîé êðàòíîñòè, è ëþáîé òàêîé ïåðåõîä ÿâëÿåòñÿ ðàçíîíàïðàâëåí-
íûì. Íà ðèñ. 3 ïðèâåäåíû âñå ïåðåõîäû, èñêàæàþùèå êîäîâûé âåêòîð
00011 êîíòðîëüíîé ãðóïïû 100 è ïåðåâîäÿùèå åãî â êîäîâûé âåêòîð ýòîé
æå êîíòðîëüíîé ãðóïïû. Ñðåäè íåîáíàðóæèâàåìûõ èñêàæåíèé — òîëüêî
èñêàæåíèÿ ÷åòíîé êðàòíîñòè, ïðè÷åì ðàçíîíàïðàâëåííûå.
Êîä WS (8,5, [1,1,1,1,3]) èìååò 124 íåîáíàðóæèâàåìûå îøèáêè, ÷òî â
1,77 ðàçà ìåíüøå, ÷åì â êëàññè÷åñêîì êîäå Áåðãåðà (WS (8,5, [1,1,1,1,1])-
Âçâåøåííûå êîäû ñ ñóììèðîâàíèåì äëÿ îðãàíèçàöèè êîíòðîëÿ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 71
000 001 010 011 100 101 110 111
00000 00010 00110 00001 00011 00111 01111 11111
00100 01010 01110 00101 01011 10111
01000 01100 10110 01001 01101 11011
10000 10010 11010 10001 10011 11101
10100 11100 11110 10101
11000 11001
Òàáëèöà 7
êîäå èëè S (8,5)-êîäå), èìåþùåì 220 íåîáíàðóæèâàåìûõ îøèáîê. Âçâå-
øåííûé êîä ñ ñóììèðîâàíèåì WS (8,5, [1,1,1,1,3]) áîëåå áëèçîê ê îïòè-
ìàëüíîìó, ÷åì S (8,5)-êîä, ââèäó áîëåå ðàâíîìåðíîãî ðàñïðåäåëåíèÿ èí-
ôîðìàöèîííûõ âåêòîðîâ íà êîíòðîëüíûå ãðóïïû.
Òàêèì îáðàçîì, ëþáîé âçâåøåííûé êîä ñ íå÷åòíûìè âåñàìè èíôîðìà-
öèîííûõ ðàçðÿäîâ îáíàðóæèâàåò ëþáûå îøèáêè íå÷åòíûõ êðàòíîñòåé è
âñå îäíîíàïðàâëåííûå ÷åòíûå èñêàæåíèÿ èíôîðìàöèîííûõ âåêòîðîâ. Âçâå-
øåííûå êîäû ñ ñóììèðîâàíèåì ìîãóò áûòü ýôôåêòèâíî ïðèìåíåíû äëÿ
îðãàíèçàöèè ñèñòåì ôóíêöèîíàëüíîãî êîíòðîëÿ êîìáèíàöèîííûõ ëîãè÷åñ-
êèõ ñõåì ñ ìîíîòîííûìè è ìîíîòîííî íåçàâèñèìûìè âûõîäàìè [21, 22].
Óñòàíîâèì íåêîòîðûå ñâîéñòâà âçâåøåííûõ êîäîâ ñ ñóììèðîâàíèåì,
óäîâëåòâîðÿþùèõ óñëîâèÿì òåîðåìû, ò.å. èìåþùèõ òîëüêî íå÷åòíûå âåñà
èíôîðìàöèîííûõ ðàçðÿäîâ. Â òàáë. 8 ïðåäñòàâëåíû ðàñïðåäåëåíèÿ íåîá-
íàðóæèâàåìûõ îøèáîê â WS(n,m,[w1,w2, …,wm])-êîäàõ ñî ñâîéñòâîì îáíà-
ðóæåíèÿ ëþáûõ èñêàæåíèé èíôîðìàöèîííûõ ðàçðÿäîâ íå÷åòíûõ êðàòíîñ-
òåé äëÿ m = 3 � 12.
Íà îñíîâàíèè àíàëèçà ïîäîáíûõ òàáëèö ïðè äëèíàõ èíôîðìàöèîííûõ
âåêòîðîâ êîäîâ m � 20 óñòàíîâëåíû ñëåäóþùèå ñâîéñòâà âçâåøåííûõ
êîäîâ.
Ñâîéñòâî 3. Äëÿ WS (n,m, [1,1, …, 1,�� �])-êîäîâ, ãäå � = 1, 3, ... è � �
� � � �� � � �, ... ÷èñëî íåîáíàðóæèâàåìûõ îøèáîê êðàòíîñòè d = 2 îäèíà-
êîâî äëÿ çàäàííîãî m.
Ïîäîáíûå êîäû èìåþò îòëè÷èå â âåñàõ òîëüêî îäíîãî èíôîðìàöèîí-
íîãî ðàçðÿäà. Çàìåòèì, ÷òî äàííûì ñâîéñòâîì îáëàäàþò, íàïðèìåð, êîäû
WS (12,8, [1,1,1,1,1,1,1,3]), WS (12,8, [1,1,1,1,1,1,1,5]), WS (12,8, [1,1,1,1,1,1,1,7]),
êàæäûé èç êîòîðûõ èìååò ïî 2688 íåîáíàðóæèâàåìûõ îøèáêè èíôîðìà-
öèîííûõ ðàçðÿäîâ êðàòíîñòè d = 2. Äàííîå ñâîéñòâî ÿâíî ïðîñëåæèâàåòñÿ
íà áîëüøèõ äëèíàõ èíôîðìàöèîííûõ âåêòîðîâ. Íàïðèìåð ïðè m = 16 ó
êîäîâ WS (21,16,[1,1, …, 3,3,5]), …, WS (21,16,[1,1, …, 3,3,11]) èìååòñÿ ïî
2588672 íåîáíàðóæèâàåìûõ îøèáêè êðàòíîñòè d = 2.
Ñâîéñòâî 4. Äëÿ WS (n, m, [1,1, ..., 1, �� �])-êîäîâ, ãäå � = 1, 3, ... è � �
� � + 4, � + 6, ... ÷èñëî íåîáíàðóæèâàåìûõ îøèáîê êðàòíîñòè d = 4 îäèíà-
êîâî äëÿ çàäàííîãî m.
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ
72 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
0 0 0 1 1
0 0 1 0 1
0 0 0 1 1
0 1 0 0 1
0 0 0 1 1
1 0 0 0 1
0 0 0 1 1
1 1 1 1 0
Ðèñ. 3. Íåîáíàðóæèâàåìûå èñêàæåíèÿ âåêòîðà 00011 â êîäå WS(8,5,[1,1,1,1,3])
Âçâåøåííûå êîäû ñ ñóììèðîâàíèåì äëÿ îðãàíèçàöèè êîíòðîëÿ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 73
m k
Âåñîâûå
êîýôôèöèåíòû
ðàçðÿäîâ
Êðàòíîñòü íåîáíàðóæèâàåìîé
îøèáêè ïðè d
Nm �
2 4 6 8 10 12
3 2 [1,1,1] 12 — — — — — 12 0,6667
4 3 [1,1,1,1] 48 6 — — — — 54 0,2963
4 3 [1,1,1,3] 24 2 — — — — 26 0,6154
5 3 [1,1,1,1,1] 160 60 — — — — 220 0,4364
5 3 [1,1,1,1,3] 96 28 — — — — 124 0,7742
6 3 [1,1,1,1,1,1] 480 360 20 — — — 860 0,5209
7 3 [1,1,1,1,1,1,1] 1344 1680 280 — — — 3304 0,5811
8 4 [1,1,1,1,1,1,1,1] 3584 6720 2240 70 — — 12614 0,3044
8 4 [1,1,1,1,1,1,1,3] 2688 4488 1400 42 — — 8610 0,446
8 4 [1,1,1,1,1,1,1,5] 2688 3360 728 14 — — 6790 0,5655
8 4 [1,1,1,1,1,1,1,7] 2688 3360 560 2 — — 6610 0,5809
8 4 [1,1,1,1,1,1,3,3] 2048 3680 1280 42 — — 7050 0,5447
8 4 [1,1,1,1,1,1,3,5] 1920 2560 848 30 — — 5358 0,7167
8 4 [1,1,1,1,1,3,3,3] 1664 3360 1080 30 — — 6134 0,626
9 4 [1,1,1,1,1,1,1,1,1] 9216 24192 13440 1260 — — 48108 0,3299
9 4 [1,1,1,1,1,1,1,1,3] 7168 17024 8960 812 — — 33964 0,4673
9 4 [1,1,1,1,1,1,1,1,5] 7168 13440 5376 364 — — 26348 0,6024
9 4 [1,1,1,1,1,1,1,1,7]] 7168 13440 4480 172 — — 25260 0,6283
9 4 [1,1,1,1,1,1,1,3,3] 5632 13888 7840 756 — — 28116 0,5645
9 4 [1,1,1,1,1,1,1,3,5] 5376 10304 5376 532 — — 21588 0,7352
9 4 [1,1,1,1,1,1,3,3,3] 4608 12480 6880 612 — — 24580 0,6457
10 4 [1,1,1,1,1,1,1,1,1,1] 23040 80640 67200 12600 252 — 183732 0,3511
10 4 [1,1,1,1,1,1,1,1,1,3] 18432 59136 47040 8568 168 — 133344 0,4838
10 4 [1,1,1,1,1,1,1,1,1,5] 18432 48384 30912 4536 72 — 102336 0,6304
10 4 [1,1,1,1,1,1,1,1,3,3] 14848 48384 40320 7672 156 — 111380 0,5792
11 4 [1,1,1,1,1,1,1,1,1,1,1] 56320 253440 295680 92400 5544 — 703384 0,3698
11 4 [1,1,1,1,1,1,1,1,1,1,3] 46080 192000 215040 65520 3864 — 522504 0,4978
11 4 [1,1,1,1,1,1,1,1,1,1,5] 46080 161280 150528 38640 1944 — 398472 0,6527
11 4 [1,1,1,1,1,1,1,1,1,3,3] 37888 158208 182784 57456 3480 — 439816 0,5914
12 4 [1,1,1,1,1,1,1,1,1,1,1,1] 135168 760320 1182720 554400 66528 924 2700060 0,3868
12 4 [1,1,1,1,1,1,1,1,1,1,1,3] 112640 591360 887040 406560 48048 660 2046308 0,5104
Òàáëèöà 8
Äàííûå êîäû òàêæå îòëè÷àþòñÿ â âåñå òîëüêî îäíîãî èíôîðìàöèîí-
íîãî ðàçðÿäà. Ïðèìåðàìè êîäîâ, óäîâëåòâîðÿþùèõ ñâîéñòâó 4, ÿâëÿþòñÿ
WS (12,8, [1,1,1,1,1,1,1,5]) è WS (12,8, [1,1,1,1,1,1,1,7])-êîäû (ñì. òàáë. 7).
Äàííûå êîäû èìåþò ïî 3360 íåîáíàðóæèâàåìûõ îøèáîê êðàòíîñòè d = 4.
Ñâîéñòâà 3 è 4 ìîãóò áûòü îáîáùåíû è íà ñëó÷àé áîëüøåé êðàòíîñòè
íåîáíàðóæèâàåìûõ îøèáîê.
Ñâîéñòâî 5. Ìèíèìóì íåîáíàðóæèâàåìûõ îøèáîê ìàêñèìàëüíîé êðàò-
íîñòè (m äëÿ ÷åòíûõ çíà÷åíèé äëèíû èíôîðìàöèîííîãî âåêòîðà è m – 1
äëÿ íå÷åòíûõ) äîñòèãàåòñÿ ïðè âûáîðå åäèíè÷íûõ âåñîâ ó m – 1 èíôîð-
ìàöèîííûõ ðàçðÿäîâ è âåñà îäíîãî èíôîðìàöèîííîãî ðàçðÿäà, ìàêñèìàëü-
íî áëèçêîãî ê âåðõíåé ãðàíèöå, äëÿ ñîõðàíåíèÿ ÷èñëà êîíòðîëüíûõ ðàçðÿ-
äîâ (w mi
k� � �2 1( ) èëè w mi
k� � � �2 1 1( ) ).
Íàïðèìåð, ïðè m = 8 ìèíèìóì íåîáíàðóæèâàåìûõ îøèáîê ìàêñè-
ìàëüíîé êðàòíîñòè d = 8 èìååò WS (12,8, [1,1,1,1,1,1,1,7])-êîä. Äàííûì êî-
äîì íå îáíàðóæèâàåòñÿ äâà òàêèõ èñêàæåíèÿ, ÷òî â 35 ðàç ìåíüøå, íåæåëè
ó êëàññè÷åñêîãî êîäà ñ ñóììèðîâàíèåì ïðè äàííîì m.
Ñâîéñòâî 6. Ïðè çàäàííîì çíà÷åíèè m íàèáîëüøåé ýôôåêòèâíîñòüþ
ñðåäè âçâåøåííûõ êîäîâ ñ ñóììèðîâàíèåì, îòëè÷àþùèõñÿ â âåñå òîëüêî
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ
74 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
m k
Âåñîâûå
êîýôôèöèåíòû ðàçðÿäîâ Nm � W x w
i
m
i i�
�
�
1
W k
max � �2 1
3 2 [1,1,1] 12 0,6667 3 3
4 3 [1,1,1,3] 26 0,6154 7 7
5 3 [1,1,1,1,3] 124 0,7742 7 7
6 3 [1,1,1,1,1,1] 860 0,5209 6 7
7 3 [1,1,1,1,1,1,1] 3304 0,5811 7 7
8 4 [1,1,1,1,1,1,3,5] 5358 0,7167 14 15
9 4 [1,1,1,1,1,1,1,3,5] 21588 0,7352 15 15
10 4 [1,1,1,1,1,1,1,1,1,5] 102336 0,6304 14 15
11 4 [1,1,1,1,1,1,1,1,1,1,5] 398472 0,6527 15 15
14 4 [1,1,1,1,1,1,1,1,1,1,1,1,1,1] 40100216 0,418 14 15
15 4 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] 155084752 0,4325 15 15
16 5 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,5,11] 194257778 0,6906 30 31
17 5 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,5,11] 769242988 0,6978 31 31
18 5 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,5,9] 3385207432 0,6343 30 31
19 5 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,5,9] 13455921056 0,6383 31 31
20 5 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,3,9] 61454926968 0,5591 30 31
Òàáëèöà 9
îäíîãî èíôîðìàöèîííîãî ðàçðÿäà, îáëàäàåò òàêîé êîä, ó êîòîðîãî ñóììàð-
íûé âåñ ïðè ÷åòíîì çíà÷åíèè m
W x w
i
m
i i
k� � �
�
�
1
2 2 ,
à ïðè íå÷åòíîì —
W x w
i
m
i i
k� � �
�
�
1
2 1.
Äàííîå ñâîéñòâî, íàïðèìåð, ïðîñëåæèâàåòñÿ â òàáë. 8 äëÿ âçâåøåí-
íûõ êîäîâ ïðè m = 8. Íàèáîëåå ýôôåêòèâíûìè êîäàìè ñðåäè êîäîâ òèïà
WS (12,8, [1,1,…, 1, �]) ÿâëÿåòñÿ êîä WS (12,8, [1,1,1,1,1,1,1,7]), èìåþùèé 6610
íåîáíàðóæèâàåìûõ îøèáîê, à ñðåäè êîäîâ òèïà WS (12,8, [1,1, ..., 3, �]) —
êîä WS (12,8, [1,1,1,1,1,1,3,5]), êîòîðûé èìååò 5358 íåîáíàðóæèâàåìûõ
îøèáîê èíôîðìàöèîííûõ ðàçðÿäîâ.
Ñâîéñòâî 6 óïðîùàåò ïðàêòè÷åñêóþ çàäà÷ó âûáîðà íàèëó÷øåãî âà-
ðèàíòà êîäèðîâàíèÿ èç âñåãî ìíîæåñòâà âçâåøåííûõ êîäîâ. Áîëåå òîãî,
ìàêñèìàëüíî ýôôåêòèâíûé êîä íàõîäèòñÿ âî ìíîæåñòâå âçâåøåííûõ êî-
äîâ, óäîâëåòâîðÿþùèõ ñâîéñòâó 6.
 òàáë. 9 ïðèâåäåíû ìàêñèìàëüíî ýôôåêòèâíûå âçâåøåííûå êîäû ñ
ñóììèðîâàíèåì ïðè ìàêñèìàëüíûõ çíà÷åíèÿõ �. Êàê ïîêàçàëè ðåçóëüòàòû
Âçâåøåííûå êîäû ñ ñóììèðîâàíèåì äëÿ îðãàíèçàöèè êîíòðîëÿ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 75
m k
Âåñîâûå
êîýôôèöèåíòû ðàçðÿäîâ
×èñëî äâóêðàòíûõ
íåîáíàðóæèâàåìûõ
èñêàæåíèé êîäîâ
Îáùåå
÷èñëî
äâóêðàòíûõ
èñêàæåíèé
�2 �
WS n m( , ) S n m( , )
4 3 [1,1,1,3] 24 48 96 0,25 2
5 3 [1,1,1,1,3] 96 160 320 0,3 1,6667
8 4 [1,1,1,1,1,3,3,3] 1664 3584 7168 0,2321 2,1538
9 4 [1,1,1,1,1,1,3,3,3] 4608 9216 18432 0,25 2
10 4 [1,1,1,1,1,1,1,1,3,3] 14848 23040 46080 0,3222 1,5517
11 4 [1,1,1,1,1,1,1,1,1,3,3] 37888 56320 112640 0,3364 1,4865
12 4 [1,1,1,1,1,1,1,1,1,1,1,3] 112640 135168 270336 0,4167 1,2
13 4 [1,1,1,1,1,1,1,1,1,1,1,1,3] 270336 319488 638976 0,4231 1,1818
16 5 [1,1,1,1,1,1,1,1,1,1,1,3,3,3,3,3,5] 1802240 3932160 7864320 0,2292 2,1818
17 5 [1,1,1,1,1,1,1,1,1,1,1,1,3,3,3,3,3,5] 4259840 8912896 17825792 0,239 2,0923
18 5 [1,1,1,1,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3] 10616832 20054016 40108032 0,2647 1,8889
19 5 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3] 24379392 44826624 89653248 0,2719 1,8387
20 5 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,3,3,3,3,3] 60293120 99614720 199229440 0,3026 1,6522
Òàáëèöà 10
èññëåäîâàíèé, ñâîéñòâó 6 óäîâëåòâîðÿåò è âçâåøåííûé êîä ñ ìèíèìàëüíûì
÷èñëîì íåîáíàðóæèâàåìûõ îøèáîê êðàòíîñòè d = 2. Âçâåøåííûå êîäû ñ
ìèíèìàëüíûì ÷èñëîì äâóêðàòíûõ èñêàæåíèé îáëàäàþò áîëåå ðàâíîìåð-
íûì ðàñïðåäåëåíèåì âåñîâ èíôîðìàöèîííûõ ðàçðÿäîâ, íåæåëè íàèáîëåå
ýôôåêòèâíûå (òàáë. 10). ×àñòî êîä ñ ñóììèðîâàíèåì ïðè ìèíèìàëüíîì
÷èñëå äâóêðàòíûõ íåîáíàðóæèâàåìûõ èñêàæåíèé — ýòî êîä, ó êîòîðîãî
ñóììàðíûé âåñ èíôîðìàöèîííûõ ðàçðÿäîâ ïðè ÷åòíîì çíà÷åíèè m ñîñòàâ-
ëÿåòWmax � �2 2k , à ïðè íå÷åòíîì —W k
max � �2 1. Òàêîé êîä èìååò ìàêñè-
ìàëüíîå ÷èñëî ðàçðÿäîâ ñ âåñàìè wi = 3.
Ëó÷øèå âçâåøåííûå êîäû ïî ïàðàìåòðó ÷èñëà äâóêðàòíûõ íåîáíà-
ðóæèâàåìûõ èñêàæåíèé îáëàäàþò äîëåé íåîáíàðóæèâàåìûõ èñêàæåíèé
èíôîðìàöèîííûõ âåêòîðîâ êðàòíîñòè d = 2 îò îáùåãî ÷èñëà îøèáîê äàí-
íîé êðàòíîñòè, ìåíüøåé, ÷åì ó êëàññè÷åñêèõ êîäîâ ñ ñóììèðîâàíèåì:
�2 0 5� , . Îòíîøåíèå ÷èñëà äâóêðàòíûõ íåîáíàðóæèâàåìûõ èñêàæåíèé â
êîäàõ Áåðãåðà ïî ñðàâíåíèþ ñ ëó÷øèìè âçâåøåííûìè êîäàìè � � �15 2, .
Ñëåäîâàòåëüíî, âçâåøåííûå êîäû ÿâëÿþòñÿ áîëåå ýôôåêòèâíûìè îòíî-
ñèòåëüíî îáíàðóæåíèÿ îøèáîê ìàëîé êðàòíîñòè d = 2 ïî ñðàâíåíèþ ñ
èçâåñòíûìè êîäàìè Áåðãåðà.
Òåñòåðû âçâåøåííûõ êîäîâ ñ ñóììèðîâàíèåì. Âàæíûì ýëåìåíòîì
ñèñòåìû ôóíêöèîíàëüíîãî êîíòðîëÿ (ñì. ðèñ. 1) ÿâëÿåòñÿ òåñòåð, óñòàíàâ-
ëèâàþùèé ôàêò ïðàâèëüíîñòè âû÷èñëåíèé ðàáî÷èõ áóëåâûõ ôóíêöèé f1,
f2, ..., fm. Òåñòåð ñîñòîèò èç ãåíåðàòîðà, ôîðìèðóþùåãî ïî çíà÷åíèÿì èí-
ôîðìàöèîííûõ ðàçðÿäîâ êîíòðîëüíûå ôóíêöèè, è êîìïàðàòîðà, ñðàâíè-
âàþùåãî îäíîèìåííûå ñèãíàëû.
Êîìïàðàòîð ñòðîèòñÿ ïîñðåäñòâîì êàñêàäíîãî ñîåäèíåíèÿ ìîäóëåé
ñðàâíåíèÿ ïàðàôàçíûõ ñèãíàëîâ TRC (two-rail checker) [23]. Ãåíåðàòîð ÿâ-
ëÿåòñÿ óñòðîéñòâîì ïîäñ÷åòà ñóììàðíîãî âåñà èíôîðìàöèîííîãî âåêòîðà.
Ãåíåðàòîðû ñòðîÿòñÿ â âèäå ñóììàòîðîâ âåñîâ èíôîðìàöèîííûõ ðàçðÿäîâ
íà îñíîâå ïîëíûõ ñóììàòîðîâ (FA) è ïîëóñóììàòîðîâ (HA) [24, 25].
Ïîëíûé ñóììàòîð FA (ðèñ. 4, à) èìååò òðè âõîäà, x1, x2, x3, è äâà âûõîäà, S
(ñóììà) è C (ïåðåíîñ). Îí âû÷èñëÿåò ñóììó åäèíè÷íûõ çíà÷åíèé íà âõîäàõ â
ñîîòâåòñòâèè ñ óðàâíåíèÿìè S x x x� � �1 2 3 è C x x x x x x� � �1 2 1 3 2 3. Â îò-
ëè÷èå îò ïîëíîãî ñóììàòîðà ïîëóñóììàòîð HA (ðèñ. 4, á) èìååò äâà âõîäà,
x1, x2 , è äâà âûõîäà, S è C. Ôóíêöèè S è C âû÷èñëÿþòñÿ ïî ôîðìóëàì
S x x� �1 2 è C x x� 1 2.
Ñ ïðèìåíåíèåì ýëåìåíòîâ FA è HA ìîæíî ñòðîèòü ëþáûå ñóììàòîðû
äâîè÷íûõ ÷èñåë, â òîì ÷èñëå ãåíåðàòîðû êîäîâ ñ ñóììèðîâàíèåì. Íà ðèñ. 5
ïðèâåäåíà ñõåìà ãåíåðàòîðà êîäà S (8,5), ïîñòðîåííîãî íà îñíîâå ñóì-
ìàòîðîâ è ïîëóñóììàòîðîâ. Íà ðèñ. 5, á, ïîêàçàíû ëîãè÷åñêèå ñèãíàëû
êàæäîãî âõîäà è âûõîäà ñîñòàâëÿþùèõ ãåíåðàòîðà ïðè ôîðìèðîâàíèè íà
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ
76 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
Âçâåøåííûå êîäû ñ ñóììèðîâàíèåì äëÿ îðãàíèçàöèè êîíòðîëÿ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 77
FAx2
x1
x3
C
S
HA
x2
x1 C
S
a á
Ðèñ. 4. Ýëåìåíòíàÿ áàçà ãåíåðàòîðà: à — ïîëíûé ñóììàòîð; á — ïîëóñóììàòîð
�
�
f 2
f1
f3
f5
f 4
g
1
g
2
g
3
a á
HA
f
5
=1
f
4
=1
FAf2=0
f
1=0
HA
FA
g1=0
g
3
=1
g 2=1f 3=1
0
1
0
1
1
1
0
0
1
0
1
1
0
Ðèñ. 5. Ñõåìû ãåíåðàòîðà êîäà S (8,5): à — ôóíêöèîíàëüíàÿ; á — ñòðóêòóðíàÿ
f 2
f1
f 3
f 5
f4
g1
g2
g 3
a
â
á
�
�
f 2
f1
f 3
f 5
f 4
g1
g
2
g
3
HA
f 5=1
f 5=1
HAf 5=1
f 4=1
HA
FA
g1=1
g3 =1
g2=0
HAf 2=0
f 1=0
f 3=1
HA
1
0
1
0 0
1
0
0
1
0
1
0FA
0
1
0
�
�
�
�
Ðèñ. 6. Ñõåìû ãåíåðàòîðà êîäà WS (8,5, [1,1,1,1,3]): à — ôóíêöèîíàëüíàÿ; á — ïîäðîáíàÿ
ôóíêöèîíàëüíàÿ; â — ñòðóêòóðíàÿ
âûõîäå êîíòðîëèðóåìîãî óñòðîéñòâà èíôîðìàöèîííîé êîìáèíàöèè <00111>.
 ýòîì ñëó÷àå íà âûõîäàõ ãåíåðàòîðà óñòàíàâëèâàåòñÿ êîìáèíàöèÿ <011>,
ðàâíàÿ âåñó èíôîðìàöèîííîãî ñëîâà.
Àíàëîãè÷íî ñòðîÿòñÿ ãåíåðàòîðû âçâåøåííûõ êîäîâ. Íà ðèñ. 6 ïðè-
âåäåíû ñõåìû ãåíåðàòîðà WS (8,5, [1,1,1,1,3])-êîäà, êîòîðûé ïîñòðîåí êàê
ñóììàòîð äâóõ äâîè÷íûõ ÷èñåë: ñóììàðíîãî âåñà ïåðâûõ òðåõ èíôîðìà-
öèîííûõ ðàçðÿäîâ è âåñîâ äâóõ ìëàäøèõ èíôîðìàöèîííûõ ðàçðÿäîâ, â
òîì ÷èñëå âçâåøåííîãî ðàçðÿäà f5 (ñì. ðèñ. 6, á). Ïðè ýòîì íà âûõîäàõ
ñóììàòîðà òðåõ ñòàðøèõ ðàçðÿäîâ ôîðìèðóåòñÿ äâóçíà÷íîå äâîè÷íîå ÷èñëî,
à íà âûõîäàõ ñóììàòîðà ìëàäøèõ ðàçðÿäîâ — òðåõçíà÷íîå äâîè÷íîå ÷èñëî.
Ýòî ó÷èòûâàåòñÿ ïðè ïîñòðîåíèè âûõîäíîãî ñóììàòîðà — â íåì ó ïîëóñóì-
ìàòîðà ñòàðøèõ ðàçðÿäîâ íå òðåáóåòñÿ âûõîäà ïåðåíîñà, òàê êàê ñêëàäûâàå-
ìûå â íåì ìàêñèìàëüíûå ÷èñëà, ðàâíû ñîîòâåòñòâåííî <11> è <100>.
Ñëåäóåò çàìåòèòü, ÷òî ñèíòåç ãåíåðàòîðîâ êàê ñóììàòîðîâ äâîè÷íûõ
÷èñåë, õàðàêòåðèçóþùèõ ñóììû âåñîâ èíôîðìàöèîííûõ ðàçðÿäîâ, ïî-
çâîëÿåò ïîëó÷àòü áîëåå ïðîñòûå ñòðóêòóðû ãåíåðàòîðîâ äëÿ òåñòåðîâ
WS n m w w wm( , [ , ,..., ])1 2 -êîäîâ.
Âûâîäû
Âàæíûì ñïîñîáîì îáåñïå÷åíèÿ íàäåæíîñòè ðàáîòû ïîñòîÿííî ðàçâèâàþ-
ùèõñÿ è óñëîæíÿþùèõñÿ ñèñòåì àâòîìàòè÷åñêîãî óïðàâëåíèÿ è êîíòðîëÿ
ÿâëÿåòñÿ èñïîëüçîâàíèå ôóíêöèîíàëüíîãî (ðàáî÷åãî) äèàãíîñòèðîâàíèÿ.
Ïðè îðãàíèçàöèè ïîäîáíûõ ñèñòåì ýôôåêòèâíûì ÿâëÿåòñÿ èñïîëüçîâàíèå
êîäîâ ñ ñóììèðîâàíèåì, â òîì ÷èñëå êîäîâ ñ ñóììèðîâàíèåì âçâåøåííûõ
èíôîðìàöèîííûõ ðàçðÿäîâ. Âçâåøèâàíèå ðàçðÿäîâ ïðèâîäèò ê ïîâûøå-
íèþ ýôôåêòèâíîñòè êîäîâ ñ ñóììèðîâàíèåì ïî îáíàðóæåíèþ îøèáîê â
èíôîðìàöèîííûõ âåêòîðàõ êîäîâ, ÷òî àêòóàëüíî äëÿ ñèñòåì ôóíêöèîíàëü-
íîãî êîíòðîëÿ ëîãè÷åñêèõ óñòðîéñòâ.
Îïðåäåëåíû óñëîâèÿ, ïðè êîòîðûõ âçâåøåííûé êîä ñ ñóììèðîâàíèåì
ÿâëÿåòñÿ ìàêñèìàëüíî ýôôåêòèâíûì îòíîñèòåëüíî îáíàðóæåíèÿ îøèáîê
÷åòíûõ êðàòíîñòåé â èíôîðìàöèîííûõ âåêòîðàõ, à òàêæå óñëîâèÿ ñîõðà-
íåíèÿ âàæíûõ ñâîéñòâ êëàññè÷åñêèõ êîäîâ ñ ñóììèðîâàíèåì, à èìåííî
îáíàðóæåíèå ëþáûõ îäíîíàïðàâëåííûõ èñêàæåíèé èíôîðìàöèîííûõ ðàç-
ðÿäîâ è âñåõ èñêàæåíèé íå÷åòíûõ êðàòíîñòåé.
The paper presents the results of studying the codes with summation of the weighted data bits un-
der the condition of preservation of the number of check bits, similar to the classical Berger
codes. Classes of codes which possess the main properties of the Berger codes and have the least
number of undetectable errors in data bits (among known codes) are defined.
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ
78 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Berger J.M. À note on Error Detecting Codes for Asymmetric Channels // Information and
Control. — 1961. — Vol. 4, ¹ 1. — P. 68—73.
2. Freiman C.V. Optimal Error Detection Codes for Completely Asymmetric Binary // Ibid. —
1962. — Vol. 5, ¹ 1. — P. 64—71.
3. Pradhan D.K. Fault-Tolerant Computer System Design. — N-Y : Prentice Hall, 1996. —
560 p.
4. Ñàïîæíèêîâ Â.Â., Ñàïîæíèêîâ Âë.Â. Ñàìîïðîâåðÿåìûå äèñêðåòíûå óñòðîéñòâà. —
ÑÏá : Ýíåðãîàòîìèçäàò, 1992. — 224 ñ.
5. Goessel M., Graf S. Error Detection Circuits. — London: McGraw-Hill, 1994. — 261 p.
6. Lala P.K. Self-Checking and Fault-Tolerant Digital Design. — San Francisco : Morgan
Kaufmann Publishers, 2001. — 216 p.
7. Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications. —
John Wiley & Sons, 2006. — 720 p.
8. Åôàíîâ Ä.Â., Ñàïîæíèêîâ Â.Â., Ñàïîæíèêîâ Âë.Â. Î ñâîéñòâàõ êîäà ñ ñóììèðîâàíèåì
â ñõåìàõ ôóíêöèîíàëüíîãî êîíòðîëÿ // Àâòîìàòèêà è òåëåìåõàíèêà. — 2010. — ¹6 . —
Ñ. 155—162.
9. Áëþäîâ À.À., Ñàïîæíèêîâ Â.Â., Ñàïîæíèêîâ Âë.Â. Ìîäèôèöèðîâàííûé êîä ñ ñóììè-
ðîâàíèåì äëÿ îðãàíèçàöèè êîíòðîëÿ êîìáèíàöèîííûõ ñõåì // Òàì æå. — 2012. — ¹ 1. —
Ñ. 169—177.
10. Blyudov A., Efanov D., Sapozhnikov V., Sapozhnikov Vl. Properties of Ñode 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.
11. Áëþäîâ À.À., Åôàíîâ Ä.Â., Ñàïîæíèêîâ Â.Â., Ñàïîæíèêîâ Âë.Â. Ïîñòðîåíèå ìîäèôè-
öèðîâàííîãî êîäà Áåðãåðà ñ ìèíèìàëüíûì ÷èñëîì íåîáíàðóæèâàåìûõ îøèáîê èíôîð-
ìàöèîííûõ ðàçðÿäîâ // Ýëåêòðîí. ìîäåëèðîâàíèå. — 2012. — 34, ¹ 6. — Ñ. 17—29.
12. Áëþäîâ À.À., Åôàíîâ Ä.Â., Ñàïîæíèêîâ Â.Â., Ñàïîæíèêîâ Âë.Â. Êîäû ñ ñóììèðî-
âàíèåì äëÿ îðãàíèçàöèè êîíòðîëÿ êîìáèíàöèîííûõ ñõåì // Àâòîìàòèêà è òåëåìåõà-
íèêà. — 2013. — ¹ 6. — Ñ. 153—164.
13. Bose B., Lin D. J. Systematic Unidirectional Error-Detection Codes // IEEE Trans. Comput.
— 1985. — Vol. C —34. — P. 1026—1032.
14. 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.
15. Efanov D., Sapozhnikov V., Sapozhnikov Vl., Blyudov A. On the Problem of Selection of
Code with Summation for Combinational Circuit Test Organization // Proc. of the 11th IEEE
East-West Design & Test Symposium (EWDTS`2013). Rostov-on-Don, Russia, Sept. 27—30,
2013. — P. 261—266.
16. 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.
17. 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,
15—17 Nov. 2004. — P. 210—215.
18. Favalli M., Metra C. Optimization of Error Detecting Codes for the Detection of Crosstalk
Originated Errors // Design, Automation and Test in Europe (DATE). 13—16 March, 2001. —
P. 290—296.
19. Ghosh S. Scan Chain Fault Identification Using Weight-Based Codes for SoC Circuits // Mas-
ter’s thesis, Dept. of ECECS. University of Cincinnati, Cincinnati, Ohio, USA, May, 2004.
Âçâåøåííûå êîäû ñ ñóììèðîâàíèåì äëÿ îðãàíèçàöèè êîíòðîëÿ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 79
20. Ñàïîæíèêîâ Â.Â., Ñàïîæíèêîâ Âë.Â., Åôàíîâ Ä.Â., Íèêèòèí Ä.À. Ìåòîä ïîñòðîåíèÿ
êîäà Áåðãåðà ñ ïîâûøåííîé ýôôåêòèâíîñòüþ îáíàðóæåíèÿ îøèáîê â èíôîðìàöèîí-
íûõ ðàçðÿäàõ // Ýëåêòðîí. ìîäåëèðîâàíèå. — 2013. — 35, ¹ 4. — Ñ. 21—34.
21. Sapozhnikov V.V., Morozov A., Sapozhnikov Vl.V., Goessel M. A New Design Method for
Self-Checking Unidirectional Combinational Circuits // J. of Electronic Testing: Theory and
Applications. — 1998. — Vol. 12, ¹ 2. — P. 41—53.
22. Ìàòðîñîâà À.Þ., Îñòàíèí Ñ.À., Ñèíãõ Â. Îáíàðóæåíèå íåñóùåñòâåííûõ ïóòåé ëîãè-
÷åñêèõ ñõåì íà îñíîâå ñîâìåñòíîãî àíàëèçà È-ÈËÈ äåðåâüåâ è SSBDD-ãðàôîâ //
Àâòîìàòèêà è òåëåìåõàíèêà. — 2013. — ¹ 7. — Ñ. 126—142.
23. Ìåëüíèêîâ À.Ã., Ñàïîæíèêîâ Â.Â., Ñàïîæíèêîâ Âë.Â. Ñèíòåç ñàìîïðîâåðÿþùèõñÿ
òåñòåðîâ äëÿ êîäîâ ñ ñóììèðîâàíèåì // Ïðîáëåìû ïåðåäà÷è èíôîðìàöèè. — 1986. —
XXII, ¹ 2. — Ñ. 85—97.
24. 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.
25. Piestrak S.J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes. —
Wroclaw: Oficyna Wydawnicza Politechniki Wroclavskiej, 1995. — 111 p.
Ïîñòóïèëà 09.12.13
ÑÀÏÎÆÍÈÊÎÂ Âàëåðèé Âëàäèìèðîâè÷, ä-ð òåõí. íàóê, ïðîôåññîð êàôåäðû «Àâòîìàòèêà è
òåëåìåõàíèêà íà æåëåçíûõ äîðîãàõ» Ïåòåðáóðãñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà ïóòåé
ñîîáùåíèÿ.  1963 ã. îêîí÷èë Ëåíèíãðàäñêèé èí-ò èíæåíåðîâ æåëåçíîäîðîæíîãî òðàíñ-
ïîðòà. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — íàäåæíîñòíûé ñèíòåç äèñêðåòíûõ óñòðîéñòâ,
ñèíòåç áåçîïàñíûõ ñèñòåì, ñèíòåç ñàìîïðîâåðÿåìûõ ñõåì, òåõíè÷åñêàÿ äèàãíîñòèêà äèñê-
ðåòíûõ ñèñòåì.
ÑÀÏÎÆÍÈÊÎÂ Âëàäèìèð Âëàäèìèðîâè÷, ä-ð òåõí. íàóê, çàâ. êàôåäðîé «Àâòîìàòèêà è
òåëåìåõàíèêà íà æåëåçíûõ äîðîãàõ» Ïåòåðáóðãñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà ïóòåé
ñîîáùåíèÿ.  1963 ã. îêîí÷èë Ëåíèíãðàäñêèé èí-ò èíæåíåðîâ æåëåçíîäîðîæíîãî òðàíñïîð-
òà. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — íàäåæíîñòíûé ñèíòåç äèñêðåòíûõ óñòðîéñòâ, ñèíòåç
áåçîïàñíûõ ñèñòåì, ñèíòåç ñàìîïðîâåðÿåìûõ ñõåì, òåõíè÷åñêàÿ äèàãíîñòèêà äèñêðåòíûõ
ñèñòåì.
ÅÔÀÍÎÂ Äìèòðèé Âèêòîðîâè÷, êàíä. òåõí. íàóê, äîöåíò êàôåäðû «Àâòîìàòèêà è òåëåìå-
õàíèêà íà æåëåçíûõ äîðîãàõ» Ïåòåðáóðãñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà ïóòåé ñîîá-
ùåíèÿ, êîòîðûé îêîí÷èë â 2007 ã. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — äèñêðåòíàÿ ìàòåìàòèêà,
íàäåæíîñòü è òåõíè÷åñêàÿ äèàãíîñòèêà äèñêðåòíûõ ñèñòåì.
Â.Â. Ñàïîæíèêîâ, Âë.Â. Ñàïîæíèêîâ, Ä.Â. Åôàíîâ
80 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
|
| id | nasplib_isofts_kiev_ua-123456789-100986 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-11-27T18:25:56Z |
| publishDate | 2014 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Сапожников, В.В. Сапожников, Вл.В. Ефанов, Д.В. 2016-05-28T16:36:56Z 2016-05-28T16:36:56Z 2014 Взвешенные коды с суммированием для организации контроля логических устройств / В.В. Сапожников, Вл.В. Сапожников, Д.В. Ефанов // Электронное моделирование. — 2014 — Т. 36, № 1. — С. 59-80. — Бібліогр.: 25 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/100986 681.518.5 Приведены результаты исследований кодов с суммированием взвешенных информационных разрядов при сохранении числа контрольных разрядов таким же, как у классических кодов Бергера. Определены классы кодов, которые обладают основными свойствами кодов Бергера и имеют наименьшее среди известных кодов число необнаруживаемых ошибок в информационных разрядах. Наведено результати досліджень кодів з підсумовуванням зважених інформаційних розрядів при зберіганні числа контрольних розрядів таким, як у класичних кодів Бергера. Визначено класи кодів з основними властивостями кодів Бергера, які мають найменше серед відомих кодів число похибок, що не визначаються, в інформаційних розрядах. The paper presents the results of studying the codes with summation of the weighted data bits under the condition of preservation of the number of check bits, similar to the classical Berger codes. Classes of codes which possess the main properties of the Berger codes and have the least number of undetectable errors in data bits (among known codes) are defined. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Точность, надежность, диагностика Взвешенные коды с суммированием для организации контроля логических устройств Article published earlier |
| spellingShingle | Взвешенные коды с суммированием для организации контроля логических устройств Сапожников, В.В. Сапожников, Вл.В. Ефанов, Д.В. Точность, надежность, диагностика |
| title | Взвешенные коды с суммированием для организации контроля логических устройств |
| title_full | Взвешенные коды с суммированием для организации контроля логических устройств |
| title_fullStr | Взвешенные коды с суммированием для организации контроля логических устройств |
| title_full_unstemmed | Взвешенные коды с суммированием для организации контроля логических устройств |
| title_short | Взвешенные коды с суммированием для организации контроля логических устройств |
| title_sort | взвешенные коды с суммированием для организации контроля логических устройств |
| topic | Точность, надежность, диагностика |
| topic_facet | Точность, надежность, диагностика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/100986 |
| work_keys_str_mv | AT sapožnikovvv vzvešennyekodyssummirovaniemdlâorganizaciikontrolâlogičeskihustroistv AT sapožnikovvlv vzvešennyekodyssummirovaniemdlâorganizaciikontrolâlogičeskihustroistv AT efanovdv vzvešennyekodyssummirovaniemdlâorganizaciikontrolâlogičeskihustroistv |