Устройство кодирования, способ конфигурирования кода с исправлением ошибок и программа для них

Устройство кодирования, способ конфигурирования кода с исправлением ошибок и программа для них

Иллюстрации

Показать все

Реферат

ОБЛАСТЬ ТЕХНИКИ

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

УРОВЕНЬ ТЕХНИКИ

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

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

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

Выражение 1 показывает блочную матрицу r×n (r и n - натуральные числа, удовлетворяющие rn, и k=n-r), которая показывает блочную проверочную матрицу квазициклического кода LDPC. В матрице циклической перестановки, в качестве каждого из компонентов блочной матрицы, показанной в выражении 1, порядок u(i, j) показывает целое число между 0 и m-1 (m - целое число 1 или большее) или символ -∞ (i - целое число между 0 и r-1, а j - целое число между 0 и n-1).

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

Когда u является целым числом между 0 и m-1, «Pˆu» показывает матрицу циклической перестановки, в которой только u-ый компонент самой верхней вектор-строки имеет значение «1», а другие компоненты имеют значение «0». Здесь «u» названо в качестве порядка матрицы Pˆu циклической перестановки. Когда порядок u имеет значение «0», Pˆu является единичной матрицей, в которой только диагональные компоненты имеют значение «1». Таким образом, это, в частности, выражается как «I». Кроме того, для того чтобы упростить нотацию, матрица Pˆ-∞ циклической перестановки порядка -∞ должна показывать нулевую матрицу, в которой все компоненты имеют значение «0».

В этой связи, «A с верхним индексом B» (например, A в степени B) выражается как «AˆB», а «A с нижним индексом B» выражено в качестве «A_B» в строках текста, отличных от числовых выражений.

(Выражение 1)

(Выражение 2)

Длина кода квазициклического кода LDPC, имеющего блочную матрицу в виде выражения 1 в качестве проверочной матрицы, имеет значение n×m битов. Среди битовых последовательностей из m×m битов, последовательности, чье матричное произведение с выражением 1 становится нулевым, рассматриваются в качестве набора строки битов передачи. На приемной стороне, делается вывод, есть или нет ошибка в строке битов приема, в зависимости от того, является ли нулевым матричное произведение строки битов приема и проверочной матрицы по выражению 1. Когда ошибка есть, обработка декодированием для исправления ошибки выполняется посредством использования проверочной матрицы с использованием алгоритма sum-product или min-sum, упомянутого выше.

Благодаря вышеприведенной обработке, квазициклический код LDPC, имеющий проверочную матрицу, показанную в выражении 1, определяется в зависимости от того, каким образом каждый порядок u(i, j) должен выбираться относительно каждого (i, j). Для определения порядка u(i, j), три момента, то есть способность исправления ошибок высока, обработка кодированием может легко выполняться, и емкость запоминающего устройства для сохранения значений каждого из порядков u(i, j) мала, могут браться в качестве руководящих принципов для определения порядка u(i, j). Технический вопрос, который должен быть преодолен, состоит в том, чтобы предоставить способ определения порядков u(i, j), который удовлетворяет трем моментам, и предоставить эффективное и экономичное устройство кодирования кода LDPC, имеющего проверочную матрицу, определенную согласно определенным порядкам u(i, j).

Среди таковых, известно, что способность исправления ошибок, в качестве первого руководящего принципа, должна зависеть от распределения весов относительно строчных и столбцовых блоков проверочной матрицы и количества коротких циклов. Распределение c(w) весов касательно строчного блока показывает, относительно положительного целого числа w, количество строчных блоков i, где количество столбцовых блоков j, удовлетворяющих u(i, j)≠-∞, соответствует w (i - целое число между 0 и r-1, j - целое число между 0 и n-1). Распределение v(w) весов касательно столбцового блока показывает количество столбцовых блоков j, где количество строчных блоков i, удовлетворяющих u(i, j)≠-∞, соответствует w.

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

