Устройство для определения местоположения ошибок в строке матричного накопителя Советский патент 1982 года по МПК G11C29/00 

(54) УСТРОЙСТВО ДЛЯ OПPEДEJEHИЯ МЕСТОПОЛОЖЕНИЯ ОШИБОК В СТРОКЕ МАТРИЧНОГО НАКОПИТЕЛЯ

1

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

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

Одно из известных устройств содержит вычислитель вектора ошибок строки и вычислитель номера ошибочной строки, при этом вычислитель вектора ошибок строки состоит из сумматора по модулю два с m входами и подключенного к выходу этого сумматора п-разрядного регистра сдвига (т X п - размер блока информации), а вычислитель номера ошибочной строки содержит регистр сдвига из m одинаковых ячеек, состоящих каждая из сумматора по модулю два и элемента памяти, iT) индикаторов номера ошибочной строки, выполненных каадый из сумсумматора по модулю два, триггера и вспомогательных элементов задержки 1.

Основным недостатком этого устройства является пониженная эффективность использования памяти.

Из известных устройств наиболее близким техническим решением к предлагаемому изобретению является устройство, содержа1цее вычислитель вектора ошибок строки и вычислитель номера ошибочной строки, соединенные со входами устройства, при этом вычислитель вектора ошибок строки состоит из ю-входового сумматора по 3 модулю два и подключенного к его вых ду (m-n)-разрядного регистра сдвига вычислитель номера ошибочной строки содержит преобразователь входных сигналов, кольцевой регистр сдвига с обратными связями, индикаторы соответствия содержимого двух названных регистров и при числе индикаторов менее гп - счетчик импульсов .сдвига, преобразователь входных сиг налов состоит из т-1 сумматоров по модулю два со средним числом входов близким к , кольцевой регистр сдвига состоит из т-1 ячеек, составленных каждая из сумматора по моду лю два, с двумя или тремя входами, и элемента памяти, причем первый вх сумматора каждой ячейки соединен с соответствующим по номеру выходом преобразователя, второй - с выходом предыдущей ячейки, считая по кольцу,, . а третьи вхоДы определенных сумматоров по модулю два соединены с выходом последней ячейки регистра {2 Основными недостатками этого уст ройства являются сложность входяжего в его состав вычислителя номера ошибочной строки и большая глу бина схемы этого вычислителя (боль шое число элементов на пути сиг- нала),.что отрицательно сказывается на надежности и быстродействии устройства. Цель изобретения - повышение надежности и быстродействия устройства при простом числе строк. Поставленная цель достигается тем, что в устройстве для определения местоположения ошибок в строк матричного накопителя, содержащем т-входовой сумматор по модулю два (т - простое число), входы которого являются входами устройства, а выходы подключены ко входам (т-1)-раз рядного регистра сдвига, выход которого является одним из выходов устройства, кольцевой регистр сдвига, содержащий двухвходовые сумматоры по модулю два и элементы памяти, выходы которых подключены ко входам индикаторов соответстия информации, выходы которых соединены со входами счетчика, выходы которого являются другими выходами устрой ства, первый вход каждого двухвходового сумматора по модулю два подключены к соответствующему входу устройства, выход - ко входу одноименного элемента памяти, а второй ВХОД - к выходу пред1 1дущего элемента памяти. При этом индикатор соответствия информации целесообразно выполнить в виде индикатора тождества, т.е. блока, содержащего элемент НЕ-И и сумматоры по модулю два, выходы которых подключены ко входам элемента НЕ--И, выход которого является выходом индикатора соответствия информации, входами которого являются входы сумматоров по модулю два. На фиг. 1 изображена схема предложенного устройства с одним индикатором тождества и вычислителе номера ошибочной строки (блок информации с размерами m х (, 4) ; на фиг. 2 - расположение в этом блоке информационных и проверочных символов и групп символов, входящих в каждую проверку. Устройство (фиг. 1) содержит вычислитель 1 вектора ошибок строки и вычислитель 2 номера ошибочной строки. Вычислштель I содержит Г входовой сумматор 3 по подулю два и (т-1)-разрядный регистр 4 сдвига. Вычислитель 2 содержит кольцевой регистр 5 сдвига, индикатор 6 соответствия информации, выполненный в виде индикатора тождества, и счетчик 7. Регистр 3 содержит элементы 8памяти и двухвходовые сумматоры 9по модулю два. Первый вход каждого сумматора У подключен к соответствующему входу устройства, выход ко входу одноименного элемента 8 памяти, а второй вход - к выходу предьщущего элемента 8 памяти. Индикатор 6 содержит сумматоры 10 по модулю два и элемент НЕ-И 11, входы которого подключены к выходам сумматоров 10, а выход является выходом индикатора 6, входами которого являются входы сумматоров 10. Соединение выхода регистра 5 с одним из входов элемента НЕ-И 11 (штрих-пунктир на фиг. l) для работы устройства не существенно, но может быть полезным при диагностике неисправностей устройства. Счетным входом счетчика 7 является вход 12, другой вход счетчика, соединенный с выходом элемента НЕ-И 11, используется для останова счета. Выходами устройства являются выход последней ячейки регистра 4 сдвига, откуда поразрядно вывонтся вектор ошибок строки и выхоы счетчика 7, отображающие номер ошибочной строки.

Действие устройства основано на том, что в записываемом в-память прямоугольном блоке одна строка и один столбец отведены под проверочные символы, и эти символы выбираются при записи определенным образом. Расположение записываемых символов в блоке и разбиение их на группы проверок для рассматриваемого случая показано на фиг. 2. Штриховыми линиями обозначены т-1 группы проверок, охватывающих каждая гя символов одного столбца (вертикальные проверки). Штрих-пунктирными линиями обозначены уп группы проверок, охватывающих каждая т-1 символов, расположенных в разных строках и столбцах (косые проверки). С точки зрения записи, для проверочных символов удобно использовать последний столбец, что позволяет обойтись без буферной памяти при записи. Проверочной строкой может служить любая строка, например, последняя (). Значения проверочных символов при записи выбирают так, чтобы сумма по модулю два всех символов любой группы проверок бьша равна нулю. При этом при отсутствии ошибок для любого , 1 ,. ..,т-2, т.е. для каяадой вертикальной проверки, выполняется условие 5,, а для каждого , 1.. . ;гп- , т.е. для каждой косой проверки - условие С с|. . .0 (здесь символы складываются по модулю два, а индексы по модулю т). Каждый символ любой одной строки входит в одну вертикальную и одну косую проверку. Поэтому, если некоторые символы какой-то одной строки считываются с ошибкой, соответствующие этим символам проверочные суммы будут равны единице, а не нулю.

Устройство работает следующим образом.

Пусть при считывании из блока информации по столбцам, начиная с первого (),некоторые или все символы одной строки с неизвестным номером i считываются с ошибками. При считывании j-того столбца в регистр 4 с выхода сумматора 3 вводится j-тый оимвол вектора ош1бок i-строки Jii S Зд , по окончании считывания регистр 4 содержит все символы

966916

вектора ошибок i-той строки Е

При этом элемент I вектора ошибок расположен в j-топ от конца ячейке, 5 В кольцевом регистре Ь сдвига при считывании производится последовательное вычисление косых проверок, в результате чего -по окончании считывания регистр также содержит

10 вектор ошибок. Если нумеровать ячейки регистра 5 такими же индексами, как соответствующие входам ячеек строки, ,1,... ,т-1 , элемент 1. вектора ошибок будет содержаться в

15 ячейке с индексом m-2+i-j (сложение по модулю т). Так, если ошибки произошли в строке с индексом , элементы вектора ошибок этой строки

о Oio4-,о соответственно

го в ячейках с индексами т-2, т-3,.,.1,0 (в нашем случае в третьей, второй, первой и нулевой ячейках). При подключении входов индикатора 6 к выходам регистров 4 и 5 (фиг. 1)

JS и при ошибках в строке , наличие . тождества двух сопоставляемых векторов отмечается непосредственно по окончании считывания, и в счетчике 7 зафиксируется исходное нулевое

30 состояние. Если ошибки произошли в строке с i 0, то сигнал тождества на выходе индикатора 6 по окончании считывания отсутствует. В этом случае содержимое регистра 5 сдвигаетJ5 ся от ячейки к ячейке до появления сигнала тождества. При этом число сдвигов В подсчитывается счетчиком 7, а номер ошибочной строки определяется по показаниям счетчика 7 как

40 mod m. В рассматриваемом случае ошибкам в строках 0,1,2,3,4 - соответствуют показания счетчика О, 4,3,2,1. При отсутствии ошибок регистры 4 и 5 по окончании считывания

j содержат только нули, индикатор 6 индицирует товдество и в счетчике 7 фиксируется нулевое состояние.

Устройство с одним индикатором тождества (фиг. l) является наиболее простым и надежным. Глубина схем

SO регистра 5 и индикатора 6 минимальна, что обеспечивает быстродействие при сдвигах и индикации толадества. Однако для определения номера ошибочной строки, после окончания

55 считывания может потребоваться до т-1 сдвигов. Максимальное число необходимых сдвигов может быть уменьшено вплоть до нуля путем увели7чения числа индикаторов 6. Если ввести в состав устройства m индика торов 6 и входы i -того индикатора соединить с выходами регистра 5 в соответствии с расположением в нем элементов вектора ошибок -i -той стро ки, номер ошибочной строки определяется сразу же по окончании считывания по сигналу тождества на выходе соответствующего индикатора. При наличии двух индикаторов максимальное число сдвигов уменьшается до т-(/ .Возможны и другие промежуточные случаи. При числе индикаторов, мень шем vn, номер ошибочной строки определяется по числу сдвигов, необходимых для индикации тождества одним из индикаторов, и по номеру индикатора, фиксирующего тоя хества. По сравнению с известным предлагаемое устройство обладает следующими преимуществами. Из состава уст ройства исключен преобразователь входных сигналов, содержащий в прототипе т-1 сумматоров со средним числом входов, близким к rr/ij . В кольцевом регистре все ячейки выполнены и соединены одинаково, т.е. исключены имеющиеся в известно су 1маторы с тремя входами и соответ ствующие им обратные связи. Для определения ощибок в любой из m строк достаточно как минимум одного индикатора соответствия (тождества), тогда как в известном для индикации ошибок в проверочной строке требуется еще один специфический.индикатор : при таком же количестве индикаторов два) максимальное число сдвигов, необходимых для индикации (тождества) в предлагаемом устройстве, почти вдвое меньше, чем в известном. При любом числе индикаторов в устройстве все они являются одинаковыми индикаторами тождества, тогда как в известном все индикаторы различны, и кроме первых двух, более сложные и менее быстродействую1цее, чем индикаторы тождества. Формула изобретения 1.Устройство для определения местоположения ошибок в строке матричного накопителя, содержащее твходовой сумматор по модулю два (т простое число), входы которого являются входами устройства, а выходы подключены ко входам (т-1)-разрядного регистра сдвига, выход которого является одним из выходов устройства, кольцевой регистр сдвига, содержащий двухвходовые сумматоры по модулю два и элементы памяти, выходы которых подключены ко входам индикаторов соответствия информации выходы которых соединены со входами счетчика, выходы которого -являются другими выходами устройства, отличающееся тем, что, с целью повышения надежности и быстродействия устройства, в нем первый вход каждого двухвходового сумматора по модулю два подключен к соответствующему входу устройства, выход - ко входу одноименного элемента памяти, а второй вход - к выходу предьщущего элемента памяти. 2.Устройство по п. 1, отличающееся тем, что индикатор соответствия информации содержит элемент НЕ-И и сумматоры по модулю два, выходы которых подключены ко входам элемента НЕ-И, выход которого является выходом индикатора соответствия информации, входами которого являются входы сумматоров по модулю два. Источники информации, принятые во внимание при экспертизе 1.IEEE Transactions on Computers. V. 25, № 6, 1976, p. 642-645. 2.IBM Journal of Research and Development, v. 18, № 6, 1974, p. 579-588 (прототип).

yg, f 1 41 К l Ч1 41 Ч ч 41 I I | I I ч . I Гч I l |V ч N ч |

0уг. « 1 ,|