Устройство декодирования для коррекции двойных ошибок Советский патент 1993 года по МПК H03M13/02 G11C29/00 

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

Целью изобретения является повышение надежности устройства декодирования за счет снижения аппаратурных затрат.

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

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

со со

СА) О

О 00

модулю два 3, первые 4 и вторые 5 выходы блоки вычисления синдрома соединены соответственно с входами первого 6 и второго 7 дешифраторов указания степени элемен- VDS юля, выходы В первого дешифратора соединены с первыми входами первого 9 и второго 10 селекторов указания начального и текущего местоположения ошибок, вторые 11 входы и выходы 12 первого селектора соединены с выходами второго дешифратора и вторыми входами второго селектора, выходами 13 соединенного с вторыми входами блока корректирующих сумматоров по модулю два, выходы 14 которого йвляю-тсл выходами устройства, .

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

риц Ж и Н2, содержащих одинаковые столбцы (элементы поля) переставленных из длина кода определенным образом: при задании матрицы Н через элементы поля Галуа эта подстановка имеет вид

,l-LN°

-J(er), в качестве примера конкретного исполнения для кода длины п 7 с No 2 проверочная матрица имеет вид:

10

и г «1 « « 1..т HI.

LH2

При появлении одиночных ошибок значения

синдрома S (Si, Sa) fa1, d} где 01 и о верхни;е и нижние значения столбцов матрицы Н, Причем сумма значений степеней l + J-No-2.. „

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

где первый и второй столбцы в каждом классе указывают на ошибочные разряды и со- ответствую щие им синдромы. Например, ееям ошибки произошли во втором и третьем разрядах, то им соответствует синдром S - (. Первая строка в классах определяет начальное местоположение векторов ошибок, остальные - текущие. Причем, каждый класс ошибок определяется соответствующим Нг i + j, z (n -1)/2. Отсюда следует, что зная N, а следовательно 10 и Ео, по сдвигу (.- 0) определяется и фактическое Е,

.Устройство работает следующим образом, Кодовое слово однородного кода поступает на входы 2 блока вычисления синдрома . На выходах 4 и 5 блока- 1 формируется значение синдрома d и а ,которые поступают из входы первого 6 и второго 7 дешифраторов указания степени элементов поля а. На одном из выходов 8 и 11 каждого из дешифраторов появляется единичный сиг5

0 0

5

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

Единичные сигналы на одних из выходов 8 и 11 поступают на входы селектора 9; в результате на одном из (г + 1) выходов 12 появится сигнал, указывающий на соответствующее N. Например, при ошибках во втором и четвергом разрядах синдром равен S (a1/Q); тогда на первом выходе дешифратора 6 и четвертом выходе дешифратора 7 появятся единичные сигналы, которые откроют соответствующий элемент И на пересечении шин первого селектора 9; в результате на одном из выходов 12, соответствующем N2 5, появится единичный сигнал. Данный сигнал поступает на вторые входы второго селектора 10 в соответствии с разбивкой на классы N.. То-есть, шина соответствующая

N0 2 соединена с нулевой вертикальной шиной селектора 10, шина с NI ° 0 - с 3 и 2 шинами, шина с№ 5-с6и 4 шинами, шина cNa l-clnS шинами селектора 10. Это следует непосредственно из приведенной выше таблицы для классов N. На первые 8 входы (горизонтальные шины) второго селектора 10 поступает сигнал о текущем значении 1, по которому происходит сдвиг начального состояния вектора ошибок.Так, например, при единичных сигналах на шинах и I 1 на выходах 13 селектора 10 появляются сигналы, указывающие на местоположении ошибок в слове в нулевом и третьем разрядах; при N3 1 и 4-третьем и шестом разрядах.

При одиночной ошибке-No 2 опрашивается нулевая вертикальная шина селектора 10 и вектор ошибок с выходов 8 дешифратора 6 поступает без изменения на выходы 13 селектора 10. Тем самым в блоке 3 происходит коррекция информации посту- пакадей на входы 2, сигналами, отображающими вектор ошибок с выходов 13 второго селектора 10.

Технико-экономическое преимущество- предложенного устройства декодирования для коррекции двойных ошибок по сравнению с прототипом заключается в повышении надежности устройства за счет снижения аппаратурных затрат благодаря исключению накопителя ПЗУ.для хранения разрядов синдромов о двух ошибках, двух дешифраторов для нахождения вектора ошибок по обоим синдромам, применению специальной проверочной матрицы однородных кодов. Так, для устройства реализующего код известным методом декодирования требуется ПЗУ с накопителем емкостью примерно равном (Сп2 + п) х х 2 logn (для п 31; 127 - емкость ПЗУ примерно равна 5 Кбит; 112 КБИТ) плюс 2n ;t .элементов в дешифраторах. Тогда как на реализацию введенных селекторов требуется п п + п п(Зп+1)/2 двухходовых

элементов И (для п 31; 127-это составляет примерно 1,5 .10 : 24 10 двухвходовых элементов .И). Это примерно в 2 lognf/3 раз меньше сложности известного устройства (для п 31; 127 - это составляете 3,4; 4,6 раза меньше сложности известного устройства. С увеличением длины кодового слова эта разница еще больше увеличивается).

Кроме того, по сравнению с прототипом

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

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

Ф о р м у л а и з о б р е т е н и я Устройство декодирования для коррекции двойных ошибок, содержащее блок вычисления синдрома, первый и второй дешифраторы указания степени элементов поля, блок корректирующих сумматоров по модулю два, причем входы блока вычисления синдрома и первые входы блока корректирующих сумматоров по модулю два объединены и являются информационными м контрольными входами устройства, выходы блока корректирующих сумматоров по модулю два являются выходами устройства,

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

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

ошибок, выходы которого соединены с соответствующими входами блока корректирующих сумматоров по модулю два.

Lrn

L-R

rn

DA

w