Фиг. 11 - пояснительная схема, показывающая пример цикла (замкнутого контура) в проверочной матрице. На фиг. 11 проиллюстрированы цикл 801 длиной 4 и цикл 802 длиной 6. В случае использования алгоритма sum-product или min-sum, описанного выше, считается, что условие для достижения высокой способности исправления ошибок состоит в том, чтобы не иметь короткого цикла, равного или меньшего, чем длина 4, такого как цикл 801. То есть, касательно способности исправления ошибок в качестве первого руководящего принципа, необходимо принимать во внимание не только распределение весов, но также и количество коротких циклов.

В качестве технологии для преодоления описанного выше технического вопроса, есть способ, показанный в Непатентном документе 3. Эта технология определяет порядки u(i, j) как в выражении 3 (l - целое число, удовлетворяющее 0<l<r-1) касательно столбцового блока j, где jk (k показывает n-r).

(Выражение 3)

(Выражение 4)

В выражении 3 и выражении 4, порядки b_0, b_1,..., b_r1, x определены, чтобы быть способными легко применять способ кодирования, изображенный в Непатентном документе 4. Для значений касательно порядков u(i, j) значения 0i<r, 0j<k, иных, чем приведенные выше, сначала делается вывод, справедливо или нет u(i, j)=-∞. Затем, значение u(i, j) определяется относительно (i, j), которое удовлетворяет u(i, j)≠-∞.

Фиг. 12 - блок-схема алгоритма, показывающая пример способа определения u(i, j) согласно технологиям, изображенным в Непатентных документах 3 и 4. В процессе обработки, показанном на фиг. 12, сначала определяются b_0, b_1,..., b_r1, x и y (этап S901), и определяются распределение c(w) весов касательно строчного блока и распределение v(w) весов касательно столбцового блока проверочной матрицы (w - целое число). Впоследствии, вычисляются распределения v(w) и c(w) весов (этап S902), а строчные и столбцовые блоки i и j, удовлетворяющие u(i, j)≠-∞, определяются согласно распределениям весов (этап S903).

Строчные и столбцовые блоки не обязательно определяются единственным образом. Кроме того, как описано выше, все блоки согласно распределениям весов, вычисленным на этапе S902, не обязательно имеют высокую способность исправления ошибок. Это в общем принимается во внимание, и строчные и столбцовые блоки i и j, удовлетворяющие u(i, j)≠-∞, определяются подряд из тех, которые сопровождают одни и те же распределения весов, посредством использования случайных чисел, при этом обращая внимание на количество коротких циклов.

Благодаря обработке вплоть до этапа S903, может быть определено, все или нет u(i, j) имеют значение -∞. В последствии, столбцовые блоки подряд выбираются из одного с наименьшим весом (этап S904), и числовое значение u(i, j*) касательно выбранного столбцового блока j* определяется таким образом, чтобы количество коротких циклов матрицы по выражению 4 становилось меньшим (этап S905). Обработка этапов с S904 по 905 повторяется до тех пор, пока не определены все u(i, j) (этап S906). Тем самым, последовательно определяются числовые значения u(i, j) относительно (i, j), удовлетворяющие u(i, j)≠-∞.

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

Патентный документ 1: WO 2007/072721.

Патентный документ 2: WO 2007/080827.

Патентный документ 3: Публикация 2008-508776 заявки на выдачу патента Японии.

Непатентный документ 1: Robert Gallager, «Low-density-parity-check Codes», IEEE Transoperations on InformationTheory, January, 1962, pp 21-28.

Непатентный документ 2: D. J. C. Mackay, «Good Error-Correcting Codes Based on very sparse matrices», IEEE Transoperations on InformationTheory, March, 1999, pp 339-431.

Непатентный документ 3: Myung, Yang, Kim, «Quasi-Cyclic LDPC Codes for Fast Encoding», IEEE Transoperations on InformationTheory, August, 2005, pp 2894-2901.

Непатентный документ 4: Richardson, Urbanke, «Efficient Encoding Of Low-density-parity-check Codes», IEEE Transoperations on InformationTheory, February, 2001, pp 638-656.

