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

,П.Ти 8)видетельство СССН 03 М 13/00, 1986 %4562577, кл,60 Е 11/10,ГОСУДАРСТВЕН.ЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР К АВТОРСКОМУ СВИДЕТЕЛЬСТВ(71) Курский поИнститут проблции АН УССР(56) Авторское с1 Ф 1381719, кл.Патент США1985. л. %22литехнический институт ием регистрации информа(54) УСТРОЙСТВО КОДИРОВАНИЯ И ВЫЧИСЛЕНИЯ СИНДРОМОВ ПОМЕХОУСТОЙЧИВЫХ КОДОВ ДЛЯ КОРРЕКЦИИ ОШИБОК ВО ВНЕШНЕЙ ПАМЯТИ ЭВМ (57) Изобретение относится к вычислительной технике. Его использование в системах помехоустойчивого кодирования позволяет упростить устройство, содержащее блок 1 оперативной памяти, блок 2 умножения на постоянные коэффициенты, блок 3 суммирования по модулю два, буферные регистры 4-6. Благодаря введению формирователей 7, 8 адреса, коммутаторов 9, 10 и источника 11 нулевого кода в устройстве организуются последовательные процедуры кодирования и вычисления синдромов. 4 ил,Изобретение относится к вычислительной технике и может быть использовано в системах помехоустойчивого кодирования,Цель изобретения - упрощение устройства.На фиг, 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.При описании устройства использованы следующие обозначения: и-длина кодового слова; М - длина информационной части кодового слова; 1 - количество контрольных символов в кодовом слове; Л - глубина перемежения кодовых слов в секторе данных; г - размер символа кодового слова (в битах); ч - наименьшее целое, большее или равное 1 о 921; И/ - наименьшее целое, большее или равное 1 о 92 Л,Источник 11 нулевого кода имеет размерность выходов г,Рассмотрим процедуры вычисления синдрома и кодирования для кода Рида-Соломона (РС) определенного в поле Галуа 6 Е(2). В этом поле операции сложения и вычитания элементов поля совпадают, Порождающий многочлен РС кода сконтрольными символами имеет следуе 1 дий вид:91,Х) = 1,Х - О, ) (Х - гР )(х дь + - 1)где й - примитивный элемент ОР(2 );Ь - константа,Пусть с(х) - кодовый многочлен степении (его коэффициенты - символы кодовогослова), е(х)- многочлен ошибок (его коэффициенты - значения ошибок) и 0(х)=с(х)+ е(х) -5 многочлен декодируемого слова (его коэффициенты - символы считанные иэ ВЗУ),Компоненты синдрома определяются подстановкой корней порождающегомногочлена 9(х) в многочлен декодируемого10 словаЬ =0(с ) =сф )++ е ( + ь) - е (г + ь);и зависят только от многочлена ошибок.Значение О(х) чаще всего вычисляют посхеме Горнера:О(хН(Оп - 1х+ Оп - 2) х+01) х+ Оо,Тогда 1-ю компоненту синдрома дает последний член последовательности 51, Ь,З 11+1иВычисление членов последовательности осуществляется по рекуррентной формуле51 += Я С + -1- О - 1 - 1. ЯР = О,25При глубине перемежения символов кодовых слов в секторе, равной Л, сектор данных можно представить в видеПОСЛЕдОВатЕЛЬНОСтИ СИМВОЛОВ Чп,О, Чп 30 1,1 ЧпЛ; Чп - 2,о, Чп - 2,1,=, Чп - 2 Л,; Чо,оЧо.1 Чо. Л.Тогда вычисление синдромов кодовыхслоев в секторе данных можно реализовать.по формуле35 +1 +ья 1 =З 1,г +О. -- 1,1, (1)гдеменяется от Одо 1-1:) - от Одо Л;1 -от 0 до и - 1; 5= 0 для всехи.Кодирование систематического кода40 Рида-Соломона заключается в размещенииинформационных символов в старших разрядах кодового слова и вычислении контрольных символов.Пусть а(х) информационный многочлен45 степени 1-1, тогда кодовое слово можнопредставить в видес(х)= х а(х) + ц(х),где ц(х) - остаток от деления многочлена х хх а(х) на многочлен 9(х) (коэффициенты ц(х)50 - контрольные символы). Остаток можно получить в результатезавершения после М шагов рекуррентнойпроцерры. имеющей следующий вид:55 ц (х)= ц(х) х+ 9(х) (ц+ ак-1),или с учетом перемеженияЦ, =Ц 1 - 1, +9 (а - 1 - , + Ц 1 - 1,1) (2)5 10 15 20 25 30 35 40 45 50 55 гдеменяется от 0 до 1-1;) - от О до Л; т - от 0 до Ми цГ -- О, с - ц = 0Устройство работает следующим образом.При вычислении синдромов по формуле (1) текущие компоненты синдрома Яц хранятся в блоке 1 оперативной памятипо адресу. определяемому первым формирователем 7 - счетчиком компонент синдрома и контрольных символов и вторым формирователем 8 - счетчиком кодовых слов. Первый формирователь 7 предназначен для реализации перебора значений индекса 1 из формулы (1). второй формирователь 8 предназначен для реализации перебора значений индекса), Счетчики формирователей 7 и 8 - двоичные с коэффициентами пересчета соответственно 1 иЛ,Умножение Яц на с осуществляется с помощью блока 2, содержащего 2 таблиц умножения на постоянные коэффициенты, Каждая из таблиц содержит 2 г-разрядных строк, Для умножения элемента поля, хранящегося в первом регистре 4, на постоянный коэффициент необходимо с помощью управляющего входа 14 блока 2 выбрать группу из 1 таблиц, используемых при декодировании. и с помощью вторых адресных входов блока 2 выбрать таблицу умножения на коэффициент с . Для ре+ьализации сложения в формуле (1) используется блок 3 суммирования по модулю два, реализующий поразрядное суммирование по модулю два элементов поля.Реализация вычисления синдромов по формуле (1) позволяет устройству обрабатывать сектор данных в процессе считывания его с носителя (в процессе ввода с входов 12). Вычисление всех синдромов завершается после считывания последнего символа последнего кодового слова в секторе,На фиг. 3 изображен процесс обработки очередного поступившего в устройство символа )-го кодового слова, Обработка символа осуществляется за 3(1+1) тактов. Интервал времени, состоящий из первых трех тактов, называют предциклом, интервал времени. состоящий из последующих 31 тактов, называют циклом. В предцикле через второй коммутатор 10 во второй регистр 5 помещается символ кодового слова О,-1-ц, поданный на информационные входы 12 устройства. Содержимое первого формирователя 7 адреса не меняется и равно нулю (1=0), Цикл состоит из групп, каждая из трех тактов. Содержимое первого формирователя 7 увеличивается на "1" по модулю 1 в момент завершения третьего такта вгруппе (1=1+1),В каждой группе цикла устройство выполняет одни и те же операции над различными компонентами синдрома (таблицыумножения на постоянные коэффициентыпри этом используются разные). В первомтакте каждой группы текущая компонентасиндрома Яц считываетсямз блока 1 оперативной памяти через второй коммутатор 10в первый регистр 4. Во втором такте значение Яц, умноженное на сР, через второй коммутатор 1 О подается на вторыевходы блока 3 суммирования и по окончанию такта суммаМ ц +Оп - 1 - ц запоминается вь+третьем регистре 6. В третьем такте новое+значение компоненты синдрома Яц через второй коммутатор 1 О записывается вблок 1 оперативной памяти. Таким образом,каждая компонента сидрома обрабатывается три такта. В конце цикла содержимоевторого формирователя 8 адреса увеличивается на единицу по модулю Л и устройствоготово обработать символ следующего кодового слова Оп-ц+1 (или Опч,о, если)= Л).Перед началом вычисления синдромовпервый 7 и второй 8 формирователи адресадолжны быть установлены в "0". Обработка первых Л символов Оп,о.Оп,.".Чп -Л - 1 отличается от обработки всехдругих символов тем, что в первом тактекаждой группы цикла в первый регистр 4через второй коммутатор 10 заносится несодержимое определенной ячейки блока 1оперативной памяти, а нулевой элемент поля из источника 11 нулевого кода. Такимобразом реализуются начальные условияформулы (1) Яц=0Прй выгрузке синдромов иэ устройствасодержимое блока 1 оперативной памятичерез второй коммутатор 10 подается навыходы 15 устройства, После выгрузки одной компоненты синдрома содержимое первого формирователя 7 увеличивается на "1"по модулю . После завершения выгрузкисиндрома целиком содержимое второгоформирователя 8 увеличивается на единицуВ режиме кодирования реализация вычисления контрольных символов по формуле (2) позволяет устройству обрабатыватьинформационную последовательность впроцессе записи ее на носитель. Вычисление всех контрольных символов завершается после поступления в устройствопоследнего символа информационной последовательности, после чего контрольныесимволы всех кодовых слов сразу же записываются на носитель,На фиг, 4 изображен процесс обработкиочередного символа информационной части/-го кодового слова, В первом такте предцикла через второй коммутатор 10 во второйрегистр 5 помещается символ информационной части кодового слова ач поданный на информационные входы 12устройства. Во втором такте предцикла из 10блока 1 оперативной памяти считываетсятекущий контрольный символ рь 1, и черезвторой коммутатор 10 подается на вторыевходы блока 3 суммирования по модулю два.В конце второго такта сумма ач,+ рь, запоминается в третьем регистре 6, В третьемтакте предцикла содержимое третьего регистра 6 через второй коммутатор 10 пересылается в первый регистр 4,Первая группа тактов цикла отличается 20о последующих иэ-за необходимости учетаусловия р.1,=0. Во втором такте первойгруппы из блока 1 оперативной памяти счи 1тывается текущий контрольный символ ро,поступающий затем через второй коммутатор 10 на входы второго регистра 5, в котором он запоминается по окончанию тактадля использования при вычислениир 1 В третьем такте с выходом блока 2умножения произведение 309 о (Жс -- ц + р 1 - 1,) = Цо, 3 а и и с ыт+1вается в блок 1 оперативной памяти,Во второй - -й группах цикла устройство выполняет одни и те же операции надразличными контрольными символами (таблицы умножения на постоянные коэффициенты при этом используют разные). Впервом такте второй - -й групп произведен ие 9 (д( - 1 - ь + р - 1,) через второй 40коммутатор 10 с выходов блока 2 умноженияподается на вторые входы блока 3 суммирования по модулю два и в конце такта суммарГ - ц + б (ак - 1-ц + сд - 1,) запоминается в третьем регистре 6 Во втором такте иэ 45блока 1 оперативной памяти считываетсятекущий контрольный символ рц, которыйзатем подается через второй коммутатор 0на входы второго регистра 5, где и запоминается по окончанию такта для использова+1.ния при вычислении р+цВ третьемтакте с выходов третьего регистра 6 символрц 3 "исывается в блок 1 оперативной+1памяти через второй коммутатоо 10.Содержимое первого формирователя 7в конце третьего такта предцикла и в;,ех,групп цикла, кроме последней, увеличивается на "1" по модулю , В конце цикла содержимое второго формирователя 8 увеличивается на "1" по модулю А и устройство готово обработать следующий символ информационной последовательности, Начальная установка первого формирователя 7 в режиме кодирования равна -1, второго формирователя 8 равна нулю. Начальные условия формулы (2) рц= 0 реализованы таким же образом, как начальные условия формулы (1) Зц= О.Обработка одного символа информационной последовательности занимает 3(+1) тактов.При выгрузке контрольных символов из устройства кодирования и вычисления синдромов содержимое блока 1 оперативной памяти через второй коммутатор 10 псдается на выходы 15 усройства. После выгрузки очередного контрольного символа содержимое второго формирователя 8 увеличивается на "1" по модулю 1. После выгрузки контрольных символов, расположенных на одной и той же позиции перемеженных кодовых слов, содержимое первого формирователя 7 уменьшается на "1", Перед выгрузкой контрольных символов первый формирователь 7 должен хранить число- 1, второй формирователь 8 - нуль.Объем оборудования в предлагаемом устройстве меньше, чем в известном на- 1 блоков оперативной памяти, 2 - 1 блоков постоянной памяти,- 1 блоков суммирования по модулю два,регистров, один -входовый сумматор элементов поля Галуа. Формула изобретения Устройство кодирования и вычисления синдромов помехоустойчивых кодов для коорекции ошибок во внешней памяти ЭВМ, содержащее первый буферный регистр, выходы которого соединены с первыми адресными входами блока умножения на постоянные коэффициенты, второй буферный регистр, блок суммирования по модулю два, выходы которого подключены к входам третьего буферного регистра, и блок оперативной памяти, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, в него введены формирователи адреса, коммутаторы и источник нулевого кода, первые входы первого и второго коммутаторов являются соответственно адресными информационными входами устройства, управляющий вход блока умножения на постоянные коэффициенты является входом управления режимом устройства, выходы второго буферного регистра соединены с первыми входами блока суммирования по модулю два, выходы первого и второго формирователей адреса соединены соответственно с вторыми и третьимивходами первого коммутатора, первые и вторые выходы которого подключены соответственно к вторым адресным входам блока умножения на постоянные коэффициенты и адресным входам блока оперативной памяти, выходы которых и выходы буферного регистра и источника нулевого кода соединены соответственно с вторыми - пятыми входами второго коммутатора, выходы которого подключены к информационным входам блока оперативной памяти, вторым 5 входам блока суммирования по модулю два.входам первого и второго буферных регистров и являются выходами устройства.1656689Составитель О.Ревинский Редактор Е.Копча Техред М. Моргентал Корректор И.М Заказ 2057 Тираж 470 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС113035, Москва, Ж, Раушская наб., 4/5Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 10