Устройство для кодирования и декодирования информации

 

УСТРОЙСТВО ДЛЯ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ ИНФОРМАЦИИ, содержашее группу из тринадцати кодирующих сумматоров по модулю два, группу блоков декодирования нечетных разрядов , группу блоков декодирования четных разрядов, блок обнаружения двойных ошибок, причем выходы кодирующих сумматоров по модулю два группы являются выходом кодированной информации устройств, первые входы кодирующих;, сумматоров по модулю два группы ( 8) образуют вход кодирующей информации устройства , отличающееся тем, что, с целью сокращения аппаратурнвга затрат, каждый блок декодирования нечетных разрядов группы содержит четыре сумматора по модулю два, четыре элемента И и злемент ИЛИ, каждый блок декодирования четных разрядов содержит три сумматора по модулю два и мажоритарный элемент, блок обнаружения двойных ошибок содержит два сумматора по модулю два, элемент ИЛИ и два пороговых элемента с порогом два из четырех, причем в каждом блоке декодирования нечетных разрядов выход первого сумматора по модулю два сЪединен с первыми входами первого, второго и третьего элементов И, выход второго сумматора по модулю два соединен с вторым входом первого элемента И и первым входом четвертого элемента И, выход третьего .сумматора по модулю два соединен с вторыми входами второго и четвертого элементов И, выход четвертого сумматора по модулю два соединен с вторым входом третьего элемента И и третьим входом четвертого элемента И, выходы первого, второго, третьего и четСП вертого элементов И соединены с входами элемента ИЛИ, выход которого является выходом соответствующего с. нечетного разряда декодированной информации устройства, в каждом блоке декодирования четных разрядов группы выходы сумматоров по модулю два соединены с входами мажоритарного эле-vl мента, выход которого является выО5 ходом соответствующего чётного раз- 4; ряда декодированной информации устройства , в блока обнаружения двойных ошибок выходы первого и второго сумматоров по модулю два срединены соответственно.с первыми входами первого и второго пороговых элемент тов с порогом два из четьфех, выходы которьпс соединены с входами элемента ИЛИ, выход которого является выходом двойной ошибки устройства, второй вход каждого i -го кодирующего сумматора по модулю два группы

СОЮЗ СОВЕТСКИХ . СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (1% (И) зад G 06 F 11 08

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

r1O ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTHA (Я»

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMY СВИДЕТЕЛЬСТВ (21) 3613420/24-24 (22) 29.06.83 (46) 07.10.84. Бюл. В 37 (72) К.К. Ещин, В.И. Заровский и Е.П ° Маслюков (53) 681.3(088.8) (56) 1. Хетагуров А.Я. и др.

Повышение надежности цифровых устройств методами избыточного кодирования. N. "Энергия", 1974, с. 53, рис. 2-2, с. 54, рис. 2-3, с.37-38.

2. Патент США 3601798, кл. 340-146.1, опублик. 1971 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ КОДИРОВАНИЯ

И ДЕКОДИРОВАНИЯ ИНФОРМАЦИИ, содержащее группу из тринадцати кодирующих сумматоров по модулю два„ группу блоков декодирования нечетных разря" дов, группу блоков декодирования четньгх разрядов, блок обнаружения двойных ошибок, причем выходы кодирующих сумматоров по модулю два группы являются выходом кодированной информации устройств, первые входы -х кодирующих;. сумматоров по модулю два группы (1 < 1 «ь 8) образуют вход кодирующей информации устройства, о т л и ч.а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, каждый блок декодирования нечетных разрядов группы содержит четыре сумматора по модулю два, четыре элемента И и элемент ИЛИ, каждый блок декодирования четных разрядов содержит три сумматора по модулю два и мажоритарный элемент, блок обнаружения двойных ошибок содержит два сумматора по модулю два, элемент.

ИЛИ и два пороговых элемента с порогом два из четырех, причем в каждом блоке декодирования нечетных разрядов выход первого сумматора по модулю ,два соединен с первыми входами первого, второго и третьего элементов И, выход второго сумматора по модулю два соединен с вторым входом первого элемента И и первым входом четвертого элемента И, выход третьего .сумматора по модулю два соединен с вторыми входами второго и четвертого элементов И, выход четвертого сумматора по модулю два соединен с вторым входом третьего элемента И и третьим входом четвертого элемента И, выходы первого, второго, третьего и четвертого элементов И соединены с входами элемента ИЛИ, выход которого является выходом соответствующего нечетного разряда декодированной информации устройства, в каждом блоке декодирования четных разрядов группы выходы сумматоров по модулю два сое-динены с входами мажоритарного элемента, выход которого является выходом соответствующего четного разряда декодированной информации уст.ройства, в блоке обнаружения двойных ошибок выходы первого и второго сумматоров по модулю два соединены соответственно. с первыми входами первого и второго пороговых элементов с порогом два из четырех, выходы которых соединены с входами элемента ИЛИ, выход которого является выходом двойной ошибки устройства, второй вход каждого j -го кодирующего сумматора по модулю два группы (1 i 4 8) соединен с входом (1 +

1117641

+ ())mop 8)-го разряда кодируемой информации устройства, 6 -й вход .каждого (9 + ) )-го кодирующего сумматора по модулю два группы (1 @ 8 & 3; 0 « j 4 3) соединен с входои 1 + (0 + 2-)mod 81-го разряда кодируемой информации устройства (01 = 0; 0 2 2; с = 3), входы триЬ надцатого кодирующего сумматора по модулю два группы соединены с входами всех четных разрядов кодируемой информации устройства, в каждом о -м блоке декодирования нечетных рязрядов группы (16 4) первый вход каждого 0 -ro сумматора по модулю два (1 4) соединен с входом (9 +

+ (b„ +g )mop 4J-го разряда декодируемой информации устройства (Ь1

= 3; Ъ2 = 0; b> 2; Ъ = 1), 8 -й вход каждого г -ro сумматора по мо- дулю два (9 = 2 для г = 1 и 24 56 4 для 2 + г 4) соединен с входом (1 +

+ (С z > + 2с ) mo3 8) -го разряда декодируемой информации устройства (С1 = 0; С 2 = 2; С2 = 7; Cg4= 6;

СЭ2 4> С = 5; СЗ4= 6; С4г 2;

С = 3; С = 5) в каждом (-м бло1 44 ке декодирования четных разрядов группы первый вход кажцого И -ro сумматора по модулю два (1 и 6 3) соеI

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

ЭВМ с защитой информации от искажений при хранении или передаче корректирующим кодом.

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

J0

Недостатком этого устройства является большая задержка, возникающая на декодирующей стороне из-за динен с входом (9 + (Ь„ q ) os 41-го разряда декодируемой информации устройства (Ь1 = 3; b2 = 0; Ь =- 2),, П -й вход каждого Yl --го сумматора

bio модулю два (2 N 6 3) соединен с входом (1 + (С„„„ + 2))e0d 8j -го разряда декодируемой информации устройства (С г = 0; С1 = 6; С = О;

С,1. = 7; С 3 = 4; С = 5), первый, второй, третий и четвертый входы первого сумматора по модулю два блока обнаружения двойных ошибок соединены соответственно с входами четвертого, шестого, одиннадцатого и тринадцатого разрядов декодируемой информации устройства, первый, второй, третий и четвертый входы второго сумматора по модулю два блока обнаружения двойных ошибок соединены соответственно с входами второго, восьмого, девятого и тринадцатого разрядов декодируемой информации устройства, второй, третий и четвертый входы первого и второго пороговых элементов с порогом два из четы-. рех соединены с выходами первого, второго и третьего сумматоров по мо-: дулю два первого и третьего блоков декодирования четных разрядов группы соответственно. последовательного включения блоков при декодировании.

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

Известное устройство обнаружива- 20 ет все двойные ошибки и обладает меньшей кодовой избыточностью; код (14,8) исправляет одиночные и обнаруживает двойные ошибки; является достаточно быстродействующим на де- . 25 кодирующей стороне (не считая. узла обнаружения двойных ошибок) $2) .

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

Целью изобретения является сокраще- ние аппаратурных затрат.

Поставленная цель достигается тем, что в устройстве для кодирова- 40 ния и декодирования информации, содержащем группу из тринадцати кодирующих сумматоров по модулю два группу блоков декодирования нечетных разрядов, группу блоков декодирования 45 четных разрядов, блок обнаружения двойных ошибок, причем выходы кодирующих сумматоров по модулю два груп" пы являются выходом кодированной информации устройства, первые входы 50 -х кодирующих сумматоров по модулю два группы (1 < 8) образуют вход кодирующей информации устройства, каждый блок декодирования нечетных разрядов группы содержит четыре 55 сумматора по модулю два, четыре элемента И и элемент ИЛИ, каждый блок декодирования четных разрядов со7641 4 держит три сумматора по модулю два и мажоритарный элемент блок обнаружения двойных ошибок содержит два сумматора по модулю два, элемент ИЛИ и два пороговых элемента с порогом два из четырех, причем в каждом блоке декодирования нечетных разрядов выход первого сумматора по модулю два соединен с первыми входами первого, второго и третьего элементов И, выход второго сумматора по модулю два соединен с вторым входом первого элемента И и первым входом четвертого элемента И, выход третьего сумматора по модулю два соединен с вторыми входами второго и четвертого элементов И, выход четвертого сумматора по модулю два соединен с вторым входом третьего элемента И и третьим входом четвертого элемента И, выходы первого, второго, третье»

ro и четвертого элементов И соединены с входами элемента ИЛИ, выход которо-. го является выходом соответствующего нечетного разряда декодированной. информации устройства, в каждом блоке декодирования четных разрядов группы выходы сумматоров по модулю два соединены с входами мажоритарного элемента, выход которого является выходом соответствующего четного разряда декодированной информации устройства, в блоке обнаружения двойных ошибок выходы первого и второго сумматоров по модулю два соединены соответственно с первыми входами первого и второго пороговых элементов с порогом два из четырех выхоЭ ды которых соединены с входами элемента ИЛИ, выход которого является выходом двойной ошибки устройства, второй вход каждого < --го кодирую" щего сумматора по модулю два груп-пы (1 j 6 8) соединен с входом j1 +

+ ()mod 8)-ro разряда кодируемой информации устройства, 3 --й вход каждого (9+ ) )-го кодирующего сумматора по модулю два группы (1 Е Р и 3;

0 4j 3) соединен с входом (1 +

+ (О +2>)п од 8)-го разряда кодируемой информации устройства (0, = О; a = 2; О 3), входы тринадцатого кодирующего сумматора по модулю два группы соединены с входами всех четных разрядов кодируемой информации устройства, в каждом 0 -м блоке декодирования нечетных разрядов группы (1ь g f 4) первый вход

