Файл: Хетагуров, Я. А. Повышение надежности цифровых устройств методами избыточного кодирования.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 181
Скачиваний: 0
2. Если d четно, то условия существования соответствующего кода и способ вычисления его матрицы представлены в табл. 4-10. Если же d нечетно, то в табл. 4-10 числа d и п заменяются соот ветственно на d-1-l н
В табл. 4-10 через А',, и А " п обозначены матрицы, получаемые из An-матрнцы следующим образом. Если в исходной А„-матрице крайний правый столбец поразрядно сложить со всеми к столбцами
матрицы, то правый столбец полученной |
А * п матрицы |
будет |
со |
||||||||
стоять из нулей (минимальное расстояние |
в |
полученной |
таким |
об |
|||||||
разом матрице остается равным nj2). Матрица |
А'„ получается из |
||||||||||
матрицы |
А*„ отбрасыванием столбца |
из всех |
нулей, а A " , i — |
отбра |
|||||||
сыванием |
двух |
последних |
столбцов |
A * n |
и |
всех |
строк, |
у которых |
|||
в предпоследнем |
столбце |
(матрицы |
А*„) стоит |
нуль. Заметим, |
что |
||||||
минимальное расстояние между |
строками |
А'„ и |
А" „ остается |
рав |
|||||||
ным /г/2. |
|
|
|
|
|
|
|
|
|
|
|
Например, пусть требуется |
построить |
код с параметрами: |
/г=20 |
||||||||
разрядов, |
rf=12. |
Тогда £=[12/(24—20)1=3, из уравнений |
(4-20) |
на |
|||||||
ходим: я = 4 , 6=0. Так как п — четное, |
rf/(2d—п)—целое, |
то |
из |
||||||||
табл. 4-10 следует, что требуемый код существует, если число k—3
правильное. Кодовыми словами являются строки матрицы |
|
А = ^ - А " 4 Н = 2 А " , 2 |
(4-21) |
которая построена в конце параграфа.
В заключение рассмотрим некоторые теоремы (без доказатель ства) о существовании Ая -матриц.
Теорема 4-1. Если существует' АП 1 -матрица и АП з -матрица, то
существует An-матрнца порядка ft=/ti/i2.
Метод построения искомой Ап -матрнцы заключается в том, что вместо каждого элемента АП 1 -матрнцы подставляется АЛ з -матрнца,
умноженная на этот |
элемент. |
|
|
|
|
Простейшая А2 -матрпца имеет вид: |
|||
|
|
А . = |
1 |
1 |
|
|
I |
—1 |
|
|
|
|
||
|
Таким образом, согласно теореме 4-1 всегда может быть по |
|||
строена An-матрица |
порядка |
я = 2 ' , где i — любое целое положитель |
||
ное |
число. Например, из А 2 |
в соответствии с изложенным алгорнт |
||
мом |
получаем: |
|
|
|
|
|
|
|
1 |
А 4 |
= |
I |
— |
А 8 = |
|
|
|
||
|
|
1 —1 |
|
|
122
|
Теорема |
4-2. Если |
р—Р\ , |
где а — Натуральное |
число, |
p i — не |
||||||||||||||
четное простое |
число вида |
Ak—1, то существует An-матрица |
порядка |
|||||||||||||||||
п=р+1. |
|
|
|
|
|
|
|
какого порядка п могут быть |
|
|
|
|||||||||
|
Из табл. 4-11 видно, |
построены |
||||||||||||||||||
А„-матрицы согласно теореме 4-2, если ос=1. |
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Т а б л и ц а |
4-11 |
|||
|
|
k |
|
|
|
1 |
2 |
|
3 |
4 |
5 |
6 |
|
8 |
|
9 |
10 |
11 |
12 |
|
|
4k— 1 |
3 |
7 |
|
11 |
15 |
19 |
23 |
31 |
37 |
39 |
|
43 |
47 |
||||||
|
Р = |
Р* |
|
З 1 |
V |
|
111 |
— |
19' |
23' |
31' |
371 |
— |
|
43' |
471 |
||||
|
п = |
р+1 |
4 |
8 |
|
12 |
— |
20 |
24 |
32 |
38 |
— |
|
44 |
48 |
|||||
|
Построение |
А„-матриц |
порядка |
пф2{ |
связано |
с использованием |
||||||||||||||
понятия «символ Лежаидра», применяемого в теории чисел |
[Л. 39]. |
|||||||||||||||||||
Рассмотрим сравнение второй степени по модулю простого |
числа |
|||||||||||||||||||
Pi>2 |
|
|
|
|
|
|
_ |
= а |
|
|
pt). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
х 2 |
(модуль |
|
|
|
|
|
|
|
|
|||
|
Если |
0 < а ^ / ? | — 1 , |
то |
это сравнение либо име<,г два |
решения |
|||||||||||||||
(х0 ; —.to), либо |
не имеет |
ни одного решения. Все числа |
a ( 0 < a ^ |
|||||||||||||||||
^ / J i — ' К |
для которых |
рассматриваемое |
сравнение |
имеет |
два ре |
|||||||||||||||
шения, |
называются |
квадратичными |
вычетами по модулю |
Р\ и |
соот |
|||||||||||||||
ветственно |
|
все |
числа а, для которых не существует |
решении,—• |
||||||||||||||||
квадратичными |
невычетами |
по этому модулю. По любому |
p i > 2 |
чис |
||||||||||||||||
ло |
квадратичных |
вычетов |
равно |
числу |
квадратичных |
|
невычетов. |
|||||||||||||
Необходимым и достаточным условием того, чтобы а было |
квадра |
|||||||||||||||||||
тичным |
вычетом по простому модулю Pi>2, является |
справедливость |
||||||||||||||||||
сравнения |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
a(Pi—])1-=[ |
по модулю |
pt. |
|
|
|
|
|
|
|
|||||
|
Если же |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
a (Pi—4/2 = — 1 П 0 |
модулю |
Pi, |
|
|
|
|
|
|
|||||||
то а будет квадратичным |
невычетом |
(критерий |
Эйлера). |
|
|
|
|
|||||||||||||
|
Символ |
Лежандра |
для числа a по простому |
модулю р\>2 |
будем |
|||||||||||||||
записывать |
в виде |
(a/Pi), |
причем |
|
|
|
|
|
|
|
|
|
|
|||||||
(__ |
|
j +11 |
если а — квадратичный |
вычет по модулю р , . |
|
|||||||||||||||
\ |
Pi ) |
\—1, |
если а — квадратичный невычет по |
|
модулюР\. |
|
||||||||||||||
Согласно критерию |
Эйлера |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
а(Р1~^/2=(а/р,) |
|
|
по модулю |
р, , в частности |
(—1/р,) = |
( — 1 ) ( л — |
||||||||||||||
по модулю |
|
Pi. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
В теории чисел доказываются следующие свойства |
символов |
||||||||||||||||||
Лежандра: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
(a2 /Pi) = l , в частности |
( l / p i ) = l ; |
|
|
|
|
|
|
||||||||
(a,a2 ... anlpi) = (a,/pi) . . . (a„/pi).
123
Матрицы Адамара, Которые существуют согласно теореме 4-2, строятся следующим образом:
|
An = \\qti\\, |
0 < « , / < Л , |
(4-22) |
||
где элементы |
|
|
|
|
|
((/ |
— 1, |
если |
0 < i , |
— 1 и i = j; |
|
—О/А), |
если |
0 < i , |
/ < / > , — 1 и |
1ф\\ |
|
|
1, |
если |
i = pi |
или j = /?,. |
|
В связи с тем что вычисление символов Лежандра с помощью критерия Эйлера является очень трудоемким процессом, укажем сле
дующий |
способ вычисления |
(а/р). |
|
|
|
|
|
|||||||
|
Если |
|
я = |
р*'р2' |
••• pi* — каноническое разложение |
а, то |
|
|||||||
(а/р) |
= [р,/р)^ |
(рг/р)**... |
|
(р,/р)а°, |
|
|
|
|
|
|||||
причем, |
так как |
(pi/p) 2 = 1, |
то можно |
оставить |
и притом |
только |
||||||||
в |
первой |
степени |
|
те сомножители, |
у |
которых |
а,- — нечетны. Если |
|||||||
Р ; = 2 , |
то |
|
|
|
|
|
|
|
|
|
|
|
||
/ |
2 |
\ |
f |
1, |
если |
р= |
\ по модулю |
8 или / > = 7 |
по модулю |
8, |
||||
\ |
Р / |
[—1, |
если |
р = |
3 по |
модулю 8 или р=5 |
по модулю |
8, |
||||||
а |
к |
множителям |
вида |
(р,7р), г-де р . < р , применяется |
формула |
|||||||||
( ^ ) = < - " 2 |
' ( £ ) - < - • > • |
1 |
Ш - |
|
||
где г — остаток от |
деления |
р на р.. Таким |
образом, этот |
процесс |
||
сводит вычисление |
символа |
Лежандра (а/р) |
к вычислению |
других |
||
символов Лежандра, в которых а заменяется меньшими числами.
Продолжая этот процесс, мы дойдем до символов вида (l/р) и |
(2/р). |
||
В частности, для p i = l l |
получаем следующие значения |
симво |
|
лов Лежандра: |
|
|
|
(1/11) = 1; |
|
|
|
( 2 / 1 1 ) — 1 ; |
|
|
|
(3/11) = (—1>5 1 (11/3) = ( - 1 ) • (2/3) = ( - 1 ) ( - 1 ) = 1; |
|
||
(4/11) = (2V11) = |
(2/1 l)z = |
i ; |
|
(5/11) = ( - i f 2 |
(11/5) = (1/5) = 1; |
|
|
(6/11) = (2/11) (3/11) = — 1 ;
(7/11) = (-1)5 '3 (11/7) = ( - 1 ) (4/7) = ( - 1 ) ( 2 / 7 ) 2 = - 1 ;
(8/11) = |
(2»/Н) = (2/11)3= (2/11) = _ 1 ; |
|
(9/11) = |
|
(3/11)2 =1; |
(10/11) = |
(2/11) ( 5 / 1 1 ) = - 1 . |
|
124
Заметим, что количество квадратичных вычетов равно количе ству квадратичных невычетов.
Используя полученные значения символов Дежандра, а также учитывая, что при j<i
н
V 11
получаем значения элементов матрицы Ai2. Несмотря на кажущуюся сложность, матрица строится довольно просто: сначала выписывают ся все граничные элементы, а затем производится сдвиг вправо на 1 разряд первой строки, затем второй и т. д.:
1 |
1 |
1 —1 |
|
||
-1 |
1 |
1 |
1 |
|
|
1 —1 |
1 |
1 |
|
||
—1 |
|
—1 |
1 |
|
|
|
|
|
1 —1 |
|
|
1 —1 |
—1 |
1 |
(4-23) |
||
А ] 2 |
|
1 —1 —1 |
|||
-1 |
|
|
|||
-1 |
—1 |
1 |
|
|
|
-1 |
—1 —1 |
|
|
||
|
-1 —1 —1 |
|
|
|
1 —1 —1 — |
|
|
1 |
1 |
1 |
1 |
Теорема 4-3. Если существует А„-матрица |
( « i ^ 2 ) , то для лю |
||
бого р, являющегося степенью нечетного простого числа, существует
An-матрица |
порядка |
« = r t i ( p + l ) . |
|
|
||
|
Согласно |
теореме |
4-3, можно построить матрицы порядка |
|||
28=2(13+1), |
36=2(17+1), 40=2(19+1) и т. д. Построение искомой |
|||||
Ал -матрицы порядка |
гс=Я](р+1) |
состоит |
в подстановке вместо каж |
|||
дого |
недиагонального |
элемента |
матрицы |
(4-22) |
порядка р + 1 матри |
|
цы |
А П ] умноженной |
на этот элемент, а вместо каждого диагональ |
||||
ного |
элемента — матрицы, полученной из |
(—1) |
А Я [ изменением зна |
|||
ков элементов всех нечетных по номеру строк, и перестановке со следующими за ними строками.
Если в теореме 4-2 ограничиться случаем, когда р является нечетным простым, то три приведенные теоремы и способы построе ния Ап-матриц позволяют построить искомые матрицы для правиль
ных |
чисел |
k^.\Z. |
В табл. |
4-12 показано, какие из приведенных тео |
|||
рем |
следует |
использовать |
для построения Ап - матриц |
при |
k^\2. |
||
В работе |
[Л. |
38] |
можно |
найти таблицу правильных |
чисел |
й ^ 2 5 0 , |
|
а также другие известные теоремы о существовании Ап - матриц и способы их построения.
125
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Т а б л и ц а |
4-12 |
||||
|
|
|
|
|
|
|
|
|
Какую |
|
|
|
|
|
|
|
|
|
|
|
|
Какую |
||
|
Представление |
|
теорему |
|
|
|
Представление |
|
|
теорему |
||||||||||||||
k |
|
|
л=<1& |
|
|
|
с л е д у е т |
|
k |
|
|
|
n=4k |
|
|
|
|
следует |
||||||
|
|
|
|
|
|
|
|
использо |
|
|
|
|
|
|
|
|
|
|
|
использо |
||||
|
|
|
|
|
|
|
|
|
вать |
|
|
|
|
|
|
|
|
|
|
|
|
|
вать |
|
1 |
4=2= |
|
|
|
|
|
4-1 |
|
|
7 |
28=2(13+1) |
|
|
|
4-3 |
|||||||||
2 |
8=2» |
|
|
|
|
|
4-1 |
|
|
8 |
32=2 6 |
|
|
|
|
|
|
4-1 |
||||||
3 |
12=11 + 1 |
|
|
|
4-2 |
|
|
9 |
36=2(17+1) |
|
|
|
4-3 |
|||||||||||
4 |
16=2* |
|
|
|
|
|
4-1 |
|
|
10 |
40=2(19+1) |
|
|
|
4-3 |
|||||||||
5 |
20=19+1 |
|
|
|
4-2 |
|
|
11 |
44=43+1 |
|
|
|
|
4-2 |
||||||||||
6 |
24=2(11 + 1) |
|
4-3 |
|
|
12 |
48=4(11 + 1) |
|
|
|
4-3 |
|||||||||||||
Построим |
матрицу |
(4-21), |
соответствующую |
коду |
с |
параметра- |
||||||||||||||||||
ми: я = 2 0 , |
d=12, m=6 . |
Из |
(4-23) |
следует, что |
|
|
|
|
|
|
|
|
|
|||||||||||
0 |
1 0 |
1 1 1 0 |
0 |
0 |
1 0 |
1 |
|
|
1 0 1 0 0 0 1 1 1 0 1 0 |
|||||||||||||||
0 0 |
1 0 |
1 1 1 0 |
0 0 |
1 1 |
|
|
1 1 0 1 0 0 0 1 1 1 0 0 |
|||||||||||||||||
1 0 |
0 |
1 0 |
1 1 1 |
0 0 0 1 |
|
|
0 1 1 0 1 0 0 0 1 1 1 0 |
|||||||||||||||||
0 |
1 0 |
0 |
1 0 |
|
1 1 |
1 0 |
0 1 |
|
|
1 0 1 1 0 1 0 0 0 1 1 0 |
||||||||||||||
0 0 |
1 0 |
0 |
1 0 |
1 |
1 1 0 |
1 |
|
|
1 |
1 0 1 |
|
1 0 1 0 0 0 1 0 |
||||||||||||
А, , = 0 0 0 1 0 0 1 0 1 1 1 1 |
|
|
1 1 1 0 1 1 0 1 0 0 0 0 |
|||||||||||||||||||||
1 0 |
0 0 |
1 0 |
0 1 |
0 |
1 1 1 |
|
|
0 1 1 1 0 1 1 0 1 0 0 0 |
||||||||||||||||
1 1 0 |
0 0 |
1 0 |
0 |
1 0 |
1 1 |
|
|
0 0 1 1 1 0 1 1 0 1 0 0 |
||||||||||||||||
1 1 1 0 |
0 0 |
|
1 0 |
0 |
1 0 |
1 |
|
|
0 0 0 1 1 1 0 1 1 0 1 0 |
|||||||||||||||
0 1 1 1 0 0 0 1 0 0 1 1 |
|
|
1 0 0 0 1 I 1 0 1 1 0 0 |
|||||||||||||||||||||
1 0 1 1 1 0 0 0 |
1 0 0 '1 |
|
|
0 I 0 0 0 I 1 1 0 I 1 0 |
||||||||||||||||||||
1 1 1 1 1 1 1 1 |
1 1 1 1 |
|
|
0 0 0 0 0 0 0 0 0 0 0 0 |
||||||||||||||||||||
|
|
I 0 I о о о 1 1 1 0 1 |
|
|
1 0 1 0 0 0 1 1 1 0 |
|||||||||||||||||||
|
|
1 |
1 0 |
1 0 |
0 |
0 |
1 1 1 0 |
|
|
0 |
1 1 0 |
1 0 |
0 0 |
1 I |
||||||||||
|
|
0 |
1 1 0 |
|
1 0 |
0 0 |
1 1 1 |
А" |
|
1 0 |
1 1 0 |
1 0 0 0 1 |
||||||||||||
|
|
1 0 1 1 0 1 |
0 0 0 1 1 |
|
1 1 0 1 1 0 1 0 0 0 |
|||||||||||||||||||
|
|
Л 12 |
|
|||||||||||||||||||||
|
|
1 1 0 |
1 1 0 |
1 0 |
0 0 1 |
|
|
0 0 0 |
1 1 1 |
0 |
1 1 0 |
|||||||||||||
\i |
1 |
1 1 1 0 |
|
1 1 |
0 |
1 0 |
0 0 |
|
|
0 |
1 0 |
0 0 |
1 1 1 0 |
1 |
||||||||||
0 |
1 1 1 0 |
1 |
1 0 |
1 0 |
0 |
|
|
|||||||||||||||||
Л 1 2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
0 0 |
1 1 1 0 |
1 1 0 |
1 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
0 0 0 |
1 |
|
1 1 |
0 |
1 1 0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
1 0 0 0 |
|
1 1 |
1 0 |
1 1 0 |
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
0 |
1 0 0 0 1 |
1 1 0 |
1 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
0 |
0 0 0 0 0 |
0 0 0 0 0 |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
126