Кочергин В.И. Теория многомерных цифро-векторных множеств
Подождите немного. Документ загружается.
Глава 4
220
Для поворотов относительно осей симметрии только информацион-
ной части систематического кода i = 4 получается число возможных
положений геометрического образа s
4
= 384, что вполне обозримо, то-
гда как для следующего кода, исправляющего одиночные ошибки, i = 11
это число s
11
= 81 749 606 400 – огромно и необозримо. При наличии
симметрии исходной фигуры, что в нашем случае здесь имеет место,
число этих геометрических образов будет уменьшено до значения s
i
= 2
k
i!,
где k – число разрядов контрольной части систематического кода. Тогда
s
4
= 192, s
11
= 638 668 800, что также для второго случая необозримо.
Дополнительно выполняя повороты относительно осей симметрии
контрольной части кода, число кодов, исправляющих одиночные ошибки,
будет увеличено в 2
k
k! раз, что не представляется возможным все их рас-
смотреть.
Поэтому представим коды, исправляющие одиночные ошибки для
основания системы счисления n = 16, получаемые только поворотами
относительно осей симметрии информационной части систематического
кода.
Обратимся к первой главе, где в п. 1.2 представлена процедура фор-
мирования перестановок, в том числе и для четырех операндов, в качестве
которых будем рассматривать разряды a
1
, a
2
, a
3
, a
4
информационной части
систематического кода, и эти разряды будем записывать их индексами 1,
2, 3, 4, т.е. a
1
, a
2
, a
3
, a
4
≡ 1, 2, 3, 4.
В соответствии с этой процедурой в табл. 4.2.1 представлены все по-
ложения координат четырехмерного цифрового пространства, которые
получаются мысленными поворотами относительно осей его симметрии,
где первая половина первого столбца этой таблицы составлена, исходя
только из перестановок его координат (разрядов 1, 2, 3, 4), а другие столб-
цы первой половины образуются переводом одного или двух координат из
прямого кода в обратный. При этом столбцы этой таблицы обозначены
цифрами 0–7, строки – 0–47. Вторая часть всех столбцов (строки под но-
мерами 23–47) таблицы получается переводом координат пространства из
прямого кода в обратный, а для двоичного кода это – простое инвертиро-
вание всех его разрядов.
Выбрав в качестве исходного первый код, например с координатами
0, 15, табл. 4.2.1, 4.2.2 и осуществляя мысленные повороты относительно
информационных координат, получим ряд кодов, исправляющих одиноч-
ные ошибки основания n = 16. Цветной шрифт кодов в этой таблице соот-
ветствует 18 кодам, полученным нами эвристическим методом.
Примеры синтеза комбинационных схем
221
Таблица 4.2.1
0 1 2 3 4 5 6 7
0
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1
2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4
2
3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4
3
4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1
4
1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4
5
2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4
6
3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4
7
4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1
8
1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2
9
2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1
10
3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2
11
4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3
12
1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3
13
2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3
14
3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1
15
4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2
16
1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2
17
2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1
18
3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2
19
4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3
20
1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3
21
2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3
22
3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1
23
4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2
24
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
25
2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4
26
3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4
27
4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1
28
1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4
29
2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4
30
3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4
31
4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1
32
1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2
33
2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1
34
3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2
35
4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3
36
1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3
37
2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3
38
3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1
39
4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2 4 3 1 2
40
1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2
41
2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1
42
3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2
43
4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3
44
1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3
45
2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3
46
3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1 3 4 2 1
47
4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2 4 1 3 2
Результаты этих преобразований сведены в табл. 4.2.2, где повторное
получение кодов в результате соответствующего поворота отмечено за-
темненной клеткой цифрового пространства координат таблицы. Анало-
Глава 4
222
гично отмечены координаты ячеек табл. 4.2.1, совершаемые после запол-
нения табл. 4.2.2.
Из табл. 4.2.2 следует, что число кодов, исправляющих одиночные
ошибки, в нашем случае равно 192.
Таблица 4.2.2
0
1
2
3
4
5
6
7
0 7 34 7 0 4 3 3 40752616152437025161 6 2 5
5 2 61 2 5 1 6 6 15207343407162570434 3 7 0
0
6 1 52 1 6 2 5 5 26134070734251643707 0 4 3
3 4 07 4 3 7 0 0 73461525261704316252 5 1 6
0 3 74 3 0 4 7 7 4035621651247306 5 1 2 5 6 2 1
5 6 21 6 5 1 2 2 1560374304712653 0 4 7 0 3 7 4
1
6 5 12 5 6 2 1 1 2653047037421560 3 7 4 3 0 4 7
3 0 47 0 3 7 4 4 730651256217403
5 6 2 1 6 5 1 2
0 5 36 5 0 6 3 3 605724163506 3 5 027143 6 0 5
7 2 41 2 7 1 4 4 172053614271 4 2 75 0634 1 7 2
2
6 3 50 3 6 0 5 5 063142705360 5 3 64 1725 0 6 3
1 4 27 4 1 7 2 2 71463507241
7 2 4 136052 7 1 4
0 6 53 6 0 3 5 5 306356071243 5 6 0 5 3 0 6 1 7 4 2
3 5 60 5 3 0 6 6 035065342170 6 5 3 6 0 3 5 2 4 7 1
3
7 1 24 1 7 4 2 2 471421706534 2 1 7 2 4 7 1 6 0 3 5
4 2 17 2 4 7 1 1 74271243560
7 1 2 4 1 7 4 2 5 3 0 6
0 7 52 7 0 2 5 5 20734616134257043161 6 4 3
3 4 61 4 3 1 6 6 13407525207164370252 5 7 0
4
6 1 34 1 6 4 3 3 46152070752431625707 0 2 5
5 2 07 2 5 7 0 0 75261343461702516434 3 1 6
0 3 56 3 0 6 5 5 603742165306 5 3 047125 6 0 3
5
7 4 21 4 7 1 2 2 174035612471 2 4 730652 1 7 4
6 5 30 5 6 0 3 3 06512470356
0 3 5 621743 0 6 5
1 2 47 2 1 7 4 4 71265307421
7 4 2 156034 7 1 2
0 5 72 5 0 2 7 7 2053641631427506 3 1 4 3 6 4 1
3 6 41 6 3 1 4 4 1360572502714635 0 2 7 0 5 7 2
6
6 3 14 3 6 4 1 1 4635027057241360 5 7 2 5 0 2 7
5 0 27 0 5 7 2 2 750631436417205
3 6 4 1 6 3 1 4
0 6 35 6 0 5 3 3 506536071425 3 6 0 3 5 0 6 1 7 2 4
5 3 60 3 5 0 6 6 053063524170 6 3 5 6 0 5 3 4 2 7 1
7
7 1 42 1 7 2 4 4 271241706352 4 1 7 4 2 7 1 6 0 5 3
2 4 17 4 2 7 1 1 72471425360
7 1 4 2 1 7 2 4 3 5 0 6
0 7 61 7 0 1 6 6 10752343452167025434 3 2 5
5 2 34 2 5 4 3 3 45207616107432570161 6 7 0
8
3 4 52 4 3 2 5 5 23461070761254316707 0 1 6
6 1 07 1 6 7 0 0 76134525234701643252 5 4 3
0 3 65 3 0 5 6 6 50356307412
5 6 3 0 6 5 0 3 4 7 2 1
5 6 30 6 5 0 3 3 056036521470 3 6 5 3 0 5 6 1 2 7 4
9
7 4 12 4 7 2 1 1 274214703652 1 4 7 1 2 7 4 3 0 5 6
2 1 47 1 2 7 4 4 72174125630
7 4 1 2 4 7 2 1 6 5 0 3
0 5 63 5 0 3 6 6 305721436503 6 5 027416 3 0 5
7 2 14 2 7 4 1 1 472056341274 1 2 75 0361 4 7 2
10
3 6 50 6 3 0 5 5 036412705630 5 6 31 4725 0 3 6
4 1 27 1 4 7 2 2 74136507214
7 2 1 463052 7 4 1
0 6 71 6 0 1 7 7 1063542532417605 3 2 4 3 5 4 2
3 5 42 5 3 2 4 4 2350671601724536 0 1 7 0 6 7 1
11
5 3 24 3 5 4 2 2 4536017067142350 6 7 1 6 0 1 7
6 0 17 0 6 7 1 1 760532435427106
3 5 4 2 5 3 2 4
Примеры синтеза комбинационных схем
223
Продолжение табл. 4.2.2
0
1
2
3
4
5
6
7
0 7 34 7 0 4 3 3 40761525261437016252 5 1 6
6 1 52 1 6 2 5 5 26107343407251670434 3 7 0
12
5 2 61 2 5 1 6 6 15234070734162543707 0 4 3
3 4 07 4 3 7 0 0 73452616152704325161 6 2 5
0 3 74 3 0 4 7 7 4036512562147305 6 2 1 6 5 1 2
6 5 12 5 6 2 1 1 2650374304721563 0 4 7 0 3 7 4
13
5 6 21 6 5 1 2 2 1563047037412650 3 7 4 3 0 4 7
3 0 47 0 3 7 4 4 730562165127403
6 5 1 2 5 6 2 1
0 5 36 5 0 6 3 3 605635072416 3 5 0 3 6 0 5 2 7 1 4
6 3 50 3 6 0 5 5 063053614270 5 3 6 5 0 6 3 4 1 7 2
14
7 2 41 2 7 1 4 4 172142705361 4 2 7 4 1 7 2 5 0 6 3
1 4 27 4 1 7 2 2 71472416350
7 2 4 1 2 7 1 4 3 6 0 5
0 6 53 6 0 3 5 5 306712435603 5 6 017425 3 0 6
7 1 24 1 7 4 2 2 471065342174 2 1 76 0352 4 7 1
15
3 5 60 5 3 0 6 6 035421706530 6 5 32 4716 0 3 5
4 2 17 2 4 7 1 1 74235607124
7 1 2 453061 7 4 2
0 7 52 7 0 2 5 5 20761343461257016434 3 1 6
6 1 34 1 6 4 3 3 46107525207431670252 5 7 0
16
3 4 61 4 3 1 6 6 13452070752164325707 0 2 5
5 2 07 2 5 7 0 0 75234616134702543161 6 4 3
0 3 56 3 0 6 5 5 603653074216 5 3 0 5 6 0 3 4 7 1 2
6 5 30 5 6 0 3 3 065035612470 3 5 6 3 0 6 5 2 1 7 4
17
7 4 21 4 7 1 2 2 174124703561 2 4 7 2 1 7 4 3 0 6 5
1 2 47 2 1 7 4 4 71274216530
7 4 2 1 4 7 1 2 5 6 0 3
0 5 72 5 0 2 7 7 2056314364127503 6 4 1 6 3 1 4
6 3 14 3 6 4 1 1 4630572502741365 0 2 7 0 5 7 2
18
3 6 41 6 3 1 4 4 1365027057214630 5 7 2 5 0 2 7
5 0 27 0 5 7 2 2 750364163147205
6 3 1 4 3 6 4 1
0 6 35 6 0 5 3 3 506714253605 3 6 017243 5 0 6
7 1 42 1 7 2 4 4 271063524172 4 1 76 0534 2 7 1
19
5 3 60 3 5 0 6 6 053241706350 6 3 54 2716 0 5 3
2 4 17 4 2 7 1 1 72453607142
7 1 4 235061 7 2 4
0 7 61 7 0 1 6 6 10734525234167043252 5 4 3
3 4 52 4 3 2 5 5 23407616107254370161 6 7 0
20
5 2 34 2 5 4 3 3 45261070761432516707 0 1 6
6 1 07 1 6 7 0 0 76152343452701625434 3 2 5
0 3 65 3 0 5 6 6 503741256305 6 3 047216 5 0 3
7 4 12 4 7 2 1 1 274036521472 1 4 73 0561 2 7 4
21
5 6 30 6 5 0 3 3 056214703650 3 6 51 2743 0 5 6
2 1 47 1 2 7 4 4 72156307412
7 4 1 265034 7 2 1
0 5 63 5 0 3 6 6 305365072143 6 5 0 6 3 0 5 2 7 4 1
3 6 50 6 3 0 5 5 036056341270 5 6 3 5 0 3 6 1 4 7 2
22
7 2 14 2 7 4 1 1 472412705634 1 2 7 1 4 7 2 5 0 3 6
4 1 27 1 4 7 2 2 74172143650
7 2 1 4 2 7 4 1 6 3 0 5
0 6 71 6 0 1 7 7 1065324354217603 5 4 2 5 3 2 4
5 3 24 3 5 4 2 2 4530671601742356 0 1 7 0 6 7 1
23
3 5 42 5 3 2 4 4 2356017067124530 6 7 1 6 0 1 7
6 0 17 0 6 7 1 1 760354253247106
5 3 2 4 3 5 4 2
Глава 4
224
Продолжение табл. 4.2.2
0
1
2
3
4
5
6
7
7 0 4 3 0 7 3 4 4 3 7 0 2 5 1 6 1 6 2 5 3 4 0 7 5 2 6 1 6 1 5 2
2 5 1 6 5 2 6 1 1 6 2 5 7 0 4 3 4 3 7 0 6 1 5 2 0 7 3 4 3 4 0 7
24
1 6 2 5 6 1 5 2 2 5 1 6 4 3 7 0 7 0 4 3 5 2 6 1 3 4 0 7 0 7 3 4
4 3 7 0 3 4 0 7 7 0 4 3 1 6 2 5 2 5 1 6 0 7 3 4 6 1 5 2 5 2 6 1
7 4 0 3 4 7 3 0 0 3 7 4215612653 0 4 7 1 2 6 5 2 1 5 6
2 1 5 6 1 2 6 5 5 6 2 1740347306 5 1 2 4 7 3 0 7 4 0 3
25
1 2 6 5 2 1 5 6 6 5 1 2473074035 6 2 1 7 4 0 3 4 7 3 0
4 7 3 0 7 4 0 3 3 0 4 7126521560 3 7 4 2 1 5 6 1 2 6 5
7 2 4 1 2 7 1 4 4 1 7 2 0 5 3 614271 4 2 7 5 0 6 3 4 1 7 2
0 5 3 6 5 0 6 3 3 6 0 5 7 2 4 163506 3 5 0 2 7 1 4 3 6 0 5
26
1 4 2 7 4 1 7 2 2 7 1 4 6 3 5 072417 2 4 1 3 6 0 5 2 7 1 4
6 3 5 0 3 6 0 5 5 0 6 3 1 4 2 705360 5 3 6 4 1 7 2 5 0 6 3
7 1 2 4 1 7 4 2 2 47142170 6 5 3 4 2 1 7 2 4 7 1 6 0 3 5
4 2 1 7 2 4 7 1 1 74271243 5 6 0 7 1 2 4 1 7 4 2 5 3 0 6
27
0 6 5 3 6 0 3 5 5 30635607 1 2 4 3 5 6 0 5 3 0 6 1 7 4 2
3 5 6 0 5 3 0 6 6 03506534 2 1 7 0 6 5 3 6 0 3 5 2 4 7 1
7 0 2 5 0 7 5 2 2 5 7 0 4 3 1 6 1 6 4 3 5 2 0 7 3 4 6 1 6 1 3 4
4 3 1 6 3 4 6 1 1 6 4 3 7 0 2 5 2 5 7 0 6 1 3 4 0 7 5 2 5 2 0 7
28
1 6 4 3 6 1 3 4 4 3 1 6 2 5 7 0 7 0 2 5 3 4 6 1 5 2 0 7 0 7 5 2
2 5 7 0 5 2 0 7 7 0 2 5 1 6 4 3 4 3 1 6 0 7 5 2 6 1 3 4 3 4 6 1
7 4 2 1 4 7 1 2 2 1 7 4 0 3 5 6 1 2 4 712470 3 5 6 1 2 4 7
0 3 5 6 3 0 6 5 5 6 0 3 7 4 2 1 6 5 3 065307 4 2 1 6 5 3 0
29
1 2 4 7 2 1 7 4 4 7 1 2 6 5 3 0 7 4 2 174216 5 3 0 7 4 2 1
6 5 3 0 5 6 0 3 3 0 6 5 1 2 4 7 0 3 5 603561 2 4 7 0 3 5 6
7 2 0 5 2 7 5 0 0 5 7 2413614635 0 2 7 1 4 6 3 4 1 3 6
4 1 3 6 1 4 6 3 3 6 4 1720527506 3 1 4 2 7 5 0 7 2 0 5
30
1 4 6 3 4 1 3 6 6 3 1 4275072053 6 4 1 7 2 0 5 2 7 5 0
2 7 5 0 7 2 0 5 5 0 2 7146341360 5 7 2 4 1 3 6 1 4 6 3
7 1 4 2 1 7 2 4 4 27124170 6 3 5 2 4 1 7 4 2 7 1 6 0 5 3
2 4 1 7 4 2 7 1 1 72471425 3 6 0 7 1 4 2 1 7 2 4 3 5 0 6
31
0 6 3 5 6 0 5 3 3 50653607 1 4 2 5 3 6 0 3 5 0 6 7 1 4 2
5 3 6 0 3 5 0 6 6 05306352 4 1 7 0 6 3 5 6 0 5 3 2 4 1 7
7 0 1 6 0 7 6 1 1 6 7 0 2 5 4 3 4 3 2 5 6 1 0 7 5 2 3 4 3 4 5 2
2 5 4 3 5 2 3 4 4 3 2 5 7 0 1 6 1 6 7 0 3 4 5 2 0 7 6 1 6 1 0 7
32
4 3 2 5 3 4 5 2 2 5 4 3 1 6 7 0 7 0 1 6 5 2 3 4 6 1 0 7 0 7 6 1
1 6 7 0 6 1 0 7 7 0 1 6 4 3 2 5 2 5 4 3 0 7 6 1 3 4 5 2 5 2 3 4
7 4 1 2 4 7 2 1 1 27421470 3 6 5 2 1 4 7 1 2 7 4 3 0 5 6
2 1 4 7 1 2 7 4 4 72174125 6 3 0 7 4 1 2 4 7 2 1 6 5 0 3
33
0 3 6 5 3 0 5 6 6 50356307 4 1 2 5 6 3 0 6 5 0 3 7 4 1 2
5 6 3 0 6 5 0 3 3 05603652 1 4 7 0 3 6 5 3 0 5 6 2 1 4 7
7 2 1 4 2 7 4 1 1 4 7 2 0 5 6 341274 1 2 7 5 0 3 6 1 4 7 2
0 5 6 3 5 0 3 6 6 3 0 5 7 2 1 436503 6 5 0 2 7 4 1 6 3 0 5
34
4 1 2 7 1 4 7 2 2 7 4 1 3 6 5 072147 2 1 4 6 3 0 5 2 7 4 1
3 6 5 0 6 3 0 5 5 0 3 6 4 1 2 705630 5 6 3 1 4 7 2 5 0 3 6
7 1 0 6 1 7 6 0 0 6 7 1423524536 0 1 7 2 4 5 3 4 2 3 5
4 2 3 5 2 4 5 3 3 5 4 2710617605 3 2 4 1 7 6 0 7 1 0 6
35
2 4 5 3 4 2 3 5 5 3 2 4176071063 5 4 2 7 1 0 6 1 7 6 0
1 7 6 0 7 1 0 6 6 0 1 7245342350 6 7 1 4 2 3 5 2 4 5 3
Примеры синтеза комбинационных схем
225
Окончание табл. 4.2.2
0
1
2
3
4
5
6
7
7 0 4 3 0 7 3 4 4 3 7 0 1 6 2 5 2 5 1 6 3 4 0 7 6 1 5 2 5 2 6 1
1 6 2 5 6 1 5 2 2 5 1 6 7 0 4 3 4 3 7 0 5 2 6 1 0 7 3 4 3 4 0 7
36
2 5 1 6 5 2 6 1 1 6 2 5 4 3 7 0 7 0 4 3 6 1 5 2 3 4 0 7 0 7 3 4
4 3 7 0 3 4 0 7 7 0 4 3 2 5 1 6 1 6 2 5 0 7 3 4 5 2 6 1 6 1 5 2
7 4 0 3 4 7 3 0 0 3 7 4126521563 0 4 7 2 1 5 6 1 2 6 5
1 2 6 5 2 1 5 6 6 5 1 2740347305 6 2 1 4 7 3 0 7 4 0 3
37
2 1 5 6 1 2 6 5 5 6 2 1473074036 5 1 2 7 4 0 3 4 7 3 0
4 7 3 0 7 4 0 3 3 0 4 7215612650 3 7 4 1 2 6 5 2 1 5 6
7 2 4 1 2 7 1 4 4 17214270 5 3 6 1 4 2 7 4 1 7 2 5 0 6 3
1 4 2 7 4 1 7 2 2 71472416 3 5 0 7 2 4 1 2 7 1 4 3 6 0 5
38
0 5 3 6 5 0 6 3 3 60563507 2 4 1 6 3 5 0 3 6 0 5 2 7 1 4
6 3 5 0 3 6 0 5 5 06305361 4 2 7 0 5 3 6 5 0 6 3 4 1 7 2
7 1 2 4 1 7 4 2 2 4 7 1 0 6 5 3 4 2 1 742172 4 7 1 6 0 3 5
0 6 5 3 6 0 3 5 5 3 0 6 7 1 2 4 3 5 6 035605 3 0 6 1 7 4 2
39
4 2 1 7 2 4 7 1 1 7 4 2 3 5 6 0 7 1 2 471241 7 4 2 5 3 0 6
3 5 6 0 5 3 0 6 6 0 3 5 4 2 1 7 0 6 5 306536 0 3 5 2 4 7 1
7 0 2 5 0 7 5 2 2 5 7 0 1 6 4 3 4 3 1 6 5 2 0 7 6 1 3 4 3 4 6 1
1 6 4 3 6 1 3 4 4 3 1 6 7 0 2 5 2 5 7 0 3 4 6 1 0 7 5 2 5 2 0 7
40
4 3 1 6 3 4 6 1 1 6 4 3 2 5 7 0 7 0 2 5 6 1 3 4 5 2 0 7 0 7 5 2
2 5 7 0 5 2 0 7 7 0 2 5 4 3 1 6 1 6 4 3 0 7 5 2 3 4 6 1 6 1 3 4
7 4 2 1 4 7 1 2 2 17412470 3 5 6 1 2 4 7 2 1 7 4 3 0 6 5
1 2 4 7 2 1 7 4 4 71274216 5 3 0 7 4 2 1 4 7 1 2 5 6 0 3
41
0 3 5 6 3 0 6 5 5 60365307 4 2 1 6 5 3 0 5 6 0 3 4 7 1 2
6 5 3 0 5 6 0 3 3 06503561 2 4 7 0 3 5 6 3 0 6 5 2 1 7 4
7 2 0 5 2 7 5 0 0 5 7 2146341365 0 2 7 4 1 3 6 1 4 6 3
1 4 6 3 4 1 3 6 6 3 1 4720527503 6 4 1 2 7 5 0 7 2 0 5
42
4 1 3 6 1 4 6 3 3 6 4 1275072056 3 1 4 7 2 0 5 2 7 5 0
2 7 5 0 7 2 0 5 5 0 2 7413614630 5 7 2 1 4 6 3 4 1 3 6
7 1 4 2 1 7 2 4 4 2 7 1 0 6 3 524172 4 1 7 6 0 5 3 4 2 7 1
0 6 3 5 6 0 5 3 3 5 0 6 7 1 4 253605 3 6 0 1 7 2 4 3 5 0 6
43
2 4 1 7 4 2 7 1 1 7 2 4 5 3 6 071427 1 4 2 3 5 0 6 1 7 2 4
5 3 6 0 3 5 0 6 6 0 5 3 2 4 1 706350 6 3 5 4 2 7 1 6 0 5 3
7 0 1 6 0 7 6 1 1 6 7 0 4 3 2 5 2 5 4 3 6 1 0 7 3 4 5 2 5 2 3 4
4 3 2 5 3 4 5 2 2 5 4 3 7 0 1 6 1 6 7 0 5 2 3 4 0 7 6 1 6 1 0 7
44
2 5 4 3 5 2 3 4 4 3 2 5 1 6 7 0 7 0 1 6 3 4 5 2 6 1 0 7 0 7 6 1
1 6 7 0 6 1 0 7 7 0 1 6 2 5 4 3 4 3 2 5 0 7 6 1 5 2 3 4 3 4 5 2
7 4 1 2 4 7 2 1 1 2 7 4 0 3 6 521472 1 4 7 3 0 5 6 1 2 7 4
0 3 6 5 3 0 5 6 6 5 0 3 7 4 1 256305 6 3 0 4 7 2 1 6 5 0 3
45
2 1 4 7 1 2 7 4 4 7 2 1 5 6 3 074127 4 1 2 6 5 0 3 4 7 2 1
5 6 3 0 6 5 0 3 3 0 5 6 2 1 4 703650 3 6 5 1 2 7 4 3 0 5 6
7 2 1 4 2 7 4 1 1 47241270 5 6 3 4 1 2 7 1 4 7 2 5 0 3 6
4 1 2 7 1 4 7 2 2 74172143 6 5 0 7 2 1 4 2 7 4 1 6 3 0 5
46
0 5 6 3 5 0 3 6 6 30536507 2 1 4 3 6 5 0 6 3 0 5 2 7 4 1
3 6 5 0 6 3 0 5 5 03605634 1 2 7 0 5 6 3 5 0 3 6 1 4 7 2
7 1 0 6 1 7 6 0 0 6 7 1245342356 0 1 7 4 2 3 5 2 4 5 3
2 4 5 3 4 2 3 5 5 3 2 4710617603 5 4 2 1 7 6 0 7 1 0 6
47
4 2 3 5 2 4 5 3 3 5 4 2176071065 3 2 4 7 1 0 6 1 7 6 0
1 7 6 0 7 1 0 6 6 0 1 7423524530 6 7 1 2 4 5 3 4 2 3 5
Обратимся, например, к коду с координатами 15, 0 табл. 4.2.1, 4.2.2 и
представим геометрические образы исправленных разрядов a′
1
– a′
4
этого кода
в четырехмерном пространстве координат a
1
– a
4
.
Глава 4
226
0 6 5 3 6 0 3 5 5 3 0 6 7 1 2 4 3 5 6 0
7 1 2 4 1 7 4 2 2 4 7 1 0 6 5 3 4 2 1 7
3 5 6 0 5 3 0 6 6 0 3 5 4 2 1 7 0 6 5 3
Коор-
динаты
кода
15,0
4 2 1 7
a′
1
2 4 7 1
a′
2
1 7 4 2
a′
3
3 5 6 0
a′
4
7 1 2 4
.
В ячейках этого пространства записаны эквивалентные цифровые сигналы
0
x
– 7
x
контрольных разрядов x
1
– x
3
систематического кода AX и инверсии этих
цифр 0
x
– 7
x
.
Учитывая, что в представленных зависимостях значения цифровых мно-
жеств в клетках пространства подчиняются простым соотношениям i ⊃ j (i ≠ j),
логические выражения для исправленных информационных разрядов этого
кода могут быть записаны в двухуровневом исполнении следующим образом:
a′
1
= 6
x
a
3
a
4
a
2
∨ 3
x
a
3
a
4
a
2
∨ 0
x
a
3
a
4
a
1
a
2
∨ 5
x
a
3
a
4
a
1
a
2
∨
∨ 1
x
a
3
a
4
a
2
∨ 4
x
a
3
a
4
a
2
∨ 7
x
a
3
a
4
a
1
a
2
∨ 2
x
a
3
a
4
a
1
a
2
∨
∨ 5
x
a
3
a
4
a
2
∨ 0
x
a
3
a
4
a
2
∨ 3
x
a
3
a
4
a
1
a
2
∨ 6
x
a
3
a
4
a
1
a
2
∨
∨ 2
x
a
3
a
4
a
2
∨ 7
x
a
3
a
4
a
2
∨ 4
x
a
3
a
4
a
1
a
2
∨
1
x
a
3
a
4
a
1
a
2
,
a′
2
= 5
x
a
3
a
4
a
1
∨ 3
x
a
3
a
4
a
1
∨ 0
x
a
3
a
4
a
1
a
2
∨ 6
x
a
3
a
4
a
1
a
2
∨
∨ 2
x
a
3
a
4
a
1
∨ 4
x
a
3
a
4
a
1
∨ 7
x
a
3
a
4
a
1
a
2
∨ 1
x
a
3
a
4
a
1
a
2
∨
∨ 6
x
a
3
a
4
a
1
∨ 0
x
a
3
a
4
a
1
∨ 3
x
a
3
a
4
a
1
a
2
∨
5
x
a
3
a
4
a
1
a
2
∨
∨ 1
x
a
3
a
4
a
1
∨ 7
x
a
3
a
4
a
1
∨ 4
x
a
3
a
4
a
1
a
2
∨
2
x
a
3
a
4
a
1
a
2
,
a′
3
= 7
x
a
4
a
1
a
2
∨ 1
x
a
4
a
1
a
2
∨ 2
x
a
4
a
1
a
2
∨ 4
x
a
4
a
1
a
2
∨
∨ 4
x
a
4
a
1
a
2
∨ 2
x
a
4
a
1
a
2
∨ 1
x
a
4
a
1
a
2
∨ 7
x
a
4
a
1
a
2
∨
∨ 0
x
a
3
a
4
a
1
a
2
∨ 6
x
a
3
a
4
a
1
a
2
∨ 5
x
a
3
a
4
a
1
a
2
∨ 3
x
a
3
a
4
a
1
a
2
∨
∨ 3
x
a
3
a
4
a
1
a
2
∨ 5
x
a
3
a
4
a
1
a
2
∨ 6
x
a
3
a
4
a
1
a
2
∨
0
x
a
3
a
4
a
1
a
2
,
a′
4
= 3
x
a
3
a
1
a
2
∨ 1
x
a
4
a
1
a
2
∨ 2
x
a
4
a
1
a
2
∨ 4
x
a
4
a
1
a
2
∨
∨ 4
x
a
3
a
1
a
2
∨ 2
x
a
4
a
1
a
2
∨ 1
x
a
4
a
1
a
2
∨ 7
x
a
4
a
1
a
2
∨
∨ 0
x
a
3
a
4
a
1
a
2
∨ 6
x
a
3
a
4
a
1
a
2
∨ 5
x
a
3
a
4
a
1
a
2
∨ 3
x
a
3
a
4
a
1
a
2
∨
∨ 7
x
a
3
a
4
a
1
a
2
∨ 1
x
a
3
a
4
a
1
a
2
∨ 2
x
a
3
a
4
a
1
a
2
∨
4
x
a
3
a
4
a
1
a
2
.
Из геометрических образов этих логических функций реализация много-
уровневой схемы вполне очевидна и здесь приводиться не будет.
Аналогичные выражения могут быть получены для всех кодов, представлен-
ных в табл. 4.2.2, но все они при этом различны и даже в пределах одного
кода геометрические образы сигналов информационных разрядов
a′
1
– a′
4
не
могут мысленными поворотами относительно осей симметрии этого простран-
ства быть совмещены, но при этом необходимо отметить, что если исключить
инверсии цифр сигналов контрольных разрядов в геометрических образах сиг-
налов исправленных информационных разрядов a′
1
– a′
4
, то видоизмененные
таким образом геометрические фигуры могут переходить одна в другую мыс-
Примеры синтеза комбинационных схем
227
ленными поворотами относительно осей симметрии пространства, на примере
кода с координатами 15, 0, по следующему алгоритму:
0 6 5 3
7 1 2 4
3 5 6 0
a
1
a
2
a
3
a
4
4 2 1 7
6 0 3 5 5 3 0 6 7 1 2 4 3 5 6 0
1 7 4 2 2 4 7 1 0 6 5 3 4 2 1 7
5 3 0 6 6 0 3 5 4 2 1 7 0 6 5 3
Поворот
a
1
a
2
a
3
a
4
2 4 7 1
Поворот
a
1
a
2
a
3
a
4
1 7 4 2
Поворот
a
1
a
2
a
3
a
4
3 5 6 0
Поворот
a
1
a
2
a
3
a
4
7 1 2 4
.
Из этого геометрического представления непосредственно синтезируется
структурная схема для параллельного исправления всех одиночных ошибок в
информационных разрядах системы счисления основания n = 16 (рис. 4.2.1).
В этой схеме номерами 1 и 2 обозначены элементарные инверторы – соот-
ветственно простой и управляемый, а номером 3 – логический блок, функцио-
нально определяемый таблично-матричной формой представления любого из
a
1
a
2
a
3
a
4
X
1
1
1
1
3
3
3
3
2
2
2
2
a′
1
a′
2
a′
3
a′
4
Рис. 4.2.1
Глава 4
228
кодов табл. 4.2.2, который на примере кода с координатами 15, 0 может быть
записан следующим образом:
В этом выражении вторые составляющие логических произведений явля-
ются цифровыми сигналами контрольной части кода, взятыми из табл. 4.2.2, а
первые составляющие – сигналами информационной части этого систематиче-
ского кода.
Из 192 совершенных кодов табл. 4.2.2 можно выделить 16 суперсовер-
шенных кодов, которые полностью попадают под это определение: в ячейках
многомерного цифрового пространства координат кода располагаются толь-
ко цифровые сигналы определенной одиночной кратности ошибок, а в каж-
дой такой ячейке находится цифра с одной ошибкой этой кратности; много-
мерное цифровое пространство используется для размещения однократных
ошибок на 100 %; исправление ошибок контрольных разрядов кода выполня-
ется логическими схемами, которые исправляют ошибки в информационных
разрядах совершенного кода посредством соответствующего изменения
входных сигналов, осуществляемых мысленными поворотами относительно
осей симметрии этого цифрового пространства. Это коды с координатами
таблицы 15, 0; 15, 3; 3, 0; 3, 3; 10, 0; 10, 3; 22, 0; 22, 3; 15, 4; 39, 5; 3, 4; 27, 3;
10, 4; 34, 4; 22, 4; 46, 3.
Первый из этих кодов был исследован нами выше, где было показано, что
логические схемы, исправляющие ошибки в разрядах информационной части
систематического кода, могут быть использованы также для исправления ана-
логичных ошибок в разрядах его контрольной части. При последовательной
обработке систематического кода, когда первоначально выполняется, напри-
мер, исправление его ошибок в информационной части с последующей переда-
чей исправленных сигналов в регистр памяти, на втором этапе исправления
ошибок эти же логические схемы, при соответствующем изменении сигналов
на их входных шинах, позволяют исправить ошибки в контрольных разрядах с
передачей их исправленных сигналов также в регистр памяти.
В остальных типах совершенных кодов табл. 4.2.2 этого выполнить не уда-
ется: информационные и контрольные разряды систематического кода будут
обрабатываться разными принципиальными логическими схемами.
C =
0
a
0
х
∨
1
a
6
х
∨ 2
a
5
х
∨
3
a
3
х
∨
∨
4
a
7
х
∨
5
a
1
х
∨ 6
a
2
х
∨
7
a
4
х
∨
∨
8
a
3
х
∨
9
a
5
х
∨ 10
a
6
х
∨
11
a
0
х
∨
∨
12
a
4
х
∨
13
a
2
х
∨ 14
a
1
х
∨
15
a
7
х
.
(4.2.1)
Примеры синтеза комбинационных схем
229
Пример 3. Синтез одноразрядного сумматора (A ± B) с исправлением оди-
ночных ошибок в системе счисления основания n = 16
Из теоретических исследований второй главы вытекает, что алгоритм по-
строения геометрического образа одноразрядной арифметической функции для
операций сложения и вычитания весьма прост и даже не требует составления
исходной таблицы результата этой операции в цифровых данных.
Для его построения необходимо иметь только геометрические образы сиг-
налов кода операндов, которые заполняют собой первый столбец или первую
строку двухмерного цифрового пространства посредством размещения в его
ячейках символов, соответствующих логической единице (1* или *). Дальней-
шее заполнение остальных ячеек этого цифрового пространства такими же
символами осуществляется для операции суммирования, рассматривая, напри-
мер, заполнение строк путем сдвига этих строк сверху вниз при одновременном
синхронном смещении символов справа налево, а для операции вычитания
также сдвигом строк сверху вниз, но при смещении этих символов в противо-
положном направлении – слева направо.
При всех этих сдвигах символов предполагается циклическая замкнутость
цифровых значений сигналов разряда операндов, т.е. циклическая замкнутость
символов каждой строки и столбца.
Предыдущий пример устанавливает зависимость между кодовыми комби-
нациями информационной (0 – 15) и контрольной (0–7) частями систематиче-
ского кода всех его типов, исправляющих одиночные ошибки для основания
системы счисления n = 16, и представляет алгоритм получения геометрических
образов исправленных сигналов разрядов a′
1
– a′
4
, покрытие которых определя-
ет функциональную схему декодирующего устройства. Каждый из этих геомет-
рических образов задается двухмерной таблицей, где в информационных ячей-
ках пространства соответственно под номерами 0–15 размещаются прямые и
инверсные значения контрольных кодовых комбинаций под номерами 0–7.
При этом прямые и инверсные значения контрольных кодовых комбина-
ций 0–7 могут рассматриваться нами как геометрические образы логических
функций в координатах разрядов контрольной части систематического кода
либо представляются с позиций многозначной логики, где в качестве логиче-
ских сигналов многозначной логики выступают геометрические образы кон-
трольных кодовых комбинаций систематического кода.
Структурная схема одноразрядного сумматора с исправлением одиночных
ошибок (рис. 4.3.1) может быть реализована путем установки декодирующих
блоков 1, 2 на входных шинах операндов, которые представляются в система-
тическом коде, исправляющем одиночные ошибки операндов AX, BY с после-
дующим выполнением операции суммирования либо вычитания в двух сумма-
торах раздельно для информационной и контрольной частей этого кода. На
выходных шинах этих сумматоров устанавливается аналогичный декодирую-
щий блок 3, исправляющий ошибки операций суммирования, выходной сигнал
которого в систематическом коде с информационной C″(c
1
– c
4
)
и контрольной
Z″(z
1
– z
3
), если она необходима, частями поступают на выходные шины уст-