Устройство кодирования и вычисления синдромов помехоустойчивых кодов для коррекции ошибок во внешней памяти эвм

Устройство кодирования и вычисления синдромов помехоустойчивых кодов для коррекции ошибок во внешней памяти эвм

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике. Его использование в системах помехоустойчивого кодирования позволяет упростить устройство, содержащее блок 1 оперативной памяти, блок 2 умножения на постоянные коэффициенты, блок 3 суммирования по модулю два, буферные регистры 4-6. Благодаря введению формирователей 7, 8 адреса, коммутаторов 9, 10 и источника 11 нулевого кода в устройстве организуются последовательные процедуры кодирования и вычисления синдромов. 4 ил.

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

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

РЕСПУБЛИК (51)5 Н 03 М 13/00, 13/02

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

ПО ИЗОБРЕТЕНИЯМ И OTKPblTVIRM

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4722202/24 (22) 26.06.89 (46) 15.06.91. Бюл. ¹ 22 (71) Курский политехнический институт и

Институт проблем регистрации информации АН УССР (72) С. И. Егоров, А. П. Типикин, В. В, Петров и А. В. Гостев (53) 681.326(088.8) (56) Авторское свидетельство СССР № 1381719, кл. Н 03 M 13/00, 1986, Патент США ¹4562577,,кл. G 06 F 11/10, 1985.

„„Я2„„1656689 А1 (54) УСТРОЙСТВО КОДИРОВАНИЯ И ВЫЧИСЛЕНИЯ СИНДРОМОВ ПОМЕХОУСТОЙЧИВЫХ КОДОВ ДЛЯ КОРРЕКЦИИ

ОШИБОК ВО ВНЕШНЕЙ ПАМЯТИ ЭВМ (57) Изобретение относится к вычислительной технике. Его использование в системах помехоустойчивого кодирования позволяет упростить устройство, содержащее блок 1 оперативной памяти, блок 2 умножения на постоянные коэффициенты, блок 3 суммирования по модулю два, буферные регистры

4-6. Благодаря введению формирователей

7, 8 адреса, коммутаторов 9, 10 и источника

11 нулевого кода в устройстве организуются последовательные процедуры кодирования и вычисления синдромов. 4 ил, 1656689

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

На фиг. 1 приведена блок-схема устройства, на фиг, 2 — соединение входов и выходов первого коммутатора; на фиг. 3 и 4— последовательность обработки символа кодового слова в режиме соответственно декодирования и кодирования.

Устройство содержит блок 1 оперативной памяти, блок 2 умножения на постоянные коэффициенты, блок 3 суммирования по модулю два, первый — третий буферные регистры 4 — 6, первый 7 и второй 8 формирователи адреса, первый 9 и второй 10 коммутаторы и источник 11 нулевого кода, На фиг. 1 обозначены информационные входы 12, адресные входы 13, вход 14 управления режимом, выходы 15, а также вторые

16 и третьи 17 входы первого коммутатора

9 и его первые 18 и вторые 19 выходы, Конкретное подключение входов и выходов первого коммутатора 9 показано на фиг, 2, Блок 2 умножения на постоянные коэффициенты реализуется на программируемом ПЗУ.

Формирователи 7 и 8 адреса выполнены на счетчиках импульсов.

Тактовые и управляющие входы блоков на фиг, 1 не показаны, последовательности управляющих сигналов в разных режимах приведены на фиг, 3 и 4.

При описании устройства использованы следующие обозначения: и-длина кодового слова; k — длина информационной части кодового слова; 1 — количество контрольных символов в кодовом слове; А — глубина перемежения кодовых слов в секторе данных; г — размер символа кодового слова (в битах); ч — наименьшее целое, большее или равное log21; W — наименьшее целое, большее или равное log2 1

Источник 11 нулевого кода имеет размерность выходов r.

Рассмотрим процедуры вычисления синдрома и кодирования для кода Рида-Соломона (PC) определенного в поле Галуа

GF(2 ). В этом поле операции сложения и вычитания элементов поля совпадают. Порождающий многочлен РС кода с I контрольными символами имеет следующий вид:

9(х) =(x — a )(x — a )... (х — аь +1 1) где a — примитивный элемент GF(2 );

Ь вЂ” константа, Пусть с(х) — кодовый многочлен степени и (его коэффициенты — символы кодового слова), е(х)- многочлен ошибок (его коэффициенты — значения ошибок) и 0(x)=c(x)1 е(х)—

5 многочлен декодируемого слова (его коэффициенты — символы считанные иэ ВЗУ), Компоненты синдрома определяются подстановкой корней порождающего многочлена g(x) в многочлен декодируемого

10 слова

51-0(,г+ь) =с(, +ь)+ (+ь) =e(a +b) i =Оl — 1, и зависят только от многочлена ошибок.

Значение 0(x) чаще всего вычисляют по схеме Горнера:

0(х)=(...(0п — 1 X+ 0п — 2) X+...01) х+ Up.

Тогда 1-ю компоненту синдрома дает последний член последовательности S1 St

