авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 9 |

«ФЕДЕРАЛЬНОЕ КОСМИЧЕСКОЕ АГЕНТСТВО Федеральное государственное унитарное предприятие "Научно-производственный центр "Полюс" В.И. Кочергин ТЕОРИЯ ...»

-- [ Страница 4 ] --

Е с л и избыточность кода заранее определена, то необходимым и достаточ¬ н ы м условием обнаружения всех о ш и б о к определенного типа является невоз¬ можность перевода одного штатного положения в другое при этом типе оши¬ бок, а условием исправления ошибок - отсутствие перекрытия геометрических образов кодовых комбинаций соответствующего типа ошибок различных штат¬ ных кодовых комбинаций.

a a a a1 0 a •—Ы -J—• 1 f 1 a •} •\ б) a J—• ¬ 4 • *— 1 1 0 0 4 i—• 4 1 1 0 1 1 * — * — • в) № I 0 |1 |2 |3 |4 |5 |б| а) Рис. 3. Для пояснения этого обратимся к рис. 3.3, а, где для трехразрядного кода, задающего восемь позиций, показаны переходы каждой из позиций в новые о ш и б о ч н ы е при воздействии, например, одиночных ошибок.

П р и кодировании основания системы счисления n = 2 необходимым и дос¬ таточным условием обнаружения одиночных о ш и б о к является расположение, например, ц и ф р ы 0 на первой позиции, а цифры 1 - на четвертой позиции, т.е.

использование двух разрядов, когда одиночные о ш и б к и будут переводить ко¬ довые комбинации для цифр 0 и 1 в перекрывающиеся кодовые комбинации на второй и четвертой позиции (см. рис. 3.3, б).

Н е о б х о д и м ы м и достаточным условием исправления одиночных о ш и б о к для этого основания является расположение ц и ф р ы 0 на первой позиции, а ц и ф р ы 1 - на восьмой позиции, т. е. необходимо использование трех разрядов, когда одиночные ошибки будут переводить кодовую комбинацию ц и ф р ы 0 во вторую, третью и пятую позиции, а цифру 1 - в седьмую, шестую и четвертую позиции (см. рис. 3.3, в ).

Аналогично могут быть синтезированы коды, о б н а р у ж и в а ю щ и е и исправ¬ л я ю щ и е любой т и п о ш и б о к либо их комбинацию, но такой метод синтеза весь¬ ма трудоемок и не обладает необходимой «прозрачностью».

Наиболее наглядно и менее трудоемко применение для анализа и синтеза корректирующих кодов метода многомерных цифровых множеств.

Перед изложением этого метода для решения вопросов контролеспособно сти позиционных систем счисления введем обозначение штатных кодовых ком¬ бинаций сигналами обычного цифрового кода, т. е. цифрами, а кодовые комби¬ нации, появляющиеся от о ш и б о к кратности k, - этими ж е цифрами с индексом k k. Например, 0 - штатная кодовая комбинация, соответствующая цифре 0, 0 кодовая комбинация, возникающая из штатной в результате ошибки кратности k. В дальнейшем будем пользоваться терминами соответствия «цифре i» и «цифре i кратности k», подразумевая изложенное выше.

Определение о ш и б о ч н ы х кодовых комбинаций соответствующей кратности с п о м о щ ь ю средств вычислительной техники весьма просто, но их графическое представление обладает большей наглядностью и удобством использования для дальнейшего изложения. Это представление изображено на рис. 3.4, где для ошибки кратности один представлены для каждой позиции (черная заливка) их новые о ш и б о ч н ы е положения (светлая заливка).

a a a a2 ~ ~ ~ ~ ~ ~ ~ ~ a 012345678 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Рис. 3. П р о в е д е н н ы е исследования позволяют дать положительный ответ на по¬ ставленные вопросы. Таким образом, задача обнаружения и исправления оши¬ бок без наложения ограничения на число использованных разрядов сводится к обнаружению и исправлению о ш и б о к каждого разряда.

аз а ai с/с!

а 2 о а 2 о 2 i 1 2 i Рис. 3. Таким образом, нетрудно представить в двухмерном измерении «площади», определяющие одновременное исправление одиночных и двойных (рис. 3.5), а также одиночных, двойных и тройных о ш и б о к (рис. 3.6) и т.д.

а аз аг а 1 1 2 1 2 2 3 1 2 2 3 2 3 о о о о о о о о о о о ооо 13 13 о 13 1 2 2 3 2 3 3 2 3 3 о о о о о о о о о о 3 13 о Т3~ 1 2 2 3 2 3 3 2 3 3 о о о о о о о о о о 12 12 1 12 12 2 3 3 3 3 3 3 3 3 3 о о о 1 о 1 1 о 1 13 13 о 13 1 2 2 3 2 3 3 2 3 3 о о о о о о о о о о 12 12 1 12 12 2 3 3 3 3 3 3 3 3 3 о о о 1 о 1 1 о 1 12 12 1 ~72~ Г2~ 2 3 3 3 3 3 3 3 3 3 о о о 1 о 1 1 о 1 11 11 1 11 3 3 3 2 3 2 2 3 2 2 о 1 1 1 1 1 1 1 1 1 Рис. 3. Для получения логического выражения, определяющего одновременное ис¬ правление одиночных и двойных ошибок, обратимся к рис. 3.5. Представим цифровые подмножества, составляющие геометрический образ логической функции с исправлением этих ошибок для цифры 1, в координатах а1, а2, а4.

Число этих подмножеств равно трем:

a a a a M v a2a4 v a1 a4, M1= i a a a, 124 "l a a a (3.1.3) a a1 v a2 v a4.

M = a Учитывая, что M з M з M, эти цифровые подмножества могут быть 3 2 изображены в координатах a,a и соответственно записаны с л е д у ю щ и м об¬ 3 разом:

a a a 3 3 as as M I I M1(a3 a ) M1(a3 v a ) I (3.1.4) И з (3.1.3), (3.1.4) непосредственно следует логическое выражение для опре¬ деления сигнала ц и ф р ы 1, где исправляются все одиночные и двойные ошибки 1= a4 v a3 v a2a4a3v a1a4 a3 v a1a2 asv a2a4asv a1a4 as v a3as a3asa2v a3as a4.

(3.1.5) А н а л о г и ч н ы м образом одновременное исправление всех одиночных, двой¬ ных и тройных о ш и б о к в соответствии с рис. 3.6 будет определяться подмно¬ жествами в координатах a, a, a, которые в свою очередь размещаются в ячей¬ 1 2 ках пространства с координатами a3, a4, a6, a7.

a a a a aa v a a v aa, M = M1= a a a, 125 1 2 2 s 1 s as a a a a a1 v a2 v as, M = M = (3.1.6) as as Учитывая, что M з M з M з M, э т и цифровые подмножества могут 4 3 2 быть изображены в этих координатах и записаны с л е д у ю щ и м образом:

аз a * ** * ay * ** *** ** ** a v a v a v a, a a v a a va a va a v aa, *** 3 4 7 4 y 3 4 6 y 3 6 3 y I I **** **** * a3a4a6v a3a4a v a6a a3v аба а4.

а4азаба7, * 7 7 *** (3.1.7) И з (3.1.6), (3.1.7) непосредственно следует вывод логического выражения для определения сигнала ц и ф р ы 1, в котором исправляются все одиночные, д в о й н ы е и т р о й н ы е ошибки:

X a a a a v a a a a v а^а5аб aaaa v aia2a5a v v 1 2 5 4 1 2 4 1 2 5 v aia5a4a7 v a a a a v aaaa aaaa v aia5a3a v v 2 5 7 7 1 2 3 4 2 5 3 aia2a6a7 v aia5a6a7 а2а5аба7 а^а3аб v v v v aia5a3a6 v aaaa v aaaa aaaa v aia5a3a v v v v a a a a 2536 1 2 3 7 2 5 3 7 3 4 6 aaaa aaaa v a6a7a4ai v v v v v a a a a a a a a 6731 3 4 7 1 3 4 7 a a a a v а3а4аба5 aaaa v aaaa v v v v a a a a 6732 6 7 4 2 3 4 7 5 6 7 3 (3.1.8) aaaa v aaaa.

v 6 7 4 5 4 3 6 П р е д с т а в л е н н ы е на рис. 3.3, в, 3.5, 3.6 геометрические образы кодов, с воз¬ м о ж н о с т ь ю исправления о ш и б о к определенной кратности, могут быть названы с у п е р с о в е р ш е н н ы м и д л я основания n = 2. Определение суперсовершенного ко¬ да конкретного основания системы счисления, исходя из геометрического об¬ раза этого кода, состоит из трех компонентов.

Во-первых, в ячейках многомерного цифрового пространства координат ко¬ да д о л ж н ы располагаться только ц и ф р о в ы е сигналы определенной заданной нами кратности ошибок. П р и этом в каждой ячейке м о ж е т располагаться толь¬ ко цифра с одной о ш и б к о й определенной кратности.

Во-вторых, многомерное цифровое пространство д о л ж н о использоваться для размещения о ш и б о к определенных кратностей на 100 процентов.

В-третьих, исправление о ш и б о к контрольных разрядов кода должно выпол¬ няться т а к и м и ж е логическими схемами, которые исправляют о ш и б к и в ин¬ ф о р м а ц и о н н ы х разрядах кода, посредством соответствующего изменения вход¬ н ы х сигналов, которые производятся м ы с л е н н ы м и поворотами относительно осей симметрии этого цифрового пространства.

П р и отсутствии третьего компонента в этом определении совершенного кода такой код будем считать совершенным, а при отсутствии второго и третьего квазисовершенным.

С о в е р ш е н н ы е коды позволяют не только исправлять ошибки, но одновре¬ менно выполняют функцию резервирования логических и цифровых систем управления, где они используются. П о этой причине их значение сложно переоценить.

Следует отметить, что синтез совершенных кодов для больших оснований систем счисления n 2 представляет собой сложную задачу, которая до на¬ стоящего времени была полностью не решена.

Таблица 3.1. 1 2 4 8 16 1 2 4 8 0 0 3 9 17 0 3 9 1 0 3 6 10 18 0 3 6 10 2 1 2 7 11 19 1 2 7 11 3 0 6 12 20 0 6 12 4 1 4 7 13 21 1 4 7 13 5 2 4 7 14 22 2 4 7 14 6 ^ 3 6 23 3 6 7 0 9 10 12 24 0 9 10 12 8 1 8 11 13 2s 1 8 11 13 2s 9 2 8 11 14 26 2 8 11 14 10 ^ ^ 3 9 10 27 3 9 10 11 4 8 13 14 28 4 8 13 14 12 9 12 29 9 12 13 6 10 12 30 6 10 12 14 7 11 13 14 31 7 11 13 14 15 0 17 18 20 24 0 17 18 20 16 1 16 17 19 21 1 16 19 21 2s 2 16 18 19 22 26 2 16 19 22 3 17 18 23 27 3 17 18 23 19 4 16 20 21 22 28 4 16 21 22 17 20 23 29 17 20 23 21 6 18 20 23 30 6 18 20 23 22 7 19 20 22 31 7 19 21 22 23 8 16 24 26 28 8 16 26 9 17 24 27 29 9 17 24 27 25 10 18 24 27 30 10 18 24 27 26 11 19 26 31 11 19 26 27 12 20 24 29 30 12 20 24 29 28 13 21 28 31 13 21 28 29 14 22 26 28 31 14 22 26 28 30 23 27 29 30 23 27 29 31 П р и наличии меньшего количества разрядов, чем рассмотрено выше, для кодирования позиционных систем счисления синтезировать оптимальный код по критерию максимального исправления ошибок весьма сложно, и любое техниче¬ ское решение является компромиссом в ущерб каким-либо штатным состояниям.

Поэтому здесь необходимо идти от простой задачи к более сложному ее ва¬ рианту. Н а ч н е м этот путь с анализа существующих кодов оснований систем счисления, о б л а д а ю щ и х частичной контролеспособностью.

П е р е д началом такого рассмотрения представим аналитическую запись одино ч н ы х ошибок, которая следует из рис. 3.4. Эта запись может быть пред¬ ставлена простой табличной схемой, где безошибочные номера кодовых ком¬ бинаций выделены ж и р н ы м шрифтом, а номера кодовых комбинаций их экви¬ валентов при одиночной о ш и б к е - светлым ш р и ф т о м и м е н ь ш и м размером.

