Устройство кодирования с исправлением ошибок и способ кодирования с исправлением ошибок, используемый в нем

Устройство кодирования с исправлением ошибок и способ кодирования с исправлением ошибок, используемый в нем

Иллюстрации

Показать все

Реферат

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

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

Предшествующий уровень техники

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

Код с низкой плотностью проверок на четность не относится к одному конкретному способу кодирования с исправлением ошибок, но он представляет собой общий термин для кодов с исправлением ошибок, отличающихся разреженной проверочной матрицей (большинство элементов в матрице равно 0, и количество элементов «1» очень мало). Посредством выбора разреженной проверочной матрицы и использования способа итеративного декодирования, такого как алгоритм сумма-произведений, код с низкой плотностью проверок на четность может реализовать систему кодирования с исправлением ошибок, способную достигать очень большого выигрыша от кодирования, близкого к теоретическому пределу (например, смотрите непатентные документы 1 и 2).

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

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

[Выражение 1]

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

[Выражение 2]

Здесь a_{i, j} в выражении (2) представляет (i, j) элемент матрицы А размером r x k (где i представляет целое число от 1 до r включительно, и j представляет целое число от 1 до k включительно). Поэтому, чтобы образовать устройство кодирования кода с исправлением ошибок, матрица А размером r x k хранится в запоминающем устройстве, таком как память, и операции Исключающее-ИЛИ должны быть выполнены столько раз, чему равно количество «1» в элементах матрицы.

Фиг.7 изображает пример обычного устройства кодирования, относящегося к коду с низкой плотностью проверок на четность. Позиция 51 на фиг.7 представляет собой узел вычисления строки избыточных битов, который выполняет вычисления по выражению (2), позиция 52 на фиг.7 представляет собой память, которая хранит матрицу А в выражении (1), и позиция 53 на фиг.7 представляет собой переключатель.

В отношении снижения требуемого объема памяти и узлов Исключающее-ИЛИ в устройстве кодирования известны способ, в котором объем памяти уменьшается, и упрощаются операции Исключающее-ИЛИ посредством ограничения проверочной матрицы до матрицы, образованной матрицей циклических перестановок в виде блочной матрицы, и наложения регулярности на матрицу А (например, смотрите патентный документ 1), и способ составления кодов с низкой плотностью проверок на четность, в которых минимизируется количество «1» в элементах матрицы А, тогда как максимизируется выигрыш от кодирования, получаемый посредством итеративного кодирования (например, смотрите непатентный документ 3).

Далее, в качестве кодов с исправлением ошибок, с которыми легко может быть реализовано устройство кодирования, известны циклические коды, в которых строки избыточных битов вычисляются посредством использования только схемы деления многочленов; циклические коды представляются кодом Рида-Соломона (РС) и кодом Боуза-Чоудхури-Хоквингема (БЧХ-кодом), в частности. Далее, как и с вышеупомянутыми циклическими кодами, устройство кодирования легко может быть реализовано посредством использования сверточных кодов.

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

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

Как описано выше, обычное устройство кодирования, относящееся к коду с низкой плотностью проверок на четность, реализуется при помощи запоминающих устройств, которые хранят матрицу А по выражению (1), и узлов обработки операций, которые выполняют операцию по выражению (2). Далее, оценка характеристик частоты появления ошибок выполняется экспериментально.

[Патентный документ 1]

Публикация патента Японии Kokai № JP-P2003-115768A (стр.10-11, фиг.4-7)

[Патентный документ 2]

Патент США 5446747 (стр.2, фиг.1)

[Непатентный документ 1]

Gallager R., “Low-Density Parity-Check Codes”, MIT Press, 1963 г.

[Непатентный документ 2]

MacKay D. J. C., “Good Error-Correcting Codes Based on Very Sparse Matrices”, труды Института инженеров по электротехнике и радиоэлектронике (ИИЭР) по теории информации, том 45, № 2, Март 1999 г., стр.399-431.

[Непатентный документ 3]

Richardson T. J., and Urbanke, R. L., “Efficient Encoding of Low-Density Parity-Check Codes”, труды ИИЭР по теории информации, том 47, № 2, сентябрь 2001 г., стр.638-656.

[Непатентный документ 4]

Richardson, T. J., Shokrollahi, M. A. and Urbanke, R. L., “Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes”, труды ИИЭР по теории информации, том 47, № 2, сентябрь 2001 г., стр.619-637.

Сущность изобретения

Проблемы, решаемые изобретением

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

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

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

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

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

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

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

