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

Союз Советских Социалистических Республик(51)м, Кл.з С 11 С 15/00 Государственный комитет СССР по лелам изобретений и открытий(72) Авторы изобретения Ленинградский ордена Ленина электротехническийинститут им. В. И. Ульянова (Ленина)(54) ЛОГИЧЕСКОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО Изобретение относится к областизапоминающих устройств,Известны логические запоминающиеустройстваОдно из известных логических запоминакщих устройств содержит регистр адреса,.группу вентилей перезаписи, дешифратор адреса, матрицупостоянного запоминающего устройства,выходной регистр(1), , 1 аНедостатками этого устройства являются невозможность выполнения операции декодирования, большая емкостьматрицы постоянного запоминающегоустройства, что ограничивает область 15применения устройства.Из известных устройств наиболееблизким техническим решением к дан-,ному изобретению является логическоезапоминающее устройство, содержащее20постоянный накопитель, первый дешифратор, регистр адреса, накопительный регистр, первую группу элементов И,выходной регистр, ключ, второй дешифратор, причем входы постоянногонакопителя подключены к выходам первого дешифратора, входы которого соединены с выходами регистра адреса, выходы накопительного регистра подключены к одйим из входов элементов И 30 первой группы, другие входы которыхподключены к шине "Перезаписьи, а выходы - ко входам первой группы выходного регистра, входы ключа соединены соответственно с шинами иуправлениеи и "вход устройства", а выходключа соединен с одним из входов вы.ходного регистра 12),Недостатком этого логического запоминающего устройства является невысокая скорость работы устройства из"за большого количества тактов при кодировании.и декодировании.Целью настоящего изобретения является повышение быстродействия устройства.Поставленная цель достигаетсятем, что устройство содержит коммутатор адреса, коммутатор чтения, распределитель сигналов, вторую группуэлементов И, третий и четвертый дешифраторы, счетчики и шины иУстановка начального сосгоянияи, иПереключение распределителяи, "Передачаи, иЬмбор группы", "Сдвиг влевои и иУстановка нуля", причем выходы постоянно.го накопителя подключены к информационным входам ксымутатора чтения,управляющие входы которого соединены с выходамн распределителя сигналов,"Переключение распределителяф, выходы коммутатора чтения подключены ксчетным входам накопительного регистра, выходы которого соединены с одними из входов элементов И второйгруппы, другие входы которых подключены к шине "Передачаф, а выходы -ко входам третьего дешифратора, выходыкоторого соединены со входами второйгруппы выходного регистра., выходыкоторого подключены к информационнымвходам коммутатора адреса, управляющийвход коммутатдра адреса соединен сшиной "Выбор группы", а выходы подключены к одним из входов регистраадреса, входы первого счетчика подключены соответственно к шине "Сдвигвлево" и первой шине "Установка нуля", а выход соединен со входом четвертбго дешифратора, входы второго 2 Осчетчика соединены соответственно сшиной 1 Сдвиг влево" и второй шиной"Установка нуля", а выход подключенко входу второго дешифратора.Введем обозначения: и= в+Й - дчисло кодовых символов; е - числоинформационных символов; к - числопроверочных символов; М - числогрупп разбиения кодового многочлена;М - число групп разбиения информационного многочлена; р - число символов в группе, р 4 62.Циклический (и,е) код позволяетисправлять одну ошибку и используетсяс целью повышения достоверности передаваемой и принимаемой информации.Циклический код представляет собойсовокупность многочленов, делящихсяна некоторый многочлен р(х) степени к,который называется порождающим. Кодовую последовательность циклического кода можно представить в виде:%кКоэффициенты многочлена фъ)х прик членах низшего порядка равны нулю,а при щ членах высшего порядка соответстауют коэффициентам информационнойпоследовательности д (х),достоверностькоторой необходимо повысить. Иногочлен г(х) степени кназываетсямногочленом проверочных символов кодо-вого многочлена (к). Таким образом,кодовый многочлен (м) имеет степеньи -1, а число коэффициентов и = в+К.Для систематического кода процесскодирования заключается в определении 2 многочленов. г(х), каждый изкоторых является результатом преобразований над соотвтствующим мнодочленом д(х), число которых равно 2Все 2 ф многочленов г(х) образуют таблицу проверочных многочленов, которую Яможно записать в постоянный накопитель. При обращении к таблице многочленов г(х) по адресу, равному многочлену д(х), определяется многочленг(х).Такой подход позволяет построить Я кодирующее устройство, обладающеемаксимальным быстродействием, но требует постоянный накопитель большогообъема. Сократить объем постоянногонакопителя удастся, если информационную последовательность д, состоящуюнз а символов, разбивать на М равныхгрупп д 1=1,2, М, по р членовв каждой группе. В результате получим М таблиц, содержащих 2 строкркаждая,Рассмотрим способ заполнения таблиц, Известно, что циклический кодбудет задан, если определена егопорождающая матрица 6 Для систематического циклического кода порождающая матрица С имеет вид:6 =(Э, йЗ,где 3 - единичная матрица размерности щха;В - матрица проверочных символов размерности вх(и-щ),Для получения комбинации циклического кода необходимо векторкоэффициентов информационного многочлена умножить на матрицу С. Но таккак произведение векторана матрицу 3, дает вектор д, будем использовать только матрицу проверочныхсимволов. Результат умножения вектора д на матрицу й определит векторг коэффициентов многочлена г(х) проверочных символов. Для нахождениясодержимого таблиц разобъем матрицуК на М подматриц й. =1,2 М,размерностью р х (и-щ). Результатумножения -го вектора р на подматрицу й,. дает вектор г представляющий собой промежуточное значение вектора г проверочных символов.Набор многочленов ," принадлежащих-ой группе, образует таблицу объемом 2 Р х к. Число таких таблиц равно М. Для хранения всех таблиц потребуется постоянный накопитель объемоми, (2 х )МКодирование в этом случае будет заключаться в следующем, Многочлен д(х) разбивается на М многочленовц, (4 1- 1,2 М, где д; (х) многочлен, образованный -ой группой коэффициентов многочлена д(х). Из (-й таблицы по адресу д.(х) считывается многочлен (сг(х), который представляет собой промежуточное значение многочлена г(х)Сумма по модулю два многочленов г;(х) для всехобразует многочлен проверочных символов г(х). Многочлены д(х) и г(х 1 дают много- член (х),передаваемый по каналу связи. Каждая кодовая последовательность (кодовый многочлен) (х) циклического кода удовлетворяет соотношениюН =О. с1где ф - вектор коэффициентов кодовго многочлена т(х);40 Н - матрица, транспортированнаяк проверочной размерностьюи х (и-а),Если при декодировании зто соотношение не выполняется, то принятыймногочлен (11) содержит ошибку водном из символов, при этом результатумножения принятого векторана матрицу Н будет отличен от нуля.тМногочлен степени к, полученный врезультате умножения, называется локатором ошибки 5(х:О5=1 НЛокатор ошибки однозначно определяетсшибку в кодовом многочлене. Исправление ошибки производится многочленом, у которого все коэффициенты, 15кроме одного, равны нулю, и которыйназывается многочленом ошибки. Каждому локатору ошибки соответствует определенный многочлен ошибки. Если числоошибок в принятом многочлене 1 (х) боль Оше одной, происходит отказ от декордирования. Набор всех локаторов ошибокобразует таблицу, объемом 2 х к, койторую можно записать в постоянный накопитель. Но как и при кодиРованиитакой подход требует большого объемапамяти. Сократить объем памяти удастсяесли кодовую последовательность Г( х),состоящую из и членов, разобъем наИ групп 1 (х), 1= 1,2 М, по р,членов в каждой группе. В результате получим И . таблиц, объе-.мом 2 х к каждая. Чтобы определитьсодержимое таблиц, матрицу Н разобъем на М подматриц Н )=1,2ф /И размерностью р х (и-п), Результат1умножения-го векторана 1 -ю.подматрицу Н определит вектор 331представляющйй собой промежуточноезначение локатора ошибки 5. Набормногочленов 8 (ъ), принадлежащих)- й группе, обраэует таблицу объемом2 х к. Число таблиц равно И. Длярхранения всех таблиц потребуется постоянный накопитель, объем которогосоставит: р 45=(Р ЧтПроцесс декодирования будет следующий.Многочлен 1(х) разбивается на И многочленов .(х), )=1,2 5 :, гдеГ (х) - многочлен, образованный 50-й группой коэффициентов многочленаГ(х), Далее иэ 1-ой таблицы но адре-,су 1 (х) считывается многочлен 8(Х).Сумма по модулю два многочленов 6 (х).для всех 1 определит локатор ошибки5 (х). Многочлен ошибки может бытьнайден с помощью неполного дешифратора, имеющего к входов и и выходов. Многочлен ошибки суммируется номодулю два с многочленом (х) и темсамым достигается исправление ошибки. 69Таким образом, для построения кодирующего - декодирующего устройствапотребуется постоянный накопитель,объем которого равен сумме объемовЧ и Ч . Используя свойства цикли- ЯФ ческих кодов, попытаемся сократитьобъем постоянного накопителя,Для систематического циклическогокода проверочная матрица Н равна:н =1 й,),где й - матрица,транспортированная к,матрице проверочных символов;3 - единичная матрица размерности (и- а) х (и - в) .Как видно иэ формулы, матрица Н содертжит матрицу Э и матрицу проверочн-тных символов х, которая использовалась ранее при кодировании. Такимобразом, таблицы, применяемые ранеедля декодирования и записываемые впостоянный накопитель, содержит Всебе таблицы, необходимые для построе.ния кодирующего устройства. Содержимое таблиц определяется по способу,показанному при описании декодирования, Это позволяет сократить объемпостоянного накопителя враз.НКрс)ме того, разбиение информационного многочлена(или кодового многочлена)на группы позволит одновременновыполнять выдачу информационных символов в канал связи (или прием кодовых символов из канала связи)и чтение из постоянного накопителя, таккак постоянный накопитель требуетбольшего времени на обработку, чемрегистры сдвига, используемые дляприема или выдачи информации.Для сравнения опишем метод кодирования и декодирования, рассмотреннныйв прототипе 2. Здесь в постоянныйнакопитель записаны матрица проверочных символов х порождающей матрицыт6 и матрица Н , транспортированнаяк проверочной. В этом случае прикодировании выполняются следующиеоперации. Информационная последовательность посимвольно выдается в канал связи, при этом после выдачи каждого символа производится опрос постоянного накопителя. В случае, еслисимвол, выданный в канал связи, единичный, то из ячейки постоянного накопителя считывается строка матрицы йи суммируется но модулю два с цельюполучения многочлена проверочных символов г(х), который после выдачи всехинформационных символов выдается вканал связи. Кодирование заканчивается выдачей всех .символов, образующихкодовую последовательность. При декодировании кодовая последовательностьпринимается иэ канала связи; Посленрцема каждого кодового символа производится опрос постоянного накопителя, при этом, если принятый символединичный, то из ячейки постоянногонакопителя считывается строка матрицы Н и суммируется по модулю .дватс целью получения локатора ошибки3(х 1, который определяет позицию ошибки в принятом многочлене. После приема всех символов кодовой последовательности будет определен локаторошибки 811, который эатем используется в качестве адреса ячейки постоянного накопителя, Из ячейки постоянного накопителя считывается многочленошибки и производится исправление ошибочного символа.Таким образом, для выполнения кодирования - декодирования необходимо обращаться в постоянному накопителю после приема или выдачи каждого символа обрабатываемой последовательности, что значительно снижаетскорость обработки информации.Предложенный в данном -изобретенииподход к построению устройства кодирования - декодирования, основанныйна применении разбиения исходных последовательностей на группы символов,позволяет унеличить быстродействиеустройства кодирования - декодиронания за счет того, что выдача или прием группы символов происходит одновременно с чтением иэ постоянногонакопителя.На Фиг. 1 изображена схема логического запоминающего устройства наФиг. 2 представлен пример распределения области памяти постоянного накопителя,Логическое запоминающее устройство содержит постоянный накопитель 1,первый дешифратор 2, служащий для де.шифрации адреса, регистр адреса 3,коммутатор чтения 4, распределительсигналов 5, накопительный регистр б,первую 7 и вторую 8 группы элементовЙ, второй дешифратор 9, выходной регистр 10, ключ 11, хопмутатор адреса12, первый счетчик 13, третий дешифратор 14, второй счетчик 15, четвертый дешифратор 16, шины 17-34, н томчисле шину Запись в регистр а,рЕса17, шину "Чтением 18, шину "Установканачального состояния" 19, шину "Переключение распределителя" 20, шину"Установка нуля" 30, шиву "Обработано р символовф 31, вторую шину фус-,тановка нуля 32, шину "Обработанов символов" 33 и шину "Обработанои символов 34.Выходы элементов Я 7 подключеныхо входам первой группы регистра 10.Выход ключа 11 соединен с одним иэвходов регистра 10. Выходы накопи-.теля 1 подключены х информационнымвходам коммутатора 4, управляющиевходы которого соединены с выходамираспределителя сигналов 5, входыкоторого подключены к шинам 19 и 20,Выходы коммутатора 4 подключены хсчетным входам регистра б, выходикоторого соединены с одними из входон элементов И 8, другие входыкоторых подключены к шине 22, а выходы - ко входам третьего дешифратора 14, выходы которого соединены совходами второй группы регистра 10,выходы которого подключены к информационным входам коммутатора 12.Управляющий вход коммутатора 12соединен с шиной 27. Выходы коммутатора 12 подключены к одним из входов регистра адреса 2. Входы первогосчетчика 13 подключены соответственно к шинам 26 и 30, а выход соединен со входом четвертого дешифратора 16, выход которого подключен кшине 31. Входы второго счетчика 1515 соединены соответственно с шинами 26и 32, а выход подключен ко входувторого дешифратора 9, выходы которого соединены с шинами 33 и 34.Один из примеров распределения20 области памяти постоянного накопителя 1 приведен на Фиг. 2,В ячейках постоянного накопителя,разбитого на К к - разрядных зон 35,записано й таблиц размером 2 х.к,используемых для получения проверочныхсимволов при кодировании и локаторовошибок при декодировании.Устройство работает следующимобразом.Кодирование информации.В исходном состоянии распределительсигналов 5 находится в первом состоянии, регистр б установлен в нуленоесостояние сигналом на шине 21, ключ11 закрыт сигналом на шине 28,коммутатор 12 установлен в положениепередачи содержимого старших Р разря,дов выходного регистра 10 в регистрадреса 3 единичным сигналом на шике27, счетчики 13 и 15 установлены в40 нулевое состояние сигналами на шинах30 и 32 соотнетственно. В в старших разрядах выходного регистра 10записана информационная последонательность, а в и-а младших разрядахвыходного регистра 10 записаны нули.На шину 17 поступает сигнал, и содержимое старших р разрядов выходногорегистра 10 через коммутатор 12 переписывается в регистр 3 адреса. Спомощью этой операции задается адресячейки накопителя 1, На шину 26 поступают сигналы, и содержимое выходного регистра 10 посимвольно выдается в канал связи, при этомсчетчики 13 и 15 производят подсчет числа выданных символов. Одновременно с передачей содержимого регистра 10 в канал связи произнодитд ся чтение из ячейки постоянного накопителя 1 сигналом на шине 18, при этом содержимое группы разрядов ячейки накопителя 1 через коммутатор 4 поступает на счетные входы регистра б (при этом н регистре б Формируются проверочные символы кодоной последовательности. Номев группы разрядов эадает распределитель сигналов 5. После этого распределитель5 переключается н следующее состояние сигналом на шине 20, в результатвчего осуществляется выборка следующейгруппы разрядов содержимого ячеек накопителя 1, После того, как иэ регистра 10 будут выданы р символов информационной последовательности, очем будет свидетельствовать сигнална шине 31, следующий адрес ячейкинакопителя 1 из регистра 10 через 10коммутатор 12 перепишется в регистр3 адреса сигналом на шине 17. Далеебудет продолжаться процесс выдачиинформационных символов в канал связии одновременно формирование проверочных символов кодовой последовательности. И после того, как будет выданався информационная последовательностьо чем засвидетельствует сигнал нашине 33, на шину 23 поступит сигнал, 2 Ои содержимое регистра 6 (проверочныесимволы) переписывается в старше кразрядов регистра 10 через элементыИ 7. На шийу 26 поступают сигналысдвига, и пронерочные символы последовательно выдаются в канал связи,Число выданных символов подсчитывается счетчиком 15. Выдача проверочных символов продолжается до тех пор,пока не будет выдано п=щ +кодовыхсимволов, при этом на шине 34 появится сигнал. После этого, кодированиезаканчивается. Декодирование информации.В исходном состоянии распределитель сигналов 5 установлен в начальное состояние сигналом на шине 19, регистр 6 установлен в нулевое состояние на шине 21, выходной регистр 10 установлен .в нулевое состояние сигналом на шине 25, ключ 11 открыт 40 единичным сигналом на шине 28, коммутатор 12 установлен в положение передачи содержимого младших р разрядов выходного регистра 10 в регистр 3 адреса нулевым сигналом на шине 45 27, счетчики 13 и 15 установлены н нулевое состояние сигналами на шинах 30 и 32 соответственно. На шину 26поступают сигналы сдвига, и в регистр 10 через открытый ключ 11 записываются символы кодовой последовательности, принимаемые из канала связи по шине 29, при этом счетчики 13 и 15 ведут годсчет числа принятых сим" волов, Когда в регистр 10 будет записано р первых символов кодовой по следовательности, о чем засвидетельствует сигнал на шине 31, на шину 17 поступит сигнал, и р символов кодовой последовательности из регистра 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 раз быстрее.Формула изобретенияЛогическое запоминающее устройство, содержащее постоянный накокитель, первый дешифратор, регистр адреса, накопительный регистр, первую группу элементов И, выходной ре.гистр, ключ, второй дешифратор, при:чем входы постоянного накопителя подключены к выходам первого дешифратора, входы которого соединены с выходами регистра адреса, выходы накопительного регистра подключены к одним из входон элементов И первой .группы, другие входы которых подключены к шине "Перезапись", а выходы ко входам первой группы выходного регистра, вХоды ключа соединены соответственно с шинами "управление" и фВход устройства", а выход ключа соединен с одним из входов выходного регистра, о т л и ч а ю щ е е с я тем, что, с целью увеличения быстро"Выбор группыф, "Сдвиг влево" идоустановка нуля", причем выходы постоянного накопителя. подключены кинформационным входам коммутаторачтения, управляющие входы которогосоединены с выходами распределителясигналов, входы которого подключенык шинам "Установка начального состоянияф и "Переключение распределителя",выходы коммутатора чтения подключенык счетным входам накопительного регистра, выходы которого соединены содними из входов элементов И второйгруппы, другие входы . которых подключены к шине "Передачаф., а выходы -ко входам третьего дешифратора, выходы которого соединены со входамивторой группы выходного регистра,выходы которого подключены к информационным входам коммутатора адреса, управляющий вход коммутатора адреса соединен с шиной "Выбор группы", а выходы подключены к одним из входов 5 регистра адреса, входы первого счетчика подключены соответственно к шине "Сдвиг влево" и первой шине доустановка нуля", а выход соединен со входом четвертого дешифратора, входы второго счетчика соединены соответственно с шиной фСдвиг влево" .и второй шиной фустановка нуляф, а выход подключен ко входу второго дешифратора Источники информации,принятые во внимание при экспертизе1. Дроздов Е. А. Пятибратов А. П.Автоматическое преобразование и ко-,дирование информации, М., "Советс 20 кое Радио", 1964, с. 501-503.2. Авторское свидетельство СССРР б 10174, кл, С" 11 С 15/00, 1977