Кодирующее устройство кода Рида-Соломона Советский патент 1992 года по МПК H03M13/02 

(Л

С

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

( IO

iO

ю

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

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

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

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

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

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

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

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

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

Предположим, инвертируется вся матрица Fj. Тогда очевидно, что FJ IФ Fj, где I - квадратная матрица того же порядка, что и F. состоящая целиком из единиц. Умножив входной вектор (373635343.3.323130) на инвертированною

матрицу F получим (a7a635a4a3a2aiao)FJ -(3736353433323130) (a a6353433323l3o)F4.

Таким образом, к кэждому элементу

вектор-строки, полученной от умножения

исходного бэйтэ нэ матрицу F будет добэвлена сумма элементов исходного байта по

7

модулю два, т.е. Ј ai(mod 2). Отсюда слеi о

дует, что если единиц в исходном бэй45

те четное, то имеем

(373635343332313o)F (3736353433323130) F ,

т.е., в этом случэе приумножении нз инвер- тированную матрицу FJ получили тот же ре зультат, что и при умножении на мзтрицу FJ без инверсии.

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

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

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

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

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

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

Первый информационный байт поступает на вход устройства 7 и далее через первый сумматор 2 на шину без изменения, так как исходное состояние всех регистров 1 - нулевое. В1 матричных умножителях 3-6 происходит умножение на соответствующие матрицы с учетом инверсии некоторых столбцов, что уменьшает число операций суммирования и повышает быстродействие устройства. Одновременно блок определения четности 9 дает сигнал на блоки инверторов, которые пропускают полученный результат умножения на входы остальных сумматоров 2 без изменения в обрабатываемом байте, если число единиц четное или с инверсией отдельных разрядов (если число единиц нечетное). Результат умножения запоминается в регистрах 1. При записи в регистры 1, кроме первого, результатов с выходов блоков инверторов 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-К) матричных умножителей, регистров и сумматоров, где К - число информационных байт, п - общее число байт), выходы регистров с первого

по (п-К)-й подключены к первым входам одноименных сумматоров, выходы перво- 1 го (п-К-Т)-го сумматоров подключены соответственно к входам второго (п-К)-го регистров, вторые входы (п-К)-го сумматоров являются соответственно входами устройства, а вторые выходы подключены к входам матричных умножителей, выходы первого матричного умножителя подключены к входам первого регистра, отличающ е е с я тем, что, с целью упрощения устройства и повышения быстродействия, в него введены блок определения четности и первый - (п-К-1)-й блоки управляемых инверторов, выходы которых подключены соответственно к вторым входам одноименных сумматоров, входы и выходы блока определения четности подключены соответственно к выходам (п-К)-го сумматоров и первым входам первого - (п-К-1)-го блоков

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

сигнала при нечетности количества в нем единиц в тех столбцах матрицы, где количество единичных сигналов больше количества нулевых.