Способ и устройство кодирования с исправлением ошибок

Способ и устройство кодирования с исправлением ошибок

Иллюстрации

Показать все

Реферат

Область техники, к которой относится изобретение

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

Уровень техники

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

Схема кодирования с проверкой на четность с низкой плотностью не ссылается на одиночную схему кодирования исправления ошибок, но ссылается на общий термин для кодов исправления ошибок, которые характеризуются тем, что они определяются разреженной проверочной матрицей. Разреженная проверочная матрица означает, что большинство компонентов (элементов) проверочной матрицы равны "0", и число компонентов "1" очень мало. Как раскрыто в публикации D.J.C. Mackay, "Good Error-Correcting Codes Based on very sparse matrices" («Хорошие коды с исправлением ошибок на основе очень разреженных матриц»), протоколы IEEE по теории информации, стр.399-431, март 1999 г. (непатентная литература 1), кодирование с проверкой на четность с низкой плотностью характеризуется тем, что оно может предоставить схему кодирования с исправлением ошибок, которая имеет очень высокую эффективность кодирования, близкую к теоретически ограниченной, с помощью использования повторной схемы декодирования, например алгоритма суммы-произведения на основе выбора разреженной проверочной матрицы.

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

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

В частности, если предполагается, что r и k представляют собой положительные целые числа, i - целое число в интервале 1≤i≤r, А в уравнении (1) - матрицу r×k, и c₁, c₂, …, c_k - информационную битовую последовательность из k битов, тогда каждый бит p_i соответствующей избыточной битовой последовательности p₁, p₂, …, p_r вычисляется согласно следующему уравнению (2):

где j представляет собой целое число в интервале 1≤j≤k, и a_i,j - компонента (i,j) матрицы А r×k. Для того чтобы осуществить кодирование кода с исправлением ошибок, необходимо сохранить матрицу А r×k в запоминающем устройстве, например в памяти, и выполнить количество операций исключающего ИЛИ, равное количеству значений «1» в компонентах матрицы А.

Фиг.1 показывает пример конфигурации устройства кодирования согласно уровню техники для осуществления кодирования с помощью кода с проверкой на четность с низкой плотностью. Когда проиллюстрированному устройству кодирования задана информационная битовая последовательность, оно кодирует информационную битовую последовательность с кодом проверки на четность с низкой плотностью и выводит кодовую битовую последовательность. Устройство кодирования содержит устройство 11, вычисляющее избыточную битовую последовательность для осуществления вычисления согласно уравнению (2) по информационной битовой последовательности для формирования избыточной битовой последовательности, запоминающее устройство 72 матричной информации для сохранения матрицы А, показанной в уравнении (1) и предоставления компонентов (элементов) матрицы А устройству 71, вычисляющему избыточную битовую последовательность и переключатель 73, для поочередного выбора информационной битовой последовательности и избыточной битовой последовательности из устройства 71, вычисляющего избыточную битовую последовательность, для формирования, таким образом, кодовой битовой последовательности, которая содержит комбинацию информационной битовой последовательности и избыточной битовой последовательности. Устройство 71, вычисляющее избыточную битовую последовательность, включает в себя схемы исключающего ИЛИ.

Для уменьшения емкости памяти запоминающего устройства (т.е. запоминающее устройство 72 матричной информации) и снижения числа схем исключающего ИЛИ, включенных в устройство 71 вычисления избыточной битовой последовательности, известен процесс создания кода с проверкой на четность с низкой плотностью из условия, что число "1" в компонентах матрицы А настолько мало, насколько возможно, и эффективность кодирования, достигаемая с помощью повторного декодирования, является предпочтительно большей. Такой процесс создания раскрыт, например, в публикации Томаса Ричардсона, Р.Урбанке "Efficient Encoding of Low-Density Parity-Check Codes" ("эффективное кодирования кодов с проверкой на четность с низкой плотностью"), протоколы IEEE по информационной теории, стр.619-656, сентябрь 2001 г. (непатентная литература 2). JP-2003-115768A (патентная литература 1) и JP-2004-72130A (патентная литература 2) раскрывают процесс использования матрицы, содержащей блочные матрицы из матрицы циклических перестановок как проверочной матрицы и ограничивающей каждую из блочных матриц до циклической матрицы для снижения, таким образом, емкости запоминающего устройства и упрощения операций исключающего ИЛИ. Проверочная матрица, которая ограничена подобным образом, конкретно упоминается как псевдо-циклический код. Эти процессы также имеют проблему в том, что сниженная шкала устройства и упрощенная обработка являются несовместимыми. Другими словами, процессы, использующие псевдо-циклические коды, требуют сложного управления, хотя размер устройства уменьшен, или применимы к дополнительно ограниченным кодам среди псевдо-циклических кодов, т.е. только кодов, к которым добавляются дополнительные ограничивающие условия.

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

