Устройство для декодирования кода
1. УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ КОДА, содержащее первый и второй сумматоры, вычислитель.четности, блок отказа от декодирования, умножитель , формирователь кодов, корректор , блок обнаружения ошибок к первьй блок сумматоров, вход которого объединен с первым входом вычислителя четности, информационным входом корректора н соединен с первым входом устройства, а первый выход соединен с первыми входами блока обнаружения ошибок, формирователя кодов и первого сумматора, второй вход вычислителя четности соединен с вторым входом устройства, а выход - с первым входом блока отказа от декодирования , первьй выход корректора является первым выходом устройства, выход блока отказа от декодирования является вторым выходом устройства, выход первого сумматора соединен с первым корректирующим входом корректора , второй корректирующий вход которого соединен с выходом второго сумматора, к входу которого подключей выход формирователя кодов, выход блока обнаружения ошибок соединен с вторым входом блока отказа от декодирования и является третьим выходом устройства, отличающееся тем, что, с целью повышения быстродействия и достоверности обрабатываемой информации, в него введены второй и третий блоки сумматоров, вычислитель обратных корней, формирователь исключенных кодов и корректор четности, первый вход которого объединен с вторым входом устройства, второй вход объединен с вторым входом блока обнарз ения ошибок и соединен с выходом вычислителя четности, третий вход соединен с выходом блока обнаружения ошибок, четвертый вход с выходом блока отказа от декодирования , а выход является четвертым выходом устройства, первый вход второго блока сумматоров объединен с входами первого и третьего блоков сумматоров , второй вход соединен с вторым выходом первого блока сумматоров , а выход - с первым входом умножителя и вторым входом формирователя кодов, выход третьего блока сумматоров соединен с третьим входом блока обнаружения ошибок и вторым входом умножителя, третий вход которого подключен к первому выходу первого блока сумматоров, а выход - к входу вычислителя обратных корней, первый выход которого соединен с третьим входом формирователя кодов, выход которого соединен с вторым входом первого сумматора, второй выход вычислителя обратных корней соединен с третьим входом блока отказа от декодирования, четвертый вход которого подключен к выходу формирователя исключенных кодов, первьй вход ко
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИН ((9) (И) (5l)4 Н 03 И 13/00
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3667663/24-24 (22) 21.11.83 (46) 07.11.85. Бюл. ¹ 41 (72) А.В. Анохин, И.М. Бояринов и А.А. Давыдов (53) 621.394.14(088.8) (56) Патент ФРГ № 2817864, кл. Н 03 К 13/34, 1980.
Патент США № 4030067, кл. С 06 F 11/12, 17.06.77. (54)(57) 1. УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ КОДА, содержащее первый и второй сумматоры, вычислитель, четности, блок отказа от декодирования, умножитель, формирователь кодов, корректор, блок обнаружения ошибок и первый блок сумматоров, в од которого объединен с первым входом вычислителя четности, информационным входом корректора и соединен с первым входом устройства, а первый выход соединен с первыми входами блока обнаружения ошибок, формирователя кодов и первого сумматора, второй вход вычислителя четности соединен с вторым входом устройства, а выход — спервым входом блока отказа от декодирования, первый выход корректора является первым выходом устройства, выход блока отказа от декодирования является вторым выходом устройства, выход первого сумматора соединен с первым корректирующим входом корректора, второй корректирующий вход которого соединен с выходом второго сумматора, к входу которого подклю-, чен выход формирователя кодов, выход блока обнаружения ошибок соединен с вторым входом блока отказа от декодирования и является третьим выходом устройства, о т л и ч а ю щ ее с я тем, что, с целью повышения быстродействия и достоверности обрабатываемой информации, в него введены второй и третий блоки сумматоров, вычислитель обратных корней, формирователь исключенных кодов и корректор четности, первый вход которого объединен с вторым входом устройства, второй вход объединен с вторым входом блока обнаружения ошибок и соединен с выходом вычислителя четности, третий вход соединен с выходом блока обнаружения ошибок, четвертый вход — Я с выходом блока отказа от декодирования, а выход является четвертым выходом устройства, первый вход второ го блока сумматоров объединен с входами первого и третьего блоков сум- д маторов, второй вход соединен с вторым выходом первого блока сумматоров, а выход — с первым входом умножителя и вторым входом формирователя кодов, выход третьего блока сумматоров соединен с третьим входом блока обнаружения ошибок и вторым входом умножителя, третий вход которого подключен к первому выходу первого блока сумматоров, а выход — к входу вычислителя обратных корней, первый выход которого соединен с третьим входом формирователя кодов, выход которого соединен с вторым входом первого сумматора, второй выход вы. числителя обратных корней соединен с третьим входом блока отказа от декодирования, четвертый вход которого подключен к выходу формирователя исключенных кодов, первый вход которого соединен с выходом первого сумматора, второй вход — с выходом второго сумматора, а третий вход — с вторым выходом корректора, управляющий вход которого соединен с выходом блока обнаружения ошибок, выход умножителя подключен к пятому входу блока отказа от декодирования.
2. Устройство по п. 1, о т л и ч аю щ е е с я тем, что корректор содержит блок элементов И-ИЛИ-НЕ, сумматор, блок инверторов, первый и второй дешифраторы старших разрядов, первый и второй дешифраторы младших разрядов, управляющие входы которых объединены и соединены с управляющим входом корректора, первый корректирующий вход которого соединен с информационными входами первых дешифраторов младшего и старшего разрядов, а второй корректирующий вход — с информационными входами вторых дешифраторов младшего и старшего разрядов, выходы дешифратарав через блок элементов И-ИЛИ-НЕ соединены с первым входам сумматора, второй вход которого соединен через блок инверторов с информационным входом корректора, а выход — с первым выходам корректора, выходы дешифратаров соединены с вторым выходом корректора.
3. Устройство по пп. 1 и 2, о тл и ч а ю щ е е с я тем, что вычислитель обратных корней содержит дешифраторы младшего и старшего разрядов, блок элементов И-ИЛИ-НЕ, блок элементов И-HE и дешифратор нуля, вход которого соединен с выходом блока элементов И-НЕ и первым выходом вычислителя обратных корней, вход которого соединен с входами дешифраторов младшего и старшега разрядов, выходы которых соединены с соответ1190525 ствующими входами блока элементов..
И-ИЛИ-НЕ, выход которого соединен с входом блока элементов И-НЕ, выход дешифратора нуля подключен к второму выходу вычислителя обратных корней.
4. Устройство по пп. 1-3, о т л ич а ю щ е е с я тем, что формирователь исключенных кодов содержит первый, второй, третий и четвертый элементы И и первый и второй элементы
ИЛИ, входы первого и второго элементов И соединены соответственно с первым и вторым входами формирователя исключенных кодов, а выходы— с первыми входами соответственно первого и второго элементов ИЛИ, вторые входы которых, а также первые и вторые входы третьего и четвертого элементов И подключены к третьему входу формирователя исключенных кодов, выходы третьего и четвертого элементов
И соединены с третьими входами соответственно первого и второго элементов ИЛИ, выходы которых соединены с выходом формирователя исключенных кодов.
5. Устройство па пп. 1-4, о т л ич а ю щ е е с я тем, что корректор четности содержит первый и второй элементы И и сумматор, первый вход которого соединен с первым входом корректора четности, второй вход которого соединен с первым входом первого элемента И, третий и четвертый входы корректора четности соединены с соответствующими входами второго элемента И, выход которого подключен к второму входу первого элемента И, выходы элементов И и второй и третий входы корректора четности соединены с соответствующими вторыми входами сумматора.
Изобретение относится к вычислительной технике и может быть использовано в системах обработки, хранения и передачи информации, в частности в быстродействующих запоминающих устройствах с параллельной записью и считыванием.
Целью изобретения является повышение быстродействия путем ускоренной выдачи кодового слова при отсутствии ошибок и достоверности обрабатываемой информации за счет использования, при отборе от декодирования, фактов отсутствия решения ква1 190525 (N6 N ° Nî) дратного уравнения и наличия исключенных локаторов.
На фиг. I приведена блок-схема устройства для декодирования кода, на фиг. 2 — блок-схема корректора," на фиг. 3 — блок-схема вычислителя обратных корней.
Устройство для декодирования кода содержит первый блок 1 сумматоров, второй блок 2 сумматоров, третий блок .3 сумматоров, вычислитель 4 четности, корректор 5 четности, умножитель 6, блок 7 обнаружения ошибок, вычислитель 8 обратных корней, блок 9 отказа от декодирования, первый сумматор 10, корректор 11, формирователь
12 кодов, второй сумматор 13, формирователь 14 исключенных кодов, первый вход 15, второй вход 16, первый выход 17, второй выход 18, третий выход 19, четвертый выход 20.
Корректор 11 содержит первый дешифратор 21 старших разрядов, первый дешифратор 22 младших разрядов втоУ рой дешифратор 23 младших разрядов, второй дешифратор 24 старших разрядов, блок 25 элементов И-ИЛИ-НЕ, сумматор 26 и инвертор 27. Вычислитель 8 обратных корней содержит де- 30 шифратор 28 старших разрядов, дешифратор 29 младших разрядов, блок 30 элементов И-ИЛИ-НЕ, блок 31 эле.ментов И-HE и дешифратор 32 нуля.
Формирователь 14 исключенных кодов содержит первый, второй, третий и четвертый элементы И 33-36 И и первый и второй элементы ИЛИ 37 и 38.
Корректор 5 четности содержит первый и второй элементы И 39 и 40 и сумма- 40 тор 41. Блок 7 обнаружения ;ошибок содержит элементы ИЛИ 42-45, а блок 9 отказа от декодирования — элементы
ИЛИ 46-48, элементы И 49 и 50 и сумматор 51. Одной связи фиг. 1-3 соот- 4> ветствует несколько электрических связей, Например, от входа 15, выхода 17 и выходов блока 25 отходят шины шириной и -1 разрядов. От первого выхода блока 1 и от выходов бло->0 ка 3 и умножителя 6, сумматора 10 сумматора 13 отходят 2tn-разрядные шины (Ill-разрядов — прямые значения сигналов и m разрядов — инверсные значения). От первого выхода вычисли- И теля 8 отходит (m-1)-разрядная шина.
От выхода формирователя 12 отходит
42-разрядная шина.
Устройство работает следующим образом.
Работа устройства описана для случая, когда количество информационных разрядов К=64, а длина декодируемого кода и +79, т.е. 15 разрядов являются проверочными. Информация поступает в устройство и передается между блоками в параллельной форме. Декодируемое 7-9-разрядное слово а=
I I
=(ао, à,,..., à>8 ), которое, возможно, содержит ошибки, поступает на входы 15 и 16 устройства. При этом разряд проверки на четкость а поступает на вход 16, откуда проходит в вычислитель 4 и корректор 5
У а остальные разряды а,, ..., а посту"7Ю" лают на вход 15, откуда проходят в блоки 1-3, вычислитель 4 и корректор
11.
При работе устройства каждому разI ряду декодируемого слова а ставится в соответствие локатор разряда, являющийся элементом конечного поля
Р
Галуа GF(2 ). Это поле содержит 128 элементов. Элемент N поля СР(2 ) представляется либо набором из семи двоичных разрядов либо многочленом — "6вс " Уо о
6 где N, C (О, 1 ), aC — примитивный элемент поля
GF(2 ), являющийся корнем
7 многочлена х + х + 1.
IT
Знак + здесь и далее обозначает сложение по модулю два (для векторов — поразрядное сложение по модулю два). Для коррекции ошибок в устройстве вычисляются локаторы искаженных разрядов: локатор первой ошибки i, локатор второй ошибки
Локаторы ошибок формируются следующим образом. По декодируемому сло-! ву а блок 1 вычисляет сумму локаторов ошибок $ = 11+1, блок 3 вычисляет сумму обратных локаторов S
1,1
S = —.— + —.—, вычислитель 4 вычисля11 iZ ет проверку на четность P. Если S
S =0 и Р=О, то ошибок в слове а нет ° Если $ = $2= 0 и Р=1 то имеетj ся ошибка в разряде ао. Если S ф О, $1ь О,, = S2 (т.е. St Sz=1) и Р=1 то
Л
У имеется одна ошибка в разряде с лока1190525
+ "г (2) +
Яг
1г
Для решения системы (2) вначале вычисляется корень квадратного уравнения г 1 х +х+ — =О, 1 (3) 30 где g = $1$
При этом умножитель 6 формирует величину, умножая в поле GP(2 ) Я
7 на Sz. Вычислитель 8 по величине ), 7 обратной свободному члену — — нахо35 дит корень.х квадратного уравнения (3) или определяет, что уравнение (3) не имеет решений. В последнем случае устройство отказывается от декодирования.
Формирователь t2 и сумматор 13, умножая корень х íà S,формирует локатор первой ошибки
1 = хЯ
45 г
Параллельно, используя промежуточные результаты, формирователь 12 и сумматор 13 формируют локатор второй ошибки!
Корректор 11 осуществляет коррекцию искаженньгх разрядов, используя
Ф значения локаторов 1 и Z. (Если ошибка имеется в разряде а она корректируется в корректоре 5.
Блок 7 обнаруживает ошибки, сравнивая с нулем величины $7 и Бг. Блок тором ii =$7 . Если S Ф О, S Ф О, 1
S и Р О, то имеется ошибка в разряде с локатором iI=S< и, кроме того, ошибка в разряде а, . Наконец, если
Б,ф О, Я фО, Я,Яг/1 и Р=О, то предполагается, что име тся две ошибки в разрядах а,, ..., а, с локаторами
Во всех остальных случаях (s частности, если S ф О, S = О, i0 или S < О, $ ф О, или S ф О, S $ 0, Б, БД 1, Р=1) необходимо отказаться от декодирования, так как количество ошибок равно или больше трех.
В c)7> àå, когда Яс Ф. О, Б, 7 О, Б Б, 1, и Р=О, локаторы ошибок i вычисляются путем решения (в умножителе 6, вычислителе 8, сумматоре
10, формирователе 12 и сумматоре 13) системы уравнений над полем GF(2 ) 20
9, используя информацию из корректора 5, блока 7, вычислителя 8 и формирователя 14 формирует сигнал отка) за от декодирования при наличии трехкратных ошибок и фазированных пакетов ошибок длины "4".
Декодирование слова а выполняется в устройстве с учетом того, что кодовое (безошибочное) слово а =
=(а а7,, ° а 8 ) сфОрмированО с помощью матрицы К, состоящей из трех
К1, Кг, К подматриц, приведенных в табл. 1. В слове а разряды ао а, ° ° ° ) a ц 1 aI6 айаг » a<8 провероч ные, остальные разряды — а,г, aIÓ а 7 ° ° ° a)I аЗЗ, а47 а4„, ..., а78 — информационные. Каждому проверочному разряду соответствует в матрице К столбец с одной единицей, строка, содержащая эту единицу, указывает (своими единицами), какие информационные разряды участвуют в формировании данного проверочного разряда. Например, а =а
+ а +. ° ° +а ; a =a + a +...+ a + а72+ а 73+ + 78 ° матрице К при декодировании соответствует проверочная матрица Н, состоящая из трех подматриц Н<, Н, H и приведенная в табл. 2, (В табл. 2 показано также, что с входа 16 разряд А поступает на i-й разряд входа
/. блока 1, i=1 78) .
Каждый столбец матрицы Н являf ется локатором соответствующего разряда декодируемого слова а, Локатор
I разряда представляет собой семиразрядный двоичный набор — элемент поля
GF(2 ). .Каждый столбец матрицы Нг является элементом поля СГ(27), обратным соответствующему локатору, т.е. если столбец матрицы Н есть элемент
i поля GF(2 ), то соответствующий столбец матрицы Н есть элемент тг
1 поля GF (2 ) .
I матрица Н> является строкой из
79 единиц и обеспечивает проверку на четность декодируемого слова.
Блок 1 вычисляет
s>i 7+1 г=-(sag» $17 у Буо ) (4)
Г путем умножения слова (О, а, ..., абаз ) на транспонированную матрицу Н, реализуя при этом (Яд ° ° ° ° S+ у S 0 )
=(О, a„... a> )Н, где Т вЂ” знак транспонирования матрйцы.
Умножение вектора на матрицу реализуется с помощью сумматоров по моду1190525
$76 =А, +А2+А +А4, $ =А +А +А4. г% 5 6
Блок 3 с помощью сумматоров по модулю два с прямыми и инверсными выходами, входящих в его состав, вычисляет сумму обратных локаторов г 2
S 2» являющуюся элементом поля GF(2 )» 35
1 1
2 (26» » 2t » 2Р)
I t путем умножения слова (о,a,, à76 ) на транспонированную матрицу Н2.
Блок 4 с помощью сумматоров по модулю два с прямыми и инверсными выходами входящих в его состав, вы) числяет проверку на четность P реализует при этом соотношение
О» 4» » 7в) Г О Ч 45
30 г
Блок 2 с целью подготовки умножения в умножителе 6 вычисляет в фор-мирователе 12 и сумматоре 13 шесть . попарных сумм двоичных компонентов величины S)
Оj =$ Руются так: $(6 =а4 + ° ° ° +a)g =а +...+а47+а-, +...+а7В» т.е. пРи формировании i-го разряда произведения вычисляется сумма по модулю два ) тех разрядов слова а, номера которых соответствуют единичным элементам i-й строки матрицы. В связи с тем, что количество входов сумматора по модулю два не превышает 8 или 9, то при реализации умножения вектора на матрицу обычно вначале получают промежуточные суммы А. из 8-9 слагаемых из которых затем » формируют разряды произведения. Так, для получения St6 и St5 можно вначале сформировать промежуточные суммы . 20 I г At = а4В+ ... + ав ; г ° ° аб» t I ° А =аь + ° ° ° +a7t I А =а72 + ° ..+а 7в 1 =аз2+ ° ° ° +а )4, 25 » А6 =а4о+ ° ..+а„, а затем разряды произведения щает время декодирования. Вычисление U2 U6 выполняется в блоке 2 с помощью сумматоров по модулю два I / путем умножения слова (о,а,..., а7 ) на транспонированную матрйцу Н4 приведенную в табл. 3. При этом реализуется соотношение g г)г 6 Ъ|Р (о а ° а)в)Й4(5). " Для реализации выражения (5) .в блоке 2 могут быть использованы промежуточные результаты суммирования А - полученные в блоке 1 при реали1» зации выражения (4). Например, U -= =A +А +А +А +А . Указанные промежу-! точные результаты А„ поступают в блок 2 с второго выхода блока 1. С этого же выхода в блок 2 поступают двоичные компоненты величины S необходимые для формирования тех сумм П.; которые используются только в формирователе 12. В рассматриваемом случае — это $0, St2, по которым вычисляется Ut .=$), +$,2 . Умножитель 6» используя величины. U2 » ° ° ° ° U6 °, выполняет в поле GF(2 ) умножение S 7 на S 2» получая величину g=S) S 2=(g6 - g,, я„) . При этом с помощью логических элементов И-НЕ, НЕ и сумматоров по модулю два с прямыми и инверсными выходами, входящих в состав умножителя 6, реализуются соотношения 22 4 24 <5 2р f6 + $ „+ Я Я+$$Г 2ЯД 2% 6 24 1Ф 23 Ф + гг 1г г Sf4 . . $26 4 S 5 24 6 2 $1t гг г г Т е+ г Зз 26 Я 2» 4 24 5 г гв()6 22 It 2 I2 2р tэ 2 Я 24 Ч 23 у+ 22 44 2I (2 27t lg t г+ 2 24 З 24 4 23 % 22 6 2I 4 to IZ » «Од (6 )) 26 72 ) 25П2 24 Пэ гг г 2 12 гг»|г гг»1Ф гг ю -г Гг го fo Величина g обратна свободному члену квадратного уравнения (3). Это уравнение либо имеет два решения х и у, либо не имеет решений. При этом решения х и у, являющиеся элемента9 1190525 10 ми поля GF(27), имеют вид x=(x б,...-, х2э х 4, 1)э у=(хб,... s xzр x„o), т.е. решения отличаются одно от дру гого только в компоненте N. (1). Вы-! числитель 8 определяют, имеет ли решение уравнение (3), и решает это уравнение. Если решение есть, то на втором выходе вычислителя 8 форфируется дискриминант D=0, а на первом вы-1о ходе выдаются двоичные компоненты решения х4,..., х . Если решения нет, то на втором выходе формируется значение D-=1,, а на первый выход выдаются нули. 15 В случаях, когда g=$4$<=1 (т.е.в случае однократной ошибки) и когда g=0 (т.е при отсутствии ошибок или при наличии многократных ошибок), уравнение (3) не имеет решений и на 20 первый выход выдаются нули. В формирователе 12 и сумматоре 13 вычисляется локатор первой ошибки i< путем умножения корня х íà $1. При этом формирователь 12 с помощью эле- 25 ментов И-НЕ, входящих в его состав, вычисляет 21-частичное произведение вида h" =х S(> 1=ш; j=1 2, ° ., 7-ш, ш=1,2,...,6, 3g и 21-частичное произведение вида 1, =х„П, i=m j=7-ш,..., 5,6; ,m=1,...,6. Сумматор 13 с помощью сумматоров по модул(а два с прямыми и инверсными выходами, входящих в его состав, вычисляет двоичные компоненты локатора первой ошибки 1 =(1(6,..., 1(4,,!, ). При этом реализуются выражения, !6 166 5! 42 зЗ 24 1 45 $!6 ! Ц} I5 65 56 4! З2 23 (4 (5 1 !4 164 155 146 з! 22 + (з +S (4 s Я 69 54 145 136 2! (2 $6 ! 2 62 Я 44 Я 26 4! (2 5 1!! 6! 152 143 154 125 1 (5 < 45 (О 6 52 43 ЗФ 25 (6 (О (Если g=0 или g=1, то на вход формирователя 12 из вычислителя 8 поступают нули и на выходе сумматора 13 фор- 5О мируется локатор i4 =$!. Сумматор 10 с помощью сумматоров по модулю два с прямыми и инверсными выходами, входящих в его состав, вычисляет локатор ВТОрОН ошибки 12=(126 ° ° ° > 12! 12о ), при этом реализуются выражения 26 66 к 42 Ъ3 24 (5 1 25 l 65 +l 5g+hwr +h sz +h25 +h ! р +1 +146+ 41+h 22+ !3 s ,24 64 . 55 24 — 163 +154+145 +196 2! !2 162 +155 + 44+ 35 26+ н 1 2! — 161 + 52 4э 44 25 (6 > 12о h64 +h52+ 43+11з4+1 25+ (6 Блок 7 обнаруживает ошибки, срав-. нивая с нулем величины $4, $„ и P„ При этом с помощью логических элементов И, ИЛИ и НЕ, входящих в состав блока .7, реализуются соотношения, вычисляющие двоичные сигналы Р4 F2, F H n0, У $67. Л$5 VS ,1о ° ° О, если $ =.0 1, если S ф0, j=1 2,! (7) F=FVF Я О, если N78 =0 1 е 7 (8) где Н вЂ” количество ошибок в Разря ! ( дах а(а78, U — знак логической операции ИЛИ, No=PUP = з О, если в слове а ошибок нет I ! 1, если в слове а ошибка есть.(9) Сигнал М4, с выхода блока 7 поступает на выход 19 для использования в системе, включающей предлагаемый декодер. Сигнал Р с выхода блока 7 поступает на входы корректора 5 и блока 9, а также на управляющий вход 15 корректора 11. Сигналы F F поступают на блок 9. Корректор 11 дешифрирует локаторы i, i2 и корректирует разряды а а . Локатор it, поступающий на второи корректирующий вход корректора 11, разбивается на две части. Младшие тРи РазРЯДа (i 1 о,1 (о) постУлают на информационный вход дешифратора 23, а старшие четыре разряда (1(6 1 (5 s 1 (q s 1() HB ИНфОРМаЦИОН ный вход дешифратора 24. Аналогично старшие Разряды лоКатОра 12 (i 26 125 ° 124 s 12y ) поступают С ВТОРОГО КОР ректирующего входа корректора 11 в дешифратор 21, а младшие разряды (122 12! "го), — в дешифратор 22. Сигнал F с управляющего входа корректора 11 поступает на управляющие входы дешифраторов 22 и 23. 1190525 Если F=l; то дешифраторы 22 и 23 открыты. В этом случае дешифратор 23 формирует разрядное двоичное слово b=(bo,b 1 ..., Ь. ) с одной единицей в разряде, соответствующем коду на информационном входе дешифратора. Аналогично дешифратор 22 формирует 8-разрядное слово с одной единицей й=(Х,,й,...,f>). Дешифраторы 21 и 10 24 формируют 16-разрядные слова с одной единицей соответственно U = (ЦО эО1э ° . ° эU<+ ) H m (moým ь ° ° ° вш )Слова b,f,u,m с выходов дешифраторов 21-24 поступают в блок 25 и, кроме 15 того, проходят на второй выход корректора 11, откуда поступают в формирователь 14. Блок 25 формирует инверсное корректирующее слово Е=(Е,,...,Е ). Двоичный сигнал Е =О, если на первый корректирующий вход или на второй корректирующий вход корректора 11, поступил локатор j ro разряда. В противном случае, сигнал Е> =1. Таким образом, в блоке 25 выполняется вторая ступень дешифрации и объединение (по ИЛИ) соответствующих сигналов. В сумматоре 26 корректируются и исправляются разряды а,.„ З0 а путем реализации соотношений а =а k Е ; 3=1,2,...,78. (/ Если ошибок в разрядах а,...,a> ° ° ° у нет, то сигнал F=O и дешифраторы 22 и 23 закрыты. В этом случае, независимо от значений сигналов на соответствующих входах, на выходах дешифраторов 22 и 23 формируются нулевые слова, и корректирующее слово Е состоит из единиц Е=(1,...,1) Раэря-40 ды a,..., а проходят на выход 17 1 без изменения ° Если локатор i1 или iz является исключением (элемент поля GF(2 ) не ис7 пользуемый в качестве локатора) и .. 45 f / есть ошибки в разрядах a»...,a, то необходимо отказаться от декодирования. Это выполняет формирователь 14. Он анализирует, являются ли, i исключенными, и формирует сигна- gg лй Е1,Zz в соответствии с выражением О, если локатор i не исключенный, Z"= 1 если локатор i исключенный. Формирователь 14 реализует соотноше-. ния 2 =3 5 1 jq VUgVUiz Ж,з Ьб ф (10) К, = „iz4Vm>Vmi. Vme fs (11) Сигналы Z Z поступают в блок 9, который с помощью сумматоров по модулю два и логических элементов И, ИЛИ, НЕ, входящих в его состав, формирует двоичные сигналы Ви11 B=g, " V>,VS. = О, если g 1, 1, если g f 1; (12) И, „= (Г„+Fy) VFB(DVZ ЧР) VFZ О, если на выходе 17 исправленное слово 1, при отказе от декодирования (13) FB = 1 в случае, когда хотя бы одно S ф О и g g 1. Отказ от декодирования при S1=0, S фО и S f О, 8 =О обеспечен членом F +F . Если S f О, S j. О, g 41, то отказ от декодирования вырабатывается в любой из трех ситуа--ций: D=1, уравнение (3) не .имеет решений; 2 =1, локатор i< — исключенный, Р=1, количество ошибок нечетно. Кроме того, отказ от декодирования вырабатывается независимо от значе-. ния g если S1фО, $ 60 и Е1 =1 (т.е. локатор i< — исключенный). Корректор 5 корректирует разряд а, реализуя при этом соотношение E =PFVPBF, a =а. +Е,=а, +P+F+BF+BPF. (14) Функционирование вычислителя 8 saключается в том, что старшие разряды (g< g % 84 gз) aеличины g поcтупа ют на вход дешифратора 28, а младшие разряды (g,g,g ) — на вход дешифратора 29, На выходах этих дешифраторов формируются соответственно 16 — разрядное слово с=(с,,с,,..., с, ) с одной единицей и 8-разрядное слово Р=(Р,P1,...,P ) с одной единицей. Слова с и р поступают на блок 30, где формируются 15-разрядное двоичное слово й=.(й1,..., CI5-) и 12-разрядное двоичное слово g=(g>,. ° ., g, ) . .Если уравнение (3) не имеет решений (0=1), то все разряды слов и q равны единице. Если равнение (3) имеет решение (D=O), то один разряд в каждом из слов 1,п может быть равен нулю. Разряд t равен нулю, если старшие разряды (хб х5 х4,хз) реше ния образуют число j. Таких случаев ровно четыре, поскольку все 63 решения уравнения (3) различны. 14 13 1190525 Для формирования разряда t в блоке 30 реализуется логическая функция И-ИЛИ-НЕ вида а для формирования разряда q ) — функция вида q = С Р ЧСИР ЧС, Р ЧфР. (16) Слова t u q из блока 30 поступают в блок 31, где с помощью элементов И-НЕ выполняется окончательное объединение сигналов, и формируют раз.ряды х,..., х . При этом реализуются выражения i q З Л9 ю ig у х = 5 6 t 6 g fp и 12 ) ) 3 5 > 9 11 H )5 3 6 7 !оган С1 С 5 1 5 4 5 4 F t (ã В t I4 " N э Ь 8 9 ю и !2 Я м (3 ° В дешифраторе 32 реализуется выражение Р = >1Чх Ч.. ° Чхg Функции, выполняемые умножителем 6, аналогичны функциям, выполняемым формирователем 12 и сумматором 13. В блоке 7 формируют в соответствии с выражением (7) величины F, I Б(6 ЧБ!5 V. USfp и Р2 Б76 ЧБ2%Ч ° ° ЧБ7 В элементе ИЛИ 44 формируется величина F=F< VF< . На выходе 19 сформирован сигнал Ыо=РЧР, В случае, если К /64, устройство работает аналогично. При этом локаторы разрядов являются элементами поля СР(2 ), система (2) и уравнение (3) решаются над полем GF(2 ), все операции декодирования выполняются в поле GF(2®), где m=)log>ag, n=K+2m+1. Другими .словами, поле СГ(2 ) заменяется полем GF(2 ). Например, если К= =128, то m=8, и все операции при работе устройства выполняются в поле GF(2 ). 1б ° о о %» о % % % о о D О а о о %» о %% о о о С> о о о т о Ю о о % о л фЬ л Ch Ch Ф> Ю о о о т т ь о о о D о о о, ;о> ° » f ° о О> Ol л 1 % л. ь Ю о С> о о о, о. о „1!.% 1 1 о D о о а о С> т о о Ю с0 1 О ь D о .о о Ю О т о %» о С> 1 I сс> о,, о D, о б о о о О Ю о о о С> D. С> о о о о л ! % о> ф\ Ch фЪ л D о, о т о О о о о ь О о ь С>, Ю т т т I %%% %%% %1>! л > Ch Ф> л 1 .л %» С> %» о о о о о о О О .о аЮт о о о о о D о С> ь о О о о о Ю о о %» Ю Ю о Ю о Ю о о а Ю О о о о а D о О D о Ю о О О о о С> С> С> Ю О о а D о о Ю С> ь С> Ю О ,о о о С> Ю Ю Ю о а о о .о о о о I ! 1 ! >>1 Щ о с> О Ю о D о Ю Ю б о Ю С> С> Ю о о Ю о о D о Ch .о> Ch Ch л л и Ю D а Ю о О о о о а Ю О о ,Ю о. о Р о >О %» О С> О С> Ю о ь о О, о С> Ю т .О Ю Ю Ю о % ь С> С> Ю %> ь 1 ° >%% О Ю Ю о о о о о о о о т О Ю Ю Ю D о Ю Ю о D Ю Ю С> Ю Ю Ю о % о Ю о Ф ф> л .Ch в Ch л о О Ю о Ю ь Ю Ю о о О Ю о о С> о D о о о ° ° ° ° Ю Ю D о Ю Ю Ю о о. Ю О о о о С> о Ю С> ь о о Ю о С> С> Ю о Ю ° ° о Ю л л Ch л л >п о> т Ю о О D Ю Ю Ю о о о о % о о О т С> Ю о о о С> О Ю о о Ю Ю D о о Ю. Ю Ю Ю Ю С> Ю ь D о о Ю Ю о о С> Ю л %Cl >> л Ю ° Ю Ю Ю Ю о Ю Ю о о С> Ю о Ю Ю Ю Ю о С> Ю Ю Ю Ю Ю о о Ю Ю О Ю о Ю о о о Ю т т С> % %» т т о о о Ю Ю О о О ° о о О Ю о -о о Ю о о О о о о С> О о Ю С> о Ю о D ь Ю о Ю Ю Ю Ю о о Ю Ю о С> С> Ю о о о Ю о Ю О о О о о С> Ю о о О о о о о о Ю С> Ю Ю Ю о о о О о о о >Ю (— -%-4 ы Й l %c> ф О Фч I, t I 1 .! о Ц о И 3 й! с>с Р c>I с>а 1 сС I 1 >м 1 % I >>3 о ClI 1 c%. %%% 1 ° 1 сч I cc> 1 1 %%% ач 1 — 4 1 ао 1 %Ф 1 (1 е 1 1 %>> 1 g М1 сс> 1 1190525 3.Я, О о 3 D e» е ° %» о ° о о о о %» %» о ° ° о о Ф %» о о о о % Я ° % а Ю> л Ю 1» 1Л ф% а фЪ 17 18 Ф» Ф о Ф» Ф Ф Ф» о. о ф ф 1Ч - ь «! ф » (о л ° . 1Ч л о о .О о Ф» Ф» О Ю ь о о О о о Щ к IC к О Cl о, Q Ф о о о Ф Ф Ф О о о О о Ф м Ф ° » Ф» О Ф о Ф о Q Ф» о о о о Ф Ф Ф Ф м ° О Ф со о о О о о Cl о о о о о о о Ф Ю Ф Ф о ь Cl о О о о Ф» Ф о ь Ю 3 м о - о л о о D о о о о о о о Ю Ф » Ф о о о о о о о о о О Ю Cl C) Ю о о О Ч о о о о о о о о Ф Ф Ф» Ф Ф л an 0;) ФМ о Ю о ь о О о о О о о. о оО О о О o о Ф» о 3 о о о ь Ю о Ю Ю Ю Ю Cl Cl Ю о о 3 ь Ю Ю о о о о О о о о о о Ю Ю о О Ю Ю о о О Ю о о о ° » Ю Cl О О Ю о Ю о о. Ю о Ю Ю л Ю о о .о ь Ю о о о о Cl О Ю Ю Ю о о D о Cl Cl -О ОЮЮ Ю 3 о Ю Ю ь Ю о о Р о о ь о О О о о. Ch м С4 м ь Ю Ю D о о ь о ь Ф о о Ю Ю Ю о Cl Cl Ю Ю о Ю C) Ю о Ю ь Ю о о Ф» о о о О Cl о о о О о Ю Ю Ф о о м СЧ о. Ю Ю о о о ,ь ь Ю Ю ь о Ю Ю Ю Ю Ю Ю о о о Ю Ю Ю Ю Ю Ю Cl Cl Cl Ю Ю Ю о Ю ь о О о ь О о Cl Ю Ю о о Cl ь Ю ь D о о Cl м С4 О ь ь о Ю ь о о ь о о о Ю Ю Ю Ю Ю 3 ЮЮО Ю о Ю Cl Ю Ю Ю Cl о Ю Ю Ю о о о о о о Ф» О ° Ю ь Q о о о о о о Ю о Ф о Ю о о 8 8 о Cl Cl Ю Ю Ю ь Ю ь Ю Ю о О ь о о о Ф» Ю ь о Ф» Ф о Ю ь ь О Ю о о Cl о Ф Ю ь Ю о ь о о о Ю %» Ю о о о Cl Ю Ю ь о Cl Cl Cl о Ю ь о о к а о а,о ЗФ а а ф (-„в I 1-Ж I ф pe! К -.1Ф а 1ф1 с ° 1 :! i -» I О Зе С» а61 1 CI 4L В gI . 1190525 о о о ° Ф о Ю ° о о о Q о Q ч о о Ф» а1 4 I и I о аю о ахи а !» аа-Ф э маг м СЧ ° » .L., I ф о х e I lIO а аа фд офорт ж о к (еч 19 I ) 90525 20 о о о о о D о О О О о о О о ь о о о D D -ь о Ю о о о о D о D ь о с6 О Ю С1 о о о о о О о о О D ь о о о о о о Ю ь ь о о о о о о о D о ь о о о Ю о о ь Ю о о о о о о о Ю о D о . О D Ю о о D о. о о! Ю ь О О Ю Ю О о о о о О Ю ь о о о о о о о о о Ю ь о о о D о D Ю о о о о о о о о Ю о о Ю Ю О с 1 с cd 1 I ц ! I 1 I 1 I 1 1 1 l I 1 I 1 I I 1 I 1 l ) .I I I I 1 I I I ! I ! I I 1 I l I 1 I 1 ) 1 1 Е I I ° I м! «л, 1 cd ч I 1 cd 1 ° 1 1 ° 1 1 ° I е 1.,ф 1 cd) !.1 1 I l 1 I 6 1 1 1 1 cd I 1 ° 1 св) Ф 1 <6 I 3 чi I cd I Е) м. I cd 1 1 I I I 1! ьl 1 - t I cd I l ° I I ° I 1 ° 1 I a I I « I 1 1 1 1 I o I Нъ 1 ° 1Ф 6) 1 1 I 1 . I I I I - l N ill I cd!! ° 1 ° f v t l. ev 1 I 6) ff 1 I I I «) Ь с6 1 1 ° I I iр I м I, Ф 1! 1 1, 1 1 - I f Ф 1 l ° I I 1 ° 1 1 «001 1 cd) I ) — ! I I t 1 )- » 1! (6! ° I! . ° ) 1 ° I t 1 I <6 1 I l I, ! 1 1(I t 1 I I I I I. I 1 1 (I ! ) I 1 1 ! l ! 1)90525 1190525 Составитель Б. Ходов Техред А.Бабинец Редактор О. Юрковецкая Корректор А.Зимокосов Заказ 7003/59 Тираж 871 ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раувская наб., д. 4/5 Подписное Филиал ППП "Патент", г. Ужгород; ул. Проектная, 4
