Устройство для кодирования кода рида-соломона над простым полем Советский патент 1980 года по МПК G06F11/10 H03M13/51 

Изобретение относится кэлектронным дискретным устройствам систем автоматики, телемеханики, вычислительной техники и связи. Оно предназначено для использования в системах передачи и хранения дискретной информации. Причем, использование целесообразно в случаях, когда необходимо кодировать информацию таким образом, чтобы при декодировании ока залось возможным исправление многократных независимых ошибок количест во избыточных символов было, по воз можности, минимальным. В указанных условиях применение кода Рида-Соломона целесообразно, та так как этот код обладает минимальной возможной избыточностью при заданном количестве исправляемых ошибо Использование Изобретения в система передачи и хранения дискретной информации (в частности, построение декодирующих программ) необходимо осуществлять с учетом того, что код Рида-Соломона представляет собой ко над простым полем. Это означает, чт основанием кода является простое чксло. Известны устройства для кодирования корректирующих кодов с основанием q (где ), осуществляющие кодирование информации таким образе, что при декодировании возможно исправление многократных независиквлх саиибок. Эти устройства содержат блок управления и вычислительный блок, состоящий. из п-разрядов, каждый из которых содержит сумматор по модулю, основания кода и ячейку сдвига (п - количество контрольных символов);, для кодирования используется циклический корректирующий код над конечным полем с основанием j. В частности, в качестве такого кода может быть взят и, циклический вариант кода Рида-Соломона над простым полем 1. Кодирование в известных устройствах осуществляется путем деления информационного многочлена на порождающий многочлен кода. Указанные известные устройства содержат сравнительно много оборудования, так как вычисли-, тельный блок включает умножитель, осуществляк)1дае операции над конечным полем с основанием с. Этот недостаток частично устранен в устройствах, которые не содержат