Патентный документ 1: JP-2003-115768A

Патентный документ 2: JP-2004-72130A

Непатентная литература 1: Д.Дж.К. Макей, "Good Error-Correcting Codes Based on very sparse matrices" ("Хорошие коды с исправлением ошибок на основе очень разреженных матриц"), протоколы IEEE по теории информации, стр.399-431, март 1999 г.

Непатентная литература 2: Томас Ричардсон, Р.Урбанке "Efficient Encoding of Low-Density Parity-Check Codes" ("эффективное кодирования кодов с проверкой на четность с низкой плотностью"), протоколы IEEE по теории информации, стр.619-656, сентябрь 2001 г.

РАСКРЫТИЕ ИЗОБРЕТЕНИЯ

Проблемы, которые должны быть решены изобретением

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

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

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

Средство для решения проблем

Способ кодирования исправления ошибок согласно настоящему изобретению, который использует код с проверкой на четность с низкой плотностью, включает в себя: разделение информационной битовой последовательности, которая имеет длину К, которую необходимо обработать для кодирования исправления ошибок, на (m-r) частей первых блоков, каждый из которых содержит битовую последовательность, которая имеет длину n, и r частей вторых блоков, которые содержат соответствующие битовые последовательности, которые имеют длины k₁, k₂, …, k_r, где К, m, n являются положительными целыми числами, r целое число в интервале 1≤r≤m, и k₁, k₂, …, k_r целые числа в интервале 0≤k₁, k₂, …, k_r≤n-1; первую арифметическую операцию для осуществления полиномиального умножения на (m-r) частей первых блоков, вывод r частей битовых последовательностей, которые имеют длину n; вторую арифметическую операцию для осуществления полиномиального деления и полиномиального умножения на r частей вторых блоков и r частей результатов операций первой арифметической операции, вывод битовой последовательности, включая избыточные битовые последовательности, которые имеют соответствующие длины n-k₁, n-k₂, …, n-k_r.

Устройство кодирования исправления ошибок согласно настоящему изобретению, которое использует код с проверкой на четность с низкой плотностью, включает в себя: разделитель для разделения информационной битовой последовательности, которая имеет длину К, которую необходимо обработать для кодирования исправления ошибок, на (m-r) частей первых блоков, каждый из которых содержит битовую последовательность, которая имеет длину n, и r частей вторых блоков, которые содержат соответствующие битовые последовательности, которые имеют длины k₁, k₂, …, k_r, где К, m, n являются положительными целыми числами, r - целое число в интервале 1≤r≤m, и k₁, k₂, …, k_r целые числа в интервале 0≤k₁, k₂, …, k_r≤N-1; r частей первых арифметических процессоров для осуществления полиномиального умножения на (m-r) частей первых блоков, и каждый выводит битовые последовательности, которые имеют длину n, как результат операции; второй арифметический процессор для осуществления полиномиального деления и полиномиального умножения на r частей вторых блоков и результатов операций, соответственно обеспечиваемых параллельно от r частей первых арифметических процессоров, и вывод битовой последовательности, включая избыточные битовые последовательности, которые имеют соответствующие длины n-k₁, n-k₂, …, n-k_r.