Другими словами, чтобы достичь задачи, описанной выше, устройство кодирования с исправлением ошибок согласно настоящему изобретению содержит (m-1) узлов умножения многочленов, которые дополнительно делят строку информационных битов, имеющую длину K (где K представляет целое число), которая была разделена на блоки для кодирования с исправлением ошибок, на (m-1) блоков, имеющих длину n, и один блок, имеющий длину (n-r) (где m и n представляют целые числа, равные или большие двух, и r представляет целое число от 1 до n включительно), принимают (m-1) блоков, которые имеют длину n, из числа разделенных строк информационных битов, выполняют умножение многочленов и выводят серию, имеющую длину n; узел сумматора, который суммирует каждый выход (m-1) узлов умножения многочленов; и узел деления многочленов, который принимает выходной результат узла сумматора и блок, имеющий длину (n-r), выполняет деление многочленов и выводит серию избыточных битов, имеющую длину r.

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

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

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

Выгоды изобретения

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

Краткое описание чертежей

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

Фиг.2 представляет собой блок-схему, изображающую конфигурацию узла умножения многочленов (n-1)-го порядка, изображенного на фиг.1.

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

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

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

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

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

Объяснение ссылочных символов

1: блок умножения многочленов

2: узел деления многочленов r-го порядка

3, 4, 24, 34, 124: переключатель

11, 40: узел последовательно-параллельного преобразователя

12, 12-1 - 12-(m-1): узел умножения многочленов (n-1)-го порядка

13: узел сумматора

21-1 - 21-r, 31-1 - 31-n, 121-1 - 121-n: регистр

22-1 - 22-r, 32-1 - 32-n, 122-1 - 122-n: узел операции Исключающее-ИЛИ

23-1 - 23-(r-1), 33, 123-1 - 123-n: переключатель, указывающий скоммутированное или нескоммутированное состояние

Предпочтительные варианты для осуществления изобретения

Ниже описываются примеры настоящего изобретения с ссылкой на чертежи. Фиг.1 представляет собой блок-схему, изображающую конфигурацию устройства кодирования с исправлением ошибок согласно примеру настоящего изобретения. На фиг.1 устройство кодирования с исправлением ошибок согласно примеру настоящего изобретения образовано блоком 1 умножения многочленов, содержащим узел 11 последовательно-параллельного (Пос-Пар) преобразователя, узлы 12-1 - 12-(m-1) умножения многочленов (n-1)-го порядка в количестве m-1 и узел 13 сумматора, узлом 2 деления многочленов r-го порядка и переключателями 3 и 4 и представляет собой устройство, которое преобразует строку информационных битов из (nm-r) битов в строку кодовых битов из nm битов (где m и n представляют целые числа, равные или большие двух, и r представляет целое число от 1 до n включительно).

Как описано ниже, блок 1 умножения многочленов конфигурируется так, как показано на фиг.4, однако, чтобы упростить объяснение, заявители предполагают, что блок 1 умножения многочленов составлен из узлов 12-1 - 12-(m-1) умножения многочленов (n-1)-го порядка в количестве m-1.

Способ (или система) кодирования настоящего изобретения представлена в качестве схемы систематического кодирования, в которой (nm-r) битов с первого бита строки кодовых битов совпадает со строкой информационных битов, тогда как остальные r битов становятся строкой избыточных битов для исправления ошибок.

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

Узел 13 сумматора складывает каждый выход (m-1) узлов 12-1 - 12-(m-1) умножения многочленов (n-1)-го порядка. Узел 2 деления многочленов r-го порядка принимает блок, имеющий длину (n-r), и выходной результат узла 13 сумматора, выполняет деление многочленов r-го порядка и выводит серию избыточных битов, имеющую длину r.

Фиг.2 представляет собой блок-схему, изображающую конфигурацию узла умножения многочленов (n-1)-го порядка. На фиг.2 узел 12 умножения многочленов (n-1)-го порядка составлен из регистров 121-1 - 121-n в количестве n и узлов 122-1 - 122-n Исключающее-ИЛИ в количестве n, максимум. Узлы 12-1 - 12-(m-1) умножения многочленов (n-1)-го порядка на фиг.1 все конфигурируются идентично этому узлу 12 умножения многочленов (n-1)-го порядка.

Узел 12 умножения многочленов (n-1)-го порядка принимает/выводит n битов и последовательно принимает строку входных битов из n битов. После того как он примет все биты, переключатель 124 переключается и последовательно выводится содержимое n регистров 121-1 - 121-n.