111764:f ветственно с входами второго, восьмого,. девятого и тринадцатого разрядов декодируемой информации устройства, второй, третий и четвертый входы 40 первого и второго пороговых элементов с порогом два из четырех соединены с выходами первого, второго и третьего сумматоров по модулю два первого и третьего блоков декодиро- 45 вания четных разрядов группы соот" ветственно. каждого о -го сумматора по модулю два (1<г 6 4) соединен с входом

1.9 + (b„+ )вод 4)-го разряда декодируемой информации устройства (Ь1 * 3; b2 - 0; b3 * 2; Ъ4 1), б -й S вход каждого г -го сумматора по модулю два (5 2 для г 1; 2cgc4 для 2 и и 4) соединен с входом (1 + (С„ + 2с )во<3 8)-го разряда декодируемой информации устройства (С1 0; С 2 2; С2 7; С24

6; С 2 4; C 11= 5; С 4 6;

С4 2; С4 .,3р С44 5), в каждом

42 (-м блоке декодирования четных разрядов группы первый вход каждого и -го сумматора по модулю два (1 4 и 4 3) соединен с входом (9 +

+ (Ъ„ + g )maÄ 4)-го разряда декрдируемой информации устройства . (Ь1 = 3; Ь2 = 01 Ъ = 2), 1т)-й вход каждого и "го сумматора по модулю два (2 4П1 4 3) соединен с входом (1 + (Сп + 2g)mod 8)-ro разряда декодируемой информации устройства (С 2= 0; С4 = 6; С22= 0;

С23 7; С.32= 4; С = 5), первый, второй, третий и четвертый входы . первого сумматора по модулю два блока обнаружения двойных ошибок соединены соответственно с входами чет- 30, вертого, шестого, одиннадцатого и тринадцатого разрядов декодируемой информации устройства, первый, второй, третий и четвертый входы второго . сумматора по модулю два блока обнаружения двойных ошибок соединены соотг»

На фиг. 1 приведена структурная. схема устройства для кодирования 50 и декодирования. информации, на фиг ° 2.— функциональная схема блока декодирования четных разрядов группы; на фиг. 3 — функциональная схема блока декодирования нечетных разрядов группы; на фиг. 4 — функциональная схема порогового элемента.с порогом два из четырех.

Устройство для кодирования и деко дирования информации (фиг. 1) содер- жит входы 1 — 8 кодируемой информации устройства, группу кодирующих сумматоров 9 - 21 по модулю. два, выход 22 кодированной информации устройства, выход 23 двойной ошибки устройства, вход 24 декодируемой информации устройства, группу блоков

25 — 28 декодирования нечетных разрядов и группу блоков 29 — 32 декодирования четных разрядов, блок 33 обнаружения двойных ошибок, содержащий пороговые элементы 34 и 35 с порогом два из четырех, элемент

ИЛИ 36, входы 37 и 38 пороговых элементов с порогом два из четырех и сумматоры 39 и 40 по модулю два.

Блок 29 декодирования четных разрядов (фиг. 2) содержит мажоритарный элемент 41 и сумматоры 42 — 44 по модулю два.

Блок 25 декодирования нечетных разрядов (фиг. 3) содержит элементы И 45 - 48, элемент ИЛИ 49, сумматоры 50 — 53 по модулю два.

Пороговый элемент 34 с порогом два из четырех (фиг.,4) содержит сумматоры 54 и 55 по модулю два, элемент ИЛИ 56, элементы НЕ 57 и 58 и элемент И 59.

Подключение входов кодирующих сумматоров 9 — 21 по модулю два к входам 1 — 8 кодируемой информации устройства приведено в табл. 1

Подключение входов сумматоров блоков 25 — 32 декодирования четных

-и нечетных разрядов с номером и к входам 24 разрядов декодируемой информации устройства приведено в табл. 2. В графе "Номер g,áëoêà" приведен номер блока декодирования ,в соответствующей группе. В графе

"Номер информационного разряда" приведены номера разрядов декодированной информации, соответствующие блокам декодирования. В графе ."Номер .сумматора .1 " приведены входы разрядов де.кодируемой информации устройства, с которыми соединены входы соответствующих сумматоров в каждом блоке декодирования. В графе. 4 для блоков декодирования четных разрядов (в скобках) приведены входы разрядов декодируемой информации устройства, с которыми соединены входы сумматоров по модулю два блока 33 обна, ружения двойной ошибки для получеI 1176 ния на их выходе значения соответствующего четного разряда.

Ф

Устройство для кодирования и.декодирования информации работает следующим образом. 5

На кодирующей стороне нри поступлении на входы 1-8 устройства коди- . руемой информации сумматоры 9 — 21 формируют 13-разрядный корректируюI щий код в соответствии с табл. 1 и

1О выдают его на выход 22 кодированной информации устройства..

Декодируемая информация поступает на выход 23 устройства. При отсутствии в коде искажений все сумматоры по модулю два блоков 25 — 32 декодирования четных и нечетных разрядов (фиг. 2 и 3) формируют пра» вильные значения соответствующих информационных разрядов, которые передаются на выходы декодированной информации устройства. Сумматоры 39 и 40 блока 33 обнаружения дврйных ошибок формируют значения второго и шестого разрядов, которые вместе с тремя такими же значениями, сфор- мированными в соответствующих бло- ках 26 и 30 декодирования этих раз-; рядов, поступают на входы пороговых элементов 34 и 35 с порогам два из четырех. Так- как .сигналы на всех входах каждого порогового элемента 34 и 35 совпадают, на их выходах и на выходе элемента ИЛИ 36 сигнал двойной ошибки отсутствует. 35

При наличии в поступившем на вход

24 устройства корректирующем коде одиночной ошибки в любом разряде, кроме тринадцатого, устройство работает следующим образом.

В блоках 29 - 32 декодирования четного разряда группы (фиг.2) в соответствии с табл..2 одиночная ошибка может вызвать. появление неправильного результата на выходе не более чем одного. сумматора 42 - 44 по модулю два, так как эти сумматоры не имеют общих входов, и на выходе мажоритарного элемейта 41 формируется правильное значение информационного декодированного разряда. В блоках

25 — 28 декодирования нечетного разряда группы (фиг. 3) в этом случае возможны три ситуации, которые рас смотрим применительно к узлу декодиро55 вания первого разряда 25 (табл. 2).

Может оказаться искаженным выходной сигнал первого .сумматора 50 по

41 8 модулю два (при искажении разрядов

9 или 3 кода), а выходы остальных сумматоров 51 — 53. искажены не будут так как их входы не подключены к входам искаженных разрядов. В этом случае на выходах первого 45, второг .

46 и третьего 47 элементов И сигнал будет равен нулю, а на выходе чет-. вертого 48 элемента И он будет равен правильному значению данного информационного разряда (из-за совпадения сигналов сумматоров 51 — 53), которое и появится на выходе элемента ИЛИ 49.

Может оказаться искаженным выходной сигнал одного из сумматоров 51

53 из-за ошибки в разрядах. 2, 6, 7, 10, 11 и 12. В этом случае на выходе четвертого элемента И 48 и одного иэ элементов И 45 — 47.сигнал будет равен нулю, а два других элемента И сформируют правильное значение выходного разряда (вследствие совпадения сигналов на выходах первого 50 и двух из остальных 51 — 53 сумматоров), которое появится на выходе элемента ИЛИ 49.

Могут оказаться искаженными сигналы двух сумматоров 51 — 53 иэ-эа ошибки в разрядах 1, 5 и 8. При этом выходной сигнал первого сумматора будет правильным и вместе с неискаженным сигналом одного из сумматоров 51 — 53 сформирует на выходе одного соответствующего элемента

И 45, 46 или 47 и элемента ИЛИ 49 правильное значение. Сигналы на выходах двух остальных элементов И 45—

47 и четвертого элемента И 48 будут равны нулю.

При искажении 13-ro разряда кода все блоки декодирования работают так же, как и при неискаженном коде.

В блоке 33 обнаружения двойных ошибок при наличии одиночной ошибки на входах каждого порогового эле мента 34 и 35 с порогом два из четырех один из сигналов, сформированных сумматорами 39 и 40 блока 33 обнаружения двойных ошибок и тремя сумматорами 42 — 44 соответствующего блока 26 и блока 30 декодирования, будет отличаться от трех других. и на,выходе элемента ИЛИ 36 и на выходе 23 двойной ошибки устройства сигнал будет отсутствовать.

При возникновении двойной.ошибки возможна неправильная работа

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

"два нуля — две единицы", либо, если искаженные разряды .подключены к одному и тому же сумматору, сигналы всех четырех сумматоров будут 2п правильными и совпадут. Но в этом случае для блока 31 декодирования . шестого разряда обязательно возникнет ситуация "два нуля — две единицы, так как разряды кода, под- 25 ключенные к одному и тому же сумматору во втором разряде, обязательно подключены к разным сумматорам в шестом разряде (аналогичная картина для сумматоров четвертого и восьмого раз-щ рядов). Б любом случае хотя бы один яз пороговых элементов 34 и 35 сформирует на выходе сигнал "1", который пройдет на выход 23 двойной ошибки устройства.

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

9 (1) 1,2

10- (2) 2,3

11 (3) 3,4

4,5

12 (4) 13 (5) 5,6

14 (6) 6,7

15 (7)

16 (8) 7,8

8,1

17 (9) 1,3,4

3,5,6

5,7,8

18 (10)

19 (11)

20 (12) 7,1,2

21 (13) 2,4,6,8 Т а б л и ц а

Номер сумматора (p ) 2 ) 3

9,3

9,3,1

11,5,6,8 (11,4,6, 13)

12,7,8,2

10,5, 2, 1

10,5,2

12,7,8,1

12,7,8

9,1,2,3

10,5

11,7, 4,3

10,5,3

11,7

11,7,4

12, 1,6,5

9,1,2

10,3,4,5 (12,6,8,13) 11,7,5, 12, 1,6

12 1 9,3,8,7

12,1,7 9,3,8

10,3,4

11,5,6,7

11,5,6 (9,8,2, 13) 10,3,4,6 (10,2,4,13) 4

9 1 блоков 25 - 32 декодирования. При этом хотя бы у одного из пороговых элементов 34 и 35 с порогом два из четырех блока 33 обнаружения двойных ошибок сигналы на двух входах будут отличаться от сигналов на двух других входах. Действительно сигналы на этих входах формируются сумматорами 42 — 44 и 39 (40) в соответствии с табл. 2 для второго и шестого разрядов, Для блока 29 декодирования второго разряда при

Номер Номер блока информацион- 1 ного разряда

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

Т а б л и ц а 1

111 7б41

123 4 1678

E) )764 j

Составитель В. Гречнев

Редактор P. Цицина Техред 3.Палий Корректор В. Гирняк

Заказ 7221/33 Тираж 698 Подписное

ВНИИПИ Государственного комитета .СССР по делам изобретений и открытий

113035„ Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4