В проверочной матрице в виде выражения 4, определенного описанной выше технологией, между значениями каждого из порядков u(i, j) наблюдают не регулярность, а случайность. Таким образом, необходимо иметь область хранения размера (k_r) log (2_m), для того чтобы сохранять проверочную матрицу, требуемую в конструкции устройства кодирования или декодирования. Однако, когда есть регулярность между значениями каждого из порядков u(i, j), характеристика частоты появления ошибок ухудшается.

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

Патентные документы 1 и 2 предназначены для преодоления описанных выше проблем и эффективны в уменьшении области хранения, требуемой для использования множества кодов LDPC. Однако нет специального соображения, предпринятого для укорачивания времени, требуемого для переключения, так что они не преодолевают такой проблемный момент. Этот момент не учитывается технологиями в Патентном документе 3 и Непатентных документах с 1 по 4, так что он не может быть преодолен комбинированием таких технологий.

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

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

Для того чтобы решить вышеизложенную задачу, устройство кодирования согласно настоящему изобретению является устройством кодирования для построения квазициклического кода контроля четности с низкой плотностью, которое включает в себя: модуль генерирования проверочной матрицы, который генерирует блочную проверочную матрицу квазициклического кода контроля четности с низкой плотностью, которая имеет матрицу циклической перестановки, где количество строк и количество столбцов оба имеют значение q-1, или нулевую матрицу в качестве компонентов (q - целое число 4 или большее, и является степенью 2), количество строчных блоков имеет значение r, а количество столбцовых блоков имеет значение q+1 (r - целое число между 4 и q включительно), и компоненты i-ого строчного блока и j-ого столбцового блока (i - целое число между 0 и r-1, j - целое число между 0 и q, крайний левый столбец матрицы определен в качестве 0-ого столбца, а крайняя верхняя строка определена в качестве 0-ой строки) соответствуют нулевой матрице или матрице циклической перестановки, чей порядок является значением функции λ(j-i), имеющей целое число j-i в качестве аргумента; и модуль кодирования, который генерирует и выдает кодовое слово посредством блочной проверочной матрицы из введенного сообщения, при этом, модуль генерирования проверочной матрицы дополнительно включает в себя: блок назначения порядка, который предписывает значение функции λ(j-i) блочной проверочной матрицы посредством коэффициента самодвойственного многочлена, имеющего q-1 фрагментов элементов поля Галуа, GF(qˆ2), в качестве корней; блок определения распределения весов, который предписывает количество компонентов, которые должны быть ненулевой матрицей, из числа компонентов каждого столбцового блока блочной проверочной матрицы и количество компонентов, которые должны быть ненулевой матрицей, из числа компонентов каждого строчного блока блочной проверочной матрицы посредством использования заданного шаблона маски; первый блок изменения порядка, который берет полную сумму компонентов k_r-ого блока (k_r - целая часть (q+1-r)/2) блочной проверочной матрицы в качестве матрицы циклической перестановки; и второй блок изменения порядка, который предписывает количество компонентов строчного блока, которые должны быть ненулевой матрицей, из числа компонентов каждого столбцового блока, за исключением k_r-ого столбцового блока блочной проверочной матрицы.

