Логическое запоминающее устройство Советский патент 1980 года по МПК G11C15/00 

1

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

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

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

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

Из известных устройств наиболее близким техническим решением к данному изобретению является логическое запоминающее устройство, содержащее 20 постоянный накопитель, первый дешифратор, регистр адреса, накопительный регистр, первую группу элементов И, выходной регистр, ключ, второй дешифратор , причем ВХОД1Ы постоянного 25 накопителя подключены к выходам первого дешифратора, входы которого соедииены с выходс1ми регистра адреса, выходы накопительного регистра подключены к одним из входов элементов И 30

первой группы, другие входы которых подключены к шине Перезапись, а выходы - ко входам первой группы выходного регистра, входы к.шоча соединены соответственно с шинами Управление и вход устройства, а выхЬд ключа соединен с одним из входов выходного регистра 2.

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

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

Поставленная цель достигается тем, что устройство содержит коммутатор адреса, коммутатор чтения, распределитель сигналов, вторую группу элементов И, третий и четвертый дешифраторы, счетчики Н шины Установка начального состояния, Переключен ние распределителя, Передача, Выбор группы, Сдвиг влево и Установка нуля, причем выходы постоянного накопителя подключены к информационньв4 ксммутатора чтения, управляющие входы которого соединены, с выходами распределителя сигналов, .входьа которого подключены к шинам Установка начального состояния и Переключение распределителя., выходы коммутатора чтения подключены к счетным входам накопительного регист ра, выходы которого соединены с одними из входов элементов И второй группы, другие входы которых подключены к шине Передача, а выходы ко входам третьего дешифратора, выхо которого соединены со входами второй группы выходного регистра., выходы которого подключены к информационным входам коммутатора адреса, управляющ вход коммутатбра адреса соединен с шиной Выбор группы, а выходы подкл чены к одним из входов регистра адреса, входы первого счетчика подключены соответственно к шине Сдвиг влево и первой шине Установка нуля, а выход соединен со входом четвертбго дешифратора, входы второго счетчика соединены соответственно с Ш1ГНОЙ Сдвиг влево и второй шиной Установка нуля, а выход подключен ко входу второго дешифратора. Введем обозначения; п m-i-k число кодовых символов; m - число информационных символов; к - число проверочных символов; N - число групп разбиения кодового многочлена; М - число групп разбиения информационного многочлена; 0 - число симв лов в группе, Р4И/2. Циклический (n,m) код позволяет исправлять одну сяиибку и используетс с целью повышения достоверности пере даваемой и принимаемой информации. Циклический код представляет собой совокупность многочленов, делящихся на некоторый многочлен р{х1 степени который называется порождающим. Кодовую последовательность циклического кода можно представить в виде: f(4)(2Wx r{.. Коэффициенты многочлена Wx пр к членах низшего порядка равны нулю а при m членах высшего порядка соответствуют коэффициентам информацион последовательности g (х), достовернос которой необходимо повысить. Многочлен г(х) степени к-1 называется многочленом проверочных символов код вого многочлена f(A. Таким образом, кодовый многочлен f(x) имеет степень п-1 , а число коэффициентов п . для систематического кода процесс кодирования заключается.в определении 2 многочленов, г(х), каждый из которых является результатом преобр зований над соотЕетствукяцим ном д(х), число которых равно 2 , Все 2 многочленов г(х) образуют та лицу проверочных многочленов, котор можно записать в постоянный накопитель. При обраиаении к таблице много членов г(х) по адресу, равному мног члену д(х), определяется многочлен г (х) .Такой подход позволяет построит кодирующее устройство, обладающее максимальным быстродействием, но требует постоянный накопитель большого объема. Сократить объем постоянного накопителя удастся, если информационную последовательность д, состоящую из m символов, разбивать на М равных групп 9, ,2...., М, по р членов в каждой группе. В результате получим М таблиц, содержащих 2 строк каждая. Рассмотрим способ заполнения таблиц. Известно, что циклический код будет задан, если определена его порождающая матрица С..Для систематического циклического кода порождающая матрица G имеет вид: G tD, R, единичная матрица размерности mxm; матрица проверочных символов размерности mx(n-m). Для получения комбинации циклического кода необходимо вектор а коэффициентов информационного многочлена умножить на матрицу G. Но так как произведение вектора д- на матрицу э дает вектор g , будем испЪльзовать только матрицу проверочных символов. Результат умножения вектора 9 на матрицу R определит вектор г коэффициентов многочлена г(х) проверочных символов. Для нахождения содержимого таблиц разобьем матрицу R на М подматриц R|. ,2,,,., М, размерностью р х (n-m). Результат. i -го вектора grj. умножения на подматрицу R( дает вектор г| представляющий собой промежуточное значение вектора г проверочных символов. Набор многочленов принадлежащих i-ой группе, образует таблицу объемом 2 X к. Число таких таблиц равно М. -Для хранения всех таблиц потребуется постоянный накопитель объемом V, ( k)M Кодирование в этом случае будет заключаться в следующем . Многочлен д(х) разбивается на М многочленов g (Х) i- 1,2,... , М, где д- (х) многочлен, образованный i-ой группой коэффициентов многочлена д(х). Из i-й таблицы по адресу д (х) считывается многочлен (х) , который представляет собой промежуточное значение многочлена г(х). Сумма по модулю два многочленов ((х) для всех i образует многочлен проверочных символов г(х). Многочлены д(х) и г(х1 дают многочлен -fCX), передаваемый по каналу связи. Каяадая кодовая последовательность (кодовый многочлен f(x) циклического кода удовлетворяет соотношению f. н о, где - вектор коэффициентов кодов го многочлена f(x); Н - матрица, транспортированна к проверочной размерностью п X (гг т) . Если при декодировании это соотно шение не выполняется, то принятый многочлен f(x) содержит ошибку в одном из символов, при этом результа умножения принятого вектора f на ма рицу н будет отличен от нуля, Многочлен степени к-1, полученный в результате умножения, называется локатором ошибки S ( х) : Локатор схиибки однозначно определяет сшибку в кодовом многочлене. Исправление ошибки производится многочленом, у которого все коэффициенты, кроме одного, равны нулю, и который называется многочленом ошибки. Каждо му локатору сшибки соответствует опр деленный многочлен ошибки. Если числ ошибок в принятом многочлене f(x) боль ше одной,происходит отказ от декордиро вания. Набор всех локаторов ошибок образует таблицу, объемом к, которую можно записать в постоянный на копитель. Но как и при кодировании такой подход требует большого объема памяти. Сократить объем памяти удаст если кодовую последовательность f( х состоящую из п членов, разобьем на N групп f (X) , j 1,2 , .. . , М, по р , членов в каждой группе. В результате получим N .-таблиц, объетмом к каждая. Чтобы определить содержимое таблиц, матрицу Н разобъем на N подматриц н- , ,2,..,, N размерностью р х (гг т) . Результат умножения j-го вектора -f- на j -ю. подматрицу Hj. определит вектор S; , представляющий собой промежуточное значение локатора ошибки S. Набор многочленов Sj (), принадлежащих J-и группе, образует таблицу объемом 2 X к, Число таблиц равно N. Для хранения всех таблиц потребуется постоянный накопитель, объем которого составит: V, . Процесс декодирования будет следующи Многочлен f(x) разбивается на N мног членов ,(х), j l,2,. .. , М ., .где f (х) - многочлен, образованный j-й группой коэффициентов многочлена f(x). Далее из j-ой таблицы по адресу fj (х) считывается многочлен ) Сумма по модулю два многочленов Sj J для всех j определит локатор ошибки S (х). Многочлен ошибки может быть найден с помощью неполного дешифратора, имеющего к входов и п выходов . Многочлен ошибки суммируется по модулю два с многочленом f(x),.H тем самым достигается исправление сииибки Таким образом, для построения кодирующего - декодирующего устройства потребуется постоянный накопитель, объем которого равен сумме объемов V- и V,. Используя свойства цйклит Zt ческих кодов, попытаемся сократить объем постоянного накопителя. Для систематического циклического кода проверочная матрица Н равна: г .J. где R - матрица,транспортированная к ,матрице проверочных символов; 5n-m единичная матрица размерности (n-m)x{n-m). Как видно Из формулы, матрица нсодер жит матрицу D и матрицу проверочных символов R, которая использовалась ранее при кодировании. Таким образом, таблицы, применяемые ранее для декодирования и записываемые в постоянный накопитель, содержит э себе таблицы, необходимые для построения кодирующего устройства. Содержимое таблиц определяется по способу, показанному при описании декодирования. Это позволяет сократить объем постоянного накопителя в раз. KpqMe того, разбиение информационного многочлена (.или кодового многочлена) на группы позволит одновременно выполнять выдачу информационных символов в канал связи {или прием кодовых символов из канал.а связи) и чтение из постоянного накопителя, так как постоянный накопитель требует большего времени на обработку, чем регист ял сдвига, используемые для приема или выдачи информации. Для сравнения опишем метод кодирования и декодирован 5я, рассмотреннный в прототипе 2,Здесь в постоянный накопитель записаны матрица провероч-ных символов R порождающей матрицы & и матрица Н , транспортированная к проверочной. В этом случае при кодировании выполняются следующие операции. Информационная последовательность посимвольно выдается в канал связи, при этом после выдачи каждого символа производится опрос постоянного накопителя. В случае, если символ, вьаданный в канал связи, единичный, то из ячейки постоянного накопителя считывается строка матрищл R и су Ф4ируется по модулю два с целью . получения многочлена проверочных символов г(х), который после выдачи всех инфоЕМчаииоиных символов выдается в канал связи. Кодирование эакаичивает ся вьщачей всех символов, образуккшх кодовую последовательность. При декодировании кодовая последовательность принимается из канала снизив После приема каждого кодового символа производится опрос постоянного накопителя, при этом, если принятый символ единичный, то Из ячейки постоянного накопителя считывается строка матрицы И и суммируется по модулю .два с целью получения локатора ошибки S (X), который определяет позицию ошибки в принятом многочлене. После приема всех символов кодовой последовательног-ти будет определен локатор

отиибки S(X), который затем используется в качестве адреса ячейки постоянного накопителя. Из ячейки постоянного накопителя Считывается многочлен Сйлибки и производится исправление свиибочного символа.

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

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

На фиг. 1 изображена схема логического запоминающего устройства} фиг. 2 представлен пример распределения области памяти постоянного накопителя.

Логическое запоминающее устройство содержит постоянный накопитель 1, первый дешифратор 2, служащий для деишф рации адреса, регистр адреса 3, коммутатор чтения 4, распределитель сигналов 5, накопительный регистр 6, первую 7 и вторую 8 группы элементов И, второй дешифратор 9, выходной регистр 10, ключ 11, коммутатор адреса 12, первый счетчик 13, третий дешифратор 14, второй счетчик 15, четвертый дешифратор 16, шины 17-34, в том числе шину Запись в регистр адреса 17, шину Чтение 18, шину Установк начального состояния IS, шину Переключение распределителя 20, шину Установка начального состояния 21 шину Передача 22, шину Перезапись 23, шину Выход устройства 24, шину Установка начального состояния 25, шину Сдвиг влево 26, ишну Выбор группы 27, шину Прием 28, шиму Вход устройства 29, первую айну Установка нуля 30, шину Обработано р символов 31, вторую шину Ус, тановка нуля 32, шняу Обработано m символов 33 и шину Обработано п символов 34.

Выходы элементов И 7 подключены ко входам первой группы регистра 10„ Выход ключа 11 соединен с одним из входов регистра 10. Выходы накопителя 1 подключены к информационным входа м KOMijyTaTopa 4, управлшоцие входы которого соединены с вьжолами распределителя сигналов 5, входы которого подключены к шинам 19 и 20. ВЫХОД1Л коммутатора 4 подключены к счетньм входам регистра б, выходаа которого соединены с одними из вкодов элементов И 8, другие входы которых подключены к шине 22, а выходы - ко входам третьего дешифратора 14, выходы которого соединены со входами второй группы регистра 10, выходы которого подключены к информационным входам коммутатора 12.

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

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

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

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

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

В исходном состоянии распределите сигналов 5 находится в первом состоянии , регистр 6 установлен в нулевое состояние сигналом на шине 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 поступает на счетные входы регистра 6 (при этом в регистре 6 формируются проверочные символы кодовой последовательности, Номег группы раз рядов задает распределитель сигналов 5. После этого распределитель 5 переключается в следующее состояние сигналом на шине 20, в результат чего осуществляется выборка следующ группы разрядов содержимого ячеек на копителя 1. После того, как из регистра 10 будут выданы р символов ин формационной последовательности, о чем будет свидетельствовать сигнал на шине 31, следующий адрес ячейки накопителя 1 из регистра 10 через коммутатор 12 перепишется в регистр 3 адреса сигналом на шине 17. Далее будет продолжаться процесс вьадачи информационных символов в канал свя и одновременно формирование провероч ных символов кодовой последовательности. И после того, как будет вьлда вся информационная последовательност о чем засвидетельствует сигнал на шине 33, на шину 23 поступит сигнал и содержимое регистра 6 (проверочные символы) переписывается в старше к разрядов регистра ,10 через элементы И 7. На шину 26 поступают сигналы сдвига, и проверочные символы последовательно выдаются в канал связи. Число выданных символов подсчитывается счетчиком 15. Выдача проверочных символов продолжается до тех пор пока не будет выдано -t- k кодовых символов, при этом на шине 34 появит ся сигнал. После этого,кодирование заканчивается. Декодирование информации. В исходном состоянии распределитель сигналов 5 установлен в начальное состояние сигналом на шине 19, регистр 6 установлен в нулевое состояние на шине 21, выходной регистр 10 установлен .в нулевое состояниеi.. сигналом на шине 25, ключ 11 открыт единичным сигналом на шине 28, коммутатор 12 установлен в положение передачи содержимого младших р разрядов выходного регистра 10 в регист 3 адреса нулевым сигналом на шине 27, счетчики 13 и 15 установлены в нулевое состояние сигналами на шинах 30 и 32 соответственно. На шину 26 поступают сигналы сдвига, и в регистр 10 через открытый ключ 11 за писываются символы кодовой последова тельности, принимаемые из канала св по шине 29, при этом счетчики 13 и 15 ведут подсчет числа принятых с волов. Когда в регистр 10 будет записано р первых символов кодовой по следовательности, о чем засвидетель ствует сигнал на шине 31, на шину 1 поступит сигнал, и р символов кодов последовательности из регистра 10 через коммутатор 12: адреса запишутс в регистр 3. После этого прием кодо вых символов продолжается и одновре менно производится чтение содержимо го ячейки постоянного накопителя 1 сигналом на шине 18, при этом содер жимое группы разрядов через коммутатор 4 поступает на счетные входы регистра 6, в результате чего в регистре 6 формируется локатор ошибки. Далее распределитель 5 переключается в следующее состояние сигналом на шине 20. После того в регистр 10 будет записано р очередных символов кодовой последовательности, о чем засвидетельствует сигнал на шине 31, на шину 17 подается сигнал, и очередная группа символов кодовой Последовательности из регистра 10 через коммутатор 12 переписывается в регистр 3. Затем процесс приема кодовых символов продолжается и, одновременно производится формирование локатора ошибки до тех пор, пока не будет принята вся кодовая последовательность, при этом на шине 34 появится сигнал. После этого на шину 22 поступит сигнал, и локатор ошибки из .регистра 6 через элементы И 8 подается на входы дешифратора 14, в результате чего определяется многочлен ошибки, который с выходов дешифратора 14 поступает на счетные входы регистра 10, при этом, происходит исправление ошибки в кодовом многочлене. На этом декодирование заканчивается. Описанное устройство по сравнению с известньом отличается повышен-ным быстродействием. Так, например, для циклического кода, имеющего 10 информационных символов и 5 проверочных символов, при М 2 и логическое запоминающее устройство, построенное на микросхемах 133 серии, при такте Чтения из постоянного накопителя 600 не и такте сдвига и передачи, равном 100 НС, кодирование выполняет в 3 раза быстрее, а декодирование - в 1,7 раз быстрее. Формула изобретения Логическое запоминающее устройство, содержащее постоянный накопитель, первый дешифратор, регистр адреса, накопительный регистр, пер|Вую группу элементов И, выходной ре:гистр, ключ, второй дешифратор, причем входы постоянного накопителя подключены к выходам первого дешифратора, входы которого соединены с выходами регистра адреса, выходы на:копительного регистра подключены к одним из входов элементов И первой группы, другие входы которых подключены к шине Перезапись, а выходы ко входам первой группы выходного регистра, входы ключа соединены соответственно с шинс1ми Управление и Вход устройства, а выход ключа соединен с одним из входов выходного регистра, отличающееся тем, что, с целью увеличения быстро