Устройство для определения местоположения ошибок в строке матричного накопителя

 

Союз Советских

Социалистических

Респубики

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ () ))896691 (6l ) Дополнительное к авт. свид-ву(22)Заявлено 22.04.80 (21) 2916966/18-24 с присоединением заявки рв) (23 1 Приоритет —

Опубликовано 07.01.82 ° бюллетень Р1е 1

Дата опубликования описания07.01 ° 82 (5! )М. Кл.

G 11 С 29/00

Государственный коинтет

СССР ао делаи нзабретеннй н открьпнй (53) УДК681 ° 327 (088.8) (72) Авторы изобретения

Г.В.Зайцев и Н.В.Семаков (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МЕСТОПОЛОЖЕНИЯ

ОШИБОК В СТРОКЕ МАТРИЧНОГО НАКОПИТЕЛЯ

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

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

Одно из известных устройств содержит вычислитель вектора ошибок строки и вычислитель номера ошибочной строки, при этом вычислитель вектора ошибок строки состоит иэ сумматора по модулю два с m входа-. ми и подключенного к выходу этого сумматора п -ðàçðÿäíîãî регистра сдвига (а х и — размер блока информации), а вычислитель номера ошибочной строки содержит регистр сдвига из m одинаковых ячеек, состоящих каждая из сумматора по модулю два и элемента памяти, rn индикаторов номера ошибочной строки, выполненных каждый из сум" сумматора по модулю два, триггера и вспомогательных элементов задержки $13.

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

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

89669

45 модулю два и подключенного к его выходу (m-n)-разрядного регистра сдвига, вычислитель номера ошибочной строки содержит преобразователь входных сигналов, кольцевой регистр сдвига с обратными связями, индикаторы соответствия содержимого двух названных регистров и при числе индикаторов менее rn — счетчик импульсов .сдвига, преобразователь входных сигналов состоит из m-l сумматоров по модулю дна со средним числом входов, близким к Д, кольцевой регистр сдвига состоит из m-1 ячеек, составленных каждая из сумматора по модулю два, с двумя или тремя входами, и элемента памяти, причем первый вход сумматора каждой ячейки соединен с соответствующим по номеру выходом преобразователя, второй — с выходом предыдущей ячейки, считая по кольцу,, . а третьи входы определенных сумматоров по модулю два соединены с выходом последней ячейки регистра $2), Основными недостатками этого устройства являются сложность входяжего в его состав вычислителя номера ошибочной строки и большая глубина схемы этого вычислителя (большое число элементов на пути сигзо нала), что отрицательно сказывается на надежности и быстродействии устройства.

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

Поставленная цель достигается тем, что в устройстве для определения местоположения ошибок в строке матричного накопителя, содержащем

4О

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

I 4 вход — к выходу предыдущего элемента памяти.

IlPH To H HK ToI> cooTBeTcTBHn информации целесообразно выполнить в виде индикатора тождества, т.е. блока, содержащего элемент НЕ-И и сумматоры по модулю дна, выходы которых подключены ко входам элемента НЕ-.И, выход которого является выходом индикатора соответствия информации, входами которого являются входы сумматоров по модулю два.

На фиг, I изображена схема предложенного устройства с одним индикатором тождества и вычислителе номера ошибочной строки (блок информации с размерами m х (m-1)=5 Х 4); на фиг. 2 — расположение в этом блоке информационных и проверочных символов и групп символов, входящих в каж-, дую проверку.

Устройство (фиг. 1) содержит вычислитель 1 вектора ошибок строки и вычислитель 2 номера ошибочной строки. Вычислитель I содержит входовой сумматор 3 по подулю дна и (m-1)-разрядныи регистр 4 сдвига.

Вычислитель 2 содержит кольцевой регистр 5 сдвига, индикатор 6 соответствия информации, выполненный в виде индикатора тождества, и счетчик 7. Регистр э содержит элементы

8 памяти и двухвходовые сумматоры

9 по модулю два. Ilервый вход каждого сумматора 9 подключен к соответствующему входу устройства, выход ко входу одноименного элемента 8 памяти, а второй вход — к выходу предыдущего элемента 8 памяти. Индикатор 6 содержит сумматоры 10 по модулю два и элемент НЕ-И 11, входы которого подключены к выходам сумматоров 10, а выход является выходом индикатора 6, входами которого являются входы сумматоров 10.

Соединение выхода регистра 5 с одним из входов элемента HE-И 11 (штрих-пунктир на фиг. 1) для работы устройства не существенно, но может быть полезным при диагностике неисправностей устройства.

Счетным входом счетчика 7 является вход 12, другой вход счетчика, соединенный с выходом элемента

НЕ-И ll, используется для останова счета. Выходами устройства являются выход последней ячейки регистра сдвига, откуда поразрядно ныво896691 б

1$

2S

3$

4$

$0

$$ дится вектор ошибок строки и выходы счетчика 7, отображающие номер ошибочной строки.

Действие устройства основано на том, что в записываемом в память прямоугольном блоке одна строка и один столбец отведены под проверочные символы, и эти символы выбираются при записи определенным образом. Расположение записываемых символов в блоке и разбиение их на группы проверок для рассматриваемого случая m.=-5 показано на фиг. 2.

Штриховыми линиями обозначены m=1 .группы проверок, охватывающих каж дая rn символов одного столбца (вертикальные проверки). Штрих-пунктирными линиями обозначены н группы проверок, охватывающих каждая m-! символов, расположенных в разных строках и столбцах (косые проверки), С точки зрения записи, для проверочных символов удобно использовать последний столбец, что позволяет обойтись без буферной памяти при записи. Проверочной строкой может служить любая строка, например, последняя (i=m-1). Значения проверочных символов при записи выбирают так, чтобы сумма по модулю два всех символов любой группы проверок была равна нулю. Ири этом при отсутствии ошибок для любого 1=0;1 m-2, т.е. для каждой вертикальной проверки, выполняется условие Qá„",=0, а для каждого !<>=О;1;...;m-I„ т.е. для каждой косой проверки — условие G a ° =0 (здесь символы скла1+3!j дываются по модулю два, а индексы— по модулю m). Ка»дый символ любой одной строки входит в одну вертикальную и одну косую проверку. Поэтому, если некоторые символы какой-то одной строки считываются с ошибкой, соответствующие этим символам проверочные суммы будут равны единице, а не нулю.

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

Пусть при считывании из блока информации по столбцам, начиная с первого (j=0), некоторые или все символы одной строки с неизвестным номером 1 считываются с ошибками. Ири считывании j-того столбца в регистр

4 с выхода сумматора 3 вводится

j-тый символ вектора ошибок 1-строки

1; = „ 0;„., по окончании считывания регистр 4 содержит все символы вектора ошибок i -той строки Е (!(,01„, ° .1„, .21

При этом элемент 1„. вектора ошибок

1 1 расположен в j-той от конца ячейке.

В кольцевом регистре 5 сдвига при считывании производится последовательное вычисление косых проверок, в результате чего .по окончании считывания регистр также содержит вектор ошибок. Если нумеровать ячейки регистра 5 такими же индексами, как соответствующие входам ячеек строки, 1=0,1,...,m-1, элемент 1„ вектора ошибок будет содержаться в ячейке с индексом m-2+1-j (сложение по модулю m). Так, если ошибки произошли в строке с индексом 1=О, элементы вектора ошибок этой строки

1 „,1 +,! „содержатся соответственно в ячейках с индексами m-2, m-3 ...1 0 (в нашем случае m=5 в третьей, второй, первой и нулевой ячейках). Ири подключении входов индикатора 6 к выходам регистров 4 и 5 (фиг. 1) и при ошибках в строке i=0 наличие тождества двух сопоставляемых векторов отмечается непосредственно по окончании считывания, и в счетчике

7 зафиксируется исходное нулевое состояние. Если ошибки произошли в строке с i ФО, то сигнал тождества на выходе индикатора 6 по окончании считывания отсутствует. В этом случае содержимое регистра 5 сдвигается от ячейки к ячейке до появления сигнала тождества. Ири этом число сдвигов 3 подсчитывается счетчиком

7, а номер ошибочной строки определяется по показаниям счетчика 7 как

i=-1mod m. Б рассматриваемом случае ошибкам в строках 0,1,2,3,4 — соответствуют показания счетчика О, 4,3,2,1 ° Ири отсутствии ошибок регистры 4 и 5 по окончании считывания содержат только нули, индикатор 6 индицирует тождество и в счетчике 7 фиксируется нулевое состояние.

Устройство с одним индикатором тождества (фиг. 1) является наиболее простым и надежным. Глубина схем регистра 5 и индикатора 6 минимальна, что обеспечивает быстродействие при сдвигах и индикации тождества.

Однако для определения номера ошибочной строки, после окончания считывания может потребоваться до

m-I сдвигов. Максимальное число необходимых сдвигов может быть уменьшено вплоть до нуля путем увели896691

8 действующее, чем индикаторы тождества.

Формула изобретения

1О

20

30

40

45 чения числа индикаторов 6. Если ввести в состав устройства rn индикаторов 6 и входы -того индикатора соединить с выходами регистра 5 в соответствии с расположением в нем элементов вектора ошибок 1 -той строки, номер ошибочной строки определяется сразу же по окончании считывания по сигналу тождества на выходе соответствующего индикатора. При наличии двух индикаторов максимальное число сдвигов уменьшается до;и-q g . .Возможны и другие промежуточные случаи. При числе индикаторов, меньшем 1н,номер ошибочной строки определяется по числу сдвигов, необходимых для индикации тождества одним из индикаторов, и по номеру индикатора, фиксируюцего тождества.

По сравнению с известным предлагаемое устройство обладает следующими преимуществами. Из состава устройства исключен преобразователь входных сигналов, содержащий в прототипе m-1 сумматоров со средним числом входов, близким к "/2 . В кольцевом регистре все ячейки выполнены и соединены одинаково, т.е. исключены имеющиеся в известном сумматоры с тремя входами и соответствующие ии обратные связи. Для определения ошибок в любой из 1т1 строк достаточно как минимум одного индикатора соответствия (тождества), тогда как в известном для индикации ошибок в проверочной строке требуется еще один специфический.индикатор: при таком же количестве индикаторов (два) максимальное число сдвигов, необходимых для иццикации (тождества) в предлагаемом устройстве, почти вдвое меньше, чем в известном. При любом числе индикаторов в устройстве все они являются одинаковыми индикаторами тождества, тогда как в известном все индикаторы различны, и кроме первых двух, более сложные и менее быстро1. Устройство для определения местоположения ошибок в строке матричного накопителя, содержащее mвходовой сумматор по модулю два (m— простое число), входы которого являются входами устройства, а выходы подключены ко входам (m-1)-разрядного регистра сдвига, выход которого является одним из выходов устройства, кольцевой регистр сдвига, содержащий двухвходовые сумматоры по модулю два и элементы памяти, выходы которых подключены ко входам индикаторов соответствия информации выходы которых соединены

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

2. Устройство по п. !, о т л и— ч а ю щ е е с я тем, что индикатор соответствия информации содержит элемент НŠ— И и сумматоры по модулю два, выходы которых подключены ко входам элемента НЕ-И, выход которого является выходом индикатора соответствия информации, входами которого являются входы сумматоров по модулю два.

Источники информации, принятые во внимание при экспертизе

1. IEEE Transactions on Computers. ч. 25, 11.- 6, 1976, р. 642-645.

2. 1ВМ Journal of Research and

Deve}opment. ч. 18, М 6, 1974, р. 579-588 (прототип).

896691

1, !

47 р

ФЬ Г

Составитель В,Рудаков

Редактор M.Лысогорова Техред И. Гайду Корректор Г.Огар

Заказ 11715/41 Тираж 623 Подписное

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

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

Филиал ШШ "11атент, г. Ужгород, ул. Проектная, 4

I!

gl

47

,1

1

1 ,1

l!

I

1

I 1

\

I

I

I y