744576 « умножителей, благолйря томУ| что используют коды с проверочной матрицей, составленной из чисел сочетаний Наиболее близким по технической сущности к предлагаемому является устройство для кодирования кода Рида Соломона над простым полем содержаще блок управления и вычислительный блок, состоящий из п-разрядов, кажды ИЗ которых содержит сумматор по модулю основания кода и ячейку сдвига, причем первый вход сумматора младшего разряда вычислительного блока свя зан со входом устройства. Устройство кодирует информацию с помощью кода Рида-Соломона над простым полем. Кон рбльные символы вычисляются путем ре шенйя системы управлений, а не путем деления многочленов. Процесс вычисления контрольных символов состоит из четырех этапов. В течение первых двух этапов вычисляются правые части уравнений. В Течение третьегй этапа система уравнений решается. На четвертом этапе полученные контрольные символы выдаются на выход 2. Недостатком известного устройства является относительно низкое быстродействие. После подачи в устройство всех информационных символов необходимо еще 2п-тактов сдвига (второй и третий этап) прежде, чем начнут выда ваться контрольные символы. Цель изобретения - повышение быст родействия устройства. Поставленная цель достигается тем что в устройство для кодирования кода Рида-Соломона над простым полем содержащее блок управления, п-ячеек, сдвига и п-сумматоров по модулю с, причей вход первого сумматора по модулю ej. является входом устройства, а выход п-го сумматора по модулю «j. является выходом устройства,введены п-ком 1утаторов,первый вход управлени ,-,.,-т,.-.--.-1.«...-. . .. ... А.- .;..;..--..- . ....A..f,:.....r,«3ffaiVite; ... которых соединен с первым выходом блока управления, а второй вход управления которых - с (1+1) выходом блока управления, где i - порядковый номер коммутатора, выход i-го сумматора подключен к первому входу (i+l)-ro сумматора, к первому информационному входу i-rb коммутатора и второму информационному входу (n+1-i го коммутатора, выход i-ro коммутатора подсоединён ко входу i-ой ячей iof сдвига, выход которой подсоединен ко второму входу i-ro сумматора. Введение коммутатора в каждый разряд вычислительного блока, вышеуказанные связ1| введенных коммутато ров сдаугими узлами устройства, а также новые связи сумматоров и ячеек сдвига между собой позволяют повысит быстродействие устройства за счет исключения второго этапа и совмеще Жя во времени третьего и четвертого этапов работы. Ё предлагаемом устрой стве правые уравнений вычисляются уже на первом этапе работы, в связи с чем второй этап становится ненужным. Решение системы уравнений выполняется одновременно с выдачей контрольных символов, в связи с чем третий и четвертый этапы совмещаются во времени. В результате, в предлагаемом устройстве контрольные символы выдаются сразу же после поступлений в устройство всех информационных символов. Следовательно, быстродействие предлагаемого устройства выше, чем быстродействие известного. На чертеже представлена блок-схема предлагаемого устройства для кодирования кода Рида-Соломона над простым полем. Устройство содержит блок 1 управления, предназначенный для формирования двоичных управляющих сигналов, содержащий генератор тактовых импульсов; вычислительный блок 2, состоящий из п-разрядов, причем п-й разряд является старшим, 1-й разряд является младшим. Число разрядов п совпадает с количеством контрольных символов и на единицу меньше кодового расстояния, сумматоры 3 , .. ., 3 по модулю основания кода (т.е. сумматоры по модулю cj) , ячейки 4 , ... 4 ,. сдвига, первые входы 5- , . .. ,5 сумматоров, коммутаторы 6,,.,,6fjf первые управляющие входы 7 , .. . ,.7ц коммутаторов, выходы 8,,..,8п блока 1 управления, соответствующие разрядам вычислительного блока (выход 8 соответствует т-му разряду), первые информационные входы 9,...,9 коммутаторов, вторые,информационные входы 10 , . . ., lOj коммутаторов, вторые входы 11,...,11 сумматоров, вторые управляющие входы 12, .. .,12 коммутаторов, выход 13 блока 1 управления, связанный со вторыми управляюЙ1ИМИ входами коммутаторов. 3 обозначениях вида 3, 4j...,, 9,;,, ..., 12 индекс m указывает,, что соответствующий узел или соответствую-, щий вход принадлежат т-му разряду блока 2. Гактовые входы всех ячеек 4 , . . .,4 сдвига с.вязаны с выходом генератора тактовых импульсов. (Эти связи на чертеже не показаны). , Выход сумматора 3 (где ,1,...,. п-1)связан со входами 5, ,9 %+|4hi Выход сумматора 3 ,.связан со вхо-, дами.Эи и 10, а также подключен к выходу устройства. Выходы 8 (где ,l,...,n) соединены со входами 7f. Входы 12 , , .. 12 у объединены и подключены к выходу 13. Выход коммутатора 6 уу,(где ,1,...,п) через ячейку сдвига подсоединен ко входу 11. Вход 5 связан со входом устройства . Работу устройства можно разбить на два этапа. В течение первого этапа по информационным символам вычисляются правые части А y,j (, 2 ,. . . ,п) системы линейных уравнений, в которой н.еизвестными являются контрольные символы . В течение втррого эТа.па система уравнений решается и одновременно по мере вычисления найденные неизвестные В , В,,,.,В (явлйющиеся контрольными символами) выдгиотся на выход устройства. На всех этапах работы устройства сигналы, проходящие по показанным на чертеже цепям (за исключением двоичных управляющих сигналов/ формируемых блоком 1 управления), являются , т.е. каждый сигнал может принимать одно из значений 0,1,..., . Коммутаторы 6 , . . . ,6 j на всех эт пах работы устройства функционируют следующим образом. При поступлении сигнала i на вход 7fYi и сигнала О на вход 12 на выход коммутатора буу,проходит с|: число,поступившее на вход 9,„. При по даче сигнала на вход 12 сигнал , О на вход 7уг) на выход коммутато ра 6 проходит cf число, поступившее на вход lOfi В случае, когда на оба управляющих входа 12, подается сигнал О, на выход коммутатора 6 проходит число ноль независимо от сигналов на информационных входа 9щи Юу. Одновременно сигналы на входы и 12 при работе устрой ства не подаются. Ячейки 4 , ..., 4 ( сдвига на всех этапах работы устройства функционируют следующим образом. При подаче тактового импульса ячейка 4уу, выдает хранящееся в ней q число на. вход 11 сумматора 3. Од . новременно эта ячейка запоминает CJ число, поступающее на ее вход с выхода коммутатора б. Перед начсшом работы все ячейки сдвига обнуляются. Первый этап работы устройства пр должается с тактов сдвига, где К - количество информационных сигналов. (Величина К не должна превышать раз ности cj-n) . В течение первых (К-1) тактов сдвига на, выходе 13 блока 1 формируется сигнал а на выходах 8,...,8 формируются сигналы 1 . На К-т такте сдвига на выходе 13 блока 1 формируется сигнал , а на выходах В.),.;., 8, формируются си налы О. Информационные символы а , а,..,,ау на первом этапе работ последовательно (начиная с символа а) с периодом, равным такту сдвига поступают на вход 5 сумматора 3-( . (Каждый информационный символ может принимать одно из значений 0,1,..., Ц.-1) .После (К-1)-го такта сдвига в ячейку сдвига 6,1 (где ,l,...,n) . - . . км записывается сумма S tK.-i-«-bi-2)ai jИ „- 1 Где (О) обозначает число сочетаний из и по О, причем, (о) 1.(Указанная сумма, как и все остальные суммы приведенные при описании работы устройства, вычисляется по модулю с, т.е. сумма может принимать одно из значений 0,1, . . . ,cj.-l) . После К-го такта сдвига на выходе сумматора 3 (где ,l,...,n) появ - к. . - ляется сумма .II( - Эта 1 d-i сумма представляет собой правую часть т-го уравнения системл линейных уравнений, в которой неизвестными являются контрольные символы. Благодаря подаче на К-т такте сигнала Ч на все входы , сумма выхода сумматора 3 (где ,1,.;.,п) через вход Ю.коммутатора б,.проходит в ячейку сдвига 4.и запоминается в ней. На этом первый этап работы устройства заканчивается. Второй этап работы продолжается с п тактов сдвига. Поступление информационных символов на втором этапе прекращается, и на вход 5 в течение второго этапа поступает число ноль. На выходах 13 и 8 блока 1 управления в течение всего второго этапа формируется управляющий сигнал О. На выходе 8 (где , 2 ,. . .ч,п-1) в течение первых (n-m) тактов сдвига второго этапа управляющий сигнал равен , а затем, начиная с (п-1п+1)-го такта сдвига и до конца второго этапа управляющий сигнал и . Поэтому, после (n-m+D-ro такта сдвига второго этапа и до конца втсэрого этапа в ячейке сдвига 4у(где ,2,...,n) записано число ноль. Это число, поступая на вход 1 IVY, сумматора 3, не влияет на сумму. В результате, на каждом 1-м такте сдвига второго VaTana (где ,2,...п) сумматоры 3fVH-i h просто транслируют на выходiустройства сумму bi, полученную .на выходе сумматора 3.. I Г7 , . Указанная сумма о - 2 {3ri)A; пред. I j-i-i-i J ставляет собой значение i-ro Неизвестного системы уравнений, правые части A;J , , ... ,Ау, которых были получены на первом этапе работы устройства и является i-M контрольным символом. Таким образом, в течение второго этапа на выход устройства последовательно выдаются с периодом, равным такту сдвига, контрольные символы Ц , Ъг, , . ,Ъу, Выдачей последнего символа работа устройства заканчивается.

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

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

Устройство для кодирования кода Рида-Соломона над простым полем/ содержащее блок управления, п-ячеек сдвига и п-сумматоров rto модулю д, причем вход первого сумматораtto; модулю g является входом устройства, а выход п-го сумматора по модулю g является выходом устройства, отличающееся тем, что, с цельго повышения йлстродействия устройетва, оно содержит п-коммутаторов, первый вход управления кОтирых соединён с первым выходом блока управле-« ния, а второй вход управления которых - c(H-j) выходом блока управления, где 1 - порядковый номер коммутатора, выход i-ro сумматора подключен к первому входу (i+l)-ro -сумматора, к первому информационному вхо, коммутатора и второму информационному входу (n+l-i)-ro коммутатора, выход i-ro коммутатора подсоединен ко входу i-ой ячейки сдвига, выход которой подсоединен ко второму входу i-ro сумматора.

5 Источники информации,

г ринятые во внимание при экспертизе

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

0 2. Авторское свидетельство СССР №443385, кл. G 06 Р 11/10, 1974 (прототип) .