Устройство кодирования и декодирования информации Советский патент 1992 года по МПК H03M13/22 G06F11/08 

А1 2 a Ci + а + Да,| mj Cj + i 1I}

+ 5) «i Ci.

Представление искаженных ошибок данных j-й группы в выражении (3) в виде

5j ш + Да; j mj

обусловлено тем, что появление ошибки любой кратности в любой из фиксированных

50

55

Отсюда видно, что выбирать весовые коэффициенты следует так, чтобы удовлетворялось условие

,(i 1,2п),

поскольку в противном случае все равно используется только вычет величины Q по контрольному модулю q.

Второе условие выбора также вытекает из выражения (5) и состоит в том, чтобы весовые коэффициенты не являлись делителями контрольного модуля, т.е.

OD q

или

0--3

где d - любое из натурального ряда чисел,

причем d 2S|. В противном случае вычисленный в соответствии с выражением (5) синдром ошибки для искажений Acq, кратных d, тождественно равен нулю, т.е. ошибки данной группы вида 0, d, 2d, ... по контрольному модулю оказываются неразличными, а следовательно, необнаруживаемыми.

При определении величины контрольного модуля необходимо исходить из следующих посылок.

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

Робн 1 - .

Во-вторых, для обеспечения однозначного соответствия между величиной ошибки А«| и ее синдромом (5) необходимо, чтобы величина модуля превышала число возможных ошибок Гош, обнаружение и исправление которых возможно для данного кода, т.е. необходимо обеспечить

{ «|Cj}q {ajCj}q

для всех I &. С учетом представления искаженного числа в виде (3) необходимо 5 обеспечить справедливость неравенства

{{ а + AOJ }m, Ci }q

10

Ґ{{aj+Aaj}mjCj}q,

5

0

5

что в общем случае приводит к выражению

I I - i 1 | 1 {{a, 4-Aoj}miCi- {щ +

+ ДО|Ц Cj}q 0 ,

9 vI

где знак A Xi означает вычисление

i 1

конъюнкции величин Х|. Последнее выражение для заданных значений mi, mj и конт рольного модуля q позволяет найти весовые коэффициенты О или для заданного набора Ciопределить значение q.

При таком выборе величин Ci и q обеспечивается однозначное соответствие между А г, с одной стороны, и j, с другой Это позволяет, получив, например, таблицы соответствия типа , Aq }, {q- Ar}q , Aoj }, после обнаружения ошибки обеспечить ее коррекцию, так как из (4) следует

«1 |q-Aaj) mj.

Изобретение относится к вычислительной технике и может быть использовано в устройствах запоминания и обмена информацией ЭВМ, в системах передачи данных Цель изобретения - упрощение устройства Устройство имеет вход 1 информации, вход 2 выбора режима работы, вход 3 синхронизации, элементы ИЛИ 18, 23, счетчики 19, 21, дешифраторы 20, 22, вход 24 начальной установки, корректоры 4 каналов Каждый корректор имеет вход 5 выбора режима работы, вход 6 информации, вход 7 синхронизации, входы 8, 9 управления, элементы И 10-12, 16, оегистр 13, блок 14 памяти, элемент 15 задержки, выход 17. 1 ил.

§ (2S|-1),

1

/

или, при одинаковой разрядности всех групп, т.е. при Sr S(i 1 ,n),

(2s-1).

Множитель 2 в последних выражениях обусловлен тем, что в зависимости от величины ошибки и исходного кода искажаемой группы величина г (А), рассчитанная в соответствии с выражением (1), может быть либо больше, либо меньше величины г (А), т.е. одной и той же ошибке может соответствовать либо синдром А г, либо синдром {q-Ar}q.

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

В описанном виде ВГ-код позволяет обнаружить и исправить все однократные ошибки (ошибки в одном разряде) и все те групповые ошибки кратностью Si и менее,

которые локализованы в пределах i-й группы.

Однако исправление групповых ошибок ВГ-кодом, кроме ошибок, локализованных в пределах одной из групп, не гарантируется.

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

