Кочергин В.И. Теория многомерных цифро-векторных множеств
Подождите немного. Документ загружается.
330 Глава 6
табл. 4.9.2, а на рис. 6.1, б – квазисовершенный код (k = 3, i = 3) основания
n = 7, который получен из совершенного кода основания n = 16. Аналогичным
образом формируются квазисовершенный код (k = 3, i = 2) основания n = 4
(см. рис. 6.1, в), а также совершенный код (k = 2, i = 1) основания n = 2
(см. рис. 6.1, г), который является мажоритарным кодом Дж. фон Неймана.
Подобным образом из следующего совершенного кода (k = 4, i = 11) мож-
но получить все квазисовершенные коды, которые при четырех контрольных
разрядах исправляют все одиночные ошибки в обеих частях систематического
кода оснований от 2
10
до 2
5
и т.д.
Поскольку совершенные коды играют значительную роль в системах переда-
чи информации и еще большую в цифровых и логических системах управления,
где кроме исправления ошибок при передаче и хранении информации они могут
успешно использоваться в блоках безошибочной машинной арифметики, необхо-
димо продолжить анализ и синтез таких совершенных и квазисовершенных кодов.
При этом, кроме применения двоичных кодов в информационной части
систематического кода, необходимо рассмотреть использование здесь недвоич-
ных кодов, например многофазных, интегральных, обычных цифровых и т.д. и
не только для исправления всех одиночных ошибок, но и расширения спектра
исправляемых ошибок.
С этой целью первоначально исследуем кодовые расстояния между кодовы-
ми комбинациями основного двоичного кода. Для этого в цифровом пространстве
этих кодовых комбинаций, например для основания n =16, кодовые расстояния
могут представляться как результат операции сложения или вычитания по «моду-
лю 2» операндов A и B и будут изображены соответствующей таблицей. Посколь-
ку операция сложения и вычитания по «модулю 2» одна и та же, то такая таблица,
если прямой и обратный код преобразуются один в другой простым инвертирова-
нием сигналов всех его разрядов, а именно это характерно для основного двоич-
ного кода, будет симметрична относительно главной и побочной диагонали.
На рис. 6.2, а приведена часть такой таблицы, включающая значения ко-
довых расстояний на главной и побочной диагонали, а также значения над эти-
ми диагоналями. Первая строка этой таблицы содержит кодовые расстояния
между первой кодовой комбинацией, которая определяется цифрой 0, и всеми
остальными. Вторая строка – между второй кодовой комбинацией (цифра 1) и
последующими кодовыми комбинациями и т.д. Последняя строка таблицы оп-
ределяет кодовое расстояние между кодовыми комбинациями, соответствую-
щими цифрам 14 и 15.
Вполне очевидно, что данные этой таблицы являются суммой четырех
аналогичных таблиц (рис. 6.2, б – д), которые задают кодовые расстояния меж-
ду сигналами каждого отдельного разряда соответственно a
1
– a
4
. Все эти таб-
лицы имеют одинаковую структуру, которая определяется свойствами основно-
го двоичного кода.
Остановимся на данных кодовых расстояний рис. 6.2, а. Для основания
n = 16 (цифры 0–15) на побочной диагонали таблицы располагаются значения
кодовых расстояний d = 4; для основания n = 8 (цифры 0–7) – значения d = 3;
для основания n = 4 (цифры 0–7) – значения d = 2.
На побочных диагоналях таблиц кодовых расстояний отдельных разрядов
(см. рис. 6.2, б – д) располагаются значения d = 1 и d = 0.
Продолжение геометрического синтеза кодов, исправляющих ошибки
331
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a
4
a
3
a
2
a
1
0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4
0 2 1 2 1 3 2 2 1 3 2 3 2 4
0 1 2 3 1 2 2 3 1 2 3 4
0 3 2 2 1 3 2 2 1 4
0 1 1 2 2 3 3 4
0 2 1 3 2 4
0 1 3 4
0 4
а)
a
1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0
1 0 1 0 1 0 1 0 1 0 1 0 1
0
1 0 1 0 1 0 1 0 1 0 1
0
1 0 1 0 1 0 1 0 1
0
1 0 1 0 1 0 1
0
1 0 1 0 1
0
1 0 1
0
1
б)
a
2
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0
1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 0
1 1 0 0 1 1 0 0 1 1 0 0
0
1 1 0 0 1 1 0 0 1 1 0 0
0
1 1 0 0 1 1 0 0 1 1
0
1 1 0 0 1 1 0 0 1 1
0 0
1 1 0 0 1 1 0 0
0
1 1 0 0 1 1 0 0
в)
a
3
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 0
1 1 1 1 0 0 0 0 1 1 1
0 0
1 1 1 1 0 0 0 0 1 1
0
1 1 1 1 0 0 0 0 1
0 0 0 0
1 1 1 1
0 0 0
1 1 1
0 0
1 1
0
1
г)
Рис. 6.2 (начало)
332 Глава 6
a
4
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0
1 1 1 1 1 1 1
0 0 0 0 0 0
1 1 1 1 1 1
0 0 0 0 0
1 1 1 1 1
0 0 0 0
1 1 1 1
0 0 0
1 1 1
0 0
1 1
0
1
д)
Рис. 6.2 (продолжение)
Сумма кодовых расстояний двух кодовых комбинаций, сумма весовых
значений которых равна (n – 1), определяется значением кодового расстояния
побочной диагонали этих таблиц. Для рис. 6.2, а при n = 16 это d = 4, а для
всех остальных таблиц (рис. 6.2, б – д) кодовое расстояние d = 1.
Все 192 совершенных кода основания n = 2
4
, представленные в табл. 4.2.2,
соответствуют четырем типам таблиц кодовых расстояний между кодовыми
комбинациями цифр 0–15.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
№ 1
a
4
a
3
a
2
a
1
x
3
x
2
(0,0)
x
1
0 4 3 3 3 3 4 4 3 3 4 4 4 4 3 7
0 3 3 3 3 4 4 3 3 4 4 4 4 7
0 4 4 4 3 3 4 4 3 3 3 7
0 4 4 3 3 4 4 3 3 7
0 4 3 3 4 4 3 7
0 3 3 4 4 7
0 4 3 7
d
a,x
0 7
Рис. 6.3
Продолжение геометрического синтеза кодов, исправляющих ошибки
333
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
№ 2
a
4
a
3
a
2
a
1
x
3
x
2
(1,0)
x
1
0 3 4 3 3 4 3 4 3 4 3 4 4 3 4 7
0 3 4 4 3
4
3
4
3
4
33
4
7
0 3 3 4 3
4
3
4
3
4
4
7
0 4 3
4
3
4
3
4
3 7
0 3
4
3
4
3
4
7
0 3
4
3
4
7
03
4
7
d
a,x
0 7
Рис. 6.4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
№ 3
a
4
a
3
a
2
a
1
x
3
x
2
(2,0)
x
1
0 3 3 4 4 3 3 4 3 4 4 3 3 4 4 7
0
4
3 3 4
4
3
4
33
4
4
3 7
0 3 3 4
4
3
4
33
4
4
7
0 4 3 3
4
3
4
4
3 7
0 3 3
4
3
4
4
7
0
4
3
4
3 7
03
4
7
d
a,x
0 7
Рис. 6.5
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
№ 4
a
4
a
3
a
2
a
1
x
3
x
2
(3,0)
x
1
0 3 3 4 3 4 4 3 4 3 3 4 3 4 4 7
0
4
3 4 3 3
4
3
4
4
3
4
3 7
0 3 4 3 3
4
3
4
4
3
4
7
0 3 4
4
3
4
33
4
7
0 3 3
4
3
4
4
7
0
4
3
4
3 7
03
4
7
d
a,x
0 7
Рис. 6.6
334 Глава 6
На рис. 6.3–6.6 приведены эти данные соответственно для кодов
табл. 4.2.2 с координатами (0, 0), (1, 0), (2, 0), (3, 0).
Обозначим эти кодовые комбинации курсивом под номерами № 1, № 2, № 3,
№ 4
и в координатах табл. 4.2.2 разместим под этими номерами соответствую-
щие им системы кодовых расстояний.
Результаты этого отражены в табл. 6.1.
Поскольку сигналы контрольных разрядов здесь, также как сигналы ин-
формационных разрядов кодов, при переводе из прямого кода в обратный пре-
образуются один в другой простым инвертированием сигналов, то сложение
кодовых расстояний двух кодовых комбинаций, сумма весовых значений ин-
формационной части кода которых (n – 1) = 15, будет равно кодовому расстоя-
нию d = 7, находящемуся на побочной диагонали таблиц рис. 6.3–6.6.
Таблица 6.1
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
№ №
0 1 1 1 1 1 1 1 1 24
1 2 2 2 2 2 2 25 2 2
2 3 3 3 3 3 3 26 3 3
3 4 4 4 4 4 4 27 4 4
4 1 1 1 1 1 1 1 1 28
5 3 3 3 3 3 3 29 3 3
6 2 2 2 2 2 2 30 2 2
7 4 4 4 4 4 4 31 4 4
8 1 1 1 1 1 1 1 1 32
9 4 4 4 4 4 4 33 4 4
10 3 3 3 3 3 3 34 3 3
11 2 2 2 2 2 2 35 2 2
12 1 1 1 1 1 1 1 1 36
13 2 2 2 2 2 2 37 2 2
14 4 4 4 4 4 4 38 4 4
15 3 3 3 3 3 3 39 3 3
16 1 1 1 1 1 1 1 1 40
17 4 4 4 4 4 4 41 4 4
18 2 2 2 2 2 2 42 2 2
19 3 3 3 3 3 3 43 3 3
20 1 1 1 1 1 1 1 1 44
21 3 3 3 3 3 3 45 3 3
22 4 4 4 4 4 4 46 4 4
23 2 2 2 2 2 2
47 2 2
Продолжение геометрического синтеза кодов, исправляющих ошибки
335
6.1. Синтез кодов с информационной частью в основном
двоичном коде основания n = 2
4
, исправляющих
одиночные и двойные ошибки
Кодовые комбинации, уже имеющие одиночные ошибки, при повторном
возникновении в них одиночных ошибок будут содержать двойные ошибки
либо могут вернуться в исходное безошибочное состояние. Очевидно, что ис-
правление в этих кодах групп одиночных и двойных ошибок можно выполнить,
если в таблице их кодовых расстояний будет этих значений не менее пяти.
Применение в контрольной части такого систематического кода, например
совершенного кода, исправляющего все одиночные ошибки основания n =2
4
,
которое должно совпадать с основанием информационной части синтезируемо-
го кода, не позволит обеспечить необходимое минимальное кодовое расстоя-
ние. В качестве иллюстрации этого утверждения выберем такой синтезирован-
ный код, где в его контрольной части выбран код из табл. 4.2.2 с координатами
0, 0, и построим таблицу кодовых расстояний этого систематического кода
(рис. 6. 7).
Синтезированный подобным образом код будет иметь информационную
(a
1
– a
4
) и контрольную (x
2
– x
8
) части, а также соответствующие им кодовые
расстояния. Сумма этих кодовых расстояний, определяющая общие кодовые
расстояния систематического кода, содержит значения меньше пяти (d = 4) и,
следовательно, не дает возможности исправлять одновременно все одиночные
и двойные ошибки.
Для того чтобы этот код позволял исправлять все одиночные и двойные
ошибки, необходимо в его контрольную часть добавить еще один разряд – x
1
,
который имеет кодовые расстояния 0–1 (см. рис. 6.7).
Сумма кодовых расстояний (a
1
– a
4
) и (x
1
– x
8
) представляет кодовые рас-
стояния синтезированного совершенного систематического кода, позволяюще-
го исправлять все одиночные и двойные ошибки. Очевидно, что число таких
совершенных кодов основания n =2
4
представляется табл. 4.2.2, которая опре-
деляет контрольную часть этого кода.
Квазисовершенные коды, позволяющие исправлять все одиночные и двой-
ные ошибки меньших оснований систем счисления, просто определяются из
рис. 6.6, где для основания n = 2
3
информационная и контрольная части кода
содержат соответственно разряды
– (a
1
– a
3
), (x
1
– x
7
); для основания n =2
2
это –
(a
1
– a
2
), (x
1
– x
6
); а для основания n =2 происходит превращение кода в совер-
шенный код Дж. Неймана, где общее число разрядов кода равно пяти.
Соотношения весовых значений кодовых комбинаций информационной
(0–15) и контрольной (0, 30, 39, 57, 75, 85, 108, 114, 141, 147, 170, 180, 192, 216,
225, 255) частей совершенного систематического кода позволяют представить
в соответствующем многомерном цифровом пространстве штатные и ошибоч-
ные значения цифр всех этих оснований систем счисления и на их основе по-
строить геометрические образы исправленных разрядов систематического кода.
Глава 6
336
Рис. 6.7
Результаты таких построений для основания системы счисления n =2
4
при-
ведены в табл. 6.1.1, где красным цветом отмечены штатные цифры, черным –
цифры при одиночной ошибке в разрядах систематического кода, а с одиноч-
ными и двойными штрихами – цифры при двойных ошибках в этих разрядах
кода.
и
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 вес
a
4
2
3
a
3
2
2
a
2
2
1
a
1
2
0
x
8
2
7
x
7
2
6
x
6
2
5
x
5
2
4
(0,0)
x
4
2
3
x
3
2
2
x
2
2
1
x
1
2
0
к
0 30 39 57 75 85 108 114 141 147 170 180 198 216 225 255
0 1 1 2 1 2
2
3 1
2
2
3
2
33 4
0
2
1 2 1 3
2
2
13
2
3
2
4
01 2 3 1
2
2
31
2
3
4
0 3 2
2
13
2
2
1
4
0 1 1
2
2
33
4
0
2
13
2
4
013
4
d
a
0
4
a
1
– a
4
0 4 3 3 3 3
4
4
33
4
4
4
4
3 7
0 3 3 3 3
4
4
33
4
4
4
4
7
04 4 4 33
4
4
3337
0 4 4 3 3
4
4
337
0 4 3 3
4
4
3 7
0 3 3
4
4
7
0
4
3 7
d
x
07
x
2
– x
8
0 0 1 1 1 1 0 0 1100001 1
0 1 1 1 1 0 01100001
00 0 0 11001111
0 0 0 1100111
0 0 1 1 0 0 1 1
0 11001
0011
d
x
01
x
1
0 5 5 6 5 6 6 6 666767712
0 6 5 6 5 6 666767612
05 6 6 566766712
0 6 6 65766612
0 5 5 6 6 7 7 12
0 657612
05712
0 12
d
a,x
Продолжение геометрического синтеза кодов, исправляющих ошибки
337
Таблица 6.1.1
Информационная часть кода
Контр.
часть
кода
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 0 0 0' 0 0' 0' 0 0' 0' 0'
1 0 0' 0' 0' 0'
2 0 0' 0' 0' 0'
3 0'' 2'' 4'' 9''
4 0 0' 0' 0' 0'
5 0'' 2'' 5'' 8 12''
6 0'' 1'' 2''
7 2' 2 2' 2' 2'
8 0 0' 0' 0' 0'
9 0'' 3'' 4'' 8''
10 0'' 1'' 4'' 10''
11 4' 4 4' 4' 4'
12 0'' 1'' 6'' 8''
13 8' 8 8' 8' 8'
14 1' 1 1' 1' 1'
15 1'' 2'' 4'' 8
16 0 0' 0' 0' 0'
17 0'' 3'' 5'' 9''
18 0'' 1'' 7'' 9''
19 9' 9' 9 9' 9'
20 0'' 1'' 11''
21 5' 5' 5 5' 5'
22 1' 1 1' 1' 1'
23 1'' 2'' 5'' 9''
24 0'' 1'' 3'' 13''
25 3' 3' 3 3' 3'
26 1' 1 1' 1' 1'
27 1'' 3'' 4'' 9''
28 1' 1 1' 1' 1'
29 1'' 3'' 5'' 8''
30 1 1 1' 1 1' 1 1' 1' 1 1' 1'
31 1' 1 1' 1' 1'
32 0 0' 0' 0' 0'
33 0'' 2'' 3'' 14''
34 0'' 2'' 7'' 10''
35 2' 2 2' 2' 2'
36 0'' 2 6'' 11''
37 2' 2 2' 2' 2'
38 2' 2 2' 2' 2'
39 2 2' 2 2 2' 2 2' 2' 2 2' 2'
40 0'' 3'' 6'' 10''
41 3' 3' 3 3' 3'
42 10' 10' 10 10' 10'
43 2'' 3'' 4'' 10''
44 6' 6' 6 6' 6'
45 2'' 3'' 6'' 8''
46 1'' 2'' 6'' 10''
47 2' 2 2' 2' 2'
48 0'' 3'' 7'' 11''
49 3' 3' 3 3' 3'
50 7' 7' 7' 7 7'
51 2'' 3'' 7'' 9''
Глава 6
338
Продолжение табл. 6.1.1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
52 11' 11' 11' 11 11'
53 2'' 3'' 11''
54 1'' 2'' 7'' 11''
55 2' 2 2' 2' 2'
56 3' 3' 3 3' 3'
57 3' 3 3 3 3' 3' 3 3' 3' 3 3'
58 1'' 3'' 7'' 10''
59 3' 3' 3 3' 3'
60 1'' 3'' 6'' 11''
61 3' 3' 3 3' 3'
62 1' 1 1' 1' 1'
63 1'' 2'' 3'' 15''
64 0 0' 0' 0' 0'
65 0'' 4'' 5'' 14''
66 0'' 4'' 7'' 12''
67 4' 4 4' 4' 4'
68 0'' 5'' 6'' 12''
69 5' 5' 5 5' 5'
70 12' 12' 12 12' 12'
71 2'' 4'' 5'' 12''
72 0'' 4'' 6'' 13''
73 4' 4 4' 4' 4'
74 4' 4 4' 4' 4'
75 4 4' 4' 4 4 4 4' 4' 4 4' 4'
76 6' 6' 6 6' 6'
77 4'' 5'' 6'' 8''
78 1'' 4'' 6'' 12''
79 4' 4 4' 4' 4'
80 0'' 5'' 7'' 13''
81 5' 5' 5 5' 5'
82 7' 7' 7' 7 7'
83 4'' 5'' 7'' 9''
84 5' 5' 5 5' 5'
85 5' 5 5' 5 5 5' 5 5' 5' 5 5'
86 1'' 7'' 12''
87 5' 5' 5 5' 5'
88 13' 13' 13' 13 13'
89 3'' 4'' 5'' 13''
90 1'' 4'' 7'' 13''
91 4' 4 4' 4' 4'
92 1'' 5'' 6'' 13''
93 5' 5' 5 5' 5' 13'
94 1 1 1 1 1
95 1'' 4'' 5'' 15''
96 0'' 6'' 7'' 14''
97 14' 14' 14' 14 14'
98 7' 7' 7' 7 7'
99 2'' 4'' 7'' 14''
100 6' 6' 6 6' 6'
101 2'' 5'' 6'' 14''
102 2'' 6'' 7'' 12''
103 2' 2 2' 2' 2'
Продолжение геометрического синтеза кодов, исправляющих ошибки
339
Продолжение табл. 6.1.1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
104 6' 6' 6 6' 6'
105 3'' 4'' 6'' 14''
106 4'' 6'' 7'' 10''
107 4' 4 4' 4' 4'
108 6' 6 6' 6 6' 6 6 6' 6' 6 6'
109 6' 6' 6 6' 6'
110 6' 6' 6 6' 6'
111 2'' 4'' 6'' 15''
112 7' 7' 7' 7 7'
113 3'' 5'' 7'' 14''
114 7' 7' 7 7' 7 7 7 7' 7' 7' 7
115 7' 7' 7' 7 7'
116 6'' 7'' 11''
117 5' 5' 5 5' 5'
118 7' 7' 7' 7 7'
119 2'' 7'' 15''
120 3'' 6'' 7'' 13''
121 3' 3' 3 3' 3'
122 7' 7' 7' 7 7'
123 3'' 4'' 7'' 15''
124 6' 6' 6 6' 6'
125 3'' 5'' 6''
126 1'' 6'' 7 15''
127 15' 15' 15' 15' 15
128 0 0' 0' 0' 0'
129 0'' 8'' 9'' 14''
130 0'' 9'' 10'' 12''
131 9' 9' 9 9' 9'
132 0'' 8'' 11'' 12''
133 8' 8 8' 8' 8'
134 12' 12' 12 12' 12'
135 2'' 8'' 9'' 12''
136 0'' 8'' 10'' 13''
137 8' 8 8' 8' 8'
138 10' 10' 10 10' 10'
139 4'' 8'' 9'' 10''
140 8' 8 8' 8' 8'
141 8 8' 8' 8' 8 8 8 8' 8 8' 8'
142 1'' 8'' 10'' 12''
143 8' 8 8' 8' 8'
144 0'' 9'' 11'' 13''
145 9' 9' 9 9' 9'
146 9' 9' 9 9' 9'
147 9' 9 9' 9' 9 9 9' 9 9' 9 9'
148 11' 11' 11' 11 11'
149 8'' 9'' 11''
150 1'' 9'' 11'' 12''
151 9' 9' 9 9' 9'
152 13' 13' 13' 13 13'
153 3'' 8'' 9'' 13''
154 1'' 9'' 10'' 13''
155 9' 9' 9 9' 9'