Устройство для декодирования модулярного кода Советский патент 1988 года по МПК H03M7/18 H03M13/05 

Пт

..1

Изобретение относится к вычислительной технике. Его использование в системах обработки, и..передачи информации позволяет повысить достоверность за счет обеспечения декодирования избыточного модулярного кода с повторами. Устройство содержит буферный накопитель 1, блок 5 сортировки и преобразователь 6 модулярного кода в позиционный. Благодаря введению мажоритарного блока 2 и последовательно- параллельных преобразователей 3, 4 кода обеспечивается выбор не менее К (К - весовой коэффициент) остатков, причем для каждого остатка выбирается наиболее достоверный его повтор. 3 3.п. ф-лы, 4 ил. MS (Л

Й-

25

i

3

чгп

2;

С) 00

О

Фиг.1

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

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

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

Устройство для декодирования модулярного кода содержит буферный накопитель 1, мажоритарный блок 2, первьй и второй последовательно-параллельные преобразователи 3, 4 блока, блок 5 сортировки и преобразователь 6 модуг. лярного кода в позиционный. На фиг. 1 обозначены информационные входы 7, вход 8 Пуск и вьпсоды 9.

Выполнение буферного накопителя 1 зависит от способа ввода символов мо- дулярного- кода. Если та повторов каждого символа вводится друг за другом, то это может быть сдвиговый регистр. Если же вводятся сначала первые повторы всех п символов, где п - общее число оснований модулярного кода, включая избыточные, потом вторые и т.д., то накопитель 1 представляет собой ОЗУ, запись в которое осуществляется по строкам, а считывание - по столбцам. (Шины управления накопителя 1 не показаны),

Мажоритарный блок 2 выполнен (фиг. 2) на регистре 10 сдвига, первой и второй группах И и 12 ключей, сумматоре 13, элементах 14 сравнения, счетчике 15, -элементе И 16, элементе ЗАПРЕТ 17, первом и втором элементах ИЛИ 18 и 19, первом и втором элементах 20, 21 задержки. На фиг. 2 обозначены информационные и управляющий входы 22 и 23, первые, вторые и третий вьпсоды 24-26.

Последо вательно-параллельные преоб разователи 3 и 4 кода строятся на основе регистров сдвига, содержащий каждый по п ячеек разрядностью log Р„ и log2(in-l) соответственно, где х - целая часть х плюс 1, Р,, наи- большее основание модулярного кода.

Блок 5 сортировки .выполнен (фиг. З на делителе 27 настоты, генераторе

28 импульсов, пороговом элементе 29, сумматоре 30, элементах И 31, триггерах 32, счетчиках 33 и элементах 34 сравнения. На фиг. 3 обозначены информационные и управляющий входы 35 и 36 и выходы 37.

Преобразователь 6 модулярного кода в позиционный выполнен (фиг. 4) на группах 38 ключей, блоке 39 памяти, кодопреобразователях 40 и сумматоре 41. На фиг. 4 обозначены информационные и управляющие входы 42 и 43.

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

Ключи в группах 11, 12 и 38 могут быть выполнены на элементах И.

Элементы 14.1-14 (т-1) и 34 сравнения формируют на своих выходах сигналы логической единицы при равенстве кодов на их первых и вторых входах. Элемент 14.т сравнения формирует на выходе сигнал логической единицы, если код на его первых входах (с выходов сумматора 13) не меньше кода на вторых входах (со счетчика 15).

Счетчик 15 - вычитающий от исходГт+Пкого состояния, равного

х - целая часть х до нуля.

Время задержки элемента 20 должно быть не меньше суммарного времени переходных процессов в регистре 10, сумматоре 13 и элементах 14.1-14, (т-1) и 14.т. Время задержки элемента 21 должно быть не меньше времени переходных процессов в буферном накопителе 1.

Делитель 27 частоты осуществляет выдачу импульса после поступления на его вход га последовательных импульсов.

Период следования импульсов с генератора 28 не меньше суммарного времени переходных процессов в элементе И 31, счетчике 33, элементе 34 сравнения, сумматоре 30 и пороговом элементе 29.

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

Счетчики 33 - вычитающие от исходного состоялия, равного Р.

Блок 39 памяти - ППЗУ из 2 ячеек, каждая разрядностью logjP t.

Кодопреобразователи 40 преобразуют входной код числа X в код числа

Kt X, где

Kj постоянный коэффициент.

В своей работе устройство для декодирования модулярного кода использует следующее.

Известно, что число А из диапазр; на

l-lt

можно однозначно представить совокупностью остатков ° 1, К), по основаниям Pj, i 1, К

