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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (19) (11) А3 (51) 4 Н 03 М 7/18 13/00

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

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

Фиг.1

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4184772/24-24

:(22) 20.01.87 (46) 23.07.88. Бюл. Ф 27 (7;Ц С. Н. Хлевной, А. Б. Акулинчев, Н. И. Швецов и В. В. Фомин (53) 681.325(088.8) (56) Авторское свидетельство СССР

111 1243100, кл. Н 03 М 13/00, 1984.

Авторское свидетельство СССР

Р !295528, кл. Н 03 М 7/18, 1986.

Авторское свидетельство СССР

У 960823, кл. G 06 F 11/08, 1980. (54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ МОДУЛЯРНОГО КОДА (57) Изобретение относится к вычислительной технике. Его использование в системах обработки.и передачи информации позволяет повысить достоверность за счет обеспечения декодирования избыточного модулярного кода с повторами. Устройство содержит буферный накопитель 1, блок 5 сортировки и преобразователь 6 модулярного кода в позиционный. Благодаря введению мажоритарного блока 2 и последовательнопараллельных преобразователей 3, 4 кода обеспечивается выбор не менее

К (К " весовой коэффициент) остатков, Я причем для каждого остатка выбирается наиболее достоверный его повтор.

3 з.п. ф-лы, 4 ил.

4С

1411980

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

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

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

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

Выполнение буферного накопителя 1 зависит от способа ввода символов мо- . дулярного- кода. Если m повторов каждого символа вводится друг за другом, то это может быть сдвиговый регистр.- 30

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

1 т.д., то накопитель I представляет собой ОЗУ, запись в которое осуществляется по строкам, а считывание— по столбцам. (Шины управления накопителя 1 не показаны).

Мажоритарный блок 2 выполнен 40 (фиг. 2) на регистре 10 сдвига, первой и второй группах 11 и 12 ключей, сумматоре.)3, элементах 14 сравнения, счетчике 15, элементе И 16, элементе

ЗАПРЕТ 17, первом и втором элементах 45

ИЛИ 18 и 19, первом и втором элементах 20, 21 задержки. На фиг. 2 обозначены информационные и управляющий входы 22 и 23, первые, вторые и третий выходы 24-26. 0

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

jx t — целая часть х плюс 1, Р„наи-! большев основание модулярного кода.

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

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

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

4!. На фиг. 4 обозначены информационные и управляющие входы 42 и 43.

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

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

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

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

Счетчик 15 — вычитающий от исход1 Г ш+11 ного состояния, равного (1, где (х) — целая часть х до нуля.

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

21 должно быть не меньше времени переходных процессов в буферном накопителе 1.

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

Период следования импульсов с генератора 28 не меньше суммарного времени переходных процессов в элементе

И 31, счетчике 33, элементе 34 сравнения, сумматоре 30 и пороговом элементе 29.

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

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

1411980

Н

А =j .>,В,.11., в. m <

1 где m. 40, На первом этапе необходимо вы-, брать иэ m повторов каждого остатка одно значение, наиболее достоверное.

Это можно сделать, сравнив между собой значения всех повторов, по прин- 45 ципу "каждый с каждым", и выбрать тот повтор, значение которого встре" чается чаще других. Чтобы оценить достоверность выбранных значений остатков им приписываются соответствующие весовые коэффициенты К;(i 1, n), которые численно равны количеству совпадений значения выбранного повтора со значениями других повторов этого остатка. Очевидно, что максимальное значение К; = m-1, а минималь55 ное — равно нулю. Если веса различных значений повторов совпадают, :;то с одинаковой достоверностью можно выА =l Ы;В;) 14 1.

Для однозначного декодирования числа А достаточно взять К остатков, а здесь берется не менее.К остатков °

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

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

Блок 39 памяти — ППЗУ из 2" ячеек, каждая разрядностью ) log P„l.

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

К 1. Х, где К1 " постоянный коэффициент °

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

Известно, что число А из диапазо+ на l-j можно однозначно предста к вить совокупностью остатков oL(i

1, К), по основаниям Pj i 1 ° К, таким, что .П P; r g Остатки М,, 21

Ы2,...,ь „ определяют модулярный код числа А.

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

1, n) таким, что fl Р; = Pn >3 » мы

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

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

2 113 I

1 ° 1I) 1 ° ° ° 1 д 1 ° 2 э 2 з ° ° ° 1 2 °

-1 2 III

° ° ° Э 11 1 +II ° ° ° 1 11

1 I 1 2 2 2

2., с, ° ° °, р1

Й Ь 1

III Ф у III

° e ° ° g y gti2 1 ° ° ° ф РУ11 °

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

35 ступить к декодированию необходимо

- преобразовать входную последовательность остатков к первому виду. брать любой из этих повторов, руководствуясь, например, принципом "кто поступил раньше". °

Для однозначного декодирования числа А достаточно взять К любых ос-.;. татков из и имеющихся (при условии, что система оснований упорядоченная, т.е. P, < Р с ... 4Р„С Р„„с ...cP„.

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

И, наконец, на последнем этапе декодирования необходимо преобразовать выбранные К остатков Ы; в число

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

Ф вЂ” вес базисного числа.

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

1с4

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

1411980

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

В начальный момент времени с. вхо да 8 подается импульс "Пуск, который формирует импульс на выходе 26 блока

2, который, в свою очередь, поступает на управляющий вход буферного накопителя 1 и вызывает появление на 10

его выходах значений повторов первоI

ro остатка — с „ — Ы„ . Коды остатка

d записываются в мажоритарный блок

2, который анализирует поступившие в него m значений первого остатка и 15 выбирает из них один, наиболее достоверный . — с, j e l, m . Значение

5 й, сформировано на выходе 24 мажори тарного блока 2. Одновременно на вы ходе 25 мажоритарного блока 2 сформи- 20 ровано вычисленное им значение весового коэффициента К|.

В тот же момент времени мажоритарный блок 2 формирует импульс на вы,ходе 26, что вызывает сдвиг содержи- 25

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

После анализа их в мажоритарном

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

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

Блок 5 сортировки сравнивает между собой все коэффициенты K; i

1. и, выбирает из них максимальные К, i e L и формирует сигнал логической единицы на выходах 37.i, i e L. IIpeобразователь 6 в соответствии с этим кодом выбирает из преобразователя 3 остатки К;, i 6 L и преобразует их в число А, значение которого появляется на выходах 9.

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

Счетчик 15 находится в исходном состоянии. Импульс "Ilycx1 на входе

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

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

j:

К,, сравнивается в элементе 14.m c содержимым счетчика 15, равным

m+1 1 (m+11

Если К< 3, (2 ), то на выходе элемента 14.m сформируется сигнал логической единицы, который поступит на первые входы элементов 16 и 17. В то же время на их вторые входы поступает импульс, задержанный элементами

20 и 21 задержки. Этот импульс проходит на выход элемента И 16, на вход установки счетчика 15, через элемент ИЛИ 18 на выход 26, а.также открывает ключи групп ll и 12, через которые на выходы 24 и 25 поступают коды,= ц, и К = К,,соответствен в+1 йо. Если К С (, то на выходе элемента 14.m сравнения присутствует потенциал логического нуля, который закрьвает элемент И 16 и открывает элемент ЗАПРЕТ 17 для импульса, который изменяет содержимое счетчика

15, проходит через элемент ИЛИ 19 на вход элемента 20 задержки, а также сдвигает содержимое регистра 10 на одну ячейку вправо. При этом со» держимое первой ячейки регистра 10 переписьвается в его последнюю ячейку. Теперь элементы К.l — 14,(m-1) сравнивают остаток,г с остальными остатками oh — g,, g . На выходе

1 сумматора 13 появляется код весового

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

1 ш+11

Если К ) — 1, то импульс

5 на выходе элемента И 16 вызывает появление кодов,= и на выходах 24, К = К вЂ” на выходах 25 и импульса ш+П на выходе 26. Если же К (), то

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

t ш+11

Если же этого не происходит, то m-й импульс, поступивший на вход счетчика 15, уменьшает его содержимое на единицу и возвращает регистр

10 в исходное состояние. Выиисляемые аналогичным образом весовые коэффициенты К, j = 1, m сравниваются эле- 25 ментом 14.m со значением

1 1m+1

Если не найдется К ),( (1, то ш-й импульс, поступивший со входа

36, формирует импульс на выходе де55 лителя 27 частоты, который устанавливает счетчики 33 в исходное, а триггеры 32 в единичное состояниеи запусодержимое счетчика 15 уменьшается 30 на единицу каждые m тактов работы мажоритарного блока 2 до тех пор, пока содержимое сумматора 13 не сравняется с содержимым счетчика 15.

Если все m повторов остатка раз- 35 личны, то содержимое сумматора 13 равно нулю, и как только содержимое счетчика 15 также станет равным нулю, элемент К.ш сформирует на своем. выходе потенциал логической единицы, 40 который откроет элемент И 16 и импульс с выхода элемента 20 задержки пройдет через элемент ИЛИ 18 на выход 26, установит счетчик 15 в исходное состояние и открывает ключи 45

: групп 11 и 12. При этом на выходах

24 появится значение ы,= А,, а на с выходах 25 — значение К, = К, = О.

Мажоритарный блок 2 приступает к анализу остатков - Ы ", 50

Блок 5 сортировки, представленный на фиг. 3, работает следующим образом скает генератор 28 импульсов. Импульсы с выхода генератора 28 через открытые элементы И 31 поступают навходы соответствующих счетчиков 33, содержимое которых сравнивается в соответствующих элементах 34 сравнения с соответствующим значением кода на входах 35. Как только содержимое счетчика 33 i сравняется со значением коэффициента К;, присутствующим на входах 35.i, элемент 34.i сформирует на.своем выходе потенциал логической единицы, который установит триггер 32,i в нулевое состояние и закроет элемент 31.i для прохождения импульсов на вход счетчика 33.i содержимое которого останется равным

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

28. Процесс сортировки закончен.

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

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

Значения остатков ;, i s L с входов 42 через открытые ключи групп

38.i i e L поступают на входы соответствующих кодопреобразователей

40.i на выходах которых формируются значения К; В;, i L, которые скла.дываются в сумматоре 41 по модулю Р„.

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

Ъ .

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

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

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

1411980

10 сортировки и преорразователь модулярного кода в позиционный, о т л и— ч а ю щ е е с я тем, что, с целью повышения достоверности устройства ( за счет обеспечения декодирования избыточного модулярного кода с повтора ми, в устройство введены последова тельно-параллельные преобразователи кода и мажоритарный блок, первые и 10 вторые выходы которого соединены с информационными входами соответственно первого и второго последовательнопараллельных преобразователей кода, выходы которых подключены к информа- f5 ционным входам соответственно преобразователя модулярного кода в позици онный и блока сортировки, выходы кото рого соединены с управляющими входами преобразователя модулярного кода в по-10 зиционный, выходы которого являются выходами устройства, третий выход мажоритарного блока подключен к управляющим входам последовательно-параллельных преобразователей кода, блока сор- 25 ,тировки и буферного накопителя, вы ходы которого соединены с одноименными информационными входами мажоритарного блока, управляющий вход которого ,является входом "Пуск" устройства. (2. Устройство по п. 1, о т л и— ч а ю щ е е с я тем, что мажоритарный блок выполнен на элементах сравнения, группах ключей, сумматоре,,счетчике, элементах. задержки, элемен,тах ИЛИ, элементе И, элементе ЗАПРЕТ

35 .и регистре сдвига, установочные входы которого являются информационными

;входами блока, выходы первого разряда регистра сдвига подключены. к первым 40 входам первого — (m-1) -го элементав сравнения (m — число повторов) и.информационным входам первой группы ключей и регистра сдвига, выходы

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

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

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

ИЛИ и входу разрешения записи регистра сдвига.

3. Устройство по п. 1, о т л и— ч а ю щ е е с я тем, что блок сортировки выполнен на генераторе импульсов, делителе частоты, пороговом элементе, сумматоре, счетчиках, триггерах, элемента И и элементах сравнения, первые входы которых являются соответствующими информационными входами блока, вход делителя частоты является управляющим входом блока, выход делителя частоты подключен к входу "Пуск" генератора импульсов, вхо.дам обнуления счетчиков и установочным входам триггеров, выходы которых соединены с первыми входами одноименных элементов И, выход генератора импульсов подключен к вторым входам элементов И, выходы которых соединены со счетными входами одноименных счетчиков, выходы которых подключены к вторым входам одноименных элементов сравнения, выходы которых соединены с входами обнуления одноименных триггеров, .соответствующими входами сум.матора и являются соответствующими выходами блока, выходы сумматора подключены к входам порогового элемента, выход которого соединен с входом блокировки генератора импульсов.

4. Устройство по п. 1, о т л ич а ю щ е е с я тем, что преобразователь модулярного кода в.позиционный выполнен на сумматоре, кодопреобразователях, блоке памяти и группах ключей, информационные входы которых являются соответствующими информационными входами преобразователя, управляющие входы групп ключей объединены с соответствующими входами блока памяти и являются соответствующими управляющими входами преобразователя, 14!1980

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

Составитель О, Ревинский

Редактор С. Патрушева Техред g,дидык Корректор М. Шароши

Заказ 3673/56 Тираж 928 Подписное

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

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

Производственно-полиграфицеское предприятие, r. Ужгород, ул. Проектная, 4