Устройство для кодирования кода рида-соломона над простым полем

 

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

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

Реслублин

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИ ИТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заязлено 19.12.77 (21) 2556858/18-24

Р1)М. Кл.2 с присоединением заявки ¹

/ (23) Приоритет

G 06 F 11/10

Н 04 Ь 1/10

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

СССР по делам изобретений и открытий

Опубликовано 3006.80. Бюллетень № 24

Дата опубликования описания 300680 (53) УДК 681. 14 (088. 8) (72) Автор. изобретения

A ..A.Давыдов (71) Заявитель (54) УСТРОЙСТВО ДЛЯ КОДИРОВАНИЯ КОДА РИДА-СОЛОМОНА

НАД ПРОСТЫМ ПОЛЕМ

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

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

Использование изобретения в системах передачи и хранени я дис кр ет ной информации (в частности, построение декодиру:ощих программ) необходимо 25 осуществлять с учетом того, что код

Рида-Соломона представляет собой код над простым полем. Это означает, что основанием кода является простое число, ЗЬ

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

Эти устройства содержат блок управления и вычислительный блок, состоящий из п-разрядов, каждый из которых содержит сумматор по модулю, основания кода и ячейку сдвига (n — количество контрольных символов);,для кодирования используется циклический корректирующий код над конечным полем с основанием . В частности, в качестве такого кода может быть взят и циклический вариант кода Рида-Соломона над простым полем (1).

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

Этот недостаток частично устранен в устройствах, которые не содержат

744576

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

Йаиболее близким по технической

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

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

Рида-Соломона над простым полем. Контрольные символы вычисляются путем ре- 15 шения системы управлений, а не путем деления многочленов.

Процесс вычисления контрольных символов состоит из четырех этапов.

В течение первых двух этапов вычис— ляютсн правые части уравнений. В течение третьего этапа система урав нений решается. На четвертом этапе

- полученные контрольные символы выдаются на выход (2). 25

Недостатком известного устройства является относительно низкое быстродействие. После подачи в устройство всех информационных символов необходимо еще 2п-тактов сдвига (второй и Я третий этап) прежде, чем начнут выдаваться контрольные символы.

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

Поставленная цель достигается тем, 35 что в устройство для кодирования кода Рида-Соломона над простым полем, содержащее блок управления, п-ячеек, сдвйга и и-сумматоров по модулю с, причем вход первого сумматора по модулю | является входом устройства, а выход и-го сумматора по модулю с является выходом устройства, введены n-кою утаторов,первый вход управления которых соединен с первйм выходом блока управления, а второй вход 45 управления которых — с(i+1) выходом блока управления, где i †порядковый номер коммутатора, выход i-го сумматора подключен к первому входу(i+1)-го сумматора, к первому инфор- 5р мационному входу i-го коммутатора и второму информационному входу (n+1-1)

ro коммутатора, выход i-го коммутатора подсоединен ко входу i-ой ячей" "ки сдвига, выход которой подсоедийен ко второму входу i-ro сумматора.

Введение коммутатора в каждый разряд вычислительного блока, вышеуказанные связи введенных коммутаторов с другими узлами устройства, а также новые связи сумматоров и ячеек 4() сдвига между собой позволяют повысить быстродействие устройства за счет исключeíèÿ второго этапа и совмеще ййя во времени третьего и четвертого этапов работы. В предлагаемом устрой- 65 стве правые части уравнений вычисляются уже на первом этапе работы, в связи с чем второй этап становится ненужным. Решение системы уравнений выполняется одновременно с выдачей контрольных символов, в связи с чем третий и четвертый этапы совмещаются во времени. В результате, в предлагаемом устройстве контрольные символы выдаются сразу же после поступлениА в устройство всех информационных символов. Следовательно, быстродействие предлагаемого устройства выше, чем быстродействие известного.

На чертеже представлена блок-схе- ма предлагаемого устройства для кодирования кода Рида-Соломона над простым полем.