На фиг.2 позиции 123-1 - 123-n представляют собой переключатели, в которых выполняется коммутационное соединение или коммутационное разъединение под действием предварительно определенной строки битов из n битов (h₁, h₂, …, h_n). Когда h_j равен 1, в элементе, обозначенном h_j, выполняется коммутационное соединение, и когда h_j равен 0, в элементе, обозначенном h_j, выполняется коммутационное разъединение (j представляет собой целое число от 1 до m включительно). Как выбирается эта строка битов из n битов (h₁, h₂, …, h_n), описывается ниже.

Фиг.3 представляет собой блок-схему, изображающую конфигурацию узла деления многочленов r-го порядка, показанного на фиг.1. На фиг.3 узел 2 деления многочленов r-го порядка составлен из регистров 21-1 - 21-r в количестве r, узлов 22-1 - 22-r Исключающее-ИЛИ в количестве r, максимум, и переключателя 24.

Узел 2 деления многочленов r-го порядка принимает результирующие n битов операций Исключающее-ИЛИ между (n-r) информационными битами и каждым выходным битом (m-1) узлов 121-1 - 121-n умножения многочленов (n-1)-го порядка и выводит r битов. После того как он примет (n-r) информационных битов, узел 2 деления многочленов r-го порядка переключает переключатель 24 и последовательно выводит результаты операций Исключающее-ИЛИ между остальными r битами с каждого выхода узлов 121-1 - 121-(m-1) умножения многочленов (n-1)-го порядка и содержимым r регистров 21-1 - 21-r на фиг.3 (в этот момент ввод строки информационных битов устанавливается в 0).

Выходные r биты узла 2 деления многочленов r-го порядка становятся строкой избыточных битов из r битов для строки информационных битов из (nm-r) битов. На фиг.3 позиции 23-1 - 23-(r-1) представляют собой переключатели, в которых выполняется коммутационное соединение или коммутационное разъединение под действием предварительно определенной строки битов из (r-1) битов (u₁, u₂, …, u_r-1). Когда u_j равен 1, в элементе, обозначенном u_j, выполняется коммутационное соединение, и когда u_j равен 0, в элементе, обозначенном u_j, выполняется коммутационное разъединение (j представляет собой целое число от 1 до (r-1) включительно). Как выбирается эта строка битов из (r-1) битов (u₁, u₂, …, u_r-1), описывается ниже.

Фиг.4 представляет собой блок-схему, изображающую подробную конфигурацию блока 1 умножения многочленов, показанного на фиг.1. На фиг.4 регистры являются совместно используемыми. Позиция 33 на фиг.4 представляет переключатель, который соединяется или разъединяется под действием строки предварительно определенных битов из n(m-1) битов. Когда этот же способ применяется для выбора этой строки битов из n(m-1) битов и строки битов, которая определяет состояние коммутационного соединения переключателей в узлах 12 умножения многочленов (n-1)-го порядка на фиг.2, зависимость между входом и выходом, показанная на фиг.4, совпадает с зависимостью между входом и выходом блока 1 умножения многочленов, реализованного с использованием узлов 12 умножения многочленов (n-1)-го порядка в количестве (m-1) на фиг.2.

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

[Выражение 3]

Проверочная матрица в выражении (3) представляет собой линейное расположение циклических матриц размера n x n в количестве m, и Hi в выражении (3) обозначает циклическую матрицу размера n x n (где i представляет собой целое число от 1 до m включительно). Циклическая матрица выражается следующим образом.

[Выражение 4]

В выражении (4) положения векторов первой строки сдвигаются на один бит влево во второй строке, и после этого положения векторов первой строки сдвигаются на (k-1) битов влево в k-ой строке (где k представляет целое число от двух до n включительно).

Векторы первой строки циклической матрицы размера n x n в выражении (4) выражаются следующим выражением:

[Выражение 5]

В выражении (5) векторы первой строки циклической матрицы размера n x n выражаются многочленом порядка (n-1) или менее как f⁽ⁱ⁾(x) (где i представляет собой целое число от 1 до m включительно).

Выбор строки n битов, которая определяет коммутационное соединение между узлами 12 умножения многочленов (n-1)-го порядка: 12-1 - 12-(m-1) и узлом 2 деления многочленов r-ого порядка, определяется выбором m многочленов порядка (n-1) или менее: f⁽¹⁾(x), f⁽²⁾(x), …, f^(m)(x). Сначала описывается способ выбора m многочленов порядка (n-1) или менее: f⁽¹⁾(x), f⁽²⁾(x), …, f^(m).

Что касается многочлена f(x) порядка (n-1) или менее, множество s(f(x)) определяется следующим выражением:

[Выражение 6]

Здесь коэффициент члена порядка i f(x) обозначается как f_i+1. Множество s(f(x)) представляет собой подмножество целых чисел от 0 до (n-1) включительно, определенное многочленом f(x).

Далее, для целых чисел v от 1 до (n-1) включительно подмножество λ v(f(x)) декартова произведения s(f(x))×s(f(x)) определяется следующим выражением:

[Выражение 7]

Одним из условий для выбора m многочленов порядка не более, (n-1): f⁽¹⁾(x), f⁽²⁾(x), …, f^(m)(x) является то, что m многочленов удовлетворяет следующему выражению для всех целых чисел v от 1 до (n-1) включительно:

[Выражение 8]

Здесь, количество элементов в множестве А обозначается как |A|. Вторым условием для выбора m многочленов порядка не более (n-1): f⁽¹⁾(x), f⁽²⁾(x), …, f^(m)(x) является то, что каждый из (m-1) многочленов f⁽²⁾(x), …, f^(m)(x) делится на многочлен f⁽¹⁾(x), при этом многочлен (xⁿ-1) используется в качестве делителя. Далее, факторы-многочлены в количестве (m-1) выражаются как g⁽²⁾(x), g⁽³⁾(x), …, g^(m)(x), что указывается следующим выражением:

[Выражение 9]

Первое условие [выражение (8)] для выбора m многочленов порядка не более (n-1): f⁽¹⁾(x), f⁽²⁾(x), …, f^(m)(x) представляет собой необходимое условие для достижения декодирования с точностью, близкой к оптимальной, используя итеративное декодирование кода с низкой плотностью проверок на четность, обычно алгоритм сумма-произведений и т.д. Фактически, посредством выполнения этого условия [выражение (8)] максимальное количество 1, включенных в каждый вектор строки проверочной матрицы, показанной в выражении (3), становится равным (nm)^1/2, и проверочная матрица становится разреженной матрицей.

Второе условие [выражение (9)] представляет собой необходимое условие, чтобы устройство кодирования с исправлением ошибок, показанное на фиг.1, точно вычисляло строку избыточных битов. Примеры многочленов, которые удовлетворяют обоим условиям [выражения (8) и (9)], описываются ниже.

Ниже описывается коммутационное соединение в узле 12 умножения многочленов (n-1)-го порядка, показанном на фиг.2. Как упомянуто выше, коммутационное соединение переключателей 123-1 - 123-n в узле 12 умножения многочленов (n-1)-го порядка на фиг.2 определяется предварительно определенной строкой битов (h₁, h₂, …, h_n). Когда h_j равен 1, элемент, обозначенный h_j, соединяется, и, когда h_j равен 0, элемент, обозначенный h_j, разъединяется (j представляет собой целое число от 1 до m включительно).

Эта строка битов из n битов (h₁, h₂, …, h_n) выбирается следующим образом. Как упомянуто ранее, устройство кодирования с исправлением ошибок содержит узлы 12-1 - 12-(m-1) умножения многочленов (n-1)-го порядка, и строка n битов, которая определяет коммутационное соединение в узлах 12-i умножения многочленов (n-1)-го порядка, выражается следующим образом.

[Выражение 10]

(где i представляет целое число от 1 до (m-1) включительно). Эта строка n битов определяется следующим выражением (11), используя (m-1) многочленов g⁽²⁾(x), g⁽³⁾(x), …, g^(m)(x), указанных в выражении (9):

[Выражение 11]

Где

[Выражение 12]

(где k представляет собой целое число от 2 до m включительно). Далее, битовая строка из n(m-1) битов, которая определяет коммутационное соединение переключателей на фиг.4, аналогично определяется выражением (10).

[Выражение 13]

Ниже описывается коммутационное соединение в узле 2 деления многочленов r-го порядка, показанном на фиг.3. В переключателях 23-1 - 23-(r-1) на фиг.3 выполняется коммутационное соединение или разъединение посредством предварительно определенной битовой строки из (r-1) битов (u₁, u₂, …, u_r-1). Когда u_j равен 1, элемент, обозначенный u_j, соединяется, и, когда u_j равен 0, элемент, обозначенный u_j, разъединяется (j представляет собой целое число от 1 до (r-1) включительно). Битовая строка из (r-1) битов (u₁, u₂, …, u_r-1) определяется следующим выражением, используя вышеупомянутый многочлен f⁽¹⁾(x):

[Выражение 14]