В устройстве кодирования с исправлением ошибок согласно настоящему изобретению каждый из первых арифметических процессоров может включать в себя, например, максимум из (m-r) частей полиномиальных схем умножения. Например, второй арифметический процессор может включать в себя первый полиномиальный производящий деление и умножение процессор для параллельного осуществления не более чем одного полиномиального деления и не более чем (r-1) полиномиальных умножений на второй блок, который имеет длину k_r, результаты операций от r частей первых арифметических процессоров, вывод (n-k_r) битов и (r-1) частей битовых последовательностей, которые имеют длину n избыточных битовых последовательностей; р-ый процессор, производящий деление и умножение, где p является целым числом в интервале 2≤p≤r для параллельного осуществления не более чем одного полиномиального деления и не более чем (r-p) полиномиальных умножений на (r-р+1) частей битовых последовательностей, которые имеют длину n, предоставляемую от (p-1)-го процессора, производящего деление и умножение, и второй блок, который имеет длину k_r-p+1, и вывод (n-k_r-p+1) битов и (r-p) части битовых последовательностей, которые имеют длину n избыточных битовых последовательностей. В этом случае, например, r-ый процессор, производящий полиномиальное деление и умножение, может включать в себя не более чем одну схему полиномиального деления и не более чем (r-q) частей схем полиномиального умножения, где q является целым числом в интервале 1≤q≤r.

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

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

Фиг.1 является блок-схемой, которая показывает пример расположения устройства кодирования с исправлением ошибок согласно существующему уровню техники;

Фиг.2 - это блок-схема, показывающая расположение устройства кодирования с исправлением ошибок согласно примерному варианту осуществления настоящего изобретения;

Фиг.3 является блок-схемой, которая показывает пример конфигурации процессора полиномиального умножения;

Фиг.4 является блок-схемой, которая показывает пример конфигурации схемы полиномиального умножения;

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

Фиг.6 является блок-схемой, которая показывает пример конфигурации схемы полиномиального деления;

Фиг.7 является схемой, которая показывает пример формата кадра для кодовой последовательности битов;

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

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

Описание символов ссылок:

11 Процессор полиномиального умножения

12 Процессор полиномиального деления и умножения

13, 14, 23, 34, 54, 55, 65, 73 Переключатели

21, 42 Схемы полиномиального умножения

22, 32, 43, 52, 62 Схемы исключающего ИЛИ

31, 51, 61 Триггеры

33, 53, 63 Соединительные элементы

41 Схема полиномиального деления

44 Селектор

45, 46 Входные выводы

47, 48 Выходные выводы

65 Последовательно-параллельный преобразователь

71 Устройство, вычисляющее избыточную битовую последовательность

72 Запоминающее устройство матричной информации

81 Устройство передачи данных

82 Устройство кодирования

83, 87 Устройства синхронного управления и преобразования данных

84 Модулятор

85 Устройство приема данных

86 Демодулятор

88 Устройство декодирования

Наилучший режим осуществления изобретения:

Устройство кодирования с исправлением ошибок согласно примерному варианту осуществления настоящего изобретения, показанное на фиг.2, осуществляет кодирование с исправлением ошибок на основе кода с проверкой на четность с низкой плотностью информационной битовой последовательности, предоставляемой как вход для формирования, таким образом, кодовой битовой последовательности. Устройство кодирования с исправлением ошибок включает в себя: r частей процессоров 11 полиномиального умножения, расположенных параллельно, где r представляет собой целое число 1 или больше; r частей процессоров 12 полиномиального деления и умножения, расположенных в сериях; переключатель 13 на стороне ввода и переключатель 14 на стороне вывода. Для того чтобы отличить друг от друга r частей расположенных процессоров 12 полиномиального деления и умножения, они обозначаются от [1] до [r], как описано ниже. Переключатель 13 служит для назначения информационной битовой последовательности, предоставляемой устройству кодирования с исправлением ошибок, какому-либо одному из процессоров 11 полиномиального умножения. Переключатель 14 служит для последовательного выбора информационной битовой последовательности и r частей выводов от процессора [1] полиномиального деления и умножения на конечном этапе для того, чтобы выводить кодовую битовую последовательность, в которой комбинируются информационная битовая последовательность и избыточная битовая последовательность, как описано ниже.

