Устройство кодирования информации для памяти с записью неполными словами

 

УСТРОЙСТВО КОДИРОВАНИЯ; ИНФОРМАЦИИ ДЛЯ ПАМЯТИ С ЗАПИСЬЮ НЕПОЛНЫМИ СЛОВАМИ, содержащее группы сумматоров,,элемент ИЛИ и группы элементов И, отличающееся тем, что, с целью повышения быстродействия и упрощения устройства, первые входы элементов И первой и второй групп являются управляющими входами устройства, первые и вторые . входы сумматоров первой группы являются информационными входами соответственно первой и второй групп устройства, первые входы сумматоров второй группы являются информационными входами третьей группы устройства , входы сумматоров третьей, четвертой и пятой групп подключены к соответствующим выходам сумматоров первой группы, выходы сумматоров третьей группы подключены к вторым входам соответствующих сумматоров второй группы, выходы сумматоров четвертой группы подключены к вторым входам соответствующих сумматоров второй группы и к вторым входам элементов И первой группы, выходы которых подключены к вторым входам соответствующих сумматоров второй группы, выходы сумматоров пятой (Л группы подключены к вторым входам С элементов И второй группы, выходы которых подключены к входам элемента ИЛИ, выход элемента ИЛИ подключен к второму входу соответствующего сумматора второй группы, выходы сумматоров второй группы являются выходами устройства .

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

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

РЕСПУБЛИК (51) 4 С 11 С 29/00

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

IlO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

1 г

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

К АBTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 3625210/24-24 (22) 19.07.83 (46) 30.10.86, Бюл. Р 40 (72) А.В.Пастухов (53) 681.327.6(088.8) (56) Электроника, 1982, Ф 18, с. 37-40.

Хетагуров Я.A. Руднев Ю.П. Повы.шение надежности цифровых устройств методами избыточного кодирования, M.:

Энергия, 1974, с. 35, 51-53.

* (54)(57) УСТРОЙСТВО КОДИРОВАНИЯ.

ИНФОРМАЦИИ ДЛЯ ПАМЯТИ С ЗАПИСЪЮ НЕ-

ПОЛНЫИИ СЛОВАМИ, содержащее группы сумматоров,,элемент ИЛИ и группы элементов И, о т л и ч а ю щ е е с я тем, что, с целью повьппения быстродействия и упрощения устройства, первые входы элементов И первой и второй групп являются управляющими входами устройства, первые и вторые входы сумматоров первой группы являются информационными входами соответственно первой и второй групп

„„SU 12 7485 А 1 устройства, первые входы сумматоров второй группы являются информационными входами третьей группы устройства, входы сумматоров третьей, четвертой и пятой групп подключены к соответствующим выходам сумматоров первой группы, выходы сумматоров третьей группы подключены к вторым входам соответствующих сумматоров вто-. рой группы, выходы сумматоров четвертой группы подключены к вторым входам соответствующих сумматоров второй группы и к вторым входам элементов И первой группы, выходы которых подключены к вторым входам соответствующих сумматоров второй группы, выходы сумматоров пятой группы подключены к вторым входам элементов И второй группы, выходы В которых подключены к входам элемента

ИЛИ, выход элемента ИЛИ подключен к 2 второму входу соответствующего сумматора второй группы, выходы сумматоров второй группы являются выходами устройства.

1267485 где

40 х.

"1 х.

t 1

r„. =ГО+ о1;;".х;, I

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

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

64 информационными и 8 контрольными

1 разрядами при длине неполного слова, равной 8 разрядам; на фиг. 2 — пример проверочной матрицы корректирующего кода Хэмминга; на фиг, 3 — схема предлагаемого устройства для корректирующего кода Хэмминга с 64 информационными и 8 контрольными разрядами при длине неполного слова, равной

1 разряду: на фиг, 4 — пример использования предлагаемого устройства в составе запоминающего устройства.

Устройство содержит группы выходов

1, 2 и 3, группы входов 4, 5 и 6, входы 7 элементов И, группу элементов И 8, управляющие входы 9, сумматор 10, группы сумматоров 11 и 12, входы 13 групп сумматоров и группа сумматоров 14, сумматор 15, группу сумматоров 16, элемент ИЛИ 17, элемент И 18, элемент ИЛИ 19, сумматор

20 и вход 21 элемента И 18.

Запоминающее устройство содержит блок 22 памяти, блок 23 контроля, входной 24 и выходной 25 коммутаторы, блок 26 исправления ошибок с информационными 27 и контрольными 28 выходами, информационные 29 и контрольные 30 выходы блока 22, управляющие 31 и информационные 32 входы устройства, выходы 33 устройства.

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

1 виде где ® — знак суммирования по модулю два; ;3- коэффициенты 1 (О), определяемые пересечением, i-го

1 столбца, соответствующего

i-му разряду кода (кроме г, ), и 3-й стРоки проверочной матрицы кода.

Для проверочной матрицы кода Хэмминга с 64 информационными разрядами и 8 контрольными разрядами 1. ь (фиг. 2) каждый сумматор по модулю два, реализующий функцию (1) извест10 ного устройства, содержит не менее

32 входов; количество сумматоров равно 8, причем каждый сумматор имеет большую глубину логики, что приводит к большой задержке при кодировании.

В предложенном устройстве (фиг. 1). на каждом j ì выходе реализуется функция (2), в которой число ненулевых значений коэффициента о,.„, может быть существенно меньше, чем число

20 ненулевых значений коэффициентов

c(функции (1), т.е. меньше, чем

32, Это приводит к упрощению устройства и уменьшению задержки при формировании значений контрольных разр5 Рядов l> переменная выходов 1, 2, 3 устройства, определяющая значение j-го контрольного разряда для записи в память; переменная входов 4 устройства, определяющая значение

j-го контрольного разряда считанного полного слова; коэффициенты с ;;, соответствующие i-м информационным разрядам (столбцам проверочной матрицы кода), которые входят в неполное. слово; переменная входов 5 устройства, определяющая значение

i-го информационного разряда записываемого неполного слова; переменная входов 6 устрой- ства, определяющая значение

-ro информационного раз1 ряда считанного неполного слона; переменная входов 7 схем совпадения, соединенных с управляющими входами 9 устройства непосредственно или через дополнительную промежуточную схему (на фиг. 1 через сумматор 10 по модулю два), На входы 9 поступает двоичный адрес неполного, слова, определяющий его место в составе полного слова.

B случае, если некоторые переменные r, не зависят от адреса неполного слова, в функции (2) соответствующие значения u., предполагаются равными единице.

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

Особенности реализации устройства зависят от вида функции (2) и проверочной матрицы используемого корректирующего кода, Вид проверочной матрицы влияет на ту часть структуры, куда не входят сумматоры 11 и 12.

При этом для различных переменных r„. характерны три возможных схемных решения, Для примера проверочной матри(фиг ° 2) переменные первой группы выходов 1 образуются с участием соответствующих трех сумматоров 14 без использования управления переменной u., так как для любых

Э байтов Б.„(неполных слов) соответствующие части проверочной матрицы строк П,, П„, П, одинаковы (учет влияния особенностей столбца х, представлен на фиг, 1 пунктирной линией и будет рассмотрен ниже).

Второе схемное решение относится к формированию второй группы выхо- . дов 2 (r> Г,, Г, Г ), I"äe используется один общий сумматор 15 с участием или без управляющей переменной и Здесь двоичный адрес байта Б; в полном слове, поступающий с управляющих входов 9 устройства, совпадает с соответствующими двоичными кодовыми наборами столбцов проверочной матрицы, ограниченных строками Пэ, П, П и одинаковых для всех разрядов байта Б; .

Третье схемное решение относится к формированию одного выхода 3 (rq ) на основе нескольких сумматоров 16, причем один сумматор 16 работает для одной группы байтов Б,, Б, Б, Б у которых число единиц двоичного кода адреса байта четное, а другой— для группы Б,, Б,, Б, Б,, у которых число единиц двоичного кода адреса байта нечетное.

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

Разряд х, приводит к незначительному усложнению реализации проверочной матрицы для байта Б, . Например, вводятся дополнительные элементы совпадения 18 и объединения 19, связи и входы для сумматоров 14 16, 20, которые показаны на фиг. 1 и 3 пунктиром. При этом разряд х проходит на выход элемента 18 под управлением признака байта Б, по входу 21.

В этом случае значение разряда х, "подмешивается" в сумму ЕО+ в функции (2). Возможно также, что несущественна и иная реализация, когда значение выхода элемента 18 предварительно "подмешивается" суммированием по модулю два к соответствующим переменным (Г; ) в функции (2), прежде чем их значения поступят на входы 13, соответствующие выходам r,, rÄ, r,, r на фиг. 1 (проверкам П,, П . П

IT1 для столбца х, на фиг, 2).

Отличительные особенности, связанные с построением трех типов схемных решений для формирования трех . соответствующих групп выходов 1, 2, 3, рассмотренные на примере фиг. 1, характерны и для другой длины неполного слова. При этом количество выходов устройства может перераспределяться между соответствующими группами выходов 1, 2, 3 в вырожденном случае отдельные группы могут отсутствовать. Например, при длине неполного слова, равной одному разряду, получаем схему, изображаемую на фиг. 3 ° с основной группой выходов типа 2 (фиг. 1). Причем в этой схеме сумматор 15, соответствующий этой

4 группе, отсутствует. Устройство может быть построено не только на элементах И, ИЛИ, но и на элементах типа

И-НЕ, ИЛИ-НЕ (серия 133).

Устройство (фиг. 1) работает следующим образом.

При постуш1ении считанного и записываемого неполного слова на входы

6 и 5 устройства происходит их сравнение сумматорами 13, далее 8-разрядЗ5 ный результат сравнения свертывается по модулю 2 сумматорами 14-16, причем три сумматора 14 свертывают

8-разрядный результат сравнения по

S 1267485 а правилам проверки П,, П,, П,, сум- сумматора 16, в формировании r матор 15 свертывает все восемь раз- в соответствии со строкой П вЂ, сумма1 рядов, входящих в проверки П, П„, тором 20 и в формировании r,в соотП .и П„. Один из сумматоров 16 свер- вествии со строкой П вЂ” через элетывает четыре разряда из восьми, мент 19. причем на выходе соответствующего Устройство, изображенное на фиг. 4, элемента 8 формируется результат работает следующим образом. свертки для первой группы байтов Б В режиме Считывание" полное слово

Б, Б, Б проверки П . Второй сум- данных иэ информационных и контрольматор 16 свертывает другие четыре 1g ных разрядов поступает из ячейки паразряда, причем на выходе другого мяти блока 22 с выходов 29 и 30 в соответствующего элемента 8 форми- блок 26, затем исправленные значения руется результат свертки для второй информационных разрядов поступают с группы байтов Б,, Б, Б, Б проверки выходов 27 в коммутатор 25, который

П . На входы 7 поступают сигналы 1 формирует по управляющему сигналу на управления от сумматора 10 как ре- своем входе 31 соответствующее счиэультаты свертки по модулю два зна- танное неполное слово. чений разрядов адреса байта в слове, В режиме "Запись" производится поступающих на входы 9. В результате предварительное считывание слова из под действием управляющих сигналов 2б блока 22 аналогично режиму "Считывавходов 9 и значений контрольных раз- ние". При этом считанное неполное рядов r ; входов 4 сумматоры 12 фор- слово поступает на вход блока 23. Номируют на выходах 1, 2, 3 соответ- вое неполное слово поступает с входа ствующие значения контрольных раэ- . 32 на вход блока 23. Кроме того, рядов r р5 контрольные разряды старого слова

В случае наличия информационного поступают с выходов 28 на вход бло- разряда Х, в соответствии с видом ка 23, формирующего под управлением соответствующего столбца проверочной сигнала на входах 3 1 .новые контрольматрицы на схему 18 (вход 21) посту- ные разряды в соответствии с функципает признак байта Б., а на другой щ ей (2) или (4), которые вместе с вход элемента 18 — значение разря- новыми информационными разрядами выда Х,, В результате участие разряда хода коммутатора 24 записываются в

Х в формировании r, в соответствии блок 22. При этом коммутатор 24 под со строкой П, осуществляется по действием управляющего сигнала с дополнительному входу сумматора 14, входов 31 может формировать новое в формировании r в соответствии со полное или неполное слово, необхострокой П вЂ” по дополнительному входу димое для записи в память, 6

1267485

1267485

0 0

f 0

0fО

111

000

111

О1!

100! оf

5! 5253

111

0!О

771

000

011

100

10!

Раг. 2

1 0

Of ба !

01 ао о! б3 гг гз оо о 0

О 1! О

0 0

f ) r5! о

0 О

О 0

О О

1267485

Заказ 5784/51 Тираж 543

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

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

Ф

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

Составитель С. Шустенко

Редактор М. Циткнна Техред Н.Глущенко

Корректор E. Сирохман

Подписное