Устройство содержит блок l управления, предназначенный для формирования двоичных управляющих сигналов, содержащий генератор тактовых импульсов; вычислительный блок 2, состоящий из п-разрядов, причем и-й разряд является старшим, 1-й разряд является младшим. Число разрядов и совпадает с количеством контрольных симвОлов и на единицу меньше кодового расстояния, сумматоры 3.|, ° .,3|„ по модулю основания кода (т.е. сумматоры по модулю q), ячейки 4(,...4, сдвига, первые входы 5.|,...,5 сумматоров, коммутаторы 6|,...,бр„ первые управляющие входы 7|,...,.7н коммутаторов, выходы 8, ...,8|| блока 1 управления, соответствующие разрядам вычислительного блока (выход 8„„соответствует m-му разряду), первые информационные входы 9,...,9 ком- . мут ат оров, вт орые, и нформацион ные входы 10<,...,10„, коммутаторов, вторые входы 11, . . °, 11„сумматоров, вторые управляющие входы 12А,..., 12 и коммутаторов, выход 13 блока 1 управления, связанный со вторыми управляющими входами коммутаторов.

В обозначениях вида 3, 4„„...,7,, 9„1,..., 12 индекс mуказйвает,,,,что соответствующий узел или соответствую-. щий вход принадлежат m-му разряду блока 2.

Тактовые входы всех ячеек 44,...4t, сдвига связаны с выходом генератора тактовых импульсов. (Эти связи на чертеже не показаны). .. Выход сумматора 3 1,„(где m=0,1,..., и-1) связан со входами 5,9„ 10>

Вйход сумматора 3 >.связан со вхо-, дами 9п и 101, а также подключен к выходу устрой ст в а .

Выходы 8 (где m=0,1,...,n) соединены со входами 7,„. Входы 12|, 121, 12 | объединены и подключены к выходу 13. Выход коммутатора б „„(где

m=0, 1,...,п) через ячейку сдвига под| соединен ко входу ll . Вход 51 связан со входом устройства.

Работу устройства можно разбить на два этапа.

744576

В течение первого этапа по информационным символам вычисляются правые части A„, (m=1 2,...,n) системы линейных уравнений, в которой неизвестными являются контрольные символы. I

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

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

Коммутаторы б,...,6» на всех этапах работы устройства функционируют следующим образом.

При поступлении сигнала 1 на вход 7 и сигнала 0 на вход 12>, на выход коммутатора б »проходит с(. число, поступившее на вход 9щ. При подаче сигнала " 1 " на вход 12 и сигнала 0 на вход 7»1 на выход коммутатора б проходит число, поступившее на вход 10„ . В случае, когда на оба управляющих входа 7 „и 12„пОдается сигнал 0, на выход коммутатора б „„проходит число ноль независимо от сигналов на информационных входах

9»1и 10, . Одновременно сигналы 1 на входы 7»„и 12 при работе устрой ства не подаются.

Ячейки 4,...,4 сдвига на всех этапах работы устройства функционируют сл едующим образом.

При подаче тактового импульса ячейка 4, выдает хранящееся в ней ф число йа вход 11 сумматора 3>. Од. новременно эта ячейка запоминает

Ч число, поступающее на ее вход с выхода коммутатора 6 .

Перед началом работы все ячейки сдвига обнуляются.

Первый этап работы устройства продолжается с тактов сдвига, где К вЂ” количество информационных сигналов. (Величина К не должна превышать разности g-n) . В течение первых (К-1) тактов сдвига на, выходе 13 блока 1 формируется сигнал 0, а на выходах 84,...,8» формируются сигнаJINNI 1 .

На К-m такте сдвига на выходе 13 блока 1 формируется сигнал . 1, a на выходах 8, . i °.,, 8» формируются сигналыы 0 . Ийформаци он ные символы а, а,...,а на первом этапе работы последовательно (начиная с символа а ) с периодом, равным такту сдвига, поступают на вход 51 сумматора 31 . (Каждый информационный символ может принимать одно из значений 0,1,..., ВВЙВЗВйФФЙФ ф®@вФ.

1 11

Указанная суммами„.= Е ()-.11А - пред3 ставляет собой значение i-го неизвестного системы уравнений, правые части A, A<,...,A> êîòoðûõ были получены на первом этапе работы устройства и является i-м контрольным символом. Таким образом, в течение второго этапа на выход устройства последовательно выдаются с периодом, равным такту сдвига, контрольные символы Ь1 ° b« . Ь». Выдачей последнего сймвола Ь работа устройства saканчивается.

cj-1) . После (К-1) -го такта сдвига в ячейку сдвига б „» (где m= 0, 1,...,n)

К-1 записывается сумма,, (К-1+и-2)с, U

Р 1 j

Где (0 ) обозначает число сочетаний из U по О, причем. (О ) = 1.(указан- ная сумма, как и все остальные суммы приведенные при описании работы устройства, вычисляется по модулю с, т.е. сумма может принимать одно иэ

10 значений О, 1,...,с -1) .

После К-го такта сдвига на выходе сумматора 3 (где m=0 1,...,и) появК, ляется сумма А,„=,Е(К-j+ q)>. Эта

15 j=1 сумма представляет соЪой правую часть

m-го уравнения система линейных уравнений, в которой неизвестными являются контрольные символы. Благодаря подаче на К-m такте сигнала 1 на 0 все входы 12»„ сумма A,с выхода сумматора 3, (где m=0.,1,.;.,n) через вход 10> коммутатора б,„+(,„проходит в ячейку сдвига 4»+, и запоминается в ней. На этом первый этап работы

25 устройства заканчивается.

Второй этап работы продолжается с и тактов сдвига. Поступление информационных символов на втором этапе прекращается, и на вход 5(в течение

3О второго этапа поступает число ноль.

На выходах 13 и 8» блока 1 управления в течение всего второго этапа формируется управляющий сигнал 0 ° .

На выходе 8 „„(где m=1,2,...,n-l) в

35 течение первых (n-m) тактов сдвига второго этапа управляющий сигнал равен 1, а затем, начиная.с (n-m+1)-го такта сдвига и до конца второго этапа управляющий сигнал ра4О вен 0 . Поэтому, после (и-m+1) -го такта сдвига второго этапа и до конца второго этапа в ячейке сдвига

4»1(где m=1,2,...,n) записано число

l ноль. Это число, поступая на вход

11, сумматора 3„„, не влияет на сумму.

В результате, на каждом i-м такте сдвига второго этапа (где i=1 2,...n) сумматоры 3, 3, „, . °,3» просто транслируют на выход, устройства сумму Ь1, полученную .на выходе сумматора 3»„.

744576

Формула иэо брет ени я а аж@:уьъ. а. 4 к - - .

Составитель В.Субботин

Техред И, Асталош Корректор M.Демчик

Редактор A.Äoëèíè÷

« « ° « «

Заказ 3794/13 Тираж 751 Подписное ЦНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

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

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

Рида-Соломона иад простым полем, содержащее блок управления, и-ячеек 15 сдвига и и-сумматоров halo модулю g, причем вход первого сумматора по модулю g является входом устройства, а выход п-го сумматора по модулю g является выходом устройства, о т - 2() личающеес ятем, что, сцелью повышения быстродействия устройA стна, оно содержит п-коммутаторов, первый вход управления кбторых соединен с первым выходом блока управле» ния, а второй вход управления которых — с (1+1) выходом блока управления, где 1 — порядковый номер комму" татора, выход 1-ro сумматора подключен к первому входу (i+1) -ro .сумматора, к первому информационному входу i-го коммутатора и второму информационному входу (n+1-1) -го коммутатора, выход 1-ro коммутатора подсоединен ко входу i-ой ячейки сдвига, ныход которой подсоединен ко второму входу i-го сумматора.

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

1. Питерсон У. Коды, исправляющие ошибки, М., Мир, 1976, с. 254, рис. 8.2.

2. Авторское свидетельство СССР

9443385, кл. G 06 F 11/10, 1974 (прототип) .