Схема кодирования в настоящем примерном варианте осуществления предоставляется с вводом, представленным информационной битовой последовательностью, которая имеет длину, представленную К битами, и выводит кодовую битовую последовательность, которая имеет длину, представленную n·m битами. В данном документе длина К битов информационной битовой последовательности выражена с помощью следующего выражения:

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

Процессоры 11 полиномиального умножения, r частей которых расположены, являются идентичными в расположении друг к другу, и каждый включает в себя, как показано на фиг.3, не более чем (m-r) частей схем 21 полиномиального умножения, схемы 22 исключающего ИЛИ, которых на одну меньше, чем схем 21 полиномиального умножения, и переключатель 23. Схемы 21 полиномиального умножения, (m-r) частей которого расположены, соединены последовательно друг с другом с помощью схем 22 исключающих ИЛИ. Переключатель 23 является переключателем с одним входом и с (m-r) выходами и предоставляет входную информационную битовую последовательность первой схеме 21 полиномиального умножения, т.е. схеме 21 полиномиального умножения на левой стороне фиг.3 либо одной из (m-r-1) частей схем 22 исключающего ИЛИ. Вывод из конечной схемы 21 полиномиального умножения, т.е. схемы 21 полиномиального умножения на правой стороне фиг.3, предоставляется как вывод процессора 11 полиномиального умножения в процессор 12 полиномиального деления и умножения на следующем этапе.

Процессор 11 полиномиального умножения принимает n(m-r) бит как вход из информационных битов, которые имеют длину К, как указано уравнением (2), и выводит битовую последовательность, которая имеет длину n. Выходная битовая последовательность предоставляется процессору 12 полиномиального деления и умножения на последующем этапе. Битовая последовательность, которая имеет длину n(m-r), разделяется на сегменты, каждый из которых содержит n битов, которые распределены на (m-r) частей схем 21 полиномиального умножения с помощью переключателя 23. Например, с первого по n-й биты последовательно предоставляются первой схеме 21 полиномиального умножения, т.е. схеме 21 полиномиального умножения на левом крае, как показано, и с (n+1)-го по 2n-й бит последовательно предоставляются через схему 22 исключающего ИЛИ второй схеме 21 полиномиального умножения, т.е. второй схеме 21 полиномиального умножения от левого края, как показано. Аналогично, с (jn+1)-го no (j+1)n-й биты, где j является целым числом в интервале 2≤j≤m-r-1, последовательно предоставляются через j-ю схему 22 исключающего ИЛИ (j+1)-й схеме 21 полиномиального умножения.

Схемы 21 полиномиального умножения в каждом из процессоров 11 полиномиального умножения являются идентичными в расположении друг к другу. Как показано на фиг.4, схема 21 полиномиального умножения содержит n частей триггеров 31, используемых как регистры, где n является положительным целым числом, не более чем n частей схем 32 исключающего ИЛИ, соединительные элементы 33, ассоциированные соответственно со схемами 32 исключающего ИЛИ, чтобы предоставлять им битовую последовательность, предоставляемую схемой 21 полиномиального умножения, и переключатель 34. Соединительные элементы 33, которые находятся в состоянии соединения или разъединения, определяемом в зависимости от проверочной матрицы. Схемы 32 исключающего ИЛИ упорядочены на соответствующих входных сторонах триггеров 31. С помощью схем 32 исключающего ИЛИ n частей триггеров 31, которые ассоциированы с соответствующими схемами 32 исключающего ИЛИ, последовательно соединены друг с другом. Переключатель 34 соединен со входом триггера 31 на конечном этапе. Переключатель 34 служит для выборочного предоставления вывода от триггера 31 на конечном этапе как вывод схемы 21 полиномиального умножения вовне или для возвращения вывода от триггера 31 на конечном этапе в триггер 31, т.е. триггер 31 на левом крае фиг.4, с помощью схемы 32 исключающего ИЛИ на первом этапе.