Для того чтобы решить вышеизложенную задачу, способ конфигурирования кода с исправлением ошибок согласно настоящему изобретению является способом конфигурирования кода с исправлением ошибок для построения квазициклического кода контроля четности с низкой плотностью, который включает в себя: генерирование посредством модуля генерирования проверочной матрицы блочной проверочной матрицы квазициклического кода контроля четности с низкой плотностью, которая имеет матрицу циклической перестановки, где количество строк и количество столбцов оба имеют значение q-1, или нулевую матрицу в качестве компонентов (q - целое число 4 или большее, и является степенью 2), количество строчных блоков имеет значение r, а количество столбцовых блоков имеет значение q+1 (r - целое число между 4 и q включительно), и компоненты i-ого строчного блока и j-ого столбцового блока (i - целое число между 0 и r-1, j - целое число между 0 и q, крайний левый столбец матрицы определен в качестве 0-ого столбца, а крайняя верхняя строка определена в качестве 0-ой строки) соответствуют нулевой матрице или матрице циклической перестановки, чей порядок является значением функции λ(j-i), имеющей целое число j-i в качестве аргумента; и генерирование и выдачу, модулем кодирования, кодового слова посредством блочной проверочной матрицы из введенного сообщения. Способ дополнительно включает в себя: при генерировании блочной проверочной матрицы, предписание, блоком назначения порядка, значения функции λ(j-i) блочной проверочной матрицы посредством коэффициента самодвойственного многочлена, имеющего q-1 фрагментов элементов поля Галуа, GF(qˆ2), в качестве корней; предписание, блоком определения распределения весов, количества компонентов, которые должны быть ненулевой матрицей, из числа компонентов каждого столбцового блока блочной проверочной матрицы и количества компонентов, которые должны быть ненулевой матрицей, из числа компонентов каждого строчного блока блочной проверочной матрицы посредством использования заданного шаблона маски; взятие, первым блоком изменения порядка, полной суммы компонентов k_r-ого блока (k_r - целая часть (q+1-r)/2) блочной проверочной матрицы в качестве матрицы циклической перестановки; и предписание, вторым блоком изменения порядка, количества компонентов строчного блока, которые должны быть ненулевой матрицей, из числа компонентов каждого столбцового блока, за исключением k_r-ого столбцового блока блочной проверочной матрицы.

Для того чтобы решить вышеизложенную задачу, программа конфигурирования кода с исправлением ошибок согласно настоящему изобретению является программой конфигурирования кода с исправлением ошибок для построения квазициклического кода контроля четности с низкой плотностью, которая побуждает компьютер выполнять: функцию генерирования блочной проверочной матрицы квазициклического кода контроля четности с низкой плотностью, которая имеет матрицу циклической перестановки, где количество строк и количество столбцов оба имеют значение q-1, или нулевую матрицу в качестве компонентов (q - целое число 4 или большее, и является степенью 2), количество строчных блоков имеет значение r, а количество столбцовых блоков имеет значение q+1 (r - целое число между 4 и q включительно), и компоненты i-ого строчного блока и j-ого столбцового блока (i - целое число между 0 и r-1, j - целое число между 0 и q, крайний левый столбец матрицы определен в качестве 0-ого столбца, а крайняя верхняя строка определена в качестве 0-ой строки) соответствуют нулевой матрице или матрице циклической перестановки, чей порядок является значением функции λ(j-i), имеющей целое число j-i в качестве аргумента; и функцию генерирования и выдачи кодового слова посредством блочной проверочной матрицы из введенного сообщения. Программа дополнительно побуждает компьютер, при генерировании блочной проверочной матрицы, выполнять: функцию предписания значения λ(j-i) функции блочной проверочной матрицы посредством коэффициента самодвойственного многочлена, имеющего q-1 фрагментов элементов поля Галуа, GF(qˆ2), в качестве корней; функцию предписания количества компонентов, которые должны быть ненулевой матрицей, из числа компонентов каждого столбцового блока блочной проверочной матрицы и количества компонентов, которые должны быть ненулевой матрицей, из числа компонентов каждого строчного блока блочной проверочной матрицы посредством использования заданного шаблона маски; функцию взятия полной суммы компонентов k_r-ого блока (k_r - целая часть (q+1-r)/2) блочной проверочной матрицы в качестве матрицы циклической перестановки; и функцию предписания количества компонентов строчного блока, которые должны быть ненулевой матрицей, из числа компонентов каждого столбцового блока, за исключением k_r-ого столбцового блока блочной проверочной матрицы.

