Устройство кодирования информации для памяти с записью неполными словами Советский патент 1986 года по МПК G11C29/00 

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

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

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

Устройство содержит группы выходо 1, 2 и 3, группы входов 4, 5 и 6, входы 7 элементов И, группу элементов И 8, управляющие вхЪды 9, сумматор lOj группы сумматоров 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-M выходе реализуетс с помощью многовходового Сумматора по модулю два значение контрольного разряда г, как результат суммирования по модулю два группы информационных разрядов X. полного слова в

виде

г. ® -х-,

(1)

где ф - знак суммирования по модутпо

два;

коэффициенты 1 (0), определяемые пересечением: i-ro

столбца, соответствующего i-му разряду кода (кроме ГУ), и j-й строки проверочной матрицы кода,

Для проверочной матрицы кода Хэмминга с 64 информационными разрядами kj и 8 контрольными разрядами г(фиг. 2) каждый сумматор по модулю два, реализующий функцию (1) известного устройства, содержит не менее 32 входов; количество сумматоров равно 8, причем каждый сумматор имеет большую глубину логики, что приводит к большой задержке при кодировании, В предложенном устройстве (фиг, 1). на каждом J-M выходе реализуется функция (2), в которой число ненулевых значений коэффициента о,.- может быть существенно меньше, чем число |Ненулевых значений коэффициентов функции (1), т.е. меньше, чем 32. Это приводит к упрощению устройства и уменьшению задержки при формировании значений контрольных разрядов Tj :

1 ® «;; (Х. (JKI ),(2)

Г-, г.

- переменная выходов 1, 2, 3

де г. устройства, определяющая значение j-ro контрольного разряда для записи в память;

г. - переменная входов 4 устройства, определяющая значение j-ro контрольного разряда считанного полного слова;

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

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

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

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

На входы 9 поступает двоичный адрес неполного .слова, определяющий его место в составе полного слова.

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

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

Особенности реализации устройства зависят от вида функции (2) и проверочной матрицы используемого корректирующего кода. Вид проверочной матрицы влияет на ту часть структуры куда не входят сумматоры 11 и 12. При этом для различных переменных Г| характерны три возможных схемных решения. Для примера проверочной матрицы (фиг. 2) переменные г , г. , г первой группы выходов 1 образуются с участием соответствующих трех сумматоров 14 без использования управления переменной и-, так как для любых байтов Bj (неполных слов) соответствующие части проверочной матрицы строк По, П,, П одинаковы (учет влияния особенностей столбца х, представлен на фиг. 1 пунктирной линией и будет рассмотрен ниже).

Второе схемное решение относится к формированию второй группы выходов 2 (TJ , г , Г5 , г), где используется один общий Сумматор 15с участием или без управляющей переменной U; . Здесь двоичный адрес байта Бв полном слове, поступающий с управляющих входов 9 устройства, совпадае с соответствующими двоичными кодовыми наборами стоТгбцов проверочной матрицы, ограниченных строками П, Пц , IIj и одинаковых для всех разрядов байта Bj.

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

Подсчет единиц .двоичного кода адреса может быть реализован, напри674854

мер, на трехвходовом сумматоре 10 с прямьпч и инверсным выходами, которые управляют соответствующими схемами совпадения 8 в случае свертки по с модулю два соответствующих разрядов для строки ng проверочной матрицы.

Разряд Xj, приводит к незначительному усложнению реализации проверочной матрицы для байта Б. Напри10 мёр, вводятся дополнительные элементы совпадения 18 и объединения 19, связи и входы для сумматоров 14, 16, 20, которые показаны на фиг. 1 и 3 пунктиром. При этом разряд х. прохоJ5 дит на выход элемента 18 под управлением признака байта В по входу 21. В этом случае значение разряда х подмешивается в сумму Z© в функции (2). Возможно также, что несу2Q щественна и иная реализация, когда значение выхода элемента 18 предварительно подмешивается суммированием по модулю два к соответствующим переменным (TJ) в функции (2), прежде 5 чем их значения поступят на входы 13, соответствующие выходам г , г , г.,, г на фиг. 1 (проверкам П, П. П, И для столбца х на фиг. 2).

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

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

При поступлении считанного и записываемого неполного слова на входы 6 и 5 устройства происходит их сравнение сумматорами 13, далее 8-разряд5 ньй результат сравнения свертьгеается по модулю 2 сумматорами 14-16, причем три сумматора 14 свертывают 8-разрядньй результат сравнения по правилам проверки П , П., П, S -ч 2 матор 15 свертывает все восемь разрядов, входящих в проверки Пз, П, П. и П, Один из сз мматоров 16 свертывает четыре разряда из восьми, причем на выходе соответствующего элемента 8 формируется результат свертки для первой группы байтов Б„, 3 s 6 проверки rig. Второй сумматор 16 свертывает другие четыре разряда, причем на выходе другого соответствующего элемента 8 формируется результат свертки для второй группы байтов Б, Б, Б4 , Б-, проверк Ilg. На входы 7 поступают сигналы управления от сумматора 10 как результаты свертки по модулю два значений разрядов адреса байта в слове поступающих на входы 9. В результате под действием управляющих сигналов входов 9 и значений контрольных разрядов rj входов 4 сумматоры 12 формируют на выходах 1, 2, 3 соответствующие значения контрольных разрядов rj . В случае наличия информационного - разряда Хр в соответствии с видом соответствующего столбца проверочной матрицы на схему 18 (вход 21) поступает признак байта Б, а на другой вход злемента 18 - значение разряда Х , В результате участие разряда Хд в формировании г в соответствии со строкой П(, осуществляется по дополнительному входу сумматора 14, в формировании г в соответствии со строкой rig - по дополнительному вход сумматора 16, в формировании г., в соответствии со строкой П т сумматором 20 и в формировании г ,в соотвествии со строкой ITj - через элемент 19. Устройство, изображенное на фиг, 4, работает следующим образом. В режиме Считывание полное слово данных из информационных и контрольных разрядов поступает из ячейки памяти блока 22 с выходов 29 и 30 в блок 26, затем исправленные значения информационных разрядов поступают с выходов 27 в коммутатор 25, который формирует по управляющему сигналу на своем входе 31 соответствующее считанное неполное слово. В режиме Запись производится предварительное считьгоание слова из блока 22 аналогично режиму Считывание, При этом считанное неполное слово поступает на вход блока 23. Новое неполное слово поступает с входа 32 на вход блока 23. Кроме того, контрольные разряды старого слова поступают с выходов 28 на вход блока 23, формирзпощего под управлением сигнала на входах 31 .новые контрольные разряды в соответствии с функцией (2) или (4), которые вместе с новыми информационными разрядами выхода коммутатора 24 записываются в блок 22. При этом коммутатор 24 под действием з равляющего сигнала с входов 31 может формировать новое полное или неполное слово, необходимое для записи в память.

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