Левая часть табл. 3.1.1 определяет процедуру формирования этих номе¬ ров, а правая часть, которая полностью соответствует ее левой части, но где б е з о ш и б о ч н ы е номера кодовых комбинаций записаны в каждой строке первы¬ ми, наиболее удобна при построении геометрических образов соответствующих логических функций и будет использована нами в дальнейшем. Эту таблицу м о ж н о продолжить и далее, но в этом нет практической необходимости. В са¬ м о м деле, таблица представляет номера ячеек с о д и н о ч н ы м и о ш и б к а м и в одно¬ м е р н о м цифровом пространстве, что возможно представить графически на лис¬ те 11 формата только для n = 5. Н а рис. 3.7, а показано такое одномерное ц и ф ­ ровое пространство для этого случая. Здесь, например, для ц и ф р ы 18 одиноч­ н ы е о ш и б к и в соответствии с табл. 3.1.1 будут располагаться в ячейках с номе­ р а м и 02, 16, 19, 22 и 26.

В эквивалентном исходному цифровому пространству двухмерном простран¬ стве (см. рис. 3.7, б) координат A ( a, а, а, а ), A ( a ) цифра 18, которая здесь яв­ 1 1 2 3 4 5 ляется уже числом, расположена на пересечении координат A - 02, A - 01. 1 а a а а 11 _ _ _ _ _ _ _ _ _ _ 0 1 2 3 4 5 6 7 8 9 1011121314151617181920212223 0 |1 | 2 |3 | 4 |5 |6 |7 |8 | 9 110111112113114115116117 18119120121122123 124125 |26 | 27 | 28 | 29 | 30 | а) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 а 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 б) [I В И 0 1 2 3 a 0 а а5 8 9 10 11 12 13|14|15| | 1, 8| 16 17 18 19 20 21 22 [23 12 a 2 ±Ц] 1 24 25 26 27 28 29 | 30 14 6|7 10| НО в) а3 а 20 21 _2 26 17 24 II 26| 18 19 30 0123 0123 22 0И 0 1 18 0 [й 0 a а4 1 20|21|22 4 | 1, 2 24 | 25 26 8 9 10 1 д) Щ 3 28 29 | 30 12 13 г) а Тогда одиночные о ш и б к и по координате A (строка 02 таблицы) попадают в ячейки по координате A в номера 0, 3, 6, 10, что соответствует ц и ф р а м яче­ ек 16, 19, 22, 26, а по координате A (строка 01 таблицы) - цифре 2. Это полно­ стью совпадает с результатами исходного одномерного пространства.

М о ж н о продолжить рассмотрение: в двухмерном цифровом пространстве координат A ( a, a, a ), A ( a, a ), для этого используется одна 02-я строка таб­ 1 1 2 3 5 4 лицы;

для трехмерного цифрового пространства координат A ( a, a ), A ( a, a ), 1 1 2 2 3 A ( a ) это будут соответственно строки 2, 0, 1;

и, наконец, для эквивалентного 3 пятимерного цифрового пространства координат a, a, a, a, a это будут только 1 2 3 4 две строки 0 и 1 т а б л и ц ы (a - 0, a - 1, a - 0, a - 0, a - 1).

1 2 3 4 Очевидно, что в л ю б о м из этих эквивалентных многомерных ц и ф р о в ы х пространств одиночные ошибки для л ю б о й из цифр одномерного цифрового пространства всегда попадают в номера ячеек, которые определяются одномер¬ н ы м цифровым пространством.

Поскольку координаты числа в многомерном цифровом пространстве яв­ ляются цифрами соответствующих оснований систем счисления, то м о ж н о пе¬ рейти от номеров ячеек в десятичной системе счисления к номерам ячеек в этих с м е ш а н н ы х системах счисления.

Например, в двухмерном цифровом пространстве координат A ( a, a, a ), 1 1 2 A ( a, a ) одиночные ошибки числа 18 десятичной системы счисления представ¬ 5 4 ляются с л е д у ю щ и м образом:

0.2 3.2 2.0 2.3 2.6, а в трехмерном цифровом пространстве координат A ( a, a ), A ( a, a ), A ( a ) 1 1 2 2 3 4 3 координаты одиночных ошибок этого числа определяются диаграммой 0.0.2 1.1.2 1.2.2 1.0.2 1.0.2.

Для пятимерного цифрового пространства диаграмма определения коор¬ динат одиночных ошибок определяется только первой и второй строками табл. 3.1.1, что приведет к следующему преобразованию кодовых комбинаций и соответствующим им ц и ф р о в ы м значениям:

a a a a a 3 5 1 0 0 1 0 = 1 0 0 1 ' = 1 0 0 0 0 = 1 0 1 1 0 = 1 1 0 1 0 = 0 0 0 1 0 = 2.

Для любого числа координат многомерного цифрового пространства при двоичном принципе кодирования их оснований систем счисления алгоритм оп­ ределения координат одиночных ошибок, представленный выше, остается не­ изменным.

Последовательное применение данного алгоритма к координатам много­ мерного цифрового пространства позволяет определить координаты двойных, т р о й н ы х и т. д. ошибок исходного числа л ю б ы х оснований систем счисления.

Например, число 19, которое является одиночной ошибкой для числа 18, при повторной ошибке даст числа, определяемые следующим образом:

a5 a4 a a ai 3 1 10 0 0 1 1 1 1 и т. д.

Н е о б х о д и м о отметить, что наиболее удобно использовать представление одиночных о ш и б о к в системах счисления больших оснований с двоичным принципом их кодирования, в цифрах десятичного кода, как это дано в табл. 3.1.1, поскольку при этом для их записи требуются небольшие размеры геометрических ячеек многомерного цифрового пространства.

П р и определении двойных, тройных и т. д. о ш и б о к данные этой таблицы используются многократно: для двойных ошибок они применяются к каждой одиночной ошибке, для тройных о ш и б о к - к каждой двойной ошибке и т.д.

И м е н н о эти принципы были использованы нами при построении геомет­ рических образов двойных и тройных ошибок, элементарной двоичной (n = 2) системы счисления, представленных на рис. 3.5, 3.6.

В а р и а н т геометрического представления одиночных ошибок, заданных табл. 3.4.1, м о ж н о выполнить, используя трехмерное цифровое пространство координат рис. 3.8, где в вершинах «куба» р а з м е щ е н ы элементарные ячейки пространства, обозначенные кодовыми комбинациями 0-7. Линии, параллель¬ ные осям координат пространства и соединяющие вершины этого «куба», определяют изменения этих комбинаций при ^ ^ / ^ одиночных ошибках в их д в о и ч н ы х разрядах. Например, ко¬ f L довая комбинация 0 при одиночной ошибке может стать V или 2 или 4;

кодовая комбинация 1 при одиночной ошибке может стать 0 или 3 или 5 и т. д. Для четырехмерного цифрового пространства, где ячей¬ f ки нумеруются кодовыми комбинациями 0-15, используется ""2 ^ Рис. 3. понятие «гиперкуба», где мерность пространства более трех.

i / 5 4 J5 4 f f V LV V 1 7—* 14 J J f / f f V f 0 Рис. 3. -36 -" 39 L V f 33 У / 32 ipf34 ?| '60 52 J 62 ?f54 V У f ^8 ?r 4 7 ' LV V f У / Ф •20 21, - 23 L 17 / '16 (18 19 5pr Рис. 3. Н а рис. 3.9 изображен «гиперкуб», составленный из двух «кубов», каждый из которых представляет собой основание системы счисления n = 2 (0-7), а вместе они представляют собой основание системы счисления n = 2 (0-15). Здесь приве¬ дены два эквивалентных варианта изображения этого «гиперкуба».

В первом варианте показаны все связи, определяющие одиночные ошибки, которые переводят одни кодовые комбинации в другие, где натуральные числа представлены двумя разрядами: первый разряд содержит ц и ф р ы (0-7), второй ц и ф р ы 0, 1. Следовательно, первый «куб» представляет цифру 0 второго разря¬ да, а второй куб - цифру 1 этого ж е второго разряда. В с е одноименные элемен¬ тарные ячейки этих «кубов» соединены линиями, о п р е д е л я ю щ и м и переход ко¬ довых комбинаций п р и одиночных ошибках.

В т о р о й вариант представления «гиперкуба» более простой: в н е м номера элементарных ячеек представлены цифрами одного разряда (0-15), а все соеди¬ нения между двумя т р е х м е р н ы м и «кубами» представляются общей ж и р н о й чертой, которая параллельна здесь оси координат x. И м е н н о такой вариант представления «гиперкубов» будет использоваться нами в дальнейшем.

Д а н н ы е табл. 3.1.1 отражаются в половине «гиперкуба» шестимерного пространства рис. 3.10. Этот «гиперкуб» состоит из восьми трехмерных «ку¬ бов», каждый из которых определяется и может задаваться рядом последова¬ тельных натуральных чисел (0-7), (8-15), (16-23), (24-31), (56-63). Ж и р н ы е линии, параллельные осям координат x1, x2, x3, соединяют соответствующие «кубы» и определяют одиночные ошибки, которые переводят натуральные чис¬ ла одного «куба» и л и «гиперкуба» в другие числа одинаковых «кубов» и л и «гиперкубов». Например, все числа «куба» (0-7) при одиночных ошибках мо¬ гут переходить в соответствующие числа внутри этого «куба», а также в числа «кубов» (8-15), (16-23), ( 3 2 - 9) и т.д.

Очевидно, что не пред¬ ставляет какого-либо труда I 64-79 80- изобразить «гиперкуб» л ю б о й мерности, поскольку увели¬ чение мерности «гиперкуба»

+ выполняется простым изо¬ бражением ему подобного, 112- 9 6 - 1 1 соединенного с первым жир¬ ной чертой, параллельной со¬ ответствующей координате трехмерного цифрового про¬ 16- 0- т странства. П р и ч е м в качестве исходного может быть при¬ нят не «куб», а «гиперкуб»

л ю б о й мерности. Например, если в качестве исходного 32-47 48- принять «гиперкуб» мерности четыре (рис. 3.9), определяе¬ м ы й цифрами (0-15), то «ги¬ Рис. 3. перкуб» мерности семь может быть изображен рис. 3.11 и т.д.

3.2. Многофазный код В а ж н о е место в системах электропривода и электропитания занимает мно¬ гофазный код, я в л я ю щ и й с я естественным кодом целого ряда их устройств, где используются многофазные напряжения.

Целесообразно начать анализ с многофазного кода, поскольку этот тип ко¬ да наиболее исследован и для него решена задача обнаружения и исправления о ш и б о к на основе особой физической структуры кода. Эта особенность кода заключается в возможности представления любого штатного состояния как со¬ ставной части двух н е п р е р ы в н ы х множеств: логических нулей и единиц.

Известная процедура обнаружения и исправления о ш и б о к [2] заключается здесь именно в контроле непрерывности этих множеств и восстановлении этой непрерывности при л ю б ы х ее нарушениях. Следовательно, имеется возмож¬ ность сравнить два способа контроля многофазного кода, отмеченные выше.

В качестве примера для рассмотрения выберем пятифазный код (n=10). И з k 2 в о з м о ж н ы х кодовых к о м б и н а ц и й многофазный код использует 2k ш т а т н ы е комбинации, которые для пятифазного кода (k=5) соответствуют десяти сигна¬ л а м обычного цифрового кода (ОЦК) 0-9, а остальные кодовые комбинации яв¬ ляются з а п р е щ е н н ы м и и каждая из них представляется как о ш и б о ч н а я выдача одновременно нескольких сигналов ОЦК.

Последовательно записанные штатные кодовые комбинации, соответст¬ в у ю щ и е ц и ф р а м от 0 до 9, и образуют сигналы пятифазного кода a - a. 1 Связь между сигналами a1 - a5 и эквива л е н т н ы м и и м сигналами О Ц К приведена на a 3.12.

р и с.

