Файл: Хетагуров, Я. А. Повышение надежности цифровых устройств методами избыточного кодирования.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 184
Скачиваний: 0
|
|
|
|
|
|
|
|
|
Т а б л и ц а 5-5 |
|
|
Значение модуля |
А |
|
Вероятность пропуска ошибки кратности t |
||||
3, |
5, 7, |
11, |
13, |
19, |
|
23, |
29, |
А У + |
(А — I ) ' - 1 J |
37, |
47, |
53, |
59, |
61, |
67, |
71, |
|
|
|
|
|
79, |
83 |
|
|
|
|
|
|
17, 41, 97
i =0
Не существует рассматриваемых арифметических раз делимых кодов с исправлением одиночных ошибок, по рожденных одним модулем. Справедливость этого утверждения следует из того факта, что при использо вании одного модуля невозможно определить, в какой части слова (информационной или контрольной) возник ла обнаруженная ошибка.
Использование двух порождающих модулей Ai и А2 позволяет построить разделимый код с исправлением
Информационное число В |
Контрольный |
Контрольный |
|
код fi, |
кодfi2 |
||
|
|||
к разрядов |
Г/ разрядов |
гг разрядов _ |
Рис. 5-1. Структура слова арифметического разделимого кода, по
рожденного |
модулями Л| и А2. |
Pi — остаток от деления числа В |
на модуль Аг. Рз — остаток от деления чис |
ла В на модуль Ai.
одиночных ошибок. В этом случае контрольная часть кодового слова состоит из двух групп разрядов, пред ставляющих собой остатки от делений информационного числа В на Ai и А2 (рис. 5-1). Таким образом, п-разряд- ное слово является кодовым, если
В — р, = 0 по |
модулю |
А,; |
) |
|
В — (32^з»0 |
по |
модулю |
А2. |
J |
Сравнения системы (5-11) будем называть контроль |
||||
ными соотношениями. |
Появление |
одиночной ошибки |
||
в информационной части слова (Ai |
и А%. не равные сте- |
|||
136
пени двойки числа) нарушит оба контрольных соотноше
ния. Если же только одно из контрольных |
соотношений |
|||
не |
выполняется, то |
это значит, |
что ошибка |
произошла |
в |
соответствующей |
контрольной |
части слова |
(предпола |
гается, что возникают только одиночные ошибки). Прежде чем сформулировать условия существования
кодов с исправлением одиночных ошибок, докажем сле
дующую |
|
лемму. |
|
|
|
|
|
|
|
|
|
||
Лемма. |
Пусть имеют место |
сравнения |
|
|
|
||||||||
|
|
|
|
2х' |
£э — 1 по |
модулю |
Л,; |
|
|
|
|
||
|
|
|
|
2 л |
==, — 1 по модулю |
Ah, |
|
|
|
|
|||
где Ai, |
..., |
Ан — нечетные |
числа, |
не |
равные |
единице, |
|||||||
a Xi, ..., |
хн — наименьшие числа, при которых сравнения |
||||||||||||
справедливы. |
|
|
|
|
|
|
|
|
|
|
|||
Для существования |
решения системы сравнений |
||||||||||||
|
|
|
|
2*== — 1 по |
модулю Л,; |
•» |
|
|
|||||
|
|
|
|
2х |
|
|
|
|
|
[ |
|
(5-12) |
|
|
|
|
|
== —к1 по модулю Л Л |
J |
|
|
||||||
необходимо и достаточно, чтобы значения |
степени |
p i = 2 |
|||||||||||
в каноническом представлении1 порядков |
двойки |
( e t = |
|||||||||||
= 2xi, |
• •., |
ел = 2х„) по |
модулям |
Аь |
..., |
Ah |
были |
равны |
|||||
между |
собой, |
причем |
x=[xit |
..., |
Xh]= |
[ej2, |
..., |
eh/2] — |
|||||
наименьшее число, являющееся решением системы (5-12). (Здесь и ниже квадратными скобками обозначено на именьшее общее кратное.)
Доказательство. |
Если решение системы (5-12) |
суще |
|||||||||
ствует, то существуют |
такие |
нечетные числа |
L±, |
..., |
L A , |
||||||
что |
x—<LiXi=LzX%= |
... =Lhxh. |
|
|
(5-13) |
||||||
|
|
|
|||||||||
Так как L b |
|
L%, |
..., |
|
Lh нечетны, то степень |
рх=2 |
в их |
||||
каноническом |
представлении |
равна |
нулю |
и |
равенства |
||||||
(5-13) возможны только в том случае, если степени |
p i = 2 |
||||||||||
в каноническом |
представлении Хи • • •, х-к равны |
между |
|||||||||
собой. Порядки |
двойки |
по модулям |
Ai, |
Ah связаны |
|||||||
'Каноническим представлением |
целого |
числа |
д > 1 |
называется |
|||||||
его представление |
в |
виде а = |
р*1р%* |
••• Pf.h> |
где Pi, |
Рг |
Рь— по |
||||
парно различные |
простые |
числа. |
Это представление |
единственно |
|||||||
с точностью до порядка |
следования |
простых |
чисел. |
|
|
|
|
||||
137
Со значениями Хг равенствами |
в\.—2хь ..., ен = 2х\х, |
поэто^ |
||
му степени |
/ ? i = 2 в каноническом |
представлении |
этих |
|
порядков также будут равны |
между |
собой. |
|
|
Обратно, |
если степени pi |
= 2 в |
каноническом |
пред |
ставлении х\ равны между собой, то могут быть найдены
такие |
нечетные |
значения |
коэффициентов |
L \ , ..., |
L/„ |
что |
|||||
будут |
иметь место |
равенства (5-13). Значения |
Li |
можно |
|||||||
вычислить |
следующим образом: |
|
|
|
|
|
|
||||
|
Li=[xu |
хъ |
|
xii]lxi, |
i = l , |
2 |
h. |
|
|
|
|
Таким образом, первая часть леммы доказана, а из |
|||||||||||
последних равенств следует, что |
|
|
|
|
|
|
|||||
|
x=LiXi=[xu |
|
xz, ..., |
* л ] = |
[ei/2, |
е2 /2, |
..., |
e,J2]. |
|
||
Лемма |
доказана полностью. |
|
|
|
|
|
|
||||
Условия |
существования кодов с |
исправлением |
оди |
||||||||
ночных ошибок, порождаемых системой модулей, сфор мулируем в виде следующей теоремы.
|
Теорема |
5-3. |
Арифметический разделимый (п, Л)-код, |
||||||||||
порожденный |
системой |
нечетных |
модулей |
Ait |
..., Ah |
||||||||
(h^2), |
позволяет исправить |
любую |
одиночную |
ошибку |
|||||||||
вида |
± 2 ' , |
если |
длина |
информационной |
части |
кодового |
|||||||
слова |
k выбирается |
следующим |
образом: |
|
|
||||||||
^ |
Пе,, ... , |
eh\, |
если |
система |
(5-12) не |
имеет |
решения; |
||||||
|
I |
[е,/2 |
|
£/i/2] |
если система (5-12) |
имеет |
решение. |
||||||
|
Доказательство. |
В кодовом слове, длина которого п = |
|||||||||||
|
+ / 4 + .. . + /"л, |
одиночная |
ошибка |
может |
возникнуть |
||||||||
в информационных либо в контрольных разрядах. Если ошибка возникла в одной из груш контрольных разря
дов, то будет нарушено лишь |
одно из контрольных соот |
|||
ношений системы |
|
|
|
|
В — р, = |
0 |
по |
модулю Л,; |
•) |
В — рЛ = |
0 |
по |
модулю Л Л |
) |
и производится коррекция соответствующего контроль ного кода.
При возникновении одиночной ошибки в информаци онной части слова будут нарушены все контрольные со
отношения, так как |
± 2 ' ^ = 0 по нечетному значению мо |
дуля. Совокупность |
наименьших положительных значе- |
138
ним вычетов от |
± 2 ' по модулям |
Л ь . .., Аи |
обозначим |
через Ai = +[zii, |
• •., г'д]. Д; будем |
называть |
корректором |
или синдромом. Код позволяет исправить любую оди
ночную |
ошибку, если различным ошибкам (одиночным) |
||||||
будут |
соответствовать |
различные |
ненулевые |
значения |
|||
корректоров Aj. Пусть A j = A ; ( t < / ) , |
т. е. имеет |
место си |
|||||
стема |
сравнений |
|
|
|
|
|
|
|
|
н-21 ' == z!r 2 j |
по |
моДулю |
Л,; 4 |
|
|
|
|
= ь2 г ' = |
н-2-' |
по |
модулю |
Ан. |
|
Отсюда |
при i<j |
следует, что |
|
|
|||
|
|
2*~= z!r 1 по модулю Л,; |
(5-14) |
||||
|
|
|
|
|
|
|
|
|
|
2 I = i ± l |
по |
модулю, Л/„ |
|
||
где x=j—/. |
Наименьшее |
значение х, являющееся реше |
|||||
нием этой системы при положительной правой части, рав но наименьшему общему кратному порядков 2 по моду лям А\, . .., Ah:
x=>[eit ... , ei,l |
(5-15) |
Если среди порождающих модулей Ai, ..., Лд найдет ся хотя 'бы один модуль, для которого сравнение 2*=—1 невозможно (порядок в — нечетное число), то решение системы (5-14) при отрицательной правой части не су ществует. Если же для всех модулей Ai сравнение 2х = = — 1 возможно, то в соответствии с леммой
[ [ е , / 2 , e h / 2 ] , если решение системы (5-12) сущест вует;
Х- [е, в/,], если решение системы (5-12) не су ществует.
(5-16)
Из выражений (5-15) и (5-16) следует утверждение теоремы, так как при длине информационной части сло ва k двоичных разрядов фаза ошибки i не превосходит величину k—1 (в ^-разрядном числе вес старшего разря да равен 2h~i). Теорема доказана.
Для синтеза кодов с исправлением одиночных оши бок в соответствии с теоремой 5-3 можно использовать табл. 5-2. Обычно. с целью уменьшения избыточности кода (количества контрольных разрядов), выбирается
139