Как описано выше, настоящее изобретение сконструировано в качестве конструкции, в которой: порядки матрицы циклической перестановки имеют значения λ(j-i), когда компоненты i-ой строки и j-ого столбца блочной проверочной матрицы не являются нулевой матрицей; порядки матрицы циклической перестановки имеют значения λ(j-i), когда компоненты i+1-ой строки и j+1-ого столбца блочной проверочной матрицы не являются нулевой матрицей; и порядки матрицы циклической перестановки имеют значения λ(j-i), когда компоненты i+2-ой строки и j+2-ого столбца блочной проверочной матрицы, компоненты i+3-ей строки и j+3-его столбца блочной проверочной матрицы, и после этого, не являются нулевой матрицей. Таким образом, область хранения, требуемая для сохранения проверочной матрицы, сгенерированной настоящим изобретением, может быть уменьшена до приблизительно (q+1-r)×r битов. Кроме того, использование шаблона маски дает возможность генерировать много видов проверочных матриц разных скоростей кодирования из одних и тех же данных и, кроме того, мгновенно переключать проверочные матрицы.

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

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

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

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

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

фиг. 4 - блок-схема алгоритма, показывающая подробности обработки, выполняемой вторым блоком изменения порядка, показанным в качестве этапа S104 на фиг. 3;

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

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

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

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

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

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

фиг. 11 - пояснительная схема для описания примера циклов (замкнутых контуров) длиной 4 и длиной 6 в проверочной матрице; и

фиг. 12 - блок-схема алгоритма, показывающая пример способа определения u(i, j) согласно технологиям, изображенным в Непатентных документах с 3 по 4.

НАИЛУЧШИЕ ВАРИАНТЫ ДЛЯ ОСУЩЕСТВЛЕНИЯ ИЗОБРЕТЕНИЯ

<ПЕРВЫЙ ПРИМЕРНЫЙ ВАРИАНТ ОСУЩЕСТВЛЕНИЯ>

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

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

Как показано на фиг. 1, устройство 10 кодирования согласно примерному варианту осуществления включает в себя: модуль 11 генерирования проверочной матрицы, который генерирует блочную проверочную матрицу квазициклического кода контроля четности с низкой плотностью (LDPC), которая является матрицей циклической перестановки, где количество строк и количество столбцов оба имеют значение q-1, или нулевой матрицей в качестве компонентов (q - целое число 4 или большее, и является степенью 2), количество строчных блоков имеет значение r, а количество столбцовых блоков имеет значение q+1 (r - целое число между 4 и q включительно), и компоненты i-ого строчного блока и j-ого столбцового блока (i - целое число между 0 и r-1, j - целое число между 0 и q, крайний левый столбец матрицы определен в качестве 0-ого столбца, а крайняя верхняя строка определена в качестве 0-ой строки) соответствуют нулевой матрице или матрице циклической перестановки, чей порядок является значением функции λ(j-i), имеющей целое число j-i в качестве аргумента; и модуль 12 кодирования, который генерирует и выдает кодовое слово посредством блочной проверочной матрицы из введенного сообщения.

Кроме того, модуль 11 генерирования проверочной матрицы включает в себя: блок 11a назначения порядка, который предписывает значение функции λ(j-i) блочной проверочной матрицы посредством коэффициента самодвойственного многочлена, имеющего q-1 фрагментов элементов поля Галуа, GF(qˆ2), в качестве корней; блок 11b определения распределения весов, который предписывает количество компонентов, которые должны быть ненулевой матрицей, из числа компонентов каждого столбцового блока блочной проверочной матрицы и количество компонентов, которые должны быть ненулевой матрицей, из числа компонентов каждого строчного блока блочной проверочной матрицы посредством использования заданного шаблона маски; первый блок 11c изменения порядка, который берет полную сумму компонентов k_r-ого блока (k_r - целая часть (q+1-r)/2) блочной проверочной матрицы в качестве матрицы циклической перестановки; и второй блок 11d изменения порядка, который предписывает количество компонентов строчного блока, которые должны быть ненулевой матрицей, из числа компонентов каждого столбцового блока, за исключением k_r-ого столбцового блока блочной проверочной матрицы.