a Н а рис. 3.13 приведены все 32 кодовые a комбинации в двухмерном ц и ф р о в о м про a странстве, где, например, по одной координа a те о т л о ж е н ы позиции сигналов первых трех разрядов a, a, a, а по второй - остальных 1 2 0 1 2 3 4 5 6 8 L L L L L L \J L L J двух разрядов a, a. Н а пересечении коорди¬ 4 нат здесь записаны эквивалентные кодовым Рис. 3. к о м б и н а ц и я м сигналы О Ц К - как штатные (выделены цветом), так и ошибочные.

Следует отметить, что эти сигналы соответствуют преобразованиям пяти фазного кода в сигналы О Ц К по алгоритму 0 = a1a5, 1 = a1a2, 2 = a2a3, 3 = a1a4, 4 = a4a5, 5 = a1a5, 6 = a1a2, 7 = a2a3, 8 = a3a4, 9 = a4a и их не следует путать с о ш и б о ч н ы м и сигналами, обозначение которых было приведено выше.

a 1 0,2 1 1, 1 0 1 1 1 0,1,9 2,1, 1 1 1 1,0,2 3,2, a4 1 1 1 0,8 2, 2 2 0,2,4, 1 4, 1 1 1 7 4 1 4,3, 2 6, a 1 7,9 2 2 1,3,5, 1 1 1 1,9 3, 1 1 9 2 1 9,0,8 2 7, 1 8,8 1 7, 1 8 1 1 1 8,7,9 7,6,8 1 1 1 6,5,7 5,4, Рис. 3. В ячейках, которые у ж е заняты сигналами одиночных ошибок, сигналы д в о й н ы х ошибок не приведены.

И з этого представления видно, что только одиночные о ш и б к и и м е ю т воз­ можность исправления (один из пяти) и обнаружения (четыре из пяти). Двой­ н ы е ж е о ш и б к и з а н и м а ю т только две оставшиеся от размещения более вероят¬ ностных сигналов ячейки и не могут быть исправлены.

a a a a' a' I a II a5 a'2 a' a' Рис. 3. В с о о т в е т с т в и и с р и с. 3.14 и з а в и с и м о с т ь ю с и г н а л о в м н о г о ф а з н о г о кода a - a от сигналов О Ц К (см. рис. 3.12) для каждого геометрического образа 1 сигналов a' - a' выберем ту ячейку пространства, которая однозначно включа­ 1 ется в э т и сигналы. Э т а процедура позволяет получить в многомерном про­ странстве (рис. 3.15) пять фигур для сигналов многофазного кода, покрытие ко¬ т о р ы х определяет логическую ф у н к ц и ю блока исправления ошибок.

a a a 0 0 1 2 0 3 0,4, 0 0 1 7 4 0 9 0 9 9 2 8 8 8 5 7 6 Рис. 3. Пропуск исправленных сигналов a' - a' через блок формирования сигна¬ 1 лов О Ц К даст распределение сигналов О Ц К в ячейках пространства, как приве¬ дено на рис. 3.16. Это распределение полностью выполняет функции исправле¬ ния о ш и б о к наибольшей вероятности, а остальные одиночные о ш и б к и исправ¬ ляются стихийно в пользу каких-либо альтернативных вариантов равной веро¬ ятности. П р и ч е м здесь имеются ячейки под номерами 17, 29, 21, где установка сигналов О Ц К произведена не в альтернативном, а в х у д ш е м варианте, чем это предлагается на рис. 3.14.

a a a 2 0 1 2 0 0 2 2 1 7 4 9 7 7 9 9 8 8 8 5 7 Рис. 3. Для исправления этого не совсем удачного размещения сигналов О Ц К м о ж н о заранее принять волевое решение о выборе конкретной цифры в ячейке в соответствии с альтернативами рис. 3.14.

Такое распределение приведено на рис. 3.17, а соответствующие ему гео­ метрические образы сигналов a' - a' - на рис. 3.18. Логические функции, опре¬ 1 д е л я ю щ и е покрытие фигур этих сигналов, более просты, чем покрытие фигур рис. 3.15, а результат исправления предпочтительней.

ai аз а' г:

а а'2 а' а'з Рис. 3. И м е н н о такой подход наиболее прост и эффективен для обеспечения ус­ тойчивости счетчиков многофазного кода.

В блоках м а ш и н н о й арифметики, где выбор каких-либо альтернативных ва­ риантов распределения сигналов О Ц К не допустим, поскольку приводит к ава­ р и й н ы м ситуациям, рабочими р е ж и м а м и являются только штатные состояния кода и те состояния, которые непрерывно исправляются контролирующими устройствами.

Для этого варианта построения блока исправления ошибок в многомерном пространстве заполняются только ячейки штатного состояния и ячейки, где располагаются исправленные кодовые комбинации.

Геометрические образы исправленных сигналов (рис. 3.19) для этого вари¬ анта более сложные для покрытия.

а а аз а' а'1 г:

а а' а' а'з Рис. 3. В этом варианте обязательно необходимо определение бесконтрольной не¬ рабочей области пространства X, появление которой требует остановки вычис¬ лительного процесса, поскольку в этой области пространства сигналы кода не¬ действительны. П р и этом в нерабочую область пространства не д о л ж н ы вхо¬ дить нулевые значения сигналов кода, которые эквивалентны цифре 0.

Известность сигнала X позволяет использовать более простые геометриче­ ские образы сигналов a' - a', ч е м такие ж е сигналы рис. 3.19, например сиг­ 1 налы рис. 3.18.

Определение оптимальных, т. е. более простых для покрытия геометриче¬ ских образов сигналов a' - a', будет сформулировано с л е д у ю щ и м образом:

1 обязательной частью этих оптимальных образов д о л ж н ы быть фигуры, напри¬ мер рис. 3.19, а поиск более простых фигур д о л ж е н производиться добавлением к н и м л ю б ы х ячеек пространства, геометрический образ которого представлен на рис. 3.20.

X a a — a a Рис. 3. Весьма прост по реализации и наиболее эффективен по быстродействию ал¬ горитм исправления ошибок, например, многофазных кодов, в записи Л и б а у Крейга, который основан на контроле и сохранении непрерывности множеств логических нулей и единиц этого типа кодов [2]. Э т и непрерывные множества всегда имеются при последовательной записи прямых и инверсных сигналов этих кодов. П р и этом здесь появляется возможность исправления не только оди¬ ночных, но и двойных, тройных и т. д. ошибок, а также различных пачек таких ошибок. Возможности этого алгоритма возрастают с увеличением числа фаз ко¬ да, но наиболее ценным является исправление именно одиночных ошибок.

В соответствии с этим алгоритмом исправление, например, одиночных о ш и б о к пятифазного кода будет производиться по с л е д у ю щ и м логическим формулам:

a'1 = a 1 a 5 v v a5a2;

a'2 = v a2a3 v a1a3;

a' = a a v a a v a a ;

3 3 2 3 4 2 a' = a a v a a v a a ;

4 4 3 4 5 3 a' = a a v a a v a a. (3.3.1) 5 5 4 5 1 4 аз а а 1 0 1 2 0 3 9 1,5,9, 3 1 7 4 3, 0 8 0,2,4, 9 9 2 6, 7 8 8 5 7 6 Рис. 3. Н а основании (3.3.1) и рис. 3.13 распределение сигналов О Ц К в ячейках мно­ гомерного пространства для этого варианта реализации приведено на рис. 3.21, а геометрические образы исправленных сигналов ( а ' - а' ) - на рис. 3.22.1 а а а а а а' Рис. 3. Несмотря на то, что данный алгоритм не следует альтернативам распреде¬ ления сигналов рис. 3.14, все исправляемые одиночные о ш и б к и о н действи­ тельно исправляет, а п р и наличии сигнала X (рис. 3.20), что требуется п р и лю¬ бых вариантах, здесь действительно аппаратурные затраты м а л ы и осуществля¬ ется полное выполнение функций контроля и исправления ошибок.

3.4. Анализ контролеспособности кодов Хемминга методом многомерных цифровых множеств О д н и м из широко известных в технике передачи информации является код Хемминга, предназначенный, например, для исправления одной ошибки или обнаружения двух и исправления одной ошибки [11].

К о д ы Х е м м и н г а имеют несколько контрольных разрядов, каждый из кото¬ р ы х контролирует по четности (нечетности) свою группу разрядов. Эти группы формируются т а к и м образом, чтобы по данным контрольных разрядов можно было бы с определенной вероятностью указать сбой соответствующего разряда.

С этой целью первый контрольный разряд контролирует по четности либо нечетности все нечетные информационные разряды кода. В нем при передаче информации записывается такая цифра, чтобы число единиц в контролируемых разрядах совместно с этим контрольным разрядом было нечетным (четным).

Е с л и при приеме и проверке кода окажется, что число единиц в нечетных раз¬ рядах и первом контрольном разряде четное (нечетное), то это с определенной вероятностью будет свидетельствовать об ошибке в нечетных разрядах. В про¬ тивном случае имеется ошибка в четных разрядах или ее вообще нет.

Следовательно, сигнал о наличии ошибки в нечетных разрядах является м л а д ш и м разрядом двоичного номера разряда с ошибкой.

В т о р о й контрольный разряд контролирует по четности (нечетности) все разряды кода, которые имеют одинаковые ц и ф р ы во втором разряде своего но¬ мера, третий контрольный разряд - все разряды, и м е ю щ и е одинаковые цифры в третьем разряде своего номера, и т. д.

И с х о д я из изложенного, для определения следующего вероятного номера разряда с о ш и б к о й необходимо сформировать аналогичную функцию от разря¬ дов с номерами 2, 3, 6, 7,... и вторым контрольным разрядом и т.д.

Все это можно наглядно представить в табл. 3.4.1, где обозначены номера информационных разрядов, которые контролируются соответствующими кон¬ т р о л ь н ы м и разрядами.

Таблица 3.4. К о н т р о л ь н ы е разряды И н ф о р м а ц и о н н ы е разряды 1 2 3 4 5 6 7 8 9 110 11 12 13 14 В литературе по теории информации высоко оцениваются возможности ко¬ дов Х е м м и н г а по контролеспособности при приеме и передаче информации, а в публикациях по вычислительной технике эти достоинства кодов Хемминга обесцениваются утверждением о непригодности этих кодов для выполнения операций м а ш и н н о й арифметики [10]. К а к первое, т а к и второе утверждения, далеки от истинных свойств этого кода.

Поскольку метод многомерных цифровых множеств является универсаль­ н ы м инструментом для анализа л ю б ы х типов корректирующих кодов, восполь­ зуемся его достоинствами для исследования кодов Хемминга применительно к выполнению арифметических операций.

В ы б е р е м в качестве первого примера для исследований основание системы счисления n = 8 (a, a, a ), что по табл. 3.4.1 определяет два контрольных разря­ 1 2 да X i, Х2.

В соответствии с алгоритмом Х е м м и н г а представим в многомерном про¬ странстве сигналов a, a, a, x, x штатные сигналы О Ц К 0 - 7, а также их о д ­ 1 2 3 1 нократные ошибочные представления, которые все приведены на рис. 3.23.

аз a ai 4 I 1,3 I 2,3 J 3 T4 I 4,5 I 4,6 I 3 ~ " Xi I 0,2 5 2 "^23" 4,5 5 " 2 5, X ол~~ 1 "~6 й""46~~1 6 ""6/ I 0 "^^~1Г~577~~677 Рис. 3. Достоинством кода является, как это видно из рис. 3.23, оптимальное раз¬ мещение сигналов 0 -7 в ячейках пространства, когда в н и х нет одиночных ошибок. В с е одиночные ошибки кода располагаются в пространстве нештатных состояний. Необходимо отметить, что если число контрольных разрядов обо­ k значить через k, число кодов, эквивалентных коду Хемминга, будет (2 !).

Из рис. 3.23 также очевидна связь между цифрами 0 -7 основания и всеми сигналами кода Хемминга, что для большей наглядности приведено на рис. 3.24.