Схема 21 полиномиального умножения является, таким образом, конфигурацией из n-битовых вводов и n-битовых выводов. Когда вывод от триггера 31 на конечном этапе предоставляется триггеру 31 на первом этапе с помощью переключателя 34, схеме 21 полиномиального умножения последовательно предоставляется входная битовая последовательность из n битов. Когда схеме 21 полиномиального умножения предоставляются все биты, она управляет переключателем 34 для последовательного вывода данных из n частей триггеров 31 (т.е. регистров). Как показано на фиг.4, n частей соединительных элементов 33 согласуются, соответственно, с заданной битовой последовательностью h₀, h₁, h_n-1 из n битов и устанавливаются в соединенном состоянии или разъединенном состоянии в зависимости от того, равен ли соответствующий бит 1 или 0. Соединенное состояние является состоянием, в котором входная битовая последовательность для схемы 21 полиномиального умножения предоставляется с помощью соединительных элементов 33 для схем 32 исключающего ИЛИ. Разъединенное состояние является состоянием, в котором входящая битовая последовательность для схемы 21 полиномиального умножения не предоставляется для схем 32 исключающего ИЛИ. Если j является целым числом в интервале 0≤j≤n-1, тогда h_j равно 1, соединительный элемент, отмеченный h_j, находится в соединенном состоянии, и когда h_j равен 0, соединительный элемент, отмеченный h_j, находится в разъединенном состоянии. Таким образом, схема 21 полиномиального умножения осуществляет полиномиальное умножение с помощью полинома, который имеет коэффициенты, представленные битовой последовательностью h₀, h₁, …, h_n-1 из n битов. Пример способа выбора битовой последовательности h₀, h₁, …, h_n-1 описан ниже.

Для того чтобы отличить друг от друга r частей процессоров 12 полиномиального деления и умножения, которые соединены последовательно, эти процессоры полиномиального деления и умножения обозначены от [1] до [r]. Как показано на фиг.2, процессор полиномиального деления и умножения на стороне входа, т.е. стороне процессора 11 полиномиального умножения, обозначен как процессор [r] полиномиального деления и умножения, и процессор полиномиального деления и умножения, расположенный на выводе процессора [r] полиномиального деления и умножения, обозначен как процессор [r-1] полиномиального деления и умножения. Аналогично, процессор полиномиального деления и умножения с правого края фиг.2 обозначен как процессор [1] полиномиального деления и умножения.

Если i является целым числом в интервале 1≤i≤r, тогда процессор [i] полиномиального деления и умножения среди процессоров 12 полиномиального деления и умножения содержит, как показано на фиг.5, не более чем одну схему 41 полиномиального деления и не более чем (i-1) частей схем 42 полиномиального умножения. Схемы 42 полиномиального умножения могут быть теми же самыми, что и схема полиномиального умножения, показанная на фиг.4. Схема 41 полиномиального деления описана ниже.

Последовательно расположенные r частей процессоров 12 полиномиального деления и умножения включают в себя различное число схем полиномиального умножения в зависимости от их положений в последовательно соединенной матрице. Соответственно, каждый из процессоров полиномиального деления и умножения задан числом их схем полиномиального умножения. В устройстве кодирования, показанного на фиг.2, процессор [r] полиномиального деления и умножения включает в себя (r-1) или меньше частей схем 42 полиномиального умножения, и процессор [r-1] полиномиального деления и умножения включает в себя (r-2) или меньше частей схем 42 полиномиального умножения. Как описано выше, процессор [i] полиномиального деления и умножения включает в себя (i-1) или меньше частей схем 42 полиномиального умножения. Если умножение нулевого полинома принимается во внимание, тогда, так как нет необходимости предоставлять схему умножения для умножения нулевого полинома, процессор [i] полиномиального деления и умножения включает в себя (i-1) схем 42 полиномиального умножения. Процессор [i] полиномиального деления и умножения описывается ниже.