что каждая 1-я, Я + 1, 2 А - 1, ... группы относятся к первому подслову, 2-я, А + 2, 2 А + 2, ... группы относятся к второму подслову и т.д.,А,А+А, 2А + А,... группы относятся кА-му подслову. если А - глубина условного перемёщения. Для каждого i-ro из А подслоев рассчитываются контрольные признаки г (A I), которые размещаются после исходного кода А. В процессе декодирования аналогичным образом рассчитываются г (м1) i 1,2, ..., А, дающие возможность определить

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

При этом ВГ-код выгодно отличается от других известных кодов при коррекции ошибок в словах сравнительно малой разрядности. Так, рекомендуемый международным стандартом ISO код (40,24), или в байтах (5,3), обеспечивает коррекцию однократных ошибок. Если же использовать для коррекции ошибок в исходных числах той же длины (24 разряда) ВГ-код (12,8) с глубиной пере- межения Я 3, то получают ВГ-код (36,24), который позволяет обеспечить коррекцию пакетов ошибок до трех разрядов При этом требуется избыточность в 12 разрядов, что на 4 разряда (25%), или по отношению к общей разрядности 10%, меньше, чем в коде (40,24).

При этом для таких условий ввиду малых значений q, Aa возможно использование занесенных в память таблиц соответствия Д г - ( Д а .1). Более того, ввиду малой разрядности подслов (nS) и контрольного признака mi 1од2г(А) + 1 возможны табличное кодирование и декодирование каждого под- слова в отверстии с задаваемым устройству режимом кодер-декодер Так, при кодировании по nS (в устройстве S 1) исходным разрядам, рассматриваемым как адрес числа А, можно сосчитать из таблицы (памяти) занесенные в нее заранее значение кода числа А вместе с mi разрядными его контрольного признака г(А). При декодировании по n-S+ mi разрядам кода числа А и его контрольного признака г(А) также можно сосчитать из таблицы значение неискаженного исходного кода числа А. Это факт использован в предлагаемом устройстве кодирования и декодирования.

На чертеже представлена схема предлагаемого устройства. Устройство содержит вход 1 информации, |ход 2 выбора режима работы, вход 3 синхронизации, Я корректоров каналов 4 с входами 5 выбора режима работы, 6 информации, 7 синхронизации, первым входом 8 управления, вторым входом 9 управления, первым, вторым, третьим и четвертым элементами И 10-12, 16, регистрами 13, блоками 14 памяти, элементами 15 задержки, выходами 17, первый и второй элементы ИЛИ 18, 23, первый и второй счетчики 19, 21, первый и второй дешифраторы 20, 22, вход начальной установки 24.

При этом вход 1 информации соединен с входами 6 информации всехЯ корректоров 5 4, вход 2 выбора режима работы подключен к входам 5 выбора режима работы всех корректоров 4, вход 3 синхронизации соединен с входами 7 синхронизации всех корректоров 4и входом первого счетчика 19, выходы

0 которого подключены к входам первого дешифратора 20. Все Я выходов первого дешифратора 20 подключены к первым входам 8 управления соответствующих корректоров 4. Выходы второго счетчика 21 подсое5 динены к входам второго дешифратора 22, выход которого подключен к входам 9 управления коррекцией всех А корректоров 4. Вход 5 корректора подключен к первому входу блока 14 памяти, выходы которого со0 единены с входами параллельного приема информации регистра 13. Вход 6 информации корректора подключен к первому входу первого элемента И 10, второй вход которого подсоединен совместно с вторым входом

5 второго элемента И 11 к второму входу 9 управления, а выход - к входу последовательного приема информации 13, Первый вход второго элемента И 11 соединен с входом 7 синхронизации корректора, а выход 0 с входом управления сдвигом информации регистра 13, первым входом третьего элемента И 12 и вторым входом четвертого элемента И 16, а выход последнего ко рректора, кроме того, - к входу второго счетчика 21 и

5 входу установки в нуль первого счетчика 19. Второй вход третьего элемента И 12 подключен к второму входу 9 управления корректора 4, а его выход - к входу элемента 15 задержки, а выход последнего корректора,