таким, что Л oi.

Р;

к

Остатки It

1

I определяют модулярный код

t числа А.

Представив число А совокупностью остатков (6,(i °° 1 п, где п К) по взаимно простым основаниям , (i

1, п) таким, что П Р

мы

чм

получим избыточный модулярный код числа А с избыточными основаниями Pj (i .К + ,и ).

Повторив т-раз каждый остаток Л ,-, i 1, п (или все числа в целом), получим избыточный модулярный код числа А с m повторами. Очевидно, что передавать его можно двумя способами:

i.oc;,

n ot eC.

.2I v v4v

Ob I Ol Olrj ) ««j Wj

. . ,

ЛХ

и

„ « t

,... 4.

Vj

. в6 Л и

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

На первом этапе необходимо выбрать из m повторов каждого остатка одно значение, наиболее достоверное. Это можно сделать, сравнив между собой значения всех повторов, по принципу каждый с каждым, и выбрать тот повтор, значение которого встречается чаще других. Чтобы оценить достоверность выбранных значений остатков им приписываются соответствующие весовые коэффициенты K,-(i 1, п), которые численно равны количеству совпадений значения выбранного повтора со значениями других повторов этого остатка. Очевидно, что максимальное значение К,. т-1, а минимальное - равно нулю. Если веса различных значений повторов совпадают, йто с одинаковой достоверностью можно выбрать любой из этих повторов, руководствуясь, например, принципом кто поступил раньше ..