Процессор [i] полиномиального деления и умножения содержит, в дополнение к не более чем одной схеме 41 полиномиального деления и не более чем (i-1) частям схем 42 полиномиального умножения, две схемы 43 исключающего ИЛИ, ассоциированные со схемой 41 полиномиального деления, и схемы 43 исключающего ИЛИ, ассоциированные с соответствующими схемами 42 полиномиального умножения, селектор (SEL) 44, вывод 45 для предоставления информационной битовой последовательности от переключателя 13 (см. фиг.2), i частей выводов 46 для предоставления битовых последовательностей параллельно от процессора [i+1] полиномиального деления и умножения на предыдущем этапе, вывод 47 для предоставления битовой последовательности переключателю 14 (см. фиг.2) и (i-1) частей выводов 48 для вывода битовых последовательностей параллельно процессору [i-1] полиномиального деления и умножения на последующем этапе. Из i частей выводов 46 первые (i-1) частей выводов соединены с помощью схем 43 исключающего ИЛИ с соответствующими схемами 42 полиномиального умножения. Выходные выводы схем 42 полиномиального умножения соединены с соответствующими выводами 48. Эти схемы 43 исключающего ИЛИ предоставляются общим выводом от селектора 44.

Вывод селектора 44 также соединен с выводом 47. Из выводов 46 оставшийся один вывод 46 соединен с оставшимися двумя схемами 43 исключающего ИЛИ. Одной из этих схем 43 исключающего ИЛИ предоставляется битовая последовательность с вывода 45 и соединяется со входом схемы 41 полиномиального деления. Другой схеме 43 исключающего ИЛИ предоставляется выходящая битовая последовательность от схемы 41 полиномиального деления и соединяется с одним из входных выводов селектора 44. Другой входной вывод селектора 44 соединяется с выводом 45.

Когда i=r, в процессоре [r] полиномиального деления и умножения r частей выводов 46 соединены с соответствующими выходными выводами из r частей процессоров 11 полиномиального умножения. Когда i=1, в процессоре [1] полиномиального деления и умножения можно обойтись без схем 42 полиномиального умножения и выводов 48.

Процессору [i] полиномиального деления и умножения, как описано выше, предоставляется k_i бит из информационных битов, которые имеют длину К, указанную уравнением (2), через вывод 45, и также параллельные наборы из i битов из n·i битов от процессора [i+1] полиномиального деления и умножения на предыдущем этапе через выводы 46. Когда i=r, выводы 46 получают соответствующие биты выходов из r частей процессоров полиномиального умножения. Процессор [i] полиномиального деления и умножения выводит битовую последовательность, которая имеет длину n, как часть кодированной битовой последовательности с вывода 47 и также выводит параллельно всего n(i-1) битов битовой последовательности, которая имеет длину n, из (i-1) частей схем полиномиального умножения через выводы 48. Схема 41 полиномиального деления принимает вход, формируемый операцией исключающего ИЛИ над k_i битами, последовательно предоставляемыми с вывода 45, и первыми k_i битами из n битов, последовательно предоставляемых с вывода 46, и последовательно выводит (n-k_i) битов после того, как схема 41 полиномиального деления приняла вход. Выход из (n-k_i) битов со схемы 41 полиномиального деления и последних (n-k_i) битов из n битов, последовательно предоставляемых с вывода 46, подвергается операции исключающего ИЛИ для получения выхода, который выдается через селектор 44 на входы схем 42 полиномиального умножения. Селектор 44 принимает первый вход, представленный k_i битами, последовательно предоставляемыми с вывода 45, и второй вход, формируемый операцией исключающего ИЛИ над выходом схемы полиномиального деления и последними (n-k_i) битами из n битов, последовательно предоставляемых с вывода 46, выборочно переключает первый и второй входы и последовательно выводит всего n битов. n битов, которые доставляются от селектора 44, выдаются как n битов из n·m битов кодированной битовой последовательности через вывод 47. Схемы 42 полиномиального умножения принимают входы, формируемые операцией исключающего ИЛИ над выходом селектора 44 и n битами, последовательно предоставляемыми на выводы 46, и последовательно выдают результат умножения из n битов через выводы 48.

Предполагается, что i является целым числом в интервале 1≤_i≤r, как описано выше, и схема 41 полиномиального деления в процессоре [i] полиномиального деления и умножения описана ниже со ссылкой на фиг.6.

