Файл: Хетагуров, Я. А. Повышение надежности цифровых устройств методами избыточного кодирования.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 179
Скачиваний: 0
Таким образом |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 0 |
1 0 |
0 |
0 |
1 |
1 1 0 |
|
1 0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
||||
|
0 |
1 1 0 |
|
1 0 |
0 0 |
1 1 0 |
|
1 1 |
0 |
1 0 |
0 |
0 |
1 1 |
|||||||
|
1 0 |
1 1 0 |
|
1 0 0 |
0 |
1 1 0 |
1 |
1 |
0 |
1 0 |
0 |
0 1 |
||||||||
А = |
2 А " 1 2 = |
|
|
1 1 0 |
|
1 |
0 |
0 |
0 |
1 |
1 0 |
1 1 0 |
|
1 0 |
0 |
0 |
||||
|
1 1 0 |
|
|
|
||||||||||||||||
|
0 |
0 |
0 |
1 |
1 |
1 0 |
1 |
1 0 |
0 |
0 |
0 |
1 1 1 0 |
|
1 1 0 |
||||||
|
0 |
1 0 |
0 |
0 |
1 1 |
1 0 |
1 0 |
1 0 0 |
0 |
1 1 1 0 |
|
1 |
||||||||
|
|
|
|
Г л а в а |
|
п я т а я |
|
|
|
|
|
|
|
|
||||||
КОДЫ ДЛЯ ОБНАРУЖЕНИЯ И ИСПРАВЛЕНИЯ |
||||||||||||||||||||
|
АРИФМЕТИЧЕСКИХ ОШИБОК |
|
|
|||||||||||||||||
|
5-1. АРИФМЕТИЧЕСКИЕ AN- |
И / Ш + В - К О Д Ы |
||||||||||||||||||
В рассматриваемом классе кодов кодовыми словами |
||||||||||||||||||||
являются числа |
AN |
или |
|
AN + B, |
|
где |
N — число, |
которое |
||||||||||||
должно быть закодировано, а Л |
и В — константы. При |
|||||||||||||||||||
этом, |
если ANi |
и AN2 |
являются |
|
кодовыми |
словами, то |
||||||||||||||
|
ANi±AN2=A(Ni±Nz), |
|
|
|
|
|
|
ANi-AN2=AzNtN2, |
||||||||||||
ANi/AN2=NilN2.
Таким образом, принятая форма кодовых слов нару шается при операциях умножения и деления.
Константа В вводится для получения корректирую щего кода, обеспечивающего простой переход от пря мого кода к обратному при записи отрицательных чисел. Пусть используется /n-ичная система счисления и для
представления |
закодированных |
чисел |
используется |
||
п значащих разрядов (без учета |
знакового |
разряда). |
|||
Число N, |
обратное числу -N, можно найти из |
известного |
|||
равенства |
|
_ |
|
|
|
|
|
N=NMai<c—N, |
|
|
|
где Ммакс |
= тх—1 |
— максимальное |
значение |
кодируемых |
|
чисел, которое не должно превышать значения, опреде ляемого из условий существования корректирующего ко да (z<n).
Константу В находим из условия, что кодовое пред ставление числа N должно получаться дополнением каждой цифры кодового слова, соответствующего числу
127
N, до m—1. Это условие можно записать следующим образом:
(AN+B) + (AN + B) =тп—\
или
AN+2B+A (-Ямакс—N) = тп— 1.
Из последнего равенства получаем выражение для вычисления константы В:
B=(mn—\—ANMai<c)/2.
В частности, если используется двоичная система ( т = 2), то
В = ( 2 » - 1 - Л # „ а к с ) / 2 .
Следующие две теоремы определяют условия суще ствования арифметических кодов для обнаружения и исправления одиночных ошибок.
Теорема 5-1. Нечетное число Аф\ порождает ЛЛ^-код произвольной длины п двоичных разрядов с обнаруже нием любой одиночной ошибки вида ±'2', г д е О ^ г ^ п — 1 .
Доказательство. Пусть при передаче, хранении или обработке информации в кодовом слове возникла оди ночная ошибка, т. е. получено слово AN±2'. Тогда
AuV±2i =Hi±'2i по модулю А, так как по определению ЛАЛкода
,4JV=0. по модулю А.
Но так как А — нечетное число, то при любом i
± 2 * ^ 0 по модулю А.
Другими словами, не существует одиночной ошибки, которая не будет обнаружена этим кодом. Тем самым теорема доказана.
Из теоремы 5-1 следует, что наименьшая величина А, гарантирующая обнаружение одиночной ошибки, равна 3. В табл. 5-1 приведены параметры некоторых арифмети ческих кодов вида 3N + B, позволяющих обнаружить одиночные ошибки. Эти коды имеют минимальное рас
стояние |
(арифметическое) |
d=2. |
Количество избыточных |
||
разрядов |
г |
определяется |
следующим |
образом: |
|
|
|
г = |
я — П о , |
|
|
где По — минимальное целое |
число, |
удовлетворяющее |
|||
неравенству |
2na^NMaKpj |
|
|
|
|
128
|
|
Т а б л и ц а |
5-1 |
|
Диапазон кодируе |
Код 3N + 3 (.1=2) |
Длина кодово |
Количество |
|
мых чисел N |
го слова п |
избыточных |
||
|
разрядов |
г\ |
||
|
|
|
||
0 - 7 |
3N+5 |
5 |
2 |
|
0—15 |
ЗМ-г-Э |
6 |
2 |
|
0—31 |
ЗЛЧ-17 |
7 |
2 |
|
0—63 |
3W+33 |
8 |
2 |
|
0—127 |
3N+65 |
9 |
2 |
|
0—255 |
ЗЛЧ-129 |
10 |
2 |
|
0—511 |
ЗЛГ+257 |
11 |
2 |
|
0—1023 |
3/V+513 |
12 |
2 |
|
0—262143 |
З А / + 1 3 1 0 7 8 |
20 |
2 |
|
По модулю А существует А классов вычетов, в ка
честве |
представителей которых обычно выбирают числа |
0, 1, |
(А—1). Функцией Эйлера ср(Л) называется |
число классов по модулю А, взаимно простых с этим
модулем, |
или, другими |
словами, |
число |
натуральных |
|||||||
чисел, не |
превосходящих А |
и |
взаимно |
простых |
с А. |
||||||
В частности, |
если |
А — простое |
число, то |
у(А)=А—1. |
|||||||
Порядком |
класса |
вычетов а называют наименьшее число |
|||||||||
ефО, которое удовлетворяет |
сравнению |
|
|
|
|||||||
|
|
|
а е = 1 |
по модулю А. |
|
|
|
||||
Если порядок |
е —ср(Л), то класс вычетов а называют |
||||||||||
первообразным |
элементом |
(первообразным |
корнем). |
||||||||
Если известен первообразный элемент а, то |
через его |
||||||||||
степени а°=1 , а1 , а2 , |
а А - 2 |
можно |
вычислить все не |
||||||||
нулевые классы вычетов по модулю А. |
|
|
|
||||||||
Теорема |
5-2. Нечетное число Аф\ |
порождает |
ариф |
||||||||
метический АЛГ-код, позволяющий |
исправить |
любую |
|||||||||
одиночную |
ошибку |
вида |
± 2 \ при условии, что все ко |
||||||||
дируемые числа N не превышают |
величину |
|
|
|
|||||||
|
Д |
+ |
— 1 , если |
2 |
= ч - 1 по модулю А; |
||||||
^ о = |
|
|
|
|
|
|
|
|
|
(5-1) |
|
—2 |
|
1> если при любом л; 2Ж:^)— 1 по модулю А, |
|||||||||
где е — порядок |
класса |
вычетов 2 по модулю |
А. |
|
|||||||
Доказательство. |
Так как А—нечетное |
число, то |
|||||||||
|
|
|
±2{Ф0 |
по модулю |
А, |
|
|
|
|||
9—236 |
129 |
т. е. любой одиночной ошибке, соответствует ненулевой корректор. Условие, которому должен удовлетворять код длиной п разрядов с исправлением любой одиноч ной ошибки вида ±2*, запишем следующим образом:
|
±2{ф±2) |
по модулю А, |
(5-2) |
если 1ф\, |
0<с; (i, j)^Zn—1. |
Выполнение этого |
условия |
означает, |
что различным |
ошибкам будут соответство |
|
вать различные корректоры. Не нарушая общности рас
суждений, предположим, что t>y. Тогда из (5-2) |
следует |
|||
условие |
|
модулю А |
|
|
2 ' _ ' # |
± 1 по |
|
||
или |
|
|
|
|
21Ф±\ |
по |
модулю |
А, |
(5-3) |
где 1 < (/ = t—y)<: п— 1. |
|
|
|
|
Пусть е—-порядок |
класса вычетов 2 по модулю Л,т. е. |
|||
2е ==Г по модулю |
А, |
|
||
и пусть существует такое наименьшее число х, |
что |
|||
2Х= — 1 по модулю |
А. |
(5-4) |
||
Тогда максимальная длина кода п, при которой бу дет выполняться условие (5-3), равна наименьшему из
этих чисел, т. е. |
|
|
|
|
|
п = мин(е, л:). |
|
||
Из сравнения (5-4) следует: |
|
|||
2 Ь = 1 по модулю А |
|
|||
или |
|
|
|
|
\ = 22л^2е |
по модулю |
А. |
||
Последнее сравнение возможно только в том случае, |
||||
если е делит 2х, т. е. |
|
|
|
|
2х=Ье, |
где b^l |
|
— целое |
число. |
.Отсюда получаем, что |
|
|
|
|
|
,х=Ье/2, |
|
(5-5) |
|
•Если е — четное |
число, |
то |
равенство (5-5) выполня |
|
ется при Ь = 1 иминимальное |
значение* равно: е/2. Тогда |
|||
я = мин(е, е/2) =е/2-