Для однозначного декодирования числа А достаточно взять К любых oc-i. татков из п имеющихся (при условии, что система оснований упорядоченная.

т.е.

10

15

20

Р,Р,

РК РКМ

. ,,,Р,

« ,

Если разные остатки lOf приняты с различными весами К;, то мы должны выбрать из них те К остатков rf , весовые коэффициенты которых максимальны. Это делается на следующем этапе декодирования,

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

25

i-s

«t,-Bj

(1)

30

где - базисные числа взятой системы оснований, определяе- мые по формуле:

В:

т,Pi

где т,-

А

Р;

N- вес базисного числа.

При наличии избыточных оснований, формула (1) имеет следующий вид:

А i6.

.ви;.

где i, L

.П Р-, ,

itu

множество номеров наиболее достоверных остатковj число членов этого множества должно быть не меньше К,

55

50

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

Устройство для декодирования модулярного кода работает следунадим образом.

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

В начальный момент времени с, вхо- да 8 подается импульс Пуск, который формирует импульс на выходе 26 блока 2, которьш, в свою очередь, поступает на управляющий вход буферного накопителя 1 и вызывает появление на его выходах значений повторов первого остатка - d - ui. Коды остатка ot, записываются в мажоритарный блок 2, которьй анализирует поступившие в него m значений первого остатка и выбирает из них один, наиболее достоверный - , j е 1J га j. Значение tL сформировано на выходе 24 мажоритарного блока 2, Одновременно на выходе 25 мажоритарного блока 2 сформи- ровано вычисленное им значение весового коэффициента К.

В тот же момент времени мажоритар- ньй блок 2 формирует импульс на выходе 26, что йызьшает сдвиг содержи- мого блоков 3 и 4 на одну ячейку.и запись р их крайнюю:ячейку кодов, присутствующих в этот момент времени на выходах соответственно 24 и 25 блока 2, Импульс на выходе 26 блока 2 поступает также на управляющий вход буферного накопителя 1 и вызывает появление на его выходах значений m повторов второго остатка о(,.

После анализа их в мажоритарном блоке 2-на его выходе 26 появляется импульс, который сдвигает на одну ячейку содержимое блоков 3 и 4 и записывает в них соответственно выбранное значение остатка d с выходов 24 и его коэффициента К с выходов 25. В то же время появление импульса на выходе 26 формирует на выходах накопителя 1 значения повторов следующего остатка, которые будут проанализиро- ваны описанным образом и т.д.

Когда мажоритарный блок 2 проанализирует все записанные в буферном накопителе 1 остатки, в блоке 3 будут записаны выбранные значения всех п остатков oi,- , а в блоке 4 - их коэффициенты К,, i 1, п.

Блок 5 сортировки сравнивает между собой все коэффициенты К-.г , выбирает из них максимальные К, i 6 L и формирует сигнал логической единицы на выходах 37.,, i е L. Преобразователь 6 в соответствии с этим

с 0 5 0

5 О

0 5

Q

5

кодом выбирает из преобразователя 3 остатки об,-, 16 L и преобразует их в число А, значение которого появляется на выходах 9.

Мажоритарный блок 2,.представлен- ньй на фиг, 2, работает следугощим образом.

Счетчик 15 находится в исходном состоянии. Импульс Пуск на входе 23 через элемент ИЛИ 18 поступает через время задержки элемента 21 на вход записи регистра 10, Под действием этого импульса в регистр 10 записываются коды остатков od, - ., присутствующие на входах 22, Элементы К.1-14,(т-1) сравнивают значения остатка записанного в первую ячейку регистра 10, со значениями остальных остатков о6 т б1 . Элементы 14, значения кодов на обоих входах которых совпадают, сформируют сигналы логической единицы на своих выходах, которые просуммируются сумматором 13. Код на выходе сумматора 13, представляющий собой значение коэффициента К., сравнивается в элементе 14.m с содержимым счетчика 15, равным

т+1 1 г.- 1/ - -g- , Р.СЛИ К,

элемента 14.m сформируется сигнал логической единицы, который поступит на первые входы элементов 16 и 17. В то же время на их вторые входы поступает импуль.с, задержанный элементами 20 и 21 задержки. Этот импульс проходил: на выход элемента И 16, на вход установки счетчика 15, через элемент ИЛИ 18 на выход 26, а.также открывает ключи групп 11 и 12, через которые на выходы 24 и 25 поступают коды й6, об, и К ,соответственно Если К - , то на выходе элемента 14.та сравнения присутствует потенциал логического нуля, который закрьшает элемент И 16 и открывает элемент ЗАПРЕТ 17 для импульса, который изменяет содержимое счетчика 15, проходит через элемент ИЛИ 19 на вход элемента 20 задержки, а также сдвигает содержимое регистра 10 на одну ячейку вправо. При этом со : держимое первой ячейки регистра 10 переписьшается в его последнюю ячейку. Теперь элементы К.1 - 14.(m-l) сравнивают остаток «i. с остальными

на выходе

остатками сумматора

oi

5

л

pi-.

На выходе

13 появляется код весового

коэффициента К , который сравнивается в элементе 14.т со значением

Гт+1 1 „ -.г Г га+П

2 сли К I -2 о импульс

на выходе элемента И 16 вызывает появление кодов fl6, dj на выходах 24,

Kj К - на выходах 25 и импульса

1

на выходе 26. Если же К

. linlLl

И 2 J

то

импульс на выходе элемента ЗАЛРЕТ 17 сдвигает содержимое регистра 10 на одну ячейку, сумматор 13 вычисляет коэффициент К, и т.д. Процесс анализа остатков проходит описанным об- . разом до тех пор, пока какой-либо К, сравняется или превысит значение

ИЕсли же этого не происходит.

то

то т-й импульс, поступивший на вход счетчика 15, уменьшает его содержимое на единицу и возвращает регистр 10 в исходное состояние. Вынисляемые аналогичным образом весовые коэффициенты Kj, j 1, га сравниваются элементом 14.m со значением I

Если не найдется К. / -и

содержимое счетчика 15 уменьшается на единицу каждые m тактов работы мажоритарного блока 2 до тех пор, пока содержимое сумматора 13 не сравняется с содержимым счетчика 15.

Если все m повторов остатка различны, то содержимое сумматора 13 равно нулю, и как только содержимое счетчика 15 также станет равным нулю, элемент К.т сформирует на своем, выходе потенциал логической единицы, который откроет элемент И 16 и импульс с выхода элемента 20 задержки пройдет через элемент ИЛИ 18 на выход 26, установит счетчик 15 в исходное состояние и открывает ключи групп 11 и 12. При этом на выходах 24 появится значение «L Л, , а на выходах 25 - значение К , К 0. Мажоритарный блок 2 приступает к анализу остатков .

Блок 5 сортировки, представленный на фиг. 3, работает следующим образом.

5 гер 32,1 в нулевое состояние и закроет элемент 31.1 для прохождения импульсов на вход счетчика 33.1, содержимое которого останется равным К 5. ЗнанЕНие на выходе сумматора 30

20 определяет количество элементов 34, на выходах-которых присутствует единичный потенциал, и как только оно . сжанет больше К - ., пороговый элег: мент 29 сформирует сигнал логической

25 единицы, который блокирует генератор 28. Процесс сортировки закончен.

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

30 Единичные потенциалы, присутствующие на входах 43.1 (где 1 е L), открывают соответствующие группы 38 и поступают на входы блока 39 памяти, который формирует на своем выходе соответствующее значение Рц.

Значения остатков ji,-, 1 б L с входов 42 через открытые ключи групп 38.1, 1е L поступают на входы соответствующих кодопреобразователей

4Q 40.1, на выходах которых формируются значения об, В,-, 1 е L, которые скла- дьгоаются в сумматоре 41 по модулю Р|. ,

Результат преобразования с выхода сумматора 41 поступает на выходы 9 1C устройства и представляет собой ис-, ходное значение числа А.

Таким образом, устройство для декодирования модулярного кода обеспечивает декодирование избыточного мо35

50

дулярного кода с повторами. Формула изобретения

т-й импульс, поступивший со входа 1 . Устройство дпя декодирования 36, формирует импульс на выходе де- 55 модулярного кода, содержащее буферный

лителя 27 частоты, который устанавливает счетчики 33 в исходное, а триггеры 32 в единичное состояниаи запу

, екает генератор 28 импульсов, Импульсы с выхода генератора 28 через открытые элементы И 31 поступают на

г входы соответствующих счетчиков 33, содержимое которых сравнивается в соответствующих элементах 34 сравнения с соответствующим значением кода на входах 35. Как только содержимое

10 счетчика 33 i сравняется со значением коэффициента К,-, присутствующим на входах 35.1, элемент 34.1 сформирует на.своем выходе потенциал логической единицы, который установит триг 5 гер 32,1 в нулевое состояние и закроет элемент 31.1 для прохождения импульсов на вход счетчика 33.1, содержимое которого останется равным К 5. ЗнанЕНие на выходе сумматора 30

20 определяет количество элементов 34, на выходах-которых присутствует единичный потенциал, и как только оно . сжанет больше К - ., пороговый элег: мент 29 сформирует сигнал логической

25 единицы, который блокирует генератор 28. Процесс сортировки закончен.

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

30 Единичные потенциалы, присутствующие на входах 43.1 (где 1 е L), открывают соответствующие группы 38 и поступают на входы блока 39 памяти, который формирует на своем выходе соответствующее значение Рц.

Значения остатков ji,-, 1 б L с входов 42 через открытые ключи групп 38.1, 1е L поступают на входы соответствующих кодопреобразователей

4Q 40.1, на выходах которых формируются значения об, В,-, 1 е L, которые скла- дьгоаются в сумматоре 41 по модулю Р|. ,

Результат преобразования с выхода сумматора 41 поступает на выходы 9 1C устройства и представляет собой ис-, ходное значение числа А.

Таким образом, устройство для декодирования модулярного кода обеспечивает декодирование избыточного мо35

50

дулярного кода с повторами. Формула изобретения

накопитель, информационные входы ко- тор ого являются одноименными информационными входами устройства, блок

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

2 а Устройство по п. 1, отличающееся тем, что мажоритарный блок выполнен на элементах сравнения, группах ключей, сумматоре, ;счетчике, элементах з адержки, элемен- {тах ИЛИ, элементе-И, элементе ЗАПРЕТ |И регистре сдвига, установочные вхо- |ды которого являются информационными (Входами блока, выходы первого разряда ;регистра сдвига подключены к первым I входам первого - (m-l)-ro элементов сравнения (т - число повторов) и информационным входам первой группы ключей и регистра сдвига, выходы

второго ,- т-го разрядов которого сое- дс ключены к входам порогового элемента.

Единены с вторыми входами Соответственно первого - (т-1)-го элементов сравнения, выходы которых подключены к входам сумматора, выходы которого соединены с информационными входами второй группы клюнай и первыми входами т-го элемента сравнения, выход которого подключен к запрещающему входу элемента ЗАПРЕТ и. первому входу элемента И, выход которого соединен с управляющими входами групп ключей, входом обнуления счетчика и первым

: входом первого элемента ШШ, второй вход которого является управляющим

50

55

выход которого соединен с входом кировки генератора импульсов.

0

5 Q 5

Q

0

5

входом блока, выходы первой и BTOjjpA групп ключей являются соответственно первыми и вторыми выходами блока, выход элемента ЗАПРЕТ подключен к так товому входу регистра сдвига, счетному входу счетчика и первому входу второго элемента ИЛИ, выход которого через первый элемент задержки соединен с разрешающим входом элемента ЗАПРЕТ и вторым входом элемента И, выход первого элемента ИЛИ соединён с входом второго элемента задержки и является третьим выходом блока, выход второго элемента задержки подключен /к второму входу второго элемента ИЛИ и входу разрешения записи регистра сдвига.

выход которого соединен с входом кировки генератора импульсов.

1411980 1112

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

Составитель О. Ревинскин Редактор С. Патрушева Техред м.Дидык Корректор М. Шадоши

Заказ 3673/56

Тираж 928

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

ФигЛ

Подписное