Кроме того, модуль 12 кодирования включает в себя: память 33 сохранения матричных данных, которая хранит блочную проверочную матрицу, сгенерированную модулем генерирования проверочной матрицы, и шаблон маски; устройства 31 умножения r фрагментов матриц, которые вычисляют матричные произведения строк битов информации сообщения и матрицы циклической перестановки, чей порядок является значением функции λ(j-i), имеющей в качестве аргумента целое число j-i, предписанное коэффициентом самодвойственного многочлена, имеющего q-1 фрагментов элементов поля Галуа, GF(qˆ2), в качестве корней; и селектор 32, который переключает входные сигналы в устройства матричного умножения согласно шаблону маски, сохраненному в памяти сохранения матричных данных.

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

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

В дальнейшем, это будет описано подробнее.

Фиг. 1 - пояснительная схема, показывающая систему 1 связи, которая включает в себя устройство 10 кодирования согласно первому примерному варианту осуществления настоящего изобретения. Система 1 связи составлена из: устройства 10 кодирования, которое генерирует кодовое слово из сообщения, которое является цифровым сигналом, введенным из устройства связи, запоминающего устройства, или тому подобного; модулятора 21, который модулирует кодовое слово, выведенное из устройства 10 кодирования, и загружает его в несущую волну; тракта 22 передачи, который передает несущую волну, выданную из модулятора 21; демодулятора 23, который извлекает кодовое слово из несущей волны, переданной через тракт 22 передачи; и устройства 24 декодирования, которое декодирует извлеченное кодовое слово и получает исходное сообщение. В качестве альтернативы, тракт 22 передачи может быть заменен носителем информации, таким как оптический диск или магнитный диск.

Устройство 10 кодирования включает в себя: модуль 11 генерирования проверочной матрицы, который генерирует блочную проверочную матрицу квазициклического кода LDPC; и модуль 12 кодирования, который генерирует кодовое слово из введенного сообщения посредством использования блочной проверочной матрицы. Выражение 5 показывает блочную проверочную матрицу, сгенерированную модулем 11 генерирования проверочной матрицы.

(Выражение 5)

В этой связи, в выражении 5, u(i, j), определенное в отношении 0i<r, k<j<n в выражении 1, описанном выше, определяется как u(i, j)=0, только когда применяется j=k+i, или j=k+1+i, и определяется как u(i, j)=-∞ в других случаях.

Для того чтобы упросить разъяснения в дальнейшем, q определяется в качестве степени 2 (q=2ˆs; s - целое число 2 или большее), r определено в качестве положительного целого числа между 4 и q, включительно, а k определено в качестве q+1-r. Кроме того, каждое из количества строк и количества столбцов матрицы P циклической перестановки, показанной на фиг. 2, определено в качестве q-1. Выражение 5 является блочной матрицей, в которой количество строчных блоков имеет значение r, а количество n столбцовых блоков имеет значение (q+1).

Фиг. 2 - пояснительная схема, показывающая более подробную структуру модуля 11 генерирования проверочной матрицы, показанного на фиг. 1. Кроме того, фиг. 3 - блок-схема алгоритма, показывающая операции для генерирования блочной проверочной матрицы (выражение 5), выполняемые модулем 11 генерирования проверочной матрицы, показанным на фиг. 2. Операции предназначены для определения u(i, j) для фрагментов r×(k+1) компонентов блочной проверочной матрицы, показанной в выражении 5 (i - целое число между 0 и r-1, j - целое число между 0 и k).

Модуль 11 генерирования проверочной матрицы включает в себя операционные блоки, такие как блок 11a назначения порядка, блок 11b определения распределения весов, первый блок 11c изменения порядка и второй блок 11d изменения порядка.

Блок 11a назначения порядка сначала назначает u(i, j)=λ(j-i) всем u(i, j) (этап S101). Отметим, что λ(t) - положительное целое число, определенное благодаря процедуре, описанной следующей, когда t+r+(q/2) не может быть поделено на q+1 для целого числа t. Когда t+r+(q/2) является кратным q+1, определяется, что λ(t)=-∞.

Будет описан способ для определения λ(t) для целого числа t. β определено в качестве примитивного элемента поля Галуа, GF(qˆ2). Для всех целых чисел h, удовлетворяющих -(q-2)/2h (q-2)/2, многочлен выражения 6, имеющий βˆh в качестве нуля, определен как g(x), а коэффициент его члена порядка t определен как g_t.