1 з St 1+1 n

Вычисление членов последовательности осуществляется по рекуррентной формуле

SI+ =Sild+ ФUn — — 1. 5Г=О, 25

При глубине перемежения символов кодовых слов в секторе, равной Л, сектор данных можно представить в виде

ПОСЛЕДОВатЕЛЬНОСтИ СИМВОЛОВ Чп-1O, V и—

1,1,...Мп-1, ):1: Vn — 2,0, Vn — 2,1,=, Vn — 2,il-1 ..., ЧО,О

Vo.1,..., Vo. Л-1.

Тогда вычисление синдромов кодовых слоев в секторе данных можно реализовать .по формуле

35 +1 +ь

Sf1 = Sf1a + Un — t — 1,1, (1) где i меняется от 0 до 1-1: J — от 0 до Л-1; t— от 0 до и — 1; Яч= 0 для всех 1 и J.

Кодирование систематического кода

40 Рида-Соломона заключается в размещении информационных символов в старших разрядах кодового слова и вычислении контрольных символов.

Пусть а(х) информационный многочлен

45 степени k-1, тогда кодовое слово можно представить в виде с(х)= х . а(х)+ р(х), где р(х) — остаток от деления многочлена х х

1 х а(х) на многочлен g(x) (коэффициенты q(x)

50 — контрольные символы).

Остаток можно получить в результате завершения после k шагов рекуррентной процедуры. имеющей следующий вид:

55 q (х)= q (x) x+ g(x) (q 1-1 + а -1-1), или с учетом перемежения

qf,1 =qf — 1+gt (at, — 1 — <,1+qf — 1,1) (2)

1656689 где i ìåíÿåòñÿ от О до I-1; J — от 0 до Л-1; t— от О до М-1 и q i — — О, q — ц = О ..

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

При вычислении синдромов по формуле (1) текущие компоненты синдрома

Яо хранятся в блоке 1 оперативной памяти

t по адресу. определяемому первым формирователем 7 — счетчиком компонент синдрома и контрольных символов и вторым формирователем 8 — счетчиком кодовых слов. Первый формирователь 7 предназначен для реализации перебора значений индекса I из формулы (1). второй формирователь 8 предназначен для реализации перебора значений индекса J, Счетчики формирователей 7 и 8 — двоичные с коэффициентами пересчета соответственно и Л.

Умножение Яц íà a осуществляется с помощью блока 2, содержащего 2! таблиц умножения на постоянные коэффициенты, Каждая из таблиц содержит

2 r-разрядных строк. Для умножения элемента поля, хранящегося в первом регистре

4, на постоянный коэффициент необходимо с помощью управляющего входа 14 блока 2 выбрать группу из I таблиц, используемых при декодировании. и с помощью вторых адресных входов блока 2 выбрать таблицу умножения на коэффициент a . Для ре+ь ализации сложения в формуле (1) используется блок 3 суммирования по модулю два, реализующий поразрядное суммирование по модулю два элементов поля.

Реализация вычисления синдромов по формуле (1) позволяет устройству обрабатывать сектор данных в процессе считывания его с носителя (в процессе ввода с входов

12). Вычисление всех синдромов завершается после считывания последнего символа последнего кодового слова B секторе, На фиг. 3 изображен процесс обработки очередного поступившего в устройство символа J-го кодового слова. Обработка символа осуществляется за 3(i+1) тактов.

Интервал времени, состоящий из первых трех тактов, называют предциклом, интервал времени. состоящий из последующих 3! тактов, называют циклом. В предцикле через второй коммутатор 10 во второй регистр

5 помещается символ кодового слова

U 1-ц, поданный на информационные входы 12 устройства. Содержимое первого формирователя 7 адреса не меняется и равно нулю (I=O). Цикл состоит из I групп, каждая из трех тактов. Содержимое первого формирователя 7 увеличивается на "1" по модулю

1 в момент завершения третьего такта в группе (I-I+1).

В каждой группе цикла устройство выполняет одни и те же операции над различными компонентами синдрома (таблицы умножения на постоянные коэффициенты при этом используются разные). В первом такте каждой группы текущая компонента синдрома Яц считываетсямз блока 1 оперативной памяти через второй коммутатор 10 в первый регистр 4. Во втором такте значение Яц, умноженное íà а, через второй коммутатор 10 подается на вторые входы блока 3 суммирования и по окончанию такта сумма

S)I а- + Un — 1 — ц запоминается в ь+ третьем регистре 6. В третьем такте новое

t+1 значение компоненты синдрома Яц через второй коммутатор 10 записывается в блок 1 оперативной памяти. Таким образом, каждая компонента сидрома обрабатывается три такта. В конце цикла содержимое второго формирователя 8 адреса увеличивается на единицу по модулю Л и устройство готово обработать символ следующего кодОВОГО СЛОВа Un-1-1,1+ 1 (ИЛИ 0л-2-r,o, ЕСЛИ

J= Л вЂ” 1).

Перед началом вычисления синдромов первый 7 и второй 8 формирователи адреса должны быть установлены в "0". Обработка первых Л символов 0л-1,о.0л-1,1."

