Файл: Хетагуров, Я. А. Повышение надежности цифровых устройств методами избыточного кодирования.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 161
Скачиваний: 0
для общего случая не существует |
алгоритма |
построе |
|||||||||
ния нелинейного |
кода (к нелинейным кодам здесь отно |
||||||||||
сятся такие |
коды, которые |
являются |
негрупповыми, |
||||||||
т. е. задание |
их |
возможно только |
с |
помощью |
|
«кодовой |
|||||
книги»); |
|
|
|
|
|
|
|
|
|
|
|
как |
правило, |
корректирующее |
устройство |
для |
нели |
||||||
нейного |
кода |
оказывается |
более сложным, |
чем |
для |
груп |
|||||
пового |
кода. |
|
|
|
|
|
|
|
|
|
|
Применение |
ЦВМ |
для |
анализа |
неисправностей |
|||||||
в схеме |
и поиска |
нелинейного кода позволяет в опреде |
|||||||||
ленной |
степени |
преодолеть |
первую |
трудность. |
Вторая |
||||||
трудность является более серьезной, так как декодиро
вание |
нелинейного |
кода основано |
на методе |
полного |
пе |
|||
ребора |
с помощью |
«кодовой |
книги». |
|
|
|||
|
Например, алгоритм работы КУ, предназначенного для исправ |
|||||||
ления любой одиночной ошибки на |
выходе схемы, |
показанной |
на |
|||||
рис. 7-3, |
описывается табл. 7-2. |
|
|
|
|
|||
|
Из |
табл. 7-2 получаем логическое |
уравнение |
для вычисле |
||||
ния |
y*t: |
|
|
|
|
|
|
|
|
|
У*1= |
{Уг^гУ^^^УхУ^гУУ^^гУУхУзУ») |
|
|
^YiYaV |
|
|
|
|
V |
Ш^^УхУгУъУУхУ^^У^г^УУ^УгУг) |
|
|
У*Ь"(г\/ |
|
|
|
|
УУхЧгЧгЪ^АхУУЯМУхУгУъЪ. |
|
(7<й\/У*Ъ) |
= |
|
||
= |
(УЛ/й^гУа) |
^ Y A / ^ i V y i ^ s ) |
</4YiYa V(7*YiV</4Yi) (i/i'Ts'/aYaV |
|||||
|
|
|
УУгУгУзЪ) |
= У^й |
(УгУУхПУгЧгУУхУгУзЪ)V |
|
||
|
|
|
V ^ Y J V M . ) |
(У&УгЧгУУхУгУгй)- |
|
|
||
Схема реализации этого выражения показана на рис. 7-4, из которого следует, что количество аппаратуры в одном канале КУ,
исчисляемое |
суммарным количеством входов схем |
совпадения, |
|
равно |
26 усл. ед. Тогда, предполагая практически одинаковую слож |
||
ность |
всех |
каналов, затраты на четырехканальное |
КУ составят |
4-26=104 усл. ед.
Для сравнения на рис. 7-5 приведена схема КУ для схемы, по казанной на рис. 7-1. Учитывая, что схема двухвходового сумма тора по модулю 2 требует 4 усл. ед. аппаратуры, а четырехвходового сумматора—12 усл. ед., получаем, что суммарные затраты аппаратуры равны 64 усл. ед. Таким образом, в данном случае при менение группового кода позволяет получить более экономичное ре шение, чем применение нелинейного кода с использованием естествен ной информационной избыточности.
В рассмотренных примерах при введении избыточности суще ственно увеличивается количество аппаратуры, и может создаться ложное впечатление, что данные методы повышения надежности неконкурентоспособны с другими методами введения избыточности. Однако отметим следующее. Введенный в рассмотрение в гл. 6 коэффициент усложнения (Р+Я^у/т0 Х) учитывает три источника увеличения количества аппаратуры на введение избыточности в устройство:
192
|
1) затраты |
аппаратуры |
па |
получение |
контрольных |
разрядов |
|
(учитывается |
коэффициентом в); |
|
|
|
|||
|
2) затраты |
аппаратуры, |
связанные с |
внесением |
изменений |
||
в |
структуру |
устройства с |
целью согласования структуры ошибок |
||||
с |
корректирующими свойствами |
кода (учитывается коэффициентом |
|||||
Р);
|
3) |
затраты |
аппаратуры |
на |
корректирующее |
устройство |
(учиты |
||||||||
вается |
коэффициентом |
Х^у/1щХ'). |
|
|
|
|
|
|
|
|
|||||
|
Проведенный в § 6-4 анализ показывает, |
что |
затраты |
аппарату |
|||||||||||
ры |
на |
один канал КУ уменьшаются с |
уменьшением |
длины |
кода |
||||||||||
(см. рис. 6-9). Минимальные |
затраты |
получаются |
в |
том |
случае, |
||||||||||
когда k=\. Порожпающая и контрольная матрицы |
такого |
кода |
име |
||||||||||||
ют |
вид: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 = 1 |
|
|
Н , . , = |
ПО |
|
|
|
|
|
|
(7-3) |
|
|
|
|
|
|
101 |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Т а б л и ц а |
7-2 |
|||
|
|
Входное |
слово КУ |
|
|
|
Выходное |
слово |
К у |
|
|||||
|
и, |
У* |
|
у, |
т. |
|
Та |
|
у\ |
у \ |
Уз |
|
<л |
||
|
0 |
0 |
0 |
0 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
0 |
0 |
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
0 |
1 |
0 |
0 |
|
0 |
|
|
|
|
||||
|
0 |
0 |
0 |
1 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
|
1 |
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
, |
, |
|
0 |
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
1 |
1 |
|
п |
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
] |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
0 |
1 |
1 |
1 |
1 |
|
0 |
• |
0 |
|
1 0 |
|
|
1 |
|
|
0 |
1 |
0 |
|
1 |
|
0 |
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
1 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
] |
1 |
•"'• |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
•» |
|
1 |
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
||
|
0 |
0 |
0 |
1 |
0 |
|
] |
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
1 |
п |
|
] |
|
|
|
|
|
|
|
|
|
1 |
0 |
I |
1 |
0 |
|
1 |
|
1 0 |
|
|
0 |
|
1 |
|
|
1 |
0 |
0 |
|
0 |
|
1 |
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
1 |
1 |
|
] |
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
I |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
I |
1 |
I |
1 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
0 |
1 |
1 |
1 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
I |
0 |
1 |
1 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
1 |
0 |
|
0 |
|
1 |
1 |
1 |
|
1 |
|
|
|
1 |
1 |
1 |
|
0 |
|
0 |
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
0 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
13—236 |
193 |
|
У,У2У3У<Г,Г2
&
ОOn
|
Рис. |
7-4. Схема |
канала КУ для схемы, |
показанной |
|
|||
|
|
|
|
на рнс. 7-3. |
|
|
|
|
Из |
(6-20) |
при сг=4, |
п=3, |
r=n—k = 2, |
£ 3 = 3 , |
ky=kz=\, |
q=\ |
по |
лучаем |
| = Х К у / я Я т = 7 , 3 , |
т. |
е. затраты |
аппаратуры на |
КУ |
мини |
||
мальны. |
|
|
|
|
|
|
|
|
Матрицы (7-3) описывают мажоритарный принцип введения из быточности, для которого характерна максимальная простота КУ, но при этом втрое увеличиваются затраты аппаратуры на реализацию избыточного устройства. При увеличении сложности неизбыточного
устройства |
(шД—voo) коэффициент усложнения (В + ХкУ/огоА,)- |
*3. |
|||
Рассмотрим |
другой предельный случай, |
когда |
к—>-оо |
и |
|
та%—>-оо, |
т. е. |
неограниченно увеличивается |
количество |
выходов |
|
в неизбыточном автомате и сложность каждого из них. Ограничимся рассмотрением кодов Хэмминга с d=3 . Из рис. 6-9 видно, что затра
ты на один канал КУ для кодов Хэмминга слабо |
зависят от |
значе |
ния k, поэтому величина (к^-у/тоХ)—>-0. С другой |
стороны, |
состав |
ляющая коэффициента В, определяемая отношением njk, при k—»-со
стремится к 1. Определить в общем случае затраты |
на |
внесение |
изменений в структуру устройства не представляется |
возможным. |
|
Если предположить, что выходы устройства реализуются |
независи |
|
мыми схемами, то в рассматриваемом случае (В+Х^у//По^)—>-1,
194
т .
\Ш2\
т2
Чп2\
т2]
&
Рис. 7-5. Схема КУ для схемы, показанной на рис. 7-1.
т. е. требование коррекции одиночной ошибки асимптотически не влияет на сложность схемы.
Рассмотренные два предельных случая свидетельствуют о том, что в определенных случаях корректирующие коды являются эко
номичным |
методом |
повышения надежности. Эти предельные оценки |
и вывод |
относятся |
ко всем классам конечных автоматов. |
Повышение достоверности работы комбинационных схем. Основным методом повышения достоверности вы ходной информации является контроль (см. рис. 1-8). В зависимости от характеристик наиболее вероятных ошибок используется один из рассмотренных в- книге классов кодов.
Рассмотрим применение кода с суммированием для контроля схемы, показанной на рис. 1-3. Применение этого кода обусловлено асимметричным характером ошибок на ее выходах. Отображение
множества |
входных |
слов |
X=i(xi, |
Хг, |
х3) |
на |
множество |
выходных |
|||||
слов |
Y = (г/1, i / 2 , .. •, |
</о), |
реализуемое |
данной |
схемой, |
показано |
|||||||
в табл. 7-3 |
(первый |
и |
второй столбцы). |
|
|
|
|
|
|
||||
|
Так как максимальная кратность ошибки |
/ |
на выходе |
схемы |
|||||||||
при |
неисправности |
одного |
элемента |
равна |
3, |
то |
значение |
модуля |
|||||
/ V = / + l = 4 |
(§ 4-3) |
и |
требуемое |
количество |
контрольных |
разрядов |
|||||||
r=log24=2. В четвертом столбце табл. 7-3 записаны вычеты по мо
дулю Л'=4 |
от веса W(Y) выходного слова |
У |
(третий столбец). Из |
||||
различных |
вариантов |
кодирования |
классов |
вычетов {1, 2, |
3} |
кодом |
|
длиной г = 2 разряда |
выбран тот, |
который |
представлен |
в |
пятом |
||
столбце. |
|
|
|
|
|
|
|
13* |
|
|
|
|
|
|
195 |
|
|
|
|
|
|
|
|
|
Т а б'ли ц а 7-3 |
|
|
|
|
|
|
|
|
|
Вес |
Вычет по |
|
|
|
|
|
|
|
|
|
ЩГ) |
модулю |
Ы > |
|
|
|
|
|
|
|
|
|
ЛГ=4 |
|
|
• |
|
|
|
2 |
|
|
3 |
4 |
5 |
О О О |
1 0 0 0 0 1 |
2 |
2 |
0 1 |
||||||
0 0 1 |
0 |
|
1 1 1 1 1 |
5 |
1 |
0 0 |
||||
0 |
1 0 |
1 1 1 1 1 0 |
5 |
1 |
0 0 |
|||||
0 |
1 1 |
1 1 1 1 1 1 |
|
6 |
2 |
0 1 |
||||
1 0 0 |
1 0 |
0 |
1 0 |
0 |
2 |
2 |
0 1 |
|||
1 0 1 |
0 |
1 1 0 |
1 0 |
3 |
3 |
1 0 |
||||
1 |
1 0 |
1 1 0 |
0 0 0 |
2 |
2 |
0 1 |
||||
1 |
1 1 |
1 |
1 1 0 |
0 0 |
3 |
3 |
1 0 |
|||
Из табл. 7-3 получаем уравнения лля |
вычисления |
контрольных |
||||||||||||||||||
разрядов: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
Yi — %\Х2%3\/ |
Х\%2%3 |
= |
Х1Х3, |
|
|
|
|
|
|
|
||||||
1 2 = |
Х1Х2Х3\/х1ХгХ.3\/ |
Х1Хгх3\/ |
Х,1Хг£3 |
= Х^зХ/ЖгХзХ/^ХгХ,, |
|
|
||||||||||||||
которые |
реализуются |
схемой, показанной |
на ряс. 7-6. |
|
|
|
|
|
|
|||||||||||
Возможная |
реализация схемы |
контроля |
показана |
на рис. |
7-7. |
|||||||||||||||
|
|
|
|
|
На |
входы |
данной |
схемы |
поступают |
|||||||||||
|
|
|
|
|
выходные |
сигналы |
yi, |
|
уг, |
|
|
уа |
||||||||
|
|
|
|
|
основного |
логического |
|
блока |
|
(см. |
||||||||||
|
|
|
|
|
рис. 1-3) « |
выходные |
сигналы |
|
ус\2 |
|||||||||||
|
|
|
|
|
дополнительного |
|
логического |
блока |
||||||||||||
|
|
|
|
|
(рис. 7-6). В схеме контроля |
исполь |
||||||||||||||
|
|
|
|
|
зуется |
унитарный |
коя, который |
|
уже |
|||||||||||
|
|
|
|
|
нами |
применялся |
в гл. 5 для |
синтеза |
||||||||||||
|
|
|
|
|
схем |
сверток. Из рис. 7-7 |
видно, |
что |
||||||||||||
|
|
|
|
|
коммутация |
выходов |
схем |
совпаде |
||||||||||||
|
|
|
|
|
ния, |
на |
входы |
которых |
поступают |
|||||||||||
|
|
|
|
|
переменные yi и yi, выполнена таким |
|||||||||||||||
|
|
|
|
|
образом, |
что происходит |
вычитание 1. |
|||||||||||||
|
|
|
|
|
'2 Действительно, |
|
если |
yi = \, |
то при |
|||||||||||
|
|
|
|
|
подаче |
сигнала |
Опрос |
|
на |
нижней |
||||||||||
|
|
|
|
|
шине, |
соответствующей |
нулевому |
(по |
||||||||||||
|
|
|
|
|
модулю |
N=4) |
|
количеству |
единиц, |
|||||||||||
|
|
|
|
|
появляется |
сигнал. Если |
же J / I = 0 , |
|||||||||||||
|
|
|
|
|
то сигнал появится на верхней шине, |
|||||||||||||||
Рис. 7-6. |
Схема |
вычисления |
соответствующей |
3 единицам |
(—1=3 |
|||||||||||||||
по модулю |
Д/=4). |
Коммутация |
|
схем |
||||||||||||||||
контрольных |
разрядов для |
|
||||||||||||||||||
совпадения |
в |
каскадах, |
связанных |
|||||||||||||||||
схемы, |
показанной |
на |
||||||||||||||||||
с |
переменными |
уг, |
Уг |
|
|
у>, |
выпол |
|||||||||||||
|
рис. |
1-3. |
|
|
|
|||||||||||||||
|
|
нена |
таким |
образом, |
что |
если |
yi=0, |
|||||||||||||
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
то |
сига ал |
транслируется |
в |
следую |
|||||||||||
щий каскад по той же шине, по которой он поступил. Если же yi = l,
то |
сигнал переключается на шину, номер которой «а единицу боль |
ше |
(по модулю # = 4 ) . |
Коммутация каскада, связанного с переменной yj, выполнена та ким образом, что происходит вычитание 1 (по модулю Л/=4), если Yz= I . Наконец, в последнем каскаде происходит вычитание 2 (по
196