(Выражение 6)

Коэффициент g_t выражения 6, упомянутый выше, имеет значение g_0=0, и он имеет значение g_t=g_(q+1-t) для случаев 0<tq. Такой многочлен, у которого нет никаких изменений, даже когда его коэффициент члена низкого порядка и коэффициент члена высокого порядка находятся в обратной очередности, называется самодвойственным многочленом. Кроме того, касательно 0<tq, коэффициент g_t может быть выражен степенью βˆt посредством использования примитивного элемента β. Показательная функция выражена в качестве μ(t). То есть g_t=(βˆ(q+1))ˆμ(t). Аргумент t у μ(t) расширен до всех целых чисел за исключением кратных q+1, чтобы иметь значение μ(t)=μ(t mod (q+1)). Кроме того, что касается целого числа t, при котором t+r+(q/2) не может делиться на q+1, λ(t), упомянутое выше, определено в качестве выражения 7 посредством использования целого числа μ(t).

(Выражение 7)

Кроме того, что касается целого числа t, при котором t+r+(q/2) может делиться на q+1, оно определено в качестве λ(t)=-∞ для целей удобства. Как описано выше, целочисленное значение λ(t) вычисляется на этапе S101, и u(i, j)= λ(j-i) устанавливается для всех u(i, j). Посредством этого, выражение 1, упомянутое выше, может быть выражено в виде выражения 8, показанного ниже.

(Выражение 8)

Затем, блок 11b определения распределения весов определяет распределение весов касательно строчных блоков и столбцовых блоков проверочной матрицы выражения 8, упомянутого выше (этап S102). Ввиду повышения возможности исправления ошибок, нормально, распределение весов определяется посредством использования эволюции плотности. Однако способ в материалах настоящей заявки не ограничен эволюцией плотности. Должно быть отмечено, что вес столбца определен как 2 для всех блоков с k+1-ого столбцового блока по q-ый столбцовый блок.

Все u(i, j) уже определены в качестве λ(j-i) на этапе S101. Однако часть u(i, j) превращается этапами с S103 по 104, показанными в последующем, в -∞ для приведения в соответствие распределению весов, вычисленному на этапе S102.

Поскольку λ(k)=λ(k+1)=0 из выражения 7, упомянутого выше, матрица по выражению 8 становится находящейся в форме матрицы по выражению 5 посредством превращения u(i, j) относительно 0i<r, k<j<n в u(i, j)= -∞ в случае, где j≠k+i, и j≠k+1+i. Поэтому должно быть отмечено, что u(i, j) относительно 0i<r, k<j<n изменяется в качестве u(i, j)=-∞ в случае, где j≠k+i, и j≠k+1+i.

Первый блок 11c изменения порядка превращает часть u(i, k_r) в -∞, так что полная сумма компонентов k_r-ого столбцового блока становится матрицей циклической перестановки (этап S103). Отметим здесь, что k_r показывает целочисленные значения, показанные в следующем выражении 9.

(Выражение 9)

То есть, k_r показывает целую часть (q+1-r)/2. Пример способа превращения части u(i, k_r) в -∞, так чтобы полная сумма компонентов k_r-ого столбцового блока становилась матрицей циклической перестановки, будет описан позже.

Второй блок 11c изменения порядка превращает часть u(i, k_r) в -∞ для каждого столбцового блока j, иного чем k_r-ый столбцовый блок, для которого обработка выполняется на этапе S103 (этап S104). В это время, это делается для удовлетворения распределения весов, определенного на этапе S102, и для уменьшения количества коротких циклов, описанных на фиг. 10, как можно меньше. Подробности обработки этапа S104 также будут описаны позже.

Операции модуля 11 генерирования проверочной матрицы будут описаны дополнительно. Как описано выше, модуль 11 генерирования проверочной матрицы определяет все u(i, j) проверочной матрицы, показанной в выражении 5 (i - целое