a a ai 0_ll2l3l4l5]Y[ Xi X Рис. 3. Для того чтобы оценить достоверность предложенной Х е м м и н г о м аналити­ ческой методики исправления ошибок, представим на рис. 3.25 результаты та­ кого исправления в многомерном цифровом пространстве.

аз а ai xi IT 2 2 5 5 2 J Х 161 0 ~0~ 7 ~0~ 7 7 Рис. 3. Сравнивая результаты такого исправления с фактическим расположением одиночных о ш и б о к (см. рис. 3.23), м о ж н о видеть, что все безальтернативные одиночные ошибки действительно исправляются, а в остальных случаях при­ нимается «жесткий» вариант для одной из альтернатив подобно тому, как это выполнялось в одном из вариантов исправления многофазного кода.

Геометрические образы информационных а', а', а' и контрольных x', x ' 1 2 3 1 сигналов такого «исправления», а также образ сигнала достоверного рабочего пространства X, который в методике Хемминга не определяется, приведены на рис. 3.26.

а а а Х' а' I*:

x Х' а' X а'3 ———————— _ ——————— Рис. 3. Очевидно, что для возможности выполнения арифметических операций в кодах Х е м м и н г а знание сигнала X обязательно и его равенство нулю будет оз начать неисправность и невозможность дальнейшего выполнения каких-либо арифметических операций.

Геометрические образы исправленных информационных a' a', a' и контроль­ b 2 ных x ' x' сигналов при этом показаны на рис. 3.27. В эти образы, с целью их уп­ b рощения без потери информации, включены ячейки нерабочего пространства X.

ai a a Xi x a' X a' Рис. 3. Таким образом, представленный вариант кода Х е м м и н г а для кодирования основания n = 8 имеет весьма простую и быстродействующую процедуру ис¬ правления одиночных о ш и б о к и полностью пригоден для выполнения л ю б ы х арифметических операций. Особый интерес представляет код Хемминга, кото¬ р ы й рационально использует все многомерное пространство сигналов, т. е. где все пространство рабочее и всегда X = 1*. Такими кодами в соответствии с табл. 3.4.1 будут те, где общая длина кода информационных и контрольных разрядов равна 3, 7, 15,....

В качестве второго примера рассмотрим именно такой код при кодировании основания n = 16, где имеются четыре информационных разряда a'1,..., a'4 и три контрольных x1, x2, x3.

Распределение в многомерном пространстве штатных сигналов 0-15, а так¬ ж е сигналов одиночных о ш и б о к для этого кода приведено на рис. 3.28, где штатные сигналы выделены.

И з этого представления очевидны зависимости между цифрами 0-15 и всеми сигналами кода, а также все геометрические образы действительно ис¬ правленных сигналов при наличии одной одиночной ошибки как в информаци¬ онных, так и в контрольных разрядах. П е р в ы е зависимости приведены на рис. 3.29, а геометрические образы исправляемых сигналов кода - на рис. 3.30.

Поскольку в этом случае X = 0*, то геометрические образы сигналов не могут подвергаться каким-либо упрощениям.

а а а а 0 0 0 3 0 5 14 7 0 9 14 11 14 13 14 Х ~0~ Т~ 3 4 13 6 3 8 13 10 3 13 13 14 Х ~0~ Т~ Т~ 11 5 5 6 5 8 11 11 11 12 5 14 ~8" ~6" 3 6 5 6 6 8 8 8 11 8 13 6 Х ~0~ ~9~ ~2~ 7 4 7 7 7 9 9 10 9 12 9 14 Т~ Т 0 3 4 4 4 7 10 9 10 10 4 13 10 Т~ 2 2 12 5 2 7 12 9 2 11 12 12 12 1 Т~ 1 4 1 6 15 8 1 10 15 12 15 15 т Рис. 3. Анализ кодов Хемминга показывает, что его процедура исправления оши¬ бок требует б о л ь ш и х аппаратурных затрат и поэтому мало приспособлена для включения в структуру арифметических устройств.

а а а а ~0 ]~1 12 Х.3 Г4 Г51б17181911011111211з114 x x x Рис. 3. Тем не менее в кодах Х е м м и н г а принципиально возможно создание быст­ родействующего логического устройства, например на П Л М, реализующего покрытие всех геометрических образов сигналов a', a', a', a', x', x', x', X.

1 2 3 4 1 2 Следовательно, вопрос об использовании кода Х е м м и н г а в том или ином арифметическом блоке определяется только аппаратурными затратами, исходя из требуемого быстродействия устройства.

В ы п о л н е н и е устройств м а ш и н н о й арифметики с использованием контроле способных кодов, в том числе и кодов Хемминга, находится в стадии развития.

И х систематическое изложение требует большого объема, что будет рассмотре­ но в дальнейшем. Однако остановимся на положениях, которые могут быть по­ л о ж е н ы в основу синтеза таких устройств. Для этого сделаем небольшой экс¬ курс в проблему исправления ошибок в теории связи и ее отличия при построе¬ нии помехоустойчивых цифровых устройств, составляющих предмет нашего анализа.

а аз а ai xi Х2 | Х II — — — — а' x' а'з Х'з а' Рис. 3. Классическое решение задачи помехозащищенности в теории связи [6] за¬ ключается в посылке через линию связи с помехами, кроме информационных сигналов, соответствующим образом сформированных в к о д и р у ю щ е м блоке контрольных сигналов (рис. 3.31, а).

i i i' k Линия связи Декодер k L Кодер k' а) i i F(i) F(i') Декодер k F(k') F(k) б) i i F(i') F(i) Декодер Т k F'(k) •X в) Рис. 3. Н а выходном конце линии связи эти две части кода поступают в декоди¬ р у ю щ и й блок, который исправляет о ш и б к и в обеих частях синтезирующего ко¬ да, где при у с п е ш н о м выполнении этой операции возможно активное использо¬ вание информационной части кода либо дальнейшая совместная ретрансляция сигнала обеих его частей.

Ф о р м а л ь н ы й перенос из теории связи операции исправления о ш и б о к на цифровые устройства, что выполняется практически во всех работах, представ¬ лен на структурной схеме рис. 3.31, б. В ней линия связи предыдущей схемы заменена на соответствующие блоки, реализующие определенные арифметиче¬ ские функционалы над информационной частью кода F(i) и его контрольной частью F(k), а кодирующие и д е к о д и р у ю щ и е блоки сохранены без изменения.

П р и попадании в нерабочую область цифрового пространства декодирующий блок выдает сигнал о невозможности исправления о ш и б о к X и необходимости остановить дальнейшее вычисление.

В описанной в ы ш е структурной схеме задача исправления о ш и б о к в цифро¬ вом устройстве неоправданно усложнена. Без ущерба для решения задачи ис¬ правления о ш и б о к в арифметическом либо логическом блоке устройства коди¬ р у ю щ и й блок и блок выполнения определенной операции над контрольной ча¬ стью кода могут быть заменены одним блоком без промежуточного преобразо¬ вания входной информационной части во входную контрольную часть кода.

К р о м е того, д е к о д и р у ю щ и й блок может быть также упрощен, поскольку нет необходимости иметь на его выходе контрольную часть кода выполняемой операции. Приведенные изменения структурной схемы изображены на рис. 3.31, в. Эта схема и может быть положена в основу синтеза арифметиче¬ ских и логических устройств, где основной задачей является создание нового блока, реализующего функционал F'(k).

3.5. Анализ контролеспособности обычного цифрового кода методом многомерных цифровых множеств Название этого позиционного кода происходит от его повседневного ис­ пользования для основания системы счисления n = 10 в обычной жизни всеми людьми. Напомним, что о б ы ч н ы м цифровым кодом названо позиционное пред¬ ставление цифр счисления основания n 2, где в каждом разряде имеется n по­ з и ц и й с номерами 0, 1,..., (n - 1) и л и ш ь один символ (сигнал), вес которого равен номеру позиции, в которой символ в данный момент расположен. Иногда в литературе этот тип кода называют унитарным, однорядным, кодом с актив¬ н ы м нулем, просто позиционным кодом и т. д.

a 0,1,2,3,4,5,6,7. аз а ai \ 1 0,1 2 0,2 1,2 3 0,3 1,3 2, а 4 0,4 1,4 2,4 3. аб 5 оУ 3. Т5~ а 3. Т6~ 4, 5. а — — 7 о/Г Т7~ 3, 4. 5, 6, Рис. 3. С первых шагов создания вычислительных устройств предпринимались и предпринимаются не очень удачные попытки их выполнения в коде О Ц К [9].

n Причем, учитывая огромную избыточность ОЦК, равную (2 - n ), ряд исследо Для основания n = 8 сигналы О Ц К относительно полюса а весьма п р о с т ы a = 0, a = 0 v l,..., a = 0 v... v 6 (рис. 3.33), а расположение в ячейках мно¬ 1 2 гомерного цифрового пространства штатных сигналов ОЦК, что показано на рис. 3.34, позволяет обнаруживать и исправлять, не останавливая Э В М, не только одиночные ошибки, но также ряд двойных и даже тройных ошибок.

a a a a 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 1 2 1 2 2 3 1 2 2 2 2 3 3 77 7 7 7 7 7 7 7 7 a 1 2 2 3 2 3 2 2 7 7 7 7 7 7 2 a6 |1 2 2 2 1 1 2 2 2 2 1 2 2 1 1 4 4 4 1 0 3 3 0 2 1 | a 1 1 2 1 2 2 1 2 2 2 4 6 6 6 6 6 6 6 6 6 1 2 2 1 2 2 1 1 |5 1 0 3 3 0 2 1 1 1 2 1 2 2 2 1 1 6 55 5 5 5 5 0 0 2 1 1 1 1 1 1 |7 44 4 1 0 33 0 2 l Рис. 3. a a a lI a Рис. 3. Без учета сигналов тройных о ш и б о к область рабочего пространства данного кода представляется фигурой рис. 3.35, а геометрические образы исправленных сигналов a' - a', д о п о л н е н н ы е с целью упрощения ячейками нерабочего про¬ 1 странства, приведены на рис. 3.36.

Е с л и еще более упростить задачу и исправлять, например, только одиноч¬ ные о ш и б к и кода и при этом использовать сигналы относительно полюсов и а, в, то логические блоки определения сигнала X и исправленных сигналов a' - a' 1 будут еще более просты.

1 g а'1 а' а' а' а'3 а' Рис. 3. а' а а а а Этот вариант кодирования сигналов а с основанием n=8 приведен на рис. 3.37, а многомерное пространство с обозначением штатных ячеек и ячеек а пространства с о д и н о ч н ы м и ошибками и геометрические образы сигналов X, 0 1 2 3 4 5 6 а ' 1 - а ' 7 - соответственно на рис. 3.38 и 3.39.

Рис. 3. а а а а 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 3 3' 0' 0 4 4' 4' 4' 1' а5 4' 3' 2' 1' 0' | а 4' 3' 2' 1' 0' 1 7' а 4 5 5' 5' 5' 5' 2' 1' 0' 1 6 6' 6' 6' 6' 1 7 7' 7' 7' 7' | Рис. 3. а'1 а' а'2 а' а'3 а' а' Рис. 3. З д е с ь н е о б х о д и м о о т м е т и т ь, что код о д н о м е р н ы х у г л о в ы х м н о ж е с т в т а к ж е, как м н о г о ф а з н ы й код, и м е е т з а м е ч а т е л ь н о е с в о й с т в о, з а к л ю ч а ю щ е е с я в т о м, что в его к а ж д о й к о д о в о й к о м б и н а ц и и з а м к н у т ы й р я д с и г н а л о в a.m a... am a... содержит два непрерывных множества сигналов: множество 1 нулей 0* и множество единиц 1*.

Это качество кода позволяет применять весьма простую по технической реализации процедуру обнаружения и исправления л ю б ы х типов ошибок: оди¬ ночных, двойных и т. д., а также их комбинаций и пачек о ш и б о к подобно тому, как это выполняется в многофазном коде [2]. П р и этом следует заметить, что если в цифровой системе либо отдельном цифровом блоке непрерывно осуще¬ ствляется обнаружение с одновременным исправлением одиночных о ш и б о к с высоким быстродействием, например за два уровня срабатывания одиночного вентиля, то в такой системе практически невозможно появление о ш и б о к боль¬ ш е й кратности, тем более пачек ошибок. Поскольку здесь будем рассматривать полностью контролеспособные цифровые системы, то станем в дальнейшем уделять больше внимания исправлению одиночных о ш и б о к в р е ж и м е реального времени.

3.6. Анализ контролеспособности кода реверсивного двоичного делителя-счетчика В реверсивном делителе-счетчике [4], где р е ж и м работы определяется по¬ рядком следования входных сигналов, имеются на выходных шинах два жестко связанных между собой кода: двоичный код i разрядности и код Грея разрядно­ сти (i - 1).

