Логическое запоминающее устройство

 

I

ВСЕСО О " R

«яАТЕЬ i (т i (:Ki" Г

Сонзз Советских

Социалистических

Республик

П 4 а .-Д .И

ИЗОБРЕТЕНИЯ (ii> 771720

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 2710.78 (21) 2678275/18-24 с присоединением заявки М (23) Приоритет

Опубликовано 15.1080. бюллетень Й 38

Дата опубликования описания 1810ВО (51)М. Кл.з

0 11 С 15/00

Государственный комитет

СССР по лелам изобретений и открытий (53) УДК 681. 327 (088. 8) Е. П. Балашов, Н. Н. Варлинский, В. Н. Волкогонов и В. С. Степанов (72) Авторы изобретения

Ленинградский ордена Ленина электротехнический институт им. В. И. Ульянова (Ленина}

{71) Заявитель (54} .ЛОГИЧЕСКОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО

Изобретение относится к области запоминающих устройств.

Известны логические запоминающие устройства

Одно из известных логических запоминакщих устройств содержит регистр адреса,.группу вентилей перезаписи, дешифратор адреса, матрицу постоянного запоминающего устройства, выходной регистр(1).

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

Из известных устройств наиболее близким техническим решением к дан-, ному изобретению является логическое запоминающее устройство, содержащее 20 постоянный накопитель, первый дешифратор, регистр адреса, накопительный регистр, первую группу элементов И, выходной регистр, ключ, второй дешифратор, причем входы постоянного накопителя подключены к выходам первого дешифратора, входы которого соединены с выходами регистра адреса, выходы накопительного регистра подключены к одйим из входов элементов И 30 первой группы, другие входы которых подключены к шине "Перезапись", а выходы — ко входам первой группы выходног.о регистра, входы ключа соединены соответственно с шинами Управление" и "вход устройства", а выход ключа соединен с одним из входов выходного регистра (2).

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

Целью настоящего изобретения является повышение быстродействия устройства.

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

we распределителя", ."Передача", "Ваабор группы, "Сдвиг влево" и "Установка нуля, причем выходы постоянного накопителя подключены к информационным входам ксымутатора чтения, управляющие входы которого соединены с выходами распределителя сигналов, 771720,входы которого подключены к шинам

"Установка начального состояния" и

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

"Установка нуля", а выход подключен ко входу второго дешифратора.

Введем обозначения: и= m+ k число кодовых символов; m - число информационных символов; к — число проверочных символов; М вЂ” число групп разбиения кодового многочлена;

М - число групп разбиения информационного многочлена; (э — число символов в группе, р 6/2.

Циклический (и, m) код позволяет исправлять одну ошибку и используется с целью повышения достоверности передаваемой и принимаемой информации.

Циклический код представляет собой совокупность многочленов, делящихся на некоторый многочлен р(х) степени к, который называется порождающим. Кодовую последовательность циклическо- 40

ro кода можно представить в виде: (() =@ах +("(х) . k

Ic

Коэффициенты многочлена фх)х при к членах низшего порядка равны нулю, а при m членах высшего порядка соот- 45 ветстауют коэффициентам информационной последовательности g (x),достоверность которой необходимо повысить. Иногочлен r(х) степени к-1 называется многочленом проверочных символов кодо- вого многочлена (к}.. Таким образом, кодовый многочлен Px) имеет степень п-1, а число коэффициентов n = m+k.

Для систематического кода процесс кодирования заключается в определении 2 многочленов. r(x), каждый из которых является результатом преобразований над соотв тствующим мнодочленом g(x) число которых равно 2

Все 2" многочленов r(x) образуют таб лицу проверочных многочленов, которую Я можно записать в постоянный накопитель. При обращении к таблице многочленов r(x) по адресу, равному многочлену g(x), определяется многочлен

r(x).Такой подход позволяет построить Я кодирующее устройство Обладающее максимальным быстродействием, но требует постоянный накопитель большого объема. Сократить объем постоянного накопителя удастся, если информационную последовательность g, состоящую нз m символов,,разбивать на М равных групп g., i=1,2...., M, по р членов в каждой группе. В результате получим M таблиц, содержащих 2 строк

P каждая.

Рассмотрим способ заполнения таблиц, Известно, что циклический код будет задан, если определена его порождающая матрица G.. Для систематического циклического кода порождающая матрица С имеет вид:

G =(Э, R)1. где Д вЂ” единичная матрица размерности mxm;

R - матрица проверочных символов размерности mx(п-m).

Для получения комбинации циклического кода необхсдимо вектор коэффициентов информационного многочлена умножить на матрицу G. Но так как произведение вектора с на матрицу 3,„ дает вектор g, будем использовать только матрицу проверочных символов. Результат умножения вектора g на матрицу R определит вектор г коэффициентов многочлена г(х) проверочных символов. Для нахождения содержимого таблиц раэобъем матрицу

R на М подматриц R„- i=1,2,..., М, размерностью р х (и-а). Результат умножения i-го вектора сг на под-! .Ф матрицу й,. дает вектор г(представляющий собой промежуточное значение вектора r проверочных символов.

Набор многочленов," принадлежащих

i-Ой группе, образует таблицу объемом 2Р х к. Число таких таблиц равно М. Для хранения всех таблиц потребуется постоянный накопитель объемом

Ц (2 x k) M

Кодирование в этом случае будет заключаться в следующем . Многочлен

g(х) разбивается на М многочленов

g . (xi i- 1,2,..., М, где g., (х) многочлен, образованный i- ой группой коэффициентов многочлена g (х) . Из

i-й таблицы по адресу д . (x) считы1 вается многочлен (" г(х}, который представляет собой промежуточное значение многочлена r (x) . Сумма по модулю два многочленов V (х) для всех l образует многочлен проверочных символов r (x) .

Многочлены g (x ) и r (x 1 дают многочлен f(xI,ïåðåäàâàåìûé по каналу связи. Каждая кодовая последовательность (кодовый многочленj f(x) циклического кода удовлетворяет соотношению

Н =О с

1 где -ф - вектор коэффициентов кодов .го многочлена f(x);

771720

Н вЂ” матрица, транспортированная к проверочной размерностью и х (п-m).

Если при декодировании зто соотношение не выполняется, то принятый многочлен f()() содержит ошибку в одном из символов, при этом результат умножения принятого вектора f на матрицу Н будет отличен от нуля. т

Многочлен степени к-1, полученный в результате умножения, называется локатором ошибки 5(х :

)0

S=f- Н

Локатор ошибки однозначно определяет сшибку в кодовом многочлене. Исправление ошибки производится многочленом, у которого все коэффициенты, 15 кроме одного, равны нулю, и который называется многочленом ошибки. Каждому локатору ошибки соответствует определенный многочлен ошибки. Если число ошибок в принятом многочлене f (х) боль- 2О ше одной, происходит отказ от декордирования. Набор всех локаторов ошибок образует таблицу, объемом 2 х к, коИ торую можно записать в постоянный накопитель. Но как и при кодиРовании такой подход требует большого объема памяти. Сократить объем памяти удастся если кодовую последовательность f(x), состоящую из и членов, разобъем на

И групп Г (x), j= 1,2,..., M, по р ,членов в каждой группе. В результате получим N ..таблиц, объе-. мом 2 х к каждая. Чтобы опреДелить содержимое таблиц, матрицу Н разобъем на N H j=1,2,..., Ф /

N размерностью р х (и- и), Результат

1 умножения j --го вектора f на -ю. подматрицу H определит вектор S

F 3

I представляющйй собой промежуточное значение локатора ошибки S. Набор многочленов 3 (к), принадлежащих

j- и группе, обраэует таблицу объемом

2 х K. Число таблиц равно И. Для р хранения всех таблиц потребуется постоянный накопитель, объем которого составит: р 45

Ч =(2. х )кИ. т

Процесс декодирования будет следующий.

Многочлен (х) разбивается на И многочленов . f> (х), j=1,2,..., g :, где

Г.(х) - .многочлен, образованный 50

j - и группой коэффициентов многочлена

f (x) . Далее иэ j- ой таблицы но адре-, су f - (х) считывается многочлен 8 (Х).

Сумма по модулю два многочленов 5 (4. для всех j определит локатор ошиоки

S (х). Многочлен ошибки может быть найден с помощью неполного дешифратора, имеющего к входов и и выходов. Многочлен ошибки суммируется но модулю два с многочленом f(x),, и тем самым достигается исправление ошибки. Щ

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

Ч„ и v . Используя свойства циклиI ческих кодов, попытаемся сократить объем постоянного накопителя.

Для систематического циклического кода проверочная матрица Н равна:

И=tu,ç„ где R — матрица,транспортированная к .,матрице проверочных символов;

7.„ - единичная матрица размерности (и- m) х (и - m) .

Как видно иэ формулы, матрица Н содер т жит матрицу и матрицу проверочн-rn ных символов R которая использовалась ранее при кодировании. Таким образом, таблицы, применяемые ранее для декодирования и записываемые в постоянный накопитель, содержит В себе таблицы, необходимые для построения кодирующего устройства. Содержимое таблиц определяется по способу, показанному при описании декодирования. Это позволяет сократить объем постоянного накопителя в м раз.

Н

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

Для сравнения опишем метод кодирования и декодирования, рассмотреннный в прототипе (2). Здесь в постоянный накопитель записаны матрица провероч» ных символов R порождающей матрицы т

4 и матрица Н, транспортированная к проверочной. В этом случае при кодировании выполняются следующие операции. Информационная последовательность посимвольно выдается B канал связи, при этом после выдачи каждого символа производится опрос постоянного накопителя. В случае, если символ, выданный в канал связи, единичный, то из ячейки постоянного накопителя считывается строка матрицы R и суммируется но модулю два с целью получения многочлена проверочных символов r(x), который после выдачи всех информационных символов выдается в канал связи. Кодирование заканчивается выдачей всех .символов, обраэукиаих кодовую . При декодировании кодовая последовательность принимается иэ канала связи; После приема каждого кодового символа производится опрос постоянного накопителя, при этом, если принятый символ единичный, то из ячейки постоянного накопителя считывается строка матрицы Н и суммируется по модулю .два т с целью получения локатора ошибки

S(x), который определяет позицию ошибки в принятом многочлене. После приема всех символов кодовой последовательно . и будет определен локатор

771720 ошибки Я(т1, который затем используется в качестве адреса ячейки постоянного накопителя, Из ячейки постоянного накопителя считывается многочлен ошибки и производится исправление ошибочного символа.

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

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

На фиг. 1 изображена схема логического запоминающего устройства на фиг. 2 представлен пример распределения области памяти постоянного накопителя, Логическое запоминающее устройство содержит постоянный накопитель 1, первый дешифратор 2, служащий для дешифрации адреса, регистр адреса 3 30 коммутатор чтения 4, распределитель сигналов 5, накопительный регистр б, первую 7 и вторую 8 группы элементов

Й, второй дешифратор 9, выходной регистр 10, ключ 11, коммутатор адреса 35

12, первый счетчик 13, третий дешифратор 14, второй счетчик 15, четвертый дешифратор 16, шины 17-34, н том числе шину Запись в регистр адреса"

17, шину "Чтение" 18, шину "Установка gg начального состояния" 19, шину "t1epeключение распределителя" 20, шину

"Установка начального состояния" 21 шину "Передача 22, шину "Перезапись"

23, шину "Выход устройства" 24, шину

"Установка начального состояния" 25, шину Сдвиг влево 26, шину "Выбор группы" 27, шину "Прием" 28, шину

"Вход устройства" 29, первую:анну

"Установка нуля" 30, шику "Обработано р символов" 31, вторую шину "Ус-, тановка нуля 32, шину "Обработано и символов" 33 и шину "Обработано и символов 34.

Выходы элементов И 7 подключены хо входам первой группы регистра 10. 55

Выход ключа 11 соединен с одним иэ входов регистра 10. Выходы накопи-. теля 1 подключены х информационным входам коммутатора 4, управляющие входы которого соединены с выходами @ распределителя сигналов 5, входы которого подключены к шинам 19 и 20.

Выходы коммутатора 4 подключены х счетным входам регистра б, выходы которого соединены с одними из вхо- д дон элементов И 8, другие входы которых подключены к шине 22, а выходы — ко входам третьего дешифратора 14, выходы которого соединены со входами второй группы регистра 10, выходы которого подключены к информационным входам коммутатора 12.

Управляющий вход коммутатора 12 соединен с шиной 27. Выходы коммутатора 12 подключены к одним из входов регистра адреса 2. Входы первого счетчика 13 подключены соответственно к шинам 26 и 30, а выход соединен со входом четвертого дешифратора 16, выход которого подключен к шине 31. Входы второго счетчика 15 соединены соответственно с шинами 26 и 32, а выход подключен ко входу второго дешифратора 9, выходы которого соединены с шинами 33 и 34.

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

В ячейках постоянного накопителя, . разбитого на и к — разрядных зон 35, ю записано и таблиц размером 2 х.к, используемых для получения проверочных символов при кодировании и локаторов ошибок при декодировании.

Устройство работает следующим образом.

Кодирование информации.

В исходном состоянии распределитель сигналов 5 находится в первом состоянии, регистр б установлен в нуленое состояние сигналом на шине 21, ключ

11 закрыт сигналом на шине 28, коммутатор 12 установлен в положение передачи содержимого старших Р разря дон выходного регистра 10 в регистр адреса 3 единичным сигналом на шике

27, счетчики 13 и 15 установлены в нулевое состояние сигналами на шинах

30 и 32 соотнетственно. В m старших разрядах выходного регистра 10 записана информационная последона тельность, а в n"m младших разрядах выходного регистра 10 записаны нули.

На шину 17 поступает сигнал, и содержимое старших р разрядов выходного регистра 10 через коммутатор 12 переписывается в регистр 3 адреса. С помощью этой операции задается адрес ячейки накопителя 1. На шину 26 поступают сигналы, и содержимое выходкого регистра 10 посимвольно выдается в канал связи, при этом счетчики 13 и 15 производят под» счет числа выданных символов. Одновременно с передачей содержимого регистра 10 в канал связи производит . ся чтение из ячейки постоянного накопителя 1 сигналом на шине 18, при этом содержимое группы разрядов ячейки накопителя 1 через коммутатор

4 поступает на счетные входы регистра б (при этом в регистре б формируются проверочные символы кодоной последовательности. Номев группы раз

771720

10 рядов эадает распределитель сигналов 5. После этого распределитель

5 переключается н следующее состояние сигналом на шине 20, в результатв чего осуществляется выборка следующей группы разрядов содержимого ячеек накопителя 1. После того, как иэ регистра 10 будут выданы р символов информационной последовательности, о чем будет свидетельствовать сигнал на шине 31, следующий адрес ячейки накопителя 1 из регистра 10 через t0 коммутатор 12 перепишется в регистр

3 адреса сигналом на шине 17. Далее будет продолжаться процесс выдачи информационных символов в канал связи и одновременно формирование провероч- !5 ных символов кодовой последовательности. И после того, как будет выдана вся информационная последовательность о чем засвидетельствует сигнал на шине 33, на шину 23 поступит сигнал, щ и содержимое регистра 6 (проверочные символы) переписывается в старше к разрядов регистра .10 через элементы

И 7. На шийу 26 поступают сигналы сдвига, и пронерочные символы последовательно выдаются в канал связи.

Число выданных символов подсчитывается счетчиком 15. Выдача проверочных символов продолжается до тех пор, пока не будет выдано п=m + k кодовых символов, при этом на шине 34 появится сигнал. После этого, кодирование заканчивается. декодирование информации.

В исходном состоянии распределитель сигналов 5 установлен в начальное состояние сигналом на шине 19, регистр 6 установлен в нулевое состояние на шине 21, выходной регистр

10 установлен .в нулевое состояние .. сигналом на шине 25, ключ 11 открыт 4О единичным сигналом на шине 28, коммутатор 12 установлен в положение передачи содержимого младших р разрядов выходного регистра 10 в регистр

3 адреса нулевым сигналом на шине 45

27, счетчики 13 и 15 установлены н нулевое состояние сигналами на шинах

30 и 32 соответственно. На шину 26

% поступают сигналы сдвига, и в регистр 10 чеРез открытый ключ 11 записываются символы кодовой последовательности, принимаемые из канала связи по шине 29, при этом счетчики 13 и 15 ведут г одсчет числа принятых символов, Когда в регистр 10 будет записано р первых символов кодовой по- 55 следовательности, о чем засвидетельствует сигнал на шине 31, на шину. 17 поступит сигнал, и р символов кодовой последовательности из регистра 10 через коммутатор 12. адреса запишутся Щ в регистр 3. После этого прием кодовых симнолон продолжается и одновременно производится чтение содержимого ячейки постоянного накопителя 1 сигналом на шине 18, при этом содер- д5 жимое группы разрядов через коммутатор 4 поступает на счетные входы регистра 6, н результате чего в регистре 6 формируется локатор ошибки. Далее распределитель 5 переключается в следующее состояние сигналом на шине 20. После того в регистр

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

31, на шину 17 подается сигнал, и очередная группа символов кодовой последовательности иэ регистра 10 через коммутатор 12 переписывается в регистр 3. Затем процесс приема кодовых символов продолжается и, одновременно производится формирование локатора ошибки до тех пор, пока не будет принята вся кодовая последовательность, при этом на шине 34 появится сигнал. После этого на шину 22 поступит сигнал, и локатор ошибки иэ,регистра 6 через элементы И 8 подаетая на входы дешифратора 14, в результате чего определяется многочлен ошибки, который с выходов дешифратора 14 поступает на счетные входы регистра 10, при этом. происходит исправление ошибки в кодовом многочлене. На этом декодирование заканчивается.

Описанное устройство по сравнению с известным отличается повышенным быстродействием.

Так, например, для циклического кода, имеющего 10 информационных символов и 5 проверочных символов, при M = 2 и М=З логическое запоминающее устройство, построенное на микросхемах 133 серии, при такте чтения из постоянного накопителя 600 нс и такте сдвига и передачи, равном

100 нс, кодирование выполняет в 3 раза быстрее, а декодирование — в

1,7 раз быстрее.

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

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

"Вход устройства", а выход ключа соединен с одним из входов выходного регистра, о т л и ч а ю щ е е с я тем, что, с целью увеличения быстро773.720

f7

f9

2f

v

Яб

64 ая,4 г.ужгород,ул.Пр действия устройства, оно содержит коммутатор адреса, коммутатор чтения, распределитель сигналов, вторую группу элементов И., третий и четвертый дешифраторы, счетчики и шины "Установка начального состояния", "Переключение распределителя", "Передача", "Выбор группы", "Сдвиг влево" и

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

5 регистра адреса, входы первого счетчика подключены соответственно к шине "Сдвиг влево" и первой шине

"Установка нуля", а выход соединен со входом четвертого дешифратора, входы второго счетчика соединены соответственно с шиной "Сдвиг влево" и второй шиной "Установка нуля", а выход подключен ко входу второго дешифратора.

Источники информации, принятые во внимание при экспертизе

1. Дроздов Е. A. Пятибратов A. П.

Автоматическое преобразование и ко-, дирование информации. М., "Советс20 кое Радио", 1964, с. 501-503.

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

Р 610174, кл. С4 11 С 15/00, 1977 (прототип).