Схема 41 полиномиального деления содержит (n-k_i) частей триггеров 51, где k_i является целым числом в интервале 0≤k_i≤n, не более чем (n-k_i) частей схем 52 исключающего ИЛИ, (n-k_i+1) частей соединительных элементов 53 и переключатели 54, 55. (n-ki+1) частей соединительных элементов 53 соответствуют битам битовой последовательности g₀, g₁, …, g_n-ki, которая имеет заранее определенную длину (n-k_i+1) битов, и установлены в соединенном состоянии или разъединенном состоянии в зависимости от значений соответствующих битов. А именно, если j является целым числом в интервале 0≤j≤n-ki, тогда (j+1)-й соединительный элемент 53, т.е. соединительный элемент, отмеченный "g_j" на фиг., находится в соединенном состоянии, когда бит g_j равен 1, и в разъединенном состоянии, когда бит g_j равен 0. (n-k_i) частей триггеров 51 соединены последовательно друг с другом с помощью схем 52 исключающего ИЛИ, каждая из которых вставлена между соседними схемами триггеров 51. Переключатель 54 служит для выборочного предоставления вывода от триггера 51 на конечном этапе как вывода схемы 41 полиномиального деления вовне или предоставления вывода от триггера 51 на конечном этапе в оставшуюся одну схему 52 исключающего ИЛИ, т.е. конечную схему 52 исключающего ИЛИ.

Конечная схема 52 исключающего ИЛИ получает битовую последовательность, которая предоставляется схеме 41 полиномиального деления, и вывод конечной схемы 52 исключающего ИЛИ подается через переключатель 55 на (n-k_i+1)-й соединительный элемент, т.е. соединительный элемент, соответствующий биту g_n-ki. Первый триггер 51, т.е. триггер 51 на правом крае на фиг.6, получает вывод от соединительного элемента 53, соответствующего биту g_n-ki, с помощью соединительного элемента 53, соответствующего биту g₀. В оставшихся триггерах 51 схемы 52 исключающего ИЛИ располагаются в их входных частях и получают вывод от соединительного элемента 53, соответствующего биту g_n-ki с помощью соответствующего соединительного элемента 53, соответствующего битам g₁, …, g_n-ki-1.

Подобная схема 41 полиномиального деления принимает последовательный ввод k_i битов, когда переключатель установлен на конечной стороне схемы 52 исключающего ИЛИ, сдвигает переключатель 54 после того, как он принял последовательный ввод, и последовательно выводит (n-k_i) битов, которые сохранены в (n-k_i) частях триггеров. Другими словами, схема 41 полиномиального деления осуществляет полиномиальное деление над входящей битовой последовательностью k_i битов и полиномом, который имеет коэффициенты, представленные битами битовой последовательности g₀, g₁, …, g_n-ki из (n-k_i+1) бит. Пример способа выбора для битовой последовательности g₀, g₁, …, g_n-ki описан позже.

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

Проверочная матрица согласно уравнению (4) является блочной матрицей r×m и имеет компоненты, каждый из которых содержит циклическую матрицу n×n. Нижняя правая треугольная часть уравнения (4), т.е. часть, указанная с помощью "0" жирным в уравнении, содержит n×n циклических матриц, которые являются нулевыми матрицами. Как указано с помощью уравнения (5) ниже, циклическая матрица n×n имеет второй вектор-строку, равный первому вектору-строке, который сдвинут на один бит вправо, и k-й вектор-столбец, равный первому вектору-строке, который сдвинут на (k-1) бит вправо, где k является целым числом в интервале 2≤k≤n.

Первый вектор-строка циклической матрицы n×n уравнения (5) может быть выражен как полином (n-1)-го порядка или меньше, как показано в уравнении (6).

Предполагается, что i является целым числом в интервале 1≤i<r, j является целым числом в интервале 1≤j≤m-r, v является целым числом в интервале 2≤v≤r, и u является целым числом в интервале 1≤u≤t-1. Первый вектор-строка H_i,j в уравнении (4) выражен как полином (n-1)-го порядка или меньше, обозначенный с помощью h^(i,j) (х), первый вектор-строка F_s,t в уравнении (4) - как полином (n-1)-го порядка или меньше, обозначенный с помощью f^(u,v)