Сигналы такого синтезированного кода, предназначенного для представле¬ i i i- ния сигналов О Ц К основания n = 2, содержат большую избыточность 2 ( 2 - 1).

Поскольку делитель-счетчик с э т и м типом кода широко используется в цифро¬ вых устройствах электропривода, преобразователях угла, генераторах много¬ фазного кода и т.д., целесообразно рассмотреть возможности этого кода по об¬ наружению и исправлению различных типов ошибок.

Для основания n = 4 соотношения между сигналами О Ц К 0-3, двоичного кода a, a и кода Грея q (рис. 3.40) весьма просты. В качестве информацион¬ 1 2 ных сигналов в этом синтезированном коде могут быть - приняты сигналы a, a либо q, a, тогда контрольными I 0 " I 1 ~1~2 ~Гз 1 2 1 сигналами будут соответственно сигналы q либо a. ' ' ' ' 1 a Для дальнейшего исследования контролеспособности кода в данном параграфе примем для л ю б ы х оснований a систем счисления выполнение информационных сигна­ лов в двоичном коде. Распределение в многомерном цифровом пространстве сигналов, кодируемых ими Рис. 3. штатных сигналов ОЦК, и их одиночных о ш и б о к приве¬ дено на рис. 3.41, из которого очевидна возможность только обнаружения этих ошибок. Здесь сигнал безошибочности кода, т.е. сиг­ нал рабочей области пространства, следует из его геометрического образа (рис. 3.42), а исправления информационных и контрольных сигналов здесь нет.

a ai a' a' qi I ~~~~ ~~~~ 1 a ai 0,1,3 0,2, 0 0 a'2 X 0,1,2 1,2, 1 Рис. 3. Рис. 3. Для следующего основания n = 8 на рис. 3.43 приведены соотношения ме­ жду сигналами О Ц К 0-7, сигналами двоичного кода a, a, a и сигналами кода 1 2 Грея q q 2.

b Ii Е Г Е Е Е Е 2 3 4 5.0 a a1 a a a a 0 0,1 0 3,7 0,4 7 6,7 q q1 -f 1 6 1, 2,6 6 6, 0, q. q 0,4 3 2,3 4 3, 3 4 4, 2 1,5 2 2,6 2,3 4,5 Рис. 3. Рис. 3. В качестве информационных сигналов в этом случае м о ж н о принять сле­ д у ю щ и е группы сигналов: a, a, a ;

q, q, a ;

q, a, a, тогда контрольными бу­ 1 2 3 1 2 3 1 2 дут соответственно следующие сигналы: q, q ;

a, a ;

a, q. 1 2 1 2 1 И з распределения ш т а т н ы х сигналов О Ц К и их о д и н о ч н ы х о ш и б о к в ячейках м н о г о м е р н о г о цифрового пространства, которое приведено на рис. 3.44, видно, что этот код является р а з н о в и д н о с т ь ю кода Х е м м и н г а с рав­ н о ц е н н о й с н и м контролеспособностью. П о э т о м у геометрический образ сиг­ нала X полностью совпадает с к о д о м Хемминга, а и н ф о р м а ц и о н н ы е и кон¬ т р о л ь н ы е сигналы с у п р о щ е н и е м их за счет ячеек нерабочего пространства (рис. 3.45) весьма просты:

(3.6.1) Совпадение кода Х е м м и н г а с н а ш и м синтезированным кодом начинается и заканчивается на основании n = 8.

а а а q q q' а' II а'2 q' X а' Рис. 3. Для основания n = 16, в котором код Х е м м и н г а рационально использует все многомерное цифровое пространство (X =1*), код реверсивного делителя счетчика не имеет таких возможностей.

Для пояснения этого обратимся к рис. 3.46, где приведены соотношения между сигналами синтезированного кода а1,..., а4, q1, q2, q3 и эквивалентными им сигналами О Ц К 0-15.

_ - — _ 0 11 Ы ~ 14 5 I6I7I8 9 10lnl12l13l14l а а а а q q q Рис. 3. a a a a 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 0 0 3 0 7,15 0,8 15 12 15 14, q1 0, 1 2 1 1 6,14 14 14 13 14, 0,1 1, q 2 0 3 4,12 3 12 3,11 12,13 12 2, 2 2 1 5,13 2 13 2,10 14 2,3 12, q 3.

4 0,8 7 4 7 8 11 6,7 8,9 7, 6 6 6 5 10 9 9 6, 6,7 8, 1, 4 6 4 3,11 4 7 8 4,12 4,5 10, 5 5 2,10 6 5 10 9 5,13 4,5 10, | Рис. 3. В данном случае в качестве информационных могут быть выбраны следую¬ щие группы сигналов: a..., a ;

q q, q, a ;

q a q, a, а контрольными сигнала¬ b 4 b 2 3 4 b b 3 ми для каждой из групп будут оставшиеся сигналы синтезированного кода.

Распределение штатных сигналов 0-15 и их одиночных о ш и б о к в ячейках многомерного пространства приведено на рис. 3.47, из которого видно, что одиночные ошибки могут быть обнаружены, но только часть из них может быть исправлена. Незаполненные ячейки многомерного пространства опреде¬ л я ю т часть двукратных ошибок, которые могут быть только обнаружены.

И з 128 ячеек многомерного цифрового пространства в 64 ячейках распола¬ гаются штатные цифровые сигналы 0-15 и исправленные сигналы 0-15, а ос¬ тальные 64 ячейки пространства делят поровну между собой неисправляемые одиночные и двойные ошибки.

В соответствии с известной из предыдущего рассмотрения методикой ана¬ лиза на рис. 3.48 приведены геометрические образы безошибочности кода X и всех сигналов упрощенного исправления о ш и б о к a a a a q a q a a q a q a a q ;

