Кочергин В.И. Теория многомерных цифро-векторных множеств
Подождите немного. Документ загружается.
Глава 3
170
Рис. 3.38
Рис. 3.39
a
4
a
3
a
2
a
1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a
5
0
4
4' 4'
4'
1'
3
3'
0'
2
1
0
a
6
1
4'
3'
2'
1' 0'
2
4'
3'
2'
1' 0'
a
7
3
7'
4
5
5' 5'
5'
5'
2'
1' 0'
5
6
6
6' 6'
6'
6'
7
7
7' 7'
7'
7'
a'
1
a'
2
a'
3
a'
4
a'
5
a'
6
a'
7
Контролеспособность позиционных систем счисления
171
Здесь необходимо отметить, что код одномерных угловых множеств так
же, как многофазный код, имеет замечательное свойство, заключающееся
в том, что в его каждой кодовой комбинации замкнутый ряд сигналов
a
m
a
1
... a
m
a
1
... a
m
содержит два непрерывных множества сигналов: множество
нулей 0* и множество единиц 1*.
Это качество кода позволяет применять весьма простую по технической
реализации процедуру обнаружения и исправления любых типов ошибок: оди-
ночных, двойных и т.д., а также их комбинаций и пачек ошибок подобно тому,
как это выполняется в многофазном коде [2]. При этом следует заметить, что
если в цифровой системе либо отдельном цифровом блоке непрерывно осуще-
ствляется обнаружение с одновременным исправлением одиночных ошибок с
высоким быстродействием, например за два уровня срабатывания одиночного
вентиля, то в такой системе практически невозможно появление ошибок боль-
шей кратности, тем более пачек ошибок. Поскольку здесь будем рассматривать
полностью контролеспособные цифровые системы, то станем в дальнейшем
уделять больше внимания исправлению одиночных ошибок в режиме реального
времени.
3.6. Анализ контролеспособности кода реверсивного
двоичного делителя-счетчика
В реверсивном делителе-счетчике [4], где режим работы определяется по-
рядком следования входных сигналов, имеются на выходных шинах два жестко
связанных между собой кода: двоичный код i разрядности и код Грея разрядно-
сти (i – 1).
Сигналы такого синтезированного кода, предназначенного для представле-
ния сигналов ОЦК основания n = 2
i
, содержат большую избыточность 2
i
(2
i–1
– 1).
Поскольку делитель-счетчик с этим типом кода широко используется в цифро-
вых устройствах электропривода, преобразователях угла, генераторах много-
фазного кода и т.д., целесообразно рассмотреть возможности этого кода по об-
наружению и исправлению различных типов ошибок.
Для основания n = 4 соотношения между сигналами ОЦК 0–3, двоичного
кода a
1
, a
2
и кода Грея q
1
(рис. 3.40) весьма просты. В качестве информацион-
ных сигналов в этом синтезированном коде могут быть
приняты сигналы a
1
, a
2
либо q
1
, a
2
, тогда контрольными
сигналами будут соответственно сигналы q
1
либо a
1
.
Для дальнейшего исследования контролеспособности
кода в данном параграфе примем для любых оснований
систем счисления выполнение информационных сигна-
лов в двоичном коде. Распределение в многомерном
цифровом пространстве сигналов, кодируемых ими
штатных сигналов ОЦК, и их одиночных ошибок приве-
дено на рис. 3.41, из которого очевидна возможность
0 1 2 3
a
1
a
2
q
1
Рис. 3.40
Глава 3
172
только обнаружения этих ошибок. Здесь сигнал безошибочности кода, т.е. сиг-
нал рабочей области пространства, следует из его геометрического образа
(рис. 3.42), а исправления информационных и контрольных сигналов здесь нет.
Для следующего основания n = 8 на рис. 3.43 приведены соотношения ме-
жду сигналами ОЦК 0–7, сигналами двоичного кода a
1
, a
2
, a
3
и сигналами кода
Грея q
1
, q
2
.
В качестве информационных сигналов в этом случае можно принять сле-
дующие группы сигналов: a
1
, a
2
, a
3
; q
1
, q
2
, a
3
; q
1
, a
2
, a
3
, тогда контрольными бу-
дут соответственно следующие сигналы: q
1
, q
2
; a
1
, a
2
; a
1
, q
2
.
Из распределения штатных сигналов ОЦК и их одиночных ошибок в
ячейках многомерного цифрового пространства, которое приведено на
рис. 3.44, видно, что этот код является разновидностью кода Хемминга с рав-
ноценной с ним контролеспособностью. Поэтому геометрический образ сиг-
нала λ полностью совпадает с кодом Хемминга, а информационные и кон-
трольные сигналы с упрощением их за счет ячеек нерабочего пространства
(рис. 3.45) весьма просты:
a
2
a
1
q
1
0
0,1,3 0,2,3
0
0,1,2
1 0
1,2,3
Рис. 3.41
a
2
a
1
q
1
a'
1
a'
3
a'
2
λ
Рис. 3.42
0 1 2 3 4 5 6 7
a
1
a
2
a
3
q
1
q
2
Рис. 3.43
a
3
a
2
a
1
q
1
0
0,103,70,476,7
7
q
2
0,1
1
2,61 61,5
6
6,7
0,432,3
34
4,5 4 3,7
21,5
2
2,3 4,5
5
2,6 5
Рис. 3.44
Контролеспособность позиционных систем счисления
173
a'
1
= a
1
, a'
2
= a
3
q
2
∨ a
3
q
2
, a'
3
= a
3
, q'
1
= q
1
, q'
2
= q
2
.
(3.6.1)
Совпадение кода Хемминга с нашим синтезированным кодом начинается и
заканчивается на основании n = 8.
Для основания n = 16, в котором код Хемминга рационально использует все
многомерное цифровое пространство (λ =1*), код реверсивного делителя-
счетчика не имеет таких возможностей.
Для пояснения этого обратимся к рис. 3.46, где приведены соотношения
между сигналами синтезированного кода a
1
, ... , a
4
, q
1
, q
2
, q
3
и эквивалентными
им сигналами ОЦК 0–15.
a
3
a
2
a
1
q
1
q
2
a'
1
q'
1
a'
2
q'
2
a'
3
λ
Рис. 3.45
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a
1
a
2
a
3
a
4
q
1
q
2
q
3
Рис. 3.46
Глава 3
174
В данном случае в качестве информационных могут быть выбраны следую-
щие группы сигналов: a
1
, ... , a
4
; q
1
, q
2
, q
3
, a
4
; q
1
, a
1
, q
3
, a
4
, а контрольными сигнала-
ми для каждой из групп будут оставшиеся сигналы синтезированного кода.
Распределение штатных сигналов 0–15 и их одиночных ошибок в ячейках
многомерного пространства приведено на рис. 3.47, из которого видно, что
одиночные ошибки могут быть обнаружены, но только часть из них может
быть исправлена. Незаполненные ячейки многомерного пространства опреде-
ляют часть двукратных ошибок, которые могут быть только обнаружены.
Из 128 ячеек многомерного цифрового пространства в 64 ячейках распола-
гаются штатные цифровые сигналы 0–15 и исправленные сигналы 0–15, а ос-
тальные 64 ячейки пространства делят поровну между собой неисправляемые
одиночные и двойные ошибки.
В соответствии с известной из предыдущего рассмотрения методикой ана-
лиза на рис. 3.48 приведены геометрические образы безошибочности кода λ и
всех сигналов упрощенного исправления ошибок
Исходя из известности геометрических образов сигналов синтезированного
кода a'
1
, ... , a'
i
, q'
1
, ... , q'
i – 1
, λ основания n = 2
i
, сформулируем общие правила
построения геометрических образов сигналов для следующего старшего осно-
вания n = 2
i+1
. С этой целью выделим в (2i – 1)-мерном цифровом пространстве,
где расположены геометрические образы сигналов основания n=2
i
, восемь не-
элементарных ячеек. Для геометрического образа каждого из названных выше
сигналов эти ячейки заполняются четырьмя геометрическими фигурами мно-
жеств M
1j
, ... , M
4j
, как это показано на рис. 3.49.
a
4
a
3
a
2
a
1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
q
1 0 0 0,1 0 3 0
7,15 0,8
15 12 15 14,15 15
q
2
1 0,1 1
2 1
1 6,14 1,9 14 14 13 14 14,15
2 0 3 2,3 3 4,12 3 12 3,11 12 12,13 12 15
q
3
3 2 1 2
2,3 5,13 2
13 2,10
12,13 13 14 13
4 0,8 7 4 7 6,7 7 8 8,9 8 11 8 7,15
5 1,9 6 6 5 6
6,7 8,9 9
10 9
9 6,14
6 4 3,11 4 4,5 4 7 8 11 10,11 11 4,12
11
7 5 2,10 4,5 5 6 5 10 9 10 10,11 5,13 10
Рис. 3.47
a'
1
= a
1
, a'
2
= a
1
q
1
∨
a
1
q
1
, a'
3
= a
4
q
3
∨ a
4
q
3
, a'
4
= a
4
, q'
1
= q
1
;
q'
2
= (a
1
q
1
∨ a
1
q
1
) (a
4
q
4
∨ a
4
q
4
) ∨ (a
1
q
1
∨ a
1
q
1
) (a
4
q
3
∨ a
4
q
3
);
q'
3
=q
3
. (3.6.2)
Контролеспособность позиционных систем счисления
175
a
4
a
3
a
2
a
1
q
1
q
2
q
3
a'
1
q'
1
a'
2
q'
2
a'
3
q'
3
a'
4
Рис. 3.48
λ
Глава 3
176
Причем для геометрических образов сигналов a'
i–1
, a'
i
, q'
i–1
многомерное
цифровое пространство может быть разбито и на более крупные четыре ячей-
ки, которые заполняются геометрическими фигурами M
(i–1)
, M
об
(i–1)
, связанные
между собой простыми соотношениями:
M
об
(i–1)
(AQ) = M
(i–1)
(AQ
•
). (3.6.3)
M
(i–1)
M
(i–1)
a'
i–1
M
(i–1)
M
об
(i–1)
a'
i
M
(i–1)
M
об
(i–1)
q'
i–1
M
об
(i–1)
M
(i–1)
M
(i–1)
M
об
(i–1)
λ
a
i
n=2
i
a
i–1
λ
q
i–1
M
1j
M
2j
M
3j
M
4j
a'
j
j=1,...,(i – 1)
M
3j
M
4j
M
1j
M
2j
q'
j
j=1,...,(i–2)
a
i+1
a
i
a
i–1
q
i–1
M
1j
M
2j
∨
M
3
M
2j
M
3j
M
2j
∨
M
3
M
4j
q
i
M
2j
∨
M
3
M
4j
M
3j
M
2j
M
1j
M
2j
∨
M
3
M
3j
M
2j
∨
M
3
M
4j
M
1j
M
2j
∨
M
3
M
2j
M
2j
M
1j
M
2j
∨
M
3
M
2j
∨
M
3
M
4j
M
3j
Рис. 3.50
Рис. 3.49
Контролеспособность позиционных систем счисления
177
Любой геометрический образ сигналов a'
1
, ... , a'
i
, q'
1
, ... , q'
i – 1
, λ основания
n=2
i+1
может быть получен из одноименных сигналов основания n=2
i
по алго-
ритму, представленному в пространстве (2i + 1) , как показано на рис. 3.50.
Причем знание геометрического образа сигнала λ либо a'
i
основания n=2
i+1
определяет непосредственно геометрические образы сигналов a'
i+1
, q'
i
этого ос-
нования аналогично тому, как это показано для основания n=2
i
на рис. 3.49.
Геометрические образы составляющих M
λ
1j
, M
λ
2j
, M
λ
3j
, M
λ
4j
сигнала λ свя-
заны между собой следующими соотношениями:
M
λ
1j
(AQ) = M
λ
4j
(A
•
Q), M
λ
2j
(AQ) = M
λ
3j
(A
•
Q). (3.6.4)
В соответствии с представленным алгоритмом на рис. 3.51 приведен гео-
метрический образ сигнала λ для основания n = 32, который синтезирован не-
посредственно из геометрического образа сигнала рис. 3.48 основания n = 16.
Первообразными для определения геометрических образов исправляемых
сигналов всех последующих оснований систем счисления являются сигналы
основания n = 8, а не n = 4, поскольку в последнем нет возможности для ис-
правления одиночных ошибок.
a
5
a
4
λ
a
3
a
2
a
1
q
1
q
2
q
3
q
4
Рис. 3.51
Глава 3
178
Если же в качестве первообразного принять сигнал λ основания n = 4, то,
синтезируя по предложенному выше алгоритму аналогичные сигналы для ос-
нований n = 8, 16, 32, ... , получаем геометрические образы сигналов λ, вклю-
чающие в себя только штатные сигналы ОЦК этих оснований, в чем можно не-
посредственно убедиться, проведя соответствующий синтез.
Таким образом, код реверсивного двоичного делителя-счетчика при любой
его протяженности обладает возможностью обнаружения и исправления оши-
бок. Структурная схема для обнаружения и исправления ошибок этого кода
приведена на рис. 3.52, где блок 1 выполняет задачу определения рабочей зоны
многомерного цифрового пространства кода, а блок 2 непосредственно исправ-
ляет ошибки, используя процедуру синтеза более простых геометрических об-
разов исправляемых сигналов введением в них клеток нерабочего цифрового
пространства λ.
a
1
. q
1
.
.
1
q
i–1
a
i
λ(2
i
)
2
a'
1
a'
2
q'
i–1
a
i
Рис. 3.52
Для быстродействующего устройства обнаружения и исправления ошибок
блоки 1 и 2 выполняются по логическим функциям в ДНФ, что при значитель-
ной протяженности кода требует больших аппаратурных затрат.
Контролеспособность позиционных систем счисления
179
3.7. Геометрический синтез контролеспособных кодов
позиционных систем счисления
До настоящего времени мы в основном занимались только анализом кон-
тролеспособности известных кодов. Здесь поставим более сложную задачу –
синтез кодов с заданной контролеспособностью, решение которой опирается
на принятую концепцию обнаружения и исправления ошибок как процедуру
поиска аварийного перехода чисел натурального ряда из отведенных им струк-
турой кода ячеек многомерного цифрового пространства в нештатные ячейки
этого пространства. Эта процедура, как показано выше, позволяет обнаружить
все виды и комбинации ошибок, определить наиболее вероятную штатную
ячейку пространства, из которой была получена ошибочная кодовая комбина-
ция информационных и контрольных сигналов.
Структура кода и все его разряды (информационные и контрольные),
составляющие все универсальное цифровое пространство, определяют
штатное λ(0) и нештатное λ(0) многомерные подмножества (фигуры) этого
пространства, где в рабочей части пространства расположены ячейки под-
множеств с одиночными, двойными и т.д. безальтернативными ошибками,
т.е. нештатное подмножество представляет собой, в свою очередь, множе-
ства подмножеств безальтернативных одиночных λ(1), двойных λ(2) и т.д.
ошибок (λ(0) ⊃ λ(1), λ(0) ⊃ λ(2), ...).
В нештатном подмножестве могут располагаться также ячейки с альтерна-
тивными ошибками, которые могут быть только обнаружены, но не исправле-
ны. Это подмножество цифрового пространства является нерабочим, и естест-
венно стремление свести его к нулю. Такие коды с нулевым нерабочим циф-
ровым пространством будем называть полностью контролеспособными для
определенного вида ошибок.
Контролеспособность кода, как это следует из предыдущего, зависит толь-
ко от конфигурации штатной фигуры λ(0) и ее соотношения со всем много-
мерным пространством.
В этом параграфе в основном развивается эвристический подход к рас-
сматриваемой проблеме, что связано со стремлением дать достаточно про-
стые, универсальные и прозрачные методы синтеза, не исключая и более стро-
гих подходов к решению поставленных задач. При этом ограничимся только
двоичным представлением информационной части кода, рассмотрение кото-
рой дает в то же время полную ясность и для любого другого принципа коди-
рования.
Предрасположением к успешному решению задачи синтеза контролеспо-
собных кодов геометрическим способом является геометрически прозрачное
распределение любого типа ошибок кодовых комбинаций на цифровой пря-
мой емкости 2
k
. Эта прозрачность была продемонстрирована на примерах
одиночных ошибок кодовых комбинаций (см. рис. 3.4).