Кодирующее устройство кода рида-соломона

 

Изобретение может быть использовано в системах передачи и обработки цифровой информации, где возможно возникновение ошибок. Целью изобретения является упрощение устройства, повышение быстродействия . Устройство содержит п-k матричных умножителей 3-6, регистры 1, сумматоры 2, блоки управляемых инверторов 8 и блок 9 определения четности. В результате введения бликов управляемых инверторов и блока определения четности появляется возможность значительного уменьшения количества сумматоров в схемах матричных умножителей. 1 ил.

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

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

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

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИ4ЕТЕЛЬСТВУ (21) 4702292/24 (22) 06.06.89 (46) 29.02.92. Бюл. М 8 (71) Ленинградский электротехнический институт связи им.М.А.Бонч-Бруевича (72) Г.П.Брызгина, А.В.Буданов и О.С.Когновицкий (53) 625.15(088.8) (56) Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. M.: Мир, 1976, с.251 — 256.

Хлебородов В.А. Международная рекомендация по цифровой видеозаписи, — Техника кино и телевидения, 1986, N 3. с.39-45.

SMPTE 3огпа! December, 1987, с,11371179, с.н. Gillard, (54) КОДИРУЮЩЕЕ УСТРОЙСТВО КОДА

РИДА-СОЛОМОНА

„,.Я.,, 1716609 А1 (57) Изобретение может быть использовано в системах передачи и обработки цифровой информации, где возможно возникновение ошибок. Целью изобретения является упрощение устройства, повышение быстродействия. Устройство содержит и-k матричных умножителей 3 — 6, регистры 1, сумматоры 2, блоки управляемых инверторов 8 и блок 9 определения четности. В результате введения блОков управляемых инверторов и блока определения четности появляется возможность значительного уменьшения количества сумматоров в схемах матричных умножителей.1 ил.

1716609

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

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

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

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

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

Для достижения поставленной цели в схему кодирующего устройства, содержащую п-К матричных умножителей, регистров и суматоров, где k — число информационных байт, п — общее число байт, выходы регистров с первого по (n-K)ый подключены к первым входам одноименных сумматоров, выходы первого (п-k-1)-ого сумматоров подключены соответственно к входам второго (и-k)-ого регистров, входы (п-k)-ого сумматора являются соответствен5 но входами устройства, а вторые входы подключены к входам матричных умножителей, выходы первого матричного умножителя подключены к входам первого регистра, введены блок определения четности и пер10 вый (n-k-1)-ый блоки управляемых инверторов, выходы которых подключены соответственно к вторым входам одноименных сумматоров„входы и выходы блока определения четности подключены

15 соответственно к выходам (и-k)-ого сумматора и первым входам первого — (n-k-1)-ого блоков управляемых инверторов, вторые входы которых подключены к выходам соответственно второго - (n-k)-oro матричных ум20 ножителей, а структура матричных умножителей упрощена за счет инвертирования входного сигнала, при нечетности количества в нем единиц, в тех столбцах матрицы, где количество единичных сигна25 лов больше количества нулевых.

Обоснованием предложенного решения являются .следующие теоретические предпосылки.

Предположим, инвертируется вся мат30 рица F . Тогда очевидно. что F =1Ъ F, где

I — квадратная матрица того же порядка, что и F, состоящая целиком из единицц. Ум нож ив входной вектор (а7абаьа4азага ао) н а инвертированную

35 матрицу F получим (агаьаьа4азага а)Р -((а7аба5а4аза2а1ао) И (а7аба5а4аза2а1до) Р ).

Таким образом, к каждому элементу вектор-строки, полученной от умножения исходного байта на матрицу F будет добав40 лена сумма элементов исходного байта по

7 модулю два, т.е. g а(тоб 2), Отсюда слеi o дует; что если чйсло единиц в исходном бай45 те четное, то имеем (а аваьа4азага>a<)F = (атаваьа4азага1ао) F, J т.е., в этом случае при умножении на ийвертированную матрицу F получили тот же результат, что и при умножении на матрицу F без инверсии.

Если же число единиц исходного байта (а7аба5а4аза2а.1ао) нечетное, то к каждому элементу вектор-строки (атаеа ааазага1ао) Fi будет добавлена единица по модулю два, т.е. в этом случае результат умножения на инвертированную матрицу F будет инвертирован. Для восстановления результата умножения входного байта на матрицу F

1716609 полученный результат необходимо инвертировать.

Аналогично доказывается и умножение на.матрицу F1, в которой инвертируются не все столбцы матрицы F, а выборочно. При 5 этом в матрице 1 единичными будут только те столбцы, которые инвертируются.

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

Структурная схема предлагаемого кодирующего устройства представлена на фиг. 1 и содержит n-k регистров 1, n-k сум- 15 маторов 2 и n-k матричных умножителей 36, причем вход устройства 7 соединен с первым входом первого сумматора 2, выход которого подключен к входам матричных умножителей 3 — 6 выход первого матрично- 20 го умножителя 3 соединен с входом первого регистра 1, входы остальных регистров 1 соединены с выходами сумматоров 2 (за исключением первого сумматора), а выходы всех регистров со вторыми входами всех 25 сумматоров; к выходу первого сумматора 2 подключен вход введенного блока 9, выход упомянутого блока соединен с первыми входами введенных блоков инверторов 8,. вторые входы которых подключены к выходам 30 матричных умножителей 4 — 6, а выходы блоков 10 соединены с первыми входами gcтальных сумматоров 2 (за исключением первого сумматора 2).

Схема заявленного устройства работа- 35 ет следующим образом.

Первый информационный байт поступает на вход устройства 7 и далее через первый сумматор 2 на шину без.изменения, так как исходное состояние всех регистров 40

1 — нулевое. В матричных умножителях 3-6 происходит умножение на соответствующие матрицы с учетом инверсии некоторых столбцов, что уменьшает число операций суммирования и повышает быстродействие 45 устройства, Одновременно блок определения четности 9 дает сигнал на блоки инверторов, которые пропускают полученный результат умножения на входы остальных сумматоров 2 без изменения в обрабатыва- 50 емом байте, если число единиц четное или с инверсией отдельных разрядов (если число . единиц нечетное). Результат умножения запоминается в регистрах 1. При записи в регистры 1, кроме первого, результатов с 55 выходов блоков инверторов 8 они предварительно складываются в сумматорах 2 с предыдущими состояниями регистров 1 (т,е. состояниями, наступившими после обработки предыдущего байта).

В первый регистр 1 результаты умножения в умножителе 3 записываются непосредственно, без суммирования. Затем на кодирующее устройство поступает следующий байт, который в первом сумматоре 2 складывается с состоянием последнего регистра 1 и результат поступает на шину, где после умножения в матричных умножителях

3 — 6 и прохождения через блоки инверторов

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

Регистры 1, сумматоры 2 и умножители

3 — 6 могут быть выполнены на ИС серий

К155, К133, К555 и др. Блок 9 может быть оеализован, например, на МС К531 ИП5П, а блоки инверторов 10 íà МС К531 ЛАЗ и

К531ЛЛ1.

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

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