' 1 = b ' 2 = 1 1 V 1 1, ' 3 = 4 3 V 4 3, ' 4 = 4, Cj'1 = q'2 = ( a 1 q 1 V a q O ( a 4 q 4 V a 4 q 4 ) V ( a ^ 1 V а ш ) ( a 4 q 3 V a 4 q 3 ) ;

(3.6.2) q' =q.

3 И с х о д я из известности геометрических образов сигналов синтезированного кода a',..., a';

, q',..., q';

, X основания n = 2, сформулируем о б щ и е правила 1 1 - построения геометрических образов сигналов для следующего старшего осно¬ 1+ вания n = 2. С этой целью выделим в (2i - 1)-мерном цифровом пространстве, ;

где расположены геометрические образы сигналов основания n=2, восемь не¬ элементарных ячеек. Д л я геометрического образа каждого из названных в ы ш е сигналов э т и ячейки заполняются четырьмя геометрическими фигурами мно¬ жеств M j,..., M j, как это показано на рис. 3.49.

1 a a a a q q q a'1 q' a'2 q' a'3 q' a' X Рис. 3. M (i-D i n= M(i-D a i- ci'i_ X M (i-D j=1,...,(i - 1) My M2j M 3 j M4j q i- об М ( -1) ;

j=1,...,(i-2) M 3 j M4j M y M2j q'j M°V1) M (i_1) q'i- об М ( _1) M (i-D ;

об M (i-l) M (i-D X Рис. 3. П р и ч е м для геометрических образов сигналов a', a', q ' многомерное i-1 i i- цифровое пространство может быть разбито и на более крупные четыре ячей¬ ки, которые заполняются геометрическими фигурами M ( ), M ^ ^ ), связанные i- между собой простыми соотношениями:

M ^ A Q ) = M(i-1)(AQ*). (3.6.3) a i+ ai a i- M2jVM3 M2jVM My M2j M4j M3j q i- 1 M2jVM3 M2jVM My qi M2jVM3 M2jVM My 1 M2jVM3 M2jVM My M2j M4j M3j Рис. 3. Л ю б о й геометрический образ сигналов а '..., a';

, q '..., q';

_ i, X основания ь b 1+1 ;

n=2 может быть получен из одноименных сигналов основания n=2 по алго­ ритму, представленному в пространстве (2i + 1), как показано на рис. 3.50.

;

П р и ч е м знание геометрического образа сигнала X либо а' основания n=2 + ;

определяет непосредственно геометрические образы сигналов а' +, q' этого ос­ 1 1 ;

;

нования аналогично тому, как это показано для основания n=2 на рис. 3.49.

Геометрические образы составляющих M j, M j, M j, M j сигнала X свя­ 1 2 3 заны между собой следующими соотношениями:

X X X X M 1j(AQ) = M 4j(A*Q), M 2j(AQ) = M 3j(A*Q). (3.6.4) В соответствии с представленным алгоритмом на рис. 3.51 приведен гео­ метрический образ сигнала X для основания n = 32, который синтезирован не­ посредственно из геометрического образа сигнала рис. 3.48 основания n = 16.

а a X i a 1 • — Рис. 3. П е р в о о б р а з н ы м и для определения геометрических образов исправляемых сигналов всех последующих оснований систем счисления являются сигналы основания n = 8, а не n = 4, поскольку в последнем нет возможности для ис¬ правления одиночных ошибок.

Е с л и ж е в качестве первообразного принять сигнал X основания n = 4, то, синтезируя по предложенному в ы ш е алгоритму аналогичные сигналы для ос­ нований n = 8, 16, 32,..., получаем геометрические образы сигналов X, вклю­ ч а ю щ и е в себя только штатные сигналы О Ц К этих оснований, в чем можно не¬ посредственно убедиться, проведя соответствующий синтез.


Таким образом, код реверсивного двоичного делителя-счетчика при любой его протяженности обладает возможностью обнаружения и исправления оши¬ бок. Структурная схема для обнаружения и исправления ошибок этого кода приведена на рис. 3.52, где блок J выполняет задачу определения рабочей з о н ы многомерного цифрового пространства кода, а блок 2 непосредственно исправ­ ляет ошибки, используя процедуру синтеза более простых геометрических об¬ разов исправляемых сигналов введением в них клеток нерабочего цифрового пространства X.

ai q i q i-i ai i -X(2 ) a2 a i q'i-i Рис. 3. Для быстродействующего устройства обнаружения и исправления ошибок блоки J и 2 выполняются по логическим функциям в Д Н Ф, что при значитель¬ ной протяженности кода требует б о л ь ш и х аппаратурных затрат.

3.7. Геометрический синтез контролеспособных кодов позиционных систем счисления Д о настоящего времени м ы в о с н о в н о м з а н и м а л и с ь т о л ь к о анализом кон т р о л е с п о с о б н о с т и известных кодов. Здесь поставим более сложную задачу синтез кодов с заданной контролеспособностью, р е ш е н и е к о т о р о й опирается на принятую к о н ц е п ц и ю обнаружения и исправления о ш и б о к как процедуру поиска аварийного перехода чисел натурального ряда из отведенных им струк¬ турой кода ячеек м н о г о м е р н о г о ц и ф р о в о г о пространства в н е ш т а т н ы е ячейки этого пространства. Эта процедура, как показано выше, позволяет обнаружить все виды и к о м б и н а ц и и ошибок, определить наиболее вероятную штатную ячейку пространства, из к о т о р о й была получена о ш и б о ч н а я кодовая комбина¬ ция и н ф о р м а ц и о н н ы х и к о н т р о л ь н ы х сигналов.

С т р у к т у р а к о д а и все его р а з р я д ы ( и н ф о р м а ц и о н н ы е и к о н т р о л ь н ы е ), с о с т а в л я ю щ и е все у н и в е р с а л ь н о е ц и ф р о в о е п р о с т р а н с т в о, о п р е д е л я ю т ш т а т н о е А,(0) и н е ш т а т н о е А,(0) м н о г о м е р н ы е п о д м н о ж е с т в а ( ф и г у р ы ) э т о г о п р о с т р а н с т в а, где в р а б о ч е й ч а с т и п р о с т р а н с т в а р а с п о л о ж е н ы я ч е й к и под¬ м н о ж е с т в с о д и н о ч н ы м и, д в о й н ы м и и т. д. б е з а л ь т е р н а т и в н ы м и о ш и б к а м и, т. е. н е ш т а т н о е п о д м н о ж е с т в о п р е д с т а в л я е т с о б о й, в с в о ю о ч е р е д ь, множе¬ ства п о д м н о ж е с т в б е з а л ь т е р н а т и в н ы х о д и н о ч н ы х д в о й н ы х А,(2) и т.д.

о ш и б о к (Х(0) з Х(0) з Х(2),...).

В н е ш т а т н о м п о д м н о ж е с т в е могут располагаться также ячейки с альтерна¬ т и в н ы м и о ш и б к а м и, к о т о р ы е могут быть т о л ь к о обнаружены, но не исправле¬ ны. Э т о п о д м н о ж е с т в о ц и ф р о в о г о пространства является нерабочим, и естест¬ венно стремление свести его к нулю. Такие коды с нулевым нерабочим циф¬ р о в ы м пространством будем называть п о л н о с т ь ю к о н т р о л е с п о с о б н ы м и для определенного вида ошибок.

К о н т р о л е с п о с о б н о с т ь кода, как это следует из предыдущего, зависит т о л ь ­ ко от конфигурации ш т а т н о й фигуры А,(0) и ее с о о т н о ш е н и я со всем много¬ м е р н ы м пространством.

В э т о м параграфе в о с н о в н о м развивается эвристический подход к рас¬ сматриваемой проблеме, что связано со стремлением дать достаточно про¬ стые, универсальные и прозрачные м е т о д ы синтеза, не исключая и более стро¬ гих подходов к р е ш е н и ю поставленных задач. П р и э т о м ограничимся т о л ь к о д в о и ч н ы м представлением и н ф о р м а ц и о н н о й части кода, рассмотрение кото¬ р о й дает в то ж е время полную ясность и для л ю б о г о другого п р и н ц и п а коди¬ рования.

П р е д р а с п о л о ж е н и е м к у с п е ш н о м у р е ш е н и ю задачи синтеза контролеспо собных кодов геометрическим с п о с о б о м является геометрически прозрачное распределение л ю б о г о типа о ш и б о к к о д о в ы х к о м б и н а ц и й на ц и ф р о в о й пря¬ k м о й емкости 2. Эта прозрачность была п р о д е м о н с т р и р о в а н а на примерах о д и н о ч н ы х о ш и б о к к о д о в ы х к о м б и н а ц и й (см. рис. 3.4).

Обращает на себя в н и м а н и е то, что при с и м м е т р и ч н о м р а с п о л о ж е н и и ш т а т н ы х ячеек относительно центра ц и ф р о в о й п р я м о й совместного д в о и ч н о ­ го представления всех и н ф о р м а ц и о н н ы х и к о н т р о л ь н ы х к о д о в ы х к о м б и н а ц и й также соблюдается строгая симметрия р а с п о л о ж е н и я их ошибок. И з этого сле­ дует правило распределения ш т а т н ы х ячеек для цифр натурального ряда на ц и ф р о в о й прямой, и с к л ю ч а ю щ е е з а п о л н е н и е остальных ячеек пространства несколькими о ш и б к а м и о д и н а к о в о й кратности. Э т о правило свидетельствует не т о л ь к о о необходимости сохранения определенного к о д о в о г о расстояния между ш т а т н ы м и ячейками на ц и ф р о в о й прямой, но и об их обязательном с и м м е т р и ч н о м р а с п о л о ж е н и и относительно центра ц и ф р о в о й прямой.

Н а п р и м е р, если первая штатная ячейка располагается на п о з и ц и и с номе¬ р о м 1, то симметричная ей ячейка д о л ж н а быть р а с п о л о ж е н а на п о з и ц и и с но¬ k м е р о м 2, что для нашего примера - 32. Для исправления, например, одиноч¬ ных о ш и б о к н е о б х о д и м о сохранить определенное кодовое расстояние между ш т а т н ы м и ячейками, и поэтому следующая штатная ячейка д о л ж н а быть в со¬ ответствии с рис. 3.4 р а с п о л о ж е н а на п о з и ц и и с н о м е р о м 8, а симметричная ей ячейка - на п о з и ц и и с н о м е р о м 25 и т.д.

3.7.1. К о д ы с о б н а р у ж е н и е м о д и н о ч н ы х о ш и б о к В п. 3.1 м ы рассмотрели п р и н ц и п ы синтеза к о н т р о л е с п о с о б н о г о кода ос­ нования n= 2. Сейчас поставим задачу распространить этот подход на системы счисления б о л ь ш е г о основания, предполагая, что построение фигур Х(0) боль¬ ш и х о с н о в а н и й систем счисления д о л ж н о производиться на основе сочетания аналогичных фигур и м е н н о основания n = 2.

Н а рис. 3.53 показано построение таких фигур с обнаружением о д и н о ч н ы х о ш и б о к соответственно для о с н о в а н и й n = 2, 4, 8, 16 и 32.

x К а ж д а я из фигур Aj(0) основания n = 2 (j=i+1) строится из аналогичных фи­ гур A,j (0), X j ( 0 ) м е н ь ш е г о на две е д и н и ц ы основания по с л е д у ю щ и м логиче­ -1 - ским в ы р а ж е н и я м :

2j-i(0) Vi(0) ад = (3.7.1) 0) = Vi(0) 2j-i(0) Очевидно, что в д а н н о м случае для л ю б о г о n требуется т о л ь к о один кон¬ т р о л ь н ы й разряд, в качестве которого м о ж е т быть принят л ю б о й из аргумен¬ т о в x (i= 1,..., j). Тогда остальные аргументы, взятые в последовательности ;

д в о и ч н о г о п р и н ц и п а кодирования либо иного принципа, определяют конкрет¬ ное распределение цифр 0 - (n -1) в ячейках ц и ф р о в о г о пространства, отме¬ ч е н н ы х соответствующей заливкой.

*a(0) Х ^4(0) *я(0) Х2 Х Х Х1 Х3 Х Х Х Х Х 4 *s(0) **(0) Х Х I • Хз II Х5, Х i !

Х II Рис. 3. Н е с м о т р я на т р и в и а л ь н о с т ь полученного решения, к о т о р о е заключается во введении в код разряда проверки на четность (нечетность), эти фигуры обла¬ дают с в о й с т в о м симметрии, когда любая перестановка сигналов разрядов кода не меняет фигуру Aj(0), а логическая функция, с в я з ы в а ю щ а я между собой сиг­ н а л ы Aj(0) и Хj, при в ы б о р е в качестве функции л ю б о г о аргумента э т о й зави¬ с и м о с т и остается п о с т о я н н о й, где новая функция и аргумент п о м е н я ю т с я мес¬ тами.

Н а п р и м е р, для о с н о в а н и я n = 4 м о ж н о записать:

Хз(0) = ^ 2 ( 0 ) Х 3 V 2к(0)Х3 = Х1 Х 2 Х 3 V Х1 Х 2 Х 3 V Х1 Х 2 Х 3 V Х1 Х 2 Х 3 ;

М 0 ) = 2k(0)x3 V ^ 2 ( 0 ) Х 3 = Х1 Х 2 Х 3 V Х1 Х 2 Х 3 V Х1 Х 2 Х 3 V Х1 Х 2 Х 3 ;

Х1 = ^ 3 ( 0 ) Х 2 Х 3 V ;

Х_3(0)Х2 Х 3 V ^ 3 ( 0 ) Х 2 Х 3 V Х_3(0)Х2 Х 3 ;

Х1 = ^3(0)Х2 Х3 V Х_3(0)Х2 Х3 V ^3(0)Х2 Х 3 V ;

Х_3(0)Х2 Х3.

Такие логические функции будем называть о б р а т и м ы м и. П р и переводе из п р я м о г о кода в о б р а т н ы й всех аргументов э т о й функции она остается неиз¬ м е н н о й при их ч е т н о м числе, а при н е ч е т н о м числе аргументов эта операция п р и в о д и т к и н в е р т и р о в а н и ю функции, в чем м о ж н о убедиться, п р о в о д я соот¬ ветствующие преобразования над фигурами рис. 3.53.

Х a Х Х • Г • Х г Х a a Х • — a Х X Х • — a a Х X Ц. — a • • a L • X Рис. 3. Э т и с о о т н о ш е н и я п о з в о л я ю т разместить в ячейках м н о г о м е р н о г о про¬ странства и н ф о р м а ц и о н н ы х сигналов кода, к о т о р ы е сохраняют стандартную нумерацию его ячеек от 0 до 3, эквивалентные ц и ф р ы 0 - 7 к о н т р о л ь н ы х раз¬ рядов синтезированного кода. Э т и эквивалентные к о н т р о л ь н ы е ц и ф р ы также соответствуют их д в о и ч н о м у принципу кодирования сигналами Х1, Х2, Х3.

Х Х Х a Ц a 2 2 Ц II 2 3 a2 a ШЛА a 0 12 Х Х Рис. 3. Х Х Х I a1 0 0 1 0I I I l°l | 0_J a I Q2 _2 2_2_i_ II I 1 I 2 I 3 3IT a2 a a a2 O.J.

I 5| I I I _0 1 2 3~| Х Х Рис. 3. И з этих графических с о о т н о ш е н и й непосредственно следует определение нерабочей области м н о г о м е р н о г о ц и ф р о в о г о пространства синтезируемого кода для этих вариантов размещения:

А ^ / щ ) = Х1Х2Х3а2 V Х1Х2Х3а2 V Х1Х2Х3Я2 V Х1Х2Х3Й2 ;

М ^ / ц О = а2Х3 V а2Х3 ;

Мц^/ц^) = Х2Х3Я1Я2 V Х2Х3а1а2 V Х2Х3а^2 V Х2Х3а1а2 ;

Мм^/ц*) = Х1Х3Я1Я2 V Х1Х3а1а2 V Х ^ а ^ V Х1Х3а1а2. (3.7.2) И з (3.7.2) следует, что определение нерабочей области ц и ф р о в о г о про¬ странства первого варианта р а з м е щ е н и я наиболее просто, но и с п о л ь з о в а н и е м н о г о м е р н о г о пространства здесь составляет т о л ь к о 5 0 %. О с т а л ь н ы е вариан­ т ы используют более р а ц и о н а л ь н о ячейки м н о г о м е р н о г о пространства (75%), но в отличие от п о л н о г о совпадения в п е р в о м варианте сигналов контроль¬ н ы х и и н ф о р м а ц и о н н ы х разрядов здесь т о л ь к о один к о н т р о л ь н ы й разряд сов¬ падает с и н ф о р м а ц и о н н ы м (Х3 = а2).


Очевидно, что при б о л ь ш е м совпадении к о н т р о л ь н ы х и и н ф о р м а ц и о н н ы х сигналов кода в ы п о л н е н и е каких-либо арифметических или логических опе¬ р а ц и й в т а к о м с и н т е з и р о в а н н о м коде упрощается. Однако это не означает, что д а н н ы й код лучше других по обеспечению к о н т р о л е с п о с о б н о с т и в к о н к р е т н о й арифметической или л о г и ч е с к о й операции, и для ответа на этот в о п р о с необ¬ х о д и м о провести отдельные исследования.

X X X I a1 010 1 0 Щ 0 1_ a2 0_J_J_ V 0 2 2_j3 2 lI I I 1 I 3 3 I 2| a2 a a X X Рис. 3. X X X 00010 a _0_ 1 1 1 3 j_ a 0 II Ц. 3 a2 a a a2 O.J.

0 12 3 X X Рис. 3. И з с и м м е т р и и м н о г о м е р н о г о ц и ф р о в о г о пространства очевидно, что число эквивалентных синтезированных к о н т р о л е с п о с о б н ы х кодов, при в ы б р а н н о м п р и н ц и п е кодирования его и н ф о р м а ц и о н н о й части, определяется т о л ь к о мер¬ ностью к о н т р о л ь н о й части кода. Ограничиваясь при э т о м т о л ь к о т а к и м и ти¬ пами кодов, число кодов о д н о г о класса будет определяться количеством пере¬ становок к о н т р о л ь н ы х разрядов. И з этого следует, что второй и третий вари¬ ант р а з м е щ е н и я (рис. 3.56 и 3.57) образуют два эквивалентных кода.

Обратимся к синтезу кода основания n — 8, для чего в соответствующих рис. 3.54 ячейках пространства Х разместим фигуры ц - ц, где a — a.

3 1 4 ;

Э т о т вариант синтезированного кода, в п о л н о й аналогии с р а с с м о т р е н н ы м в ы ш е для основания n — 4, представлен на рис. 3.59.