V< — i — 1 отличается от обработки всех других символов тем, что в первом такте каждой группы цикла в первый регистр 4 через второй коммутатор 10 заносится не содержимое определенной ячейки блока 1 оперативной памяти, а нулевой элемент поля из источника 11 нулевого кода. Таким образом реализуются начальные условия фо с мул ы (1) Я ц =О ..

Прй выгрузке синдромов иэ устройства содержимое блока 1 оперативной памяти через второй коммутатор 10 подается на выходы 15 устройства, После выгрузки одной компоненты синдрома содержимое первого формирователя 7 увеличивается на "1" по модулю I. После завершения выгрузки синдрома целиком содержимое второго формирователя 8 увеличивается на единицу

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

1656689 символы всех кодовых слов сразу же записываются на носитель.

На фиг, 4 изображен процесс обработки очередного символа информационной части

J-го кодового слова, B первом такте пред- 5 цикла через второй коммутатор 10 во второй регистр 5 помещается символ информационной части кодового слова а!-1ч,!, поданный на информационные входы 12 устройства. Во втором такте предцикла из 10 блока 1 оперативной памяти считывается текущий контрольный символ qi-1,! и через второй коммутатор 10 подается на вторые входы блока 3 суммирования по модулю два.

В конце второго такта сумма Bk-1-ц+ ql-1,! за- 15

t поминается в третьем регистре 6, В третьем такте предцикла содержимое третьего регистра 6 через второй коммутатор 10 пересылается в первый регистр 4, Первая группа тактов цикла отличается 20 о последующих иэ-за необходимости учета условия q-1,! =О. Во втором такте первой группы из блока 1 оперативной памяти счиt тывается текущий контрольный символ q

9о (ак — t — ц + q) — ц) = цо.! 3 а и и с ыt+1 вается в блок 1 оперативной памяти, Во второй — !-й группах цикла устройство выполняет одни и те же операции над различными контрольными символами (таблицы умножения на постоянные коэффициенты при этом используют разные). В первом такте второй — 1-й групп произведение gl (дМ вЂ” 1 — ь! +q) — 1,!) через второй 40 коммутатор l0 с выходов блока 2 умножения подается на вторые входы блока 3 суммирования по модулю два и в конце такта сумма

qf — ц + d> (а — q-t,I + q f — 1.!) запоминается в третьем регистре 6. Во втором такте иэ 45 блока 1 оперативной памяти считывается текущий контрольный символ цц, который затем подается через второй коммутатор i 0 на входы второго регистра 5, где и запоминается по окончанию такта для использоваt+1. ния при вычислении qt+>, В третьем такте с выходов третьего регистра 6 символ с!ц з "исывается в блок 1 оперативной +1 памяти через второй коммутатоо 10.

Содержимое первого формирователя 7 в конце третьего такта предцикла и в;.ех. групп цикла, кроме последней, увеличивается на "1" по модулю I. В конце цикла содержимое второго формирователя 8 увеличивается на "1" по модулю А и устройство готово обработать следующий символ информационной последовательности, Начальная установка первого формирователя

7 в режиме кодирования равна I-1, второго формирователя 8 равна нулю. Начальные условия формулы (2) цц = 0 реализованы таким же образом, как начальные условия формулы (1) Зцо= О.

Обработка одного символа информационной последовательности занимает 3(!+1) тактов.

При выгрузке контрольных символов из устройства кодирования и вычисления синдромов содержимое блока 1 оперативной памяти через второй коммутатор 10 псдается на выходы 15 ус ройства. После выгрузки очередного контрольного символа содержимое второго формирователя 8 увеличивается на "1" по модулю А,. После выгрузки контрольных символов, расположенных на одной и той же позиции перемеженных кодовых слов, содержимое первого формирователя 7 уменьшается на "1", Перед выгрузкой контрольных символов первый формирователь 7 должен хранить число I — 1, второй формирователь 8 — нуль.

Объем оборудования в предлагаемом устройстве меньше, чем в известном на — 1 блоков оперативной памяти, 2! — 1 блоков постоянной памяти, — 1 блоков суммирования по модулю два, регистров, один !-входовый сумматор элементов поля Галуа.

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

Устройство кодирования и вычисления синдромов помехоустойчивых кодов для коррекции ошибок во внешней памяти

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

1656689

19

Фиг. 2 входами первого коммутатора, первые и вторые выходы которого подключены соответственно к вторым адресным входам блока умножения на постоянные коэффициенты и адресным входам блока оперативной памяти, выходы которых и выходы буферного регистра и источника нулевого кода соединены соответственно с вторыми — пятыми входами второго коммутатора, выходы которого подключены к информационным входам блока оперативной памяти, вторым

5 входам блока суммирования по модулю два. входам первого и второго буферных регистров и являются выходами устройства.

1656689

1656689

Составитель О.Ревинский

Техред М.Моргентал Корректор И.Муска

Редактор Е.Копча

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 2057 Тираж 470 Подписное

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

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