Здесь gcd(f⁽¹⁾(x), xⁿ-1) представляет наибольший общий многочлен из f⁽¹⁾(x) и (xⁿ-1), и порядок этого наибольшего общего многочлена равен (n-r). Как упомянуто ранее, r представляет собой количество избыточных битов устройства кодирования настоящего изобретения. Другими словами, количество информационных битов устройства кодирования с исправлением ошибок настоящего изобретения равно количеству битов, полученному добавлением порядкового номера наибольшего общего многочлена f⁽¹⁾(x) и (xⁿ-1) к n(m-1).

Ниже описывается принцип действия настоящего примера. Устройство кодирования с исправлением ошибок, показанное на фиг.1, последовательно принимает строку информационных битов, имеющую длину K=(nm-r) битов (где m и n представляют целые числа, равные или большие двух, и r представляет целое число от 1 до n включительно), которая была разбита на блоки для кодирования с исправлением ошибок. Серия информационных битов делится на первый блок, включающий в себя от первого бита до n(m-1)-го бита, и второй блок, включающий в себя от (n(m-1)+1)-го бита до (nm-r)-го бита.

Блок 1 умножения многочленов, составленный из (m-1) узлов 12-1 - 12-(m-1) умножения многочленов (n-1)-го порядка, последовательно принимает первый блок, и, после переключения переключателя 3, второй блок последовательно принимается узлом 2 деления многочленов r-го порядка. Первый блок, имеющий длину n(m-1) в строке информационных битов, принятой блоком 1 умножения многочленов, преобразуется узлом 11 последовательно-параллельного преобразователя в (m-1) битов, и каждый бит преобразованных (m-1) битов последовательно подается на узлы 12-1 - 12-(m-1) умножения многочленов (n-1)-го порядка.

Количество узлов 12-1 - 12-(m-1) умножения многочленов (n-1)-го порядка равно (m-1), и i-ый бит (где i представляет целое число от 1 до (m-1) включительно) последовательно-параллельно преобразованных (m-1) битов подается на i-ый узел 12-i умножения многочленов (n-1)-го порядка. Другими словами, первый блок дополнительно делится на (m-1) блоков, имеющих длину n, узлом 11 последовательно-параллельного преобразователя, и каждый из (m-1) блоков, имеющих длину n, принимается каждым из (m-1) узлов 12-1 - 12-(m-1) умножения многочленов (n-1)-го порядка.

Каждый из узлов 12-1 - 12-(m-1) умножения многочленов (n-1)-го порядка принимает разделенные n биты, и их выходное количество битов равно n битов. Побитовая операция Исключающее-ИЛИ каждого выхода (m-1) узлов 12-1 - 12-(m-1) умножения многочленов (n-1)-го порядка превращает в n-битовый выход блока 1 умножения многочленов.

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

Устройство кодирования с исправлением ошибок, показанное на фиг.1, использует узлы 12 умножения многочленов (n-1)-го порядка в количестве (m-1). Так как операция Исключающее-ИЛИ каждого выхода узлов 12-1 - 12-(m-1) умножения многочленов (n-1)-го порядка превращает в выход блока 1 умножения многочленов, каждый регистр (121-1 - 121-n) может совместно использоваться с другими узлами 12-1 - 12-(m-1) умножения многочленов (n-1)-го порядка.

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

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

r-битовый выход узла 2 деления многочленов r-го порядка, показанного на фиг.3, становится строкой избыточных битов для строки информационных битов из (nm-r) битов. Когда количество r избыточных битов совпадает с n, то это означает, что количество битов строки информационных битов, принятой узлом 2 деления многочленов r-порядка, равно нулю, и в этом случае узел 2 деления многочленов r-го порядка просто выводит n-битовый выход блока 1 умножения многочленов.

Ниже описывается выходной переключатель 4 устройства кодирования с исправлением ошибок, показанный на фиг.1. Строка информационных битов из (nm-r) битов становится выходной битовой строкой устройства кодирования с исправлением ошибок одновременно с тем, как она принимается блоком 1 умножения многочленов или узлом 2 деления многочленов r-го порядка. В этот момент времени, если необходимо, с первого по n(m-1)-ый бит информационных битов, принятых блоком 1 умножения многочленов, переупорядочиваются так, что их порядок совпадает с порядком битов, указанным проверочной матрицей, показанной в выражении (3), перед выводом.

После того как будут выведены все (nm-r) биты строки информационных битов, переключатель 4 переключается так, что становится активным выход узла 2 деления многочленов r-го порядка, и r-битовый выход узла 2 деления многочленов r-го порядка выводится в качестве выхода устройства кодирования с исправле