0 кроме того, - к второму входу второго элемента ИЛИ 23, первый вход которого соединен с входом начальной установки 24, а выход - с входом установки в нуль второго счетчика 21. Первый выход элемента 15 за5 держки подключен к управляющему входу Чтение блока 14 памяти, а второй - к входу Запись разрешения параллельного приема регистра 13. Первый и второй выходы регистра 13 совместно подключены к второ0 му входу блока 14 памяти, первый, кроме того, - к первому входу четвертого элемента И 16, а выход последнего - к выходу 17 корректора. Выходы 17 всех Я корректоров 4 подключены к соответствующим входам

5 элемента ИЛИ 18 на Я входов, выход которого является выходом устройства.

Регистры 13 предназначены для приема и последующих сдвигов информации, поступающей по входу последовательного приема либо по входам параллельного приема информации при наличии сигнала разрешения ее параллельного приема Запись или управления сдвигом Сдв.. Регистры имеют по два выхода: первый - выход старшего разряда, второй - выходы всех остальных разрядов регистра.

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

Блок 14 памяти предназначен для табличного расчета выходной величины в зависимости от режима работы устройства и входной информации При этом сигнал Кодер, поступающий на первый вход блока 14 памяти с входа 5 выбора режима работы корректора, совместно с сигналами, поступающими на второй вход блока 14 памяти с обоих выходов регистра 3, образуют адрес ячейки блока 14 памяти, по которому считывается необходимая в данном режиме работы информация при наличии на его управляющем входе разрешающего сигнала Чтение.

При этом значение сигнала Кодер, являясь значением одного из разрядов адреса, определяет ту половину записанной в блоке 14 памяти таблицы, в которой хранится требуемая для считывания информация Например, при сигнале Кодер, соответствующем единичному уровню, выбирается кодировочная половина, а при сигнале Кодер, соответствующем нулевому уровню, выбирается декодировочная половина таблицы, записанной в блоках 14 памяти В кодировочной половине таблицы в каждой ячейке записано вычисленное заранее значение адреса этой ячейки совместно с его контрольным признаком, Например, для ВГ-кода (12,8) в ячейке с адресом 1001001000001 должно быть записано 100100101111. При этом первые восемь разрядов адреса поступают с реестра 13, куда поступает подлежащая кодированию информация (10010010). Следующие четыре разряда (0000) имеют значения, соответствующие нулевым уровням сигналов, так как в режиме Кодер эта информация на регистр 13 не поступает. Последний (тринадцатый) разряд (1) поступает с входа 5 выбора режима работы. Первые восемь разрядов информации, записанной в эту

ячейку (10010010), соответствуют контрольному признаку числа, рассчитанному в соответствии с выражением (1) для того же ВГ-кода.

При декодировании, т.е при сигнале

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

адресом 100100111110 должно быть написано значение 10010010, так как последний разряд адреса (0) определяет считывание информации из декодировочной части таблицы, а использование выражений (1-5) на

этапе оасчета содержимого этой таблиц , дает г(А 1) 1111, г(А ) - {8+ 5+ 2+1 }ie 0000, Дг 0001, что соответствует искажению разряда с весом Ci 1, следовательно, вместо искаженной части кода 10010011 (с контрольным признаком 1111) следует сосчитать код 10010010 Необходимость считывания контрольного признака определяется заказчиком устройства. Схема устройства от этого не изменяется

Сосчитанная из блока 14 памяти информация в любом режиме работы устройства за- писывается по входам параллельного приема информации в регистр 13 при нали чип разрешающего сигнала Запись. Первый счетчик 19 и первый дешифратор 20 образуют узел управления накоплением и выдачей В этом узле организован счет синхроимпульсов от 1 до Я. В зависимости от состояния первого счетчика 19 возбуждается соответствующий выход первого дешифратора 20, сигнал с которого поступает на вход 8 управления накоплением и выдачей соответствующего корректора 4. Второй счетчик 21 и второй дешифратор 22 образуют узел управления коррекцией. В этом узле организован счет от 1 до п + ггп числа информационных разрядов, поступивших в каждый из А корректоров 4. При приеме последнего (п + гщ) разряда на соответствующем выходе второго дешифратора 22 формируется сигнал, поступающий на входы 9 управления коррекцией всех корректоров 4. После приема последнего информационного разряда в последний корректор на выходе его третьего элемента И 12 формируется сигнал, который через второй элемент ИЛИ 23 поступает на вход второго счетчика 21, устанавливая его в нулевое, исходное состояние.