a Х Х Х 000204 0 5 13 1 a H Hi 02223 23 3 6 2 a3.

446 5755 4 045 II H H 2 762646 77573 7 a a2 a a1 a ] a3 07 ~l~2 Т з ~ Г 4 ~ Г 5 ~ Г б ~ Г _o HZi 1 52 6 X X Рис. 3. X1X2a;

X 1 a;

X 2 a;

X 1 X II и H H H 1 1 и H H H 2 2 L H H H 3 3 H H4 H IT IT. I Рис. 3. Он является представителем класса синтезированного контролеспособного кода, где остальные получаются перестановкой сигналов к о н т р о л ь н ы х разря¬ дов.

Таким образом, в к а ж д о м классе будет содержаться шесть кодов, которые связаны между собой следующей перестановкой эквивалентных цифр кон¬ т р о л ь н ы х разрядов:

X i Х2 Хз 0 12 34 5 — X i Х3 Х 2 0 14 52 3 — Х 2 X i Х3 0 2 134 6 — Х 2 Х з Х1 0 2 4 6 13 — Х з Х 2 Х1 0 4 2 6 — Х з Х1 Х 2 0 4 152 6 - (3.7. Очевидно, ч т о остальные представители классов синтезированного кода могут быть определены из рассмотрения перестановок сигналов Х Х a;

, где 1 следует взять т о л ь к о перестановки, о т л и ч а ю щ и е с я р а с п о л о ж е н и е м сигнала a. ;

Таким образом, для исправления о д и н о ч н ы х о ш и б о к м о ж е т быть выделено три класса к о н т р о л е с п о с о б н ы х кодов, к о т о р ы е характеризуются р а з л и ч н ы м р а з м е щ е н и е м фигур ц - ц в соответствующих ячейках пространства. Э т и 1 подстановки д о л ж н ы выполняться п о рис. 3.60.

Тогда типопредставители второго и третьего класса синтезированных к о ­ дов могут быть показаны с о о т в е т с т в у ю щ и м образом на рис. 3.61 и 3.62.

Связь между к о н т р о л ь н ы м и и и н ф о р м а ц и о н н ы м и сигналами для трех классов этих кодов на о с н о в а н и и рис. 3.59, 3.61 и 3.62 определяется соответ­ ственно с л е д у ю щ и м и л о г и ч е с к и м и зависимостями:

v v Х1 — a1a_2a3 v a1a_2a3 v a^a3, X2 —, X3 — v (3 7 4) X 1 — a_2a3 v a 2 a 3, X 2 — a 1 a 2 v a 1 a 2, X 3 — a 1 a 3 v a 1 a 3 ;

(3 7 5) x — a a a v a a a v a a a v a a a, x — aa v a a, x = a a v a a. (3.7.6) 1 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 1 3 1 Все приведенные здесь коды основания n =8 используют 8 7, 5 % многомер¬ ного ц и ф р о в о г о пространства.

Теперь перейдем к синтезу кода основания n =16. Д л я этого н е о б х о д и м о в соответствующих восьми ячейках пространства Х разместить четыре фигуры Hi - ц. В ы п о л н е н н ы й в ы ш е синтез кода м е н ь ш е г о основания и закон симмет¬ рии р а с п о л о ж е н и я ш т а т н ы х цифр на ц и ф р о в о й п р я м о й п о з в о л я ю т в ы п о л н и т ь эти р а з м е щ е н и я сразу. Э т и варианты размещения, о п р е д е л я ю щ и е т р и класса кодов, в п о л н о й аналогии с р а с с м о т р е н н ы м и в ы ш е с и н т е з и р о в а н н ы м и кодами представлены соответственно на рис. 3. 6 3 - 3. 6 5.

а Х Х Х 0002041 13 1 0 I а И»

0222 23 3 I 3 6 а 04 5 4 46 4755 5 I Д Н- 7 6 2 6 466 7 а2 а а1 а "1~2 ~1~3 П ~ 4 I I _0 0 6 3 5~1~6 а 5 3 6 Х Х Рис. 3. а Х Х Х 000201 4 0 а Н- II 32 73231 33 а3 | 57 5 0 5 4 6 444 И»

2 6 6 647 7 а а2 а а1 а 0 1 2 3 4 5 6 7 0 5 3 а 7 2 4 Х Х Рис. 3. Приведенные здесь синтезированные коды основания n = 16 используют на 100% все многомерное цифровое пространство относительно одиночных ошибок.

Связь между контрольным разрядом и определенной группой информацион¬ ных сигналов разрядов для всех кодов всех классов одна и та же. Эта связь полно¬ стью определяется логическим выражением (3.7.1) для Х (0). Все восемнадцать синтезированных кодов основания n = 16, представленных распределением цифр контрольных разрядов в многомерном пространстве ин¬ формационной части кода, приведены на рис. 3.66.

2L x X 3_ 0 0 2_ 0 4 8 1 0 9 5 1 1 0 H 0 2 2 3 0 6 2 3 7 11 2 3 3 2 3 H 1_ 0 4 5 12 4 _6_ 4 5 5 13 4 5 4 14 7 6 2 6 4 6 7 5 7 3 7 6 6 0 9 8 12 8 10 8 9 11 9 13 9 8 8 14 10 11 2 10 8 10 11 9 11 3 10 11 10 14 12 12 13 4 8 12 13 9 5 12 13 13 12 H 14 14 12 14 10 6 15 14 7 11 15 13 15 14 15 H a1 1_ J_ 0 2_ 5 0 Ш? [3 [4 Г [б [7j8j9]10 11 12 13 14. 6 J_ _5_ 3 40 X X X Рис. 3. x x X 3_ 0 0 2_ 0 4 1 8 0 9 1 5 1 0 0 2 2 10 3 6 2 7 3 11 2 3 1 2 3 H H 1_ 0 4 12 5 4 _6_ 4 5 5 13 4 1 4 7 14 6 2 6 4 6 7 7 5 7 3 6 6 0 9 12 8 10 8 8 9 11 9 13 9 1 8 10 14 11 2 10 10 8 11 9 11 10 3 11 10 12 12 13 4 12 8 13 9 12 5 13 13 12 14 14 12 14 10 14 6 15 7 14 11 15 13 15 15 15 H 3 H a a a3 0 6 3 1 5 3 6 a 0 [3 [4 Г [б [7j8j9]10 11 12 13 14. 1 7 1 4 1 21 4 1 X X X Рис. 3. Х X Xi 3_ a2 0 0 0 2_ 0 1 8 4 0 1 5 Ц Ц 3 0 2 2 2 6 10 3 2 11 7 3 2 31 аз | 1 0 12 5 4 6 4 4 4 5 1_ 5 5 13 1 1 6 7 14 2 6 6 6 4 7 7 5 7 67 3 a4.

0 12 8 9 8 10 8 8 11 9 9 9 13 1,1 11 10 14 2 10 10 8 10 11 11 11 9 11 10 3 12 12 14 12 13 12 8 4 13 12 5 9 13 13 13 1 Ц 2 Ц 14 12 14 14 6 10 14 15 11 7 14 15 15 13 a4 a ai аз a ai a3 0 _5_ J_ I 7 2_ 4_ a 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 6 J_ _5_ 1 42 xi X X Рис. 3. Первый класс кодов ai 1_ _6 j _ * 0 7 3 4_ 0_ _5 2_ 0_ 7_ 3_ 4_ 0_ 7 _6 j _ _ 0_ 0_ 7_ _5 2_ аз I 3_ 4_ 6 J_ _ 6 J_ _ 6 J_ 3_ 4_ _ 5 2 6 J_ 2_ 3_ 4_ _5 2_ _5_ 2_ ^ _ 4_ a 2_ 3_ 4_ 6 J_ 3_ 4_ _ 2_ 6 J_ _ 3_ 4_ 6 J_ _ 6 1 5 2_ _5 3_ 4_ _5 2_ 3 4 0 7 5207 3407 6 107 6 107 В т о р о й класс кодов 0 6 3 _5_ 0 653 05 3 6 0_ 5 6 3 0 365 03 5 5 3 6 0_ 3 560 63 5 0 3_ 6 5 0 5 630 65 3 7 1 4 2_ 7 12 4 72 4 1 7_ 2 1 4 7 4 12 74 2 2 4 1 7 4 2 17 14 2 7 4 1 2 7 2 14 7 12 4 Т р е т и й класс кодов 6_ _ 0 5 3 03 5 6 0 635 0 563 0 7 2 4 J_ 74 2 1 7 14 2 7_ 4 1 2 7 2 14 7 12 5_ 6 3 6 3 5 0_ 65 3 0 5 360 3 650 3 1 4 2 7 12 4 7 2 4 17 2147 4 12 7 4 2 XiX2X3 XiX3X2 X2XiX3 X2X3Xi X3X2Xi X3XiX Рис. 3. Сравнение распределения цифр 0-7 к о н т р о л ь н ы х разрядов в м н о г о м е р ­ н о м ц и ф р о в о м пространстве и н ф о р м а ц и о н н о й части кода с а н а л о г и ч н ы м рас­ пределением кодов о с н о в а н и й n = 4, 8 показывает, что п о л н о с т ь ю контроле с п о с о б н ы й код основания n = 16 определяет все с о о т н о ш е н и я между и н ф о р ­ м а ц и о н н о й и к о н т р о л ь н о й частями в кодах м е н ь ш и х оснований. П о э т о м у в д а л ь н е й ш е м будем рассматривать т о л ь к о такие основания систем счисления, к о т о р ы е п о з в о л я ю т синтезировать п о л н о с т ь ю к о н т р о л е с п о с о б н ы е коды.

3.7.3. К о д ы б о л ь ш и х о с н о в а н и й с и с т е м с ч и с л е н и я с исправлением одиночных ошибок Синтез кодов б о л ь ш и х о с н о в а н и й систем счисления м о ж н о выполнить, опираясь на представленную в ы ш е систему счисления основания n = 16. П р и э т о м процедура операции синтеза будет так же, как рассмотренная выше, за¬ ключаться в р а з м е щ е н и и в м н о г о м е р н о м ц и ф р о в о м пространстве информаци¬ о н н ы х и о д н о г о к о н т р о л ь н о г о разряда фигур основания n = 16 с е м и м е р н о г о ц и ф р о в о г о пространства (см. рис. 3.53), где реализовано исправление одиноч¬ ных ошибок.

Для сокращения графическо¬ го материала о г р а н и ч и м рас¬ смотрение т о л ь к о представлени¬ ем синтеза кода о д н о г о класса. a Ц 2 Ц Ц Н а рис. 3.67 приведены эти as Ц восемь ячеек с е м и м е р н о г о про¬ Ц Ц4 странства, к о т о р ы е вместе с раз¬ a Ц м е щ е н н ы м и в них фигурами обо¬ 1 О Ох О2 as Ц з н а ч е н ы o - о. Э т и фигуры ох¬ i Ц Ц4 ватывают все варианты разме¬ Ц щ е н и я цифр 0-15 основания n = Ц 2 Ц Ц 16 в с е м и м е р н о м (k = 3, i = 4) ц и ф р о в о м пространстве, где ис¬ правляются все одиночные Ц 2 Ц Ц ошибки. П о с т р о е н и е этих фигур, в ы п о л н е н н о е аналогично осно¬ Ц Ц4 ванию n = 2, определяется после¬ О И з ] Об д о в а т е л ь н ы м р а з м е щ е н и е м этих Ц цифр на ц и ф р о в о й п р я м о й емко¬ Ц 4 Ц стью 2 с сохранением симмет¬ Ц рии р а з м е щ е н и я относительно Ц 2 Ц Ц центра этой п р я м о й и неизмен¬ Рис. 3. ности к о д о в о г о расстояния меж¬ ду ними, о б е с п е ч и в а ю щ и м ис¬ правление о д и н о ч н ы х ошибок.

an аю a X CTl CTl СТ2 СТэ СТ4 СТ4 СТэ СТ CT5 CT6 СТ CT6 СТ5 СТ8 СТ7 СТ7 СТ8 СТ5 СТ CTl CTl CT2 СТ4 Т э СТэ СТ4 СТ CT7 СТ8 СТ5 СТ6СТ66 СТ5 СТ8 СТ CTl СТ2 CTl СТэ СТ4 СТ4 СТэ СТ2 CTl CTl СТ CT4 СТэ СТэ СТ CT8 СТ7 СТ6 СТ5 СТ5 СТ6 СТ7 СТ CT8 СТ7 СТ5 СТ5 СТ6 СТ7 СТ СТ СТ2 CTl CTl СТ CT4 СТэ СТэ СТ CTl СТ2 СТ2 CTl СТэ СТ4 СТ4 СТэ CT7 СТ8 СТ5 СТ6 СТ6 СТ5 СТ8 СТ CTl CTl CT2 СТ4 СТэ СТэ СТ4 СТ CT6 СТ5 СТ8 СТ7 СТ7 СТ8 СТ5 СТ CT5 СТ6 СТ CTl CTl СТ2 СТэ Т4 СТ4 СТэ СТ Рис.

3. Опустив достаточно прозрачные из изложенного выше операции подстановки фигур a - a в ячейки пространства большей мерности (см. рис. 3.53), на 1 рис. 3.68 приведен один из многочисленных вариантов такого размещения в про­ странстве Х (0), что определяет полностью контролеспособный код для основания n = 2. В соответствии с этой процедурой не представит какого-либо труда раз¬ местить в ячейках многомерного цифрового пространства информационной части кода эквивалентные контрольным сигналам разрядов x - Х4 цифры 0-15. Для компактного графического представления одного из вариантов синтеза на рис. 3.69,а показаны большие ячейки информационного пространства, которые обозначены соответственно s - s и s - s, а на рис. 3.69, б приведена ячейка s с } 1 4 заполненными элементарными ячейками информационного пространства эквива¬ лентными цифрами контрольной части синтезированного кода.

Заполнение остальных б о л ь ш и х ячеек информа¬ as ц и о н н о г о ц и ф р о в о г о пространства, к о т о р ы е и м е ю т такие ж е координаты, как s, подчиняется следую¬ щ и м в з а и м н ы м перестановкам эквивалентных цифр Si S2 S I S к о н т р о л ь н о й части кода:

Si S4 S3 S a S3 S a 11 Si 0 1 2 3 8 9 10 Si о S 2 Si S4 S3 S = г г г г г г г a) г аз 7 6 5 4 15 14 13 12, S3 о S a Si ai 0 1 2 3 4 5 6 Si о S = г г г г г г г г 035бб аб 10 9 15 12 12 15 9 14 15 12 13 10 11 8 9, S2 о S 11 8 14 13 13 14 8 a 1 2 4 7 74 2 Si Si о 12 15 9 10 10 9 15 0 1 2 3 4 5 6 S о б 5 3 0 03 5 б = 7 4 2 1 12 4 г г г г г г г г 13 14 8 11 11 8 14 a 15 14 13 12 11 10 9 8.

S о S 13 14 8 11 11 8 14 S S4 о 7 4 2 1 12 4 б 5 3 0 03 5 б Н а о с н о в а н и и зависимостей рис. 3.69, в ы п о л н я я 12 15 9 10 10 9 15 определенные преобразования, аналогичные тем, 1 2 4 7 74 2 к о т о р ы е п р о в о д и л и с ь выше, м о ж н о получить гра¬ 11 8 14 13 13 14 8 10 9 15 12 12 15 9 фические образы логических функций, с в я з ы в а ю щ и е 035бб между собой к о н т р о л ь н ы е и и н ф о р м а ц и о н н ы е сиг¬ б) налы разрядов.

Н а рис. 3.70 приведена такая з а в и с и м о с т ь между Рис. 3. сигналом к о н т р о л ь н о г о разряда x и и н ф о р м а ц и о н ­ н ы м и разрядами x = F(a, a, a, a, a, a, a ), которая п о л н о с т ь ю определяется 1 1 2 4 5 7 9 в ы р а ж е н и е м Х (0). А н а л о г и ч н ы е з а в и с и м о с т и представляются для сигналов других контроль¬ ных разрядов, к о т о р ы е отличаются и н ы м и группами сигналов информацион¬ ных разрядов, а именно:

Х2 = F ( a a2, as, a4, as);

b = а ь a^ Х a );

з a = J^X^ ^ ^ ^ ^ ^ x a ).

4 В представленных нами при a4 мерах синтеза полностью контро леспособных кодов относительно ai о д и н о ч н ы х о ш и б о к, т е м б о л е е ох­ в а т ы в а ю щ и х все их к л а с с ы, д о л ж ­ н ы с о д е р ж а т ь с я все к о д ы, синте¬ as зированные каким-либо иным способом. Например, замечатель­ ная п р о ц е д у р а с и н т е з а контроле a9 способных кодов Хемминга для исправления одиночных ошибок п р е д с т а в л е н а на рис. 3.66 в пер­ в о м классе и о т м е ч е н а з в е з д о ч к о й, aii | | | | | | | | | | | | а т о л ь к о ч т о с и н т е з и р о в а н н ы й код основания n=2 также является кодом Хемминга.

Связь между к о н т р о л ь н ы м и k и и н ф о р м а ц и о н н ы м и i сигналами раз¬ рядов п о л н о с т ь ю контролеспособ ных кодов определяется зависимо¬ k стью i = [2 - (k+1)], что для осно¬ ваний n = 2, 2, 2, 2, позволя¬ ет исправлять все о д и н о ч н ы е ошиб¬ ки.

Рис. 3. О т м е ч е н н о е з д е с ь не о з н а ч а е т, что для этих оснований и любых д р у г и х нет в о з м о ж н о с т и о б н а р у ж е н и я и и с п р а в л е н и я б о л ь ш е г о к о л и ч е с т в а к о м б и н а ц и й о ш и б о к, ч е м р а с с м о т р е н о в ы ш е. У в е л и ч е н и е ч и с л а контроль¬ н ы х р а з р я д о в с в е р х п р е д с т а в л е н н о г о п р и в е д е т к т о м у, ч т о п р и геометриче¬ с к о м с п о с о б е с и н т е з а к о д о в н е о б х о д и м о будет в я ч е й к а х п р о с т р а н с т в а рис.

3.53 р а з м е щ а т ь, н а п р и м е р, ф и г у р ы о с н о в а н и я n = 2, п о з в о л я ю щ и е и с п р а в ­ л я т ь о д и н о ч н ы е, д в о й н ы е и т.д. о ш и б к и, ч а с т и ч н о р а с с м о т р е н н ы е в п. 3.1.

И м е н н о э т и д о с т а т о ч н о с л о ж н ы е з а д а ч и будут д е т а л ь н о р а с с м о т р е н ы в п о с л е д у ю щ и х г л а в а х к н и г и, а п р е д с т а в л е н н ы й в э т о м п а р а г р а ф е с и н т е з со¬ вершенных кодов и определение числа этих кодов носят предварительный, в в о д н ы й х а р а к т е р и будут у т о ч н е н ы в д а л ь н е й ш е м и з л о ж е н и и.

3.8. Решение задачи повышения надежности логических и цифровых устройств в режиме реального времени Известно, что надежность логических и ц и ф р о в ы х устройств м о ж н о п о ­ высить, не используя резервирования их элементов. Для д о с т и ж е н и я этой цели н е о б х о д и м о применять в ы с о к о н а д е ж н ы е э л е м е н т ы и схемы с б о л ь ш и м запа­ сом надежности, где уделяется п о в ы ш е н н о е в н и м а н и е т е х н о л о г и и их изготов­ ления и сборки. Однако этот п р а в и л ь н ы й путь не м о ж е т обеспечить н а д е ж н ы е в ы ч и с л и т е л ь н ы е системы м н о г о л е т н е й длительной эксплуатации без челове¬ ческого с о п р о в о ж д е н и я и хранения, используемые для проведения, например, исследований космического пространства и управления о т в е т с т в е н н ы м и бор¬ т о в ы м и системами реального масштаба времени [13].

С целью п о в ы ш е н и я надежности таких систем нередко используется их резервирование со схемой голосования. Такой путь п о в ы ш е н и я надежности был предложен Дж. ф о н Н е й м а н о м [14], к о т о р ы й разработал и проанализиро¬ вал схему т р о й н о г о резервирования элементов с м а ж о р и т а р н о й функцией го¬ лосования. Г е о м е т р и ч е с к и й вариант п о д о б н о г о подхода к проблеме исправле­ ния о ш и б о к был представлен нами в предыдущих разделах. Э т о т подход за¬ ключается в исправлении всех о ш и б о к конечной д в о и ч н о й системы счисле¬ ния, например, всех о д и н о ч н ы х о ш и б о к или о д н о в р е м е н н о всех о д и н о ч н ы х и д в о й н ы х о ш и б о к ;

о д н о в р е м е н н о всех одиночных, д в о й н ы х и т р о й н ы х о ш и б о к и т.д. П о д т е р м и н о м «всех» понимается, что конкретная о ш и б к а м о ж е т суще¬ ствовать все время, и она д о л ж н а при э т о м непременно исправляться. Следо¬ вательно, исправление о ш и б о к и резервирование, например, элементов циф¬ р о в о й системы здесь будут совпадать при условии, что исправление о ш и б о к каждого разряда систематического кода осуществляется отдельной схемой, не и м е ю щ е й о б щ и х элементов со схемами исправления о ш и б о к других разрядов.

Повышение надежности с мажоритарной функцией голосования Дж. ф о н Неймана, где р а в н ы е о д н о в р е м е н н ы е сигналы F(a) о д и н а к о в ы х эле­ ментов 1 (рис. 3.71) объединяются м а ж о р и т а р н о й схемой голосования 2, име¬ ет м н о г о о б щ е г о с задачей исправления всех о д и н о ч н ы х о ш и б о к в системе счисления основания два (см. рис. 3.3).

В с а м о м деле, исправление всех одиноч¬ A F(a) ных о ш и б о к в к а ж д о м из разрядов л ю б о й системы счисления является резервировани¬ A F(a) ем канала связи, что р а в н о ц е н н о резервиро¬ F(a) 1 ванию в ы х о д н ы х сигналов F(a) рис. 3.71.

Здесь следует учитывать, что при несо¬ A F(a) вершенстве м а ж о р и т а р н о й схемы вероят¬ ность безотказной р а б о т ы р е з е р в и р о в а н н о й схемы определяется [15] з а в и с и м о с т ь ю где р - вероятность безотказной р а б о т ы отдельной нерезервированной схе¬ мы;

P - вероятность безотказной р а б о т ы отдельной м а ж о р и т а р н о й схемы.

m Из анализа этого выражения следует, что в резервированной таким образом схеме вероятность безотказной работы выше, чем в нерезервированной, но до оп¬ ределенного момента времени, после которого она становится меньше нерезерви¬ рованной схемы. Поэтому средняя наработка на отказ становится недостаточной для работы в течение требуемого интервала времени и для получения необходи¬ мого значения средней наработки на отказ вся схема должна будет строиться с многократным мажоритарным резервированием (см. рис. 3.5, рис. 3.6) либо необ¬ ходимо будет выполнить резервирование мажоритарного элемента.

П о с т р о е н и е логических и ц и ф р о в ы х устройств, в систематических кодах с исправлением всех заданных заранее ошибок, вполне реально, но требует зна¬ чительных аппаратурных затрат. П р и э т о м наиболее целесообразно использо¬ вать систематические коды с б о л ь ш е й разрядностью его и н ф о р м а ц и о н н о й час¬ ти, что позволяет у м е н ь ш а т ь аппаратурные затраты.

П р а в и л ь н о с т ь этого заключения легко показать на примере в ы п о л н е н и я к о м б и н а ц и о н н ы х схем бинарных логических функций при исправлении всех о д и н о ч н ы х о ш и б о к д в о и ч н о й системы счисления, где систематический код первого операнда будет содержать один и н ф о р м а ц и о н н ы й разряд - ai и два к о н т р о л ь н ы х разряда - x, x. Для второго операнда это будут соответственно 1 разряды b i, z i, Z2.

Геометрические образы бинарных логических функций y - y с исправ¬ 1 лением о д и н о ч н ы х о ш и б о к и аналогичные им функции без исправления оши¬ бок приведены на рис. 3.72 в м н о г о м е р н о м ц и ф р о в о м пространстве координат a, x, x ;



Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 9 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.