Устройство работает следующим образом. Исходные состояния первых счетчика 19, дешифратора 20 и регистров 13 произвольные (для удобства описания - нулевые), второго счетчика 21 и дешифратора 22 - нулевые. Их начальная установка осуществляется сигналом начальной установки по входу 24 устройства. На вход устройства поступает подлежащая обработке информация в последовательном коде. В режиме Декодер эта информация содержит пА информационных разрядов, за которыми следуют miA контрольных разрядов в соответствии с вышеописанной процедурой условного перемежения, при числе разрядов в группах S 1, числе групп в подслове n nS п. В этом случае 1-й, Ј1 + 1)-й, ,,., ((п- 1)А+ 1)-й информационные разряды образуют п информационных разрядов первого подслова. 2-й, (А + 2)-й((п-1)А + 2)-й

разряды - второго подслова, 1-й (А + i)

((п-1) + )-й - 1-го подслова, а 1-й, (А+ 1)-й

((mi-1)A+ 1)-й контрольные разряды образуют ml контрольных разрядов первого подслова, 2-й, (А+2)-й((mi-1)A +2)-й разряды

- второго подсловаi-й ((гщ-1) А + )-й i-ro подслова. Одновременно с каждым информационным символом на вход 3 синхронизации поступают синхронизирующие импульсы, а для задания режима Декодер на вход 2 выбора режима работы - сигнал Кодер, соответствующий, например, единичному уровню. Этот сигнал подается на входы 5 задания режима работы всех А корректоров 4, задавая блокам 14 памяти по их первым входам режим чтения из декодиро- вочных половин хранящихся в них таблиц. Узел управления накоплением и выдачей, образованный первым счетчиком 19 и первым дешифратором 20, обеспечивает отсчет групп синхроимпульсов по А импульсов в каждой. Каждому номеру синхроимпульса в группе (от 1 до А) соответствует такой же номер выхода первого дешифратора 20, на котором при этом формируется сигнал, поступающий на вход 8 управления накоплением и выдачей информации корректора 4 с этим же номером. Этим сигналом разрешается прохождение информации с входа 6 информации корректора на вход последовательного приема регистра 13 и синхроимпульсов с входа 7 синхронизации корректора через первый и второй элементы И 10, 11 соответственно. Этот синхроимпульс с выхода второго элемента И 11 поступает на вход управления сдвигом регистра 13, на второй вход четвертого и на первый вход третьего элементов И 16, 12 соответственно, а также на вход второго

счетчика 21 и вход установки в нуль первого счетчика 19. Этим обеспечивается прием в регистр 13 очередного информационного разряда и сдвиг содержимого регистра на 5 один разряд. При этом с выходного разряда регистра 13 информация выдается через четвертый элемент И 16 на выход 17 корректора и через элемент ИЛИ на А входов 18 и на выход устройства. При поступлении оче0 редного разряда информации и очередного синхроимпульса на входы 1,3 устройства изменит состояние первого счетчика 19 и выходов первого дешифратора 20 так, что очередной разряд информации будет зане5 сен в регистр 13 следующего корректора 4, а в выходного разряда регистра 13 этого корректора очередной разряд будет выдан на выход устройства. За А тактов работы устройства будут приняты А информационных

0 разрядов.по одному в каждый корректор 4, и со всех корректоров 4 будет на выход выда: но А информационных разрядов предыдущего слова. После этого первые счетчик 19 и дешифратор 20 сигналом с выхода второго

5 элемента И 11 последнего корректора устанавливаются в исходное состояние. Этот же сигнал изменяет состояние вторых счетчика 21 и дешифратора 22. После поступления (n+ mi) А синхроимпульсов в реги0 стры 13 всех А корректоров 4 будет приняты все (n+ mi) разрядов, в том числе п информационных и mi контрольных, и выданы на выход устройства (п+гщ) А разрядов исправленного предыдущего слова. При

5 этом после приема (п+ггм)-го разряда каждого подслова на выходе второго дешифратора, соответствующему коду (n+ mi), появляется сигнал, поступающий на входы 9 управления коррекцией всех коррек0 торов 4. Этот сигнал, воздействуя на второй вход третьего элемента И 12, разрешает прохождение синхросигнала с выхода второго элемента И 11 через элемент задержки 15 на блок 14 памяти в

5 качестве сигнала Чтение. Так как сигнал Чтение с первого выхода элемента 15 задержки для блока 13 памяти задержан относительно сигнала сдвига регистра 13, то за это время в регистре

0 завершится процесс приема (n+ mi)-ro разряда информации и на его выходах будет находиться (п+ гщ)-разрядный код подслова, подлежащий декодированию.

5 при этом в блоке 14 памяти по адресу, образованному (n+mi) разрядами с обоих выходов регистра 13 и входом 5 корректора 4, производится считывание скорректированного (п+ |щ)-разрядного кода, который

поступает на входы параллельного приема регистра 13. Сигнал с второго выхода элемента 15 задержки разрешает этот прием.

После приема последнего разряда Я-го подслова на выходе третьего элемента И 12 последнего А-го корректора 4 формируется сигнал, устанавливающий вторые счетчик 21 и дешифратор 22 через второй элемент ИЛИ 23 в нулевое состояние. Устройство готово к дальнейшей работе.

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

Режим Кодер отличается от режима Декодер тем, что на вход 2 выбора режима работы подается сигнал, инверсный по отношению к сигналу декодирования и соответствующий, например, нулевому уровню. Этим сигналом обеспечивается задание блокам 14 памяти всех корректоров 4 режима чтения из кодировочных половин хранящихся в них таблиц. На вход 1 информации должна поступать информация, содержащая п Я информационных символов, подле- жащих кодированию, и гщЯсимволов, имеющих нулевой уровень, На место этих ггиЯ символов после кодирования будут записаны символы контрольного признака, В остальном работа устройства осуществляется так же, как и в режиме декодирования, за исключением того, что из блоков 14 памяти будет считываться (п+ гтц)-разрядный код, содержащий п исходных разрядов и m 1 разрядов их контрольного признака.

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

Формула изобретения

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

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

5 первого дешифратора соединены с первыми управляющими входами соответствующих корректоров, первый вход первого элемента ИЛИ является входом начальной установки устройства, выход второго де0 шифратора подключен к вторым управляющим входам всех корректоров, входы выбора режима всех корректоров объединены и являются входом выбора режима устройства, информационные вьходы

5 корректоров подключены к соответствующим входам второго элемента ИЛИ, первый и второй управляющие выходы последнего корректора группы подключены соответственно к входу сброса первого счетчика УМ0 пульсов, счетному входу второго счетчм.о импульсов и второму входу первого элемента ИЛИ, в каждый корректор введены первый, второй, третий и четвертый элементы И, элемент задержки и блок памяти, первые

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

5 выход второго элемента И соединен с вторым входом третьего элемента И, первым входом четвертого элемента И и входом сдвига информации регистра, выход третьего элемента И соединен с входом элемента

0 задержки, первый выход которого соединен с входом Чтение блока памяти, второй выход - с входом Запись3 регистра, выходы которого соединены с первыми адресными входами блока памяти, выход старшего раз5 ряда регистра соединен с вторым входом четвертого элемента И, второй адресный вход блока памяти является входом выбора режима корректоров, выходы блока памяти соединены с входами параллельного приема информации регистра, выходы второго

17178362818

и третьего элементов И последнего коррек- вторым управляющими выходами последне- тора являются соответственно первым и го корректора.