Способ кодирования кода разреженного контроля четности

Способ кодирования кода разреженного контроля четности

Иллюстрации

Показать все

Реферат

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

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

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

В общем, система связи кодирует передаваемые данные перед передачей, чтобы повысить стабильность передачи, и предотвращает избыточные повторные передачи, чтобы повысить эффективность передачи. Для кодирования передаваемых данных система мобильной связи использует сверточное кодирование, турбокодирование и квазидополняемое турбокодирование (QCTC). Использование вышеперечисленных схем кодирования направлено на повышение стабильности передачи данных и эффективности передачи.

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

Кодирование с разреженным контролем четности (LDPC) предусмотрено в качестве новой схемы кодирования для удовлетворения указанной потребности. Подробное описание кода разреженного контроля четности приведено в данном документе далее. Код разреженного контроля четности впервые был предложен Галлагером в начале 60-ых гг. и пересмотрен Маккеем в конце 90 -х гг. Код разреженного контроля четности, проанализированный Маккеем, основан на алгоритме суммы-произведения. Благодаря использованию декодирования распространения убежденности код разреженного контроля четности начал привлекать всеобщее внимание как код, позволяющий демонстрировать отличную производительность, аппроксимируя ограничение по пропускной способности Шэннона.

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

Помимо этого, Ричардсон и Чанг показали, что теоретическая пропускная способность канала нерегулярного кода LDPC может аппроксимировать ограничение по пропускной способности Шэннона до всего лишь 0,0045 дБ с помощью методики эволюции плотности. В частности, компания Flarion Co., ведущий разработчик структуры и аппаратных средств кода LDPC, предложила многоконтурный векторный код LDPC, допускающий реализацию параллельного декодера, имеющего частоту ошибок по кадрам меньше, чем частота ошибок для турбокода, даже для кода LDPC с короткой длиной.

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

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

Раскрытие изобретения

Таким образом, цель настоящего изобретения - предоставить способ кодирования LDPC с простым процессом кодирования.

Еще одна цель изобретения - предоставить способ кодирования LDPC, имеющий более высокую производительность при небольшом размере кадра.

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

Предпочтительно, последовательность степеней состоит из D={15, 15, 15, 5, 5, 5, 4, 3, 3, 3, 3, 3, 3, 3, 3}, а значения смещения между диагональными линиями являются взаимно простыми относительно числа столбцов в обобщенной двухдиагональной матрице.

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

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

Предпочтительно, на этапе (a) символ четности определяется суммой информационных символов матрицы информационной части, существующих в той же строке, что и индекс строки в подматрице, символы четности которой определяются.

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

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

Фиг.1 - это схема, иллюстрирующая матрицу контроля четности для общего кода массива (p, r);

Фиг.2 - это схема, иллюстрирующая пример матрицы H_d в случае, когда максимальное число единиц, существующих в конкретном столбце, задано как d_v, число этих столбцов подматрицы задано как n_v, а число единиц, существующих в оставшихся столбцах подматрицы, всегда равно 3;

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

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

Фиг 5 - это схема, иллюстрирующая матрицу четности, в которой значение смещения T двухдиагональной матрицы повышено до конкретного значения;

Фиг.6 - это схема, иллюстрирующая процесс последовательного вычисления значений p₀, p_r-f, p_r-2f,... в процессе кодирования Фиг. 5;

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

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

Фиг.9 - это схема, иллюстрирующая матрицу H_p четности, составленную посредством повышения матрицы на подматрицу циклической перестановки pхp;

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

Фиг.11 - это схема, иллюстрирующая матрицу четности обобщенной двухдиагональной матрицы, повышенной для r=15, f=7 и p=89;

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

Фиг.13A - это схема, иллюстрирующая пример матрицы информационной части H_d для n=870 и p=29;

Фиг.13B - это схема, иллюстрирующая пример матрицы части H_p четности для n=870 и p=29;

Фиг.13C - это график моделирования результатов, иллюстрирующий сравнение кода разреженного контроля четности и турбокода;

Фиг.14A - это схема, иллюстрирующая пример матрицы информационной части H_d для n=1590 и p=53;

Фиг.14B - это схема, иллюстрирующая пример матрицы части H_p четности для n=1590 и p=53;

Фиг.14C - это график моделирования результатов, иллюстрирующий сравнение кода разреженного контроля четности и турбокода;

Фиг.15A - это схема, иллюстрирующая пример матрицы информационной части H_d для n=3090 и p=103;

Фиг.15B - это схема, иллюстрирующая пример матрицы части H_p четности для n=3090 и p=103;

Фиг.15C - это график моделирования результатов, иллюстрирующий сравнение кода разреженного контроля четности и турбокода;

Фиг.16A - это схема, иллюстрирующая пример матрицы информационной части H_d для n=7710 и p=257;

Фиг.16B - это схема, иллюстрирующая пример матрицы части H_p четности для n=7710 и p=257;

Фиг.16C - это график моделирования результатов, иллюстрирующий сравнение кода разреженного контроля четности и турбокода; и

Фиг.16D - это график моделирования результатов для кода разреженного контроля четности согласно вариации в числе итераций.

Осуществление изобретения

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

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

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

1. Структура матрицы контроля четности

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

A. Структура кода массива

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

На Фиг.1 p означает простое число, а σ^jозначает матрицу циклической перестановки pхp, получаемую посредством циклического сдвига соответствующих строк единичной матрицы pхp I, которая является квадратной матрицей, имеющей размер p, на j. Строка и столбец, каждый составленный из набора σ^j, называются строкой подматрицы и столбцом подматрицы соответственно. Столбец и строка матрицы контроля четности, задающей код массива, равномерно имеют p единиц и r единиц соответственно. Когда p достаточно большое, соотношение единиц в матрицы уменьшается, приводя к структуре кода разреженного контроля четности. Этот код массива не имеет циклической структуры с длиной 4. Т.е. если элементы, принадлежащие 4 частичным матрицам σ^ia, σ^ib, σ^ja и σ^jb (ij), формирующим квадрат или цикл-4, в матрице контроля четности имеют структуру цикл-4, следующее отношение должно удовлетворяться:

ia - ib =ja -jb(i-j) = (a-b) (mod p) (1)

В уравнении (1) должно удовлетворяться, что a=b. Тем не менее, поскольку a и b, существующие в различных строках, всегда имеют различные значения, уравнение (1) не может быть удовлетворено. Поэтому вышеописанный код массива, имеющий матрицу контроля четности, имеет структуру не цикл-4.

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

(1) j-тый столбец подматрицы матрицы контроля четности, формирующей код массива, составлен из подматриц, представленных как:

(2) В зависимости от заранее определенного распределения степеней последовательность степеней каждого столбца подматрицы задается как:

D = [d₀ d₁... d_s-1] (3)

В уравнении (3) d_j означает степень столбца, соответствующего j-тому столбцу подматрицы, а s означает общее число столбцов подматрицы. Помимо этого, s задается таким образом, чтобы быть идентичным общему числу d_v единиц, существующих в конкретном столбце.

(3) В зависимости от степени последовательности D, заданной в (2), j-тый столбец подматрицы модифицируется как:

t_j = t_j-1 + d_j-1(mod s) (4)

В уравнении (4) t_j означает номер строки подматрицы, с которой начинается ненулевая подматрица в j-том столбце H_j подматрицы.

(4) Матрица H_d, которая должна быть сгенерирована, задается уравнением (5), в котором столбцы подматрицы заменены на векторы-столбцы:

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

Фиг.2 - это схема, иллюстрирующая пример матрицы H_d в случае, когда максимальное число единиц, существующих в конкретном столбце, задано как d_v, число этих столбцов подматрицы задано как n_v, а число единиц, существующих в оставшихся столбцах подматрицы, всегда равно 3.

В настоящем изобретении матрица H_d 220 информационной части матрицы H контроля четности, заданная на основе структуры кода массива, описанной в связи с Фиг.2, используется в качестве подматрицы матрицы H контроля четности кода разреженного контроля четности, который должен быть задан в настоящем изобретении. Далее приводится описание нерегулярного повторяющегося кода накопления (IRA-кода) для генерирования подматрицы, формирующей часть четности матрицы H контроля четности.

B. Обобщенная двухдиагональная матрица

Известно, что нерегулярный повторяющийся код накопления (IRA-код) имеет простую структуру кодера и имеет относительно высокую производительность посредством декодера обмена сообщениями. Этот нерегулярный повторяющийся код накопления может быть рассмотрен как один тип режима разреженного контроля четности.

Фиг.3 - это схема, иллюстрирующая структуру графа множителей нерегулярного повторяющегося кода накопления. Далее приводится описание структуры графа множителей нерегулярного повторяющегося кода накопления со ссылкой на Фиг. Граф множителей нерегулярного повторяющегося кода накопления Фиг.3 - это систематическая версия, в которой все узлы четности, соответствующие символам четности кодового слова, за исключением только одного узла четности, имеют степень 2. Т.е. каждый из узлов четности 301, 302, 303,..., 304, 305, 306 и 307 имеет 2 ребра, подсоединенные к нему. Такая структура узлов четности является выгодной в том, что генерирование символов четности на основе данных информационных символов достигается просто линейным вычислением. Помимо этого, как можно понять из Фиг.3, информационные узлы нерегулярного повторяющегося кода накопления могут иметь различные распределения степеней. Значения информационных узлов связаны с контрольными узлами посредством случайной перестановки 320.

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

В матрице кода разреженного контроля четности, проиллюстрированной на Фиг.4, диагональные линии в части четности представляют 1, а смещение f (401) между диагональными линиями имеет значение 1 в общем нерегулярном повторяющемся коде накопления. Поэтому подматрица, соответствующая части четности матрицы контроля четности, задающей нерегулярный повторяющийся код накопления, имеет структуру двухдиагональной матрицы. Число единиц, существующих в каждом столбце информационной части в матрице контроля четности, имеет нерегулярное распределение. Это распределение задается блоком случайных перестановок Фиг.4.

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

В случае общего нерегулярного повторяющегося кода накопления Фиг.4 смещение f между диагональными линиями имеет значение 1 (f=1). В настоящем изобретении, если значение смещения f повышено таким образом, что оно имеет конкретное значение, двухдиагональная матрица части четности может быть обобщена так, как проиллюстрировано на Фиг.5. На Фиг.5 первая диагональная линия 501 формирует диагональную линию от позиции в первом столбце и первой строке до позиции в последнем столбце и последней строке матрицы. Первая частичная диагональная линия 502a второй диагональной линии имеет значение 0 в столбце первой позиции, смещенном на значение смещения, и имеет значение 1 в оставшихся позициях до своей последней точки. Вторая частичная диагональная линия 502b второй диагональной линии формирует диагональную линию со значением 1 из первого столбца в следующей строке.

При этом фиг 5 - это схема, иллюстрирующая матрицу четности, в которой значение смещения двухдиагональной матрицы повышено до конкретного значения. Хотя значение смещения изменено, как проиллюстрировано на Фиг.5, всегда существует столбец, имеющий только одну 1. Следует отметить, что если число единиц, существующих в каждом столбце, равно 2, ранг двухдиагональной матрицы становится меньше, чем число строк в матрице. Поэтому первая строка второй диагональной линии должна иметь 0, а не 1, как проиллюстрировано на Фиг.5. В случае матрицы rхr, т.е. квадратной матрицы с размером r матрицы, проиллюстрированной на Фиг.5, если значение f смещения двухдиагональной матрицы и размер r матрицы не имеют общего множителя, можно сгенерировать все из r символов четности посредством простого выполнения сложения над набором данных информационных символов r раз. Чтобы доказать это, рассматриваются следующие теоремы.

Теорема 1: В абелевой группе AG_r={0, 1, 2,..., r-1} все элементы генерируются посредством выполнения сложения над конкретным элементом f, который является взаимно-простым для r и не равен 0, меньше r раз. Чтобы доказать это, если все элементы в AG_r не могут быть сгенерированы посредством выполнения сложения над конкретным элементом f, который является взаимно-простым для r и не равен 0, меньше r, то существует k меньше r, которое удовлетворяет условию уравнения (6).

kf = 0 (mod r) (6)

Тем не менее, уравнение (6) противоречит допущению, что f является взаимно-простым для r. Т.е. минимальное значение k, удовлетворяющее уравнению (6), всегда должно быть r. Поэтому все элементы в AG_r могут быть сгенерированы посредством выполнения сложения над элементом f r раз.

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

(7)

В уравнении (7) d_i означает i-тый информационный символ, а a_i означает число единиц, существующих в i-том столбце матрицы, соответствующем информационной части матрицы контроля четности. Помимо этого, ∑ означает сложение в GF(2). GF(2) ссылается на поле Галуа по 2 и означает конечное поле, заданное в модуле 2. Термин "конечное поле" означает набор, в котором число элементов конечно и элементы закрыты для сложения и умножения по модулю 2, существует нейтральный элемент и обратный элемент для сложения, существует нейтральный элемент для умножения и обратный элемент для ненулевого элемента, и закон перестановки, сочетательный закон и распределительный закон удовлетворяются для сложения и умножения. Поэтому GF(2) означает набор {0, 1}, удовлетворяющий этому свойству. В результате первый символ четности, который может быть получен уравнением контроля четности, соответствующим первому столбцу в матрице Фиг.5, задается как:

p₀ = v₀(8)

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

y₁ = x₁, y₂ = x₂ - f (9)

Если две формулы, показанные в уравнении (9), используются, p_r-f может быть рассчитан с помощью p₀ в соответствии с уравнением (10):

p_r-f = p₀ + v_r-f (10)

Помимо этого, поскольку матрица контроля четности имеет структуру двухдиагональной матрицы, проиллюстрированной на Фиг.5, уравнение (10) может быть модифицировано в:

p_r-if = p_r-(i-1)f + v_r-if, i = 1, ..., r-1 (11)

Таким образом, конкретный символ p_r-if четности может быть получен посредством уравнения (11), и на основе теоремы 1, если r является взаимно-простым для f, по мере того, как i увеличивается, значение (r-if) (модуль r) имеет значение 1 для r-1 только один раз. Следовательно, если r является взаимно-простым для f, значения всех символов четности могут быть рассчитаны посредством вышеописанного процесса. Поэтому в вышеописанном способе матрица контроля четности, имеющая часть четности, проиллюстрированную на Фиг.5, всегда может проходить простое кодирование посредством линейного вычисления. Фиг.6 - это схема, иллюстрирующая процесс последовательного вычисления значений p₀, p_r-f, p_r-2f,... в процессе кодирования.

Ссылаясь на Фиг.6, выполнена связь из значения позиции нулевого столбца и нулевой строки со значением положения нулевого столбца и (r-f)-той строки, представленного ссылкой с номером 601. Следует заметить, что значение позиции нулевого столбца и (r-f)-той строки связано со значением положения (r-f)-того столбца и (r-f)-той строки, представленного ссылкой с номером 602. Таким образом, единицы размещены только в первой диагональной линии 610, первой частичной линии 620a второй диагональной линии и второй частичной линии 620b второй диагональной линии. Поскольку только одно значение в 1 существует в первом столбце диагональных линий, функция второго порядка вычисляется посредством непрерывного поиска значения 1 вышеописанным способом. В результате все значения могут быть найдены.

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

C. Структура матрицы контроля четности

В этом разделе приводится описание способа генерирования новой матрицы H контроля четности согласно настоящему изобретению с помощью структуры обобщенной двухдиагональной матрицы, описанной в разделе B, а также описание ее структуры. Матрица контроля четности, описанная ниже, задает матрицу H_d, заданную на основе структуры кода массива, описанной в разделе A, как информационную часть матрицы H контроля четности. Дополнительно, описанная ниже матрица контроля четности задает нормализованную двухдиагональную матрицу H_p, описанную в разделе B, как часть четности матрицы H информационной части. Поэтому матрица H контроля четности, задающая код разреженного контроля четности, которая должна быть разработана в настоящем изобретении, имеет структуру, представленную как:

H=[H_d | H_p] (12)

где H_d - подматрица контроля четности для информационной части

H_p - подматрица контроля четности для части четности

В уравнении (12) соответствующие столбцы подматрицы в матрице H_d информационной части матрицы проверки четности задаются посредством последовательности степеней D на основе заранее заданного распределения степеней, а единичная матрица σ^ij, составляющая каждый столбец подматрицы, является матрицей циклической перестановки, получаемой посредством смещения столбцов единичной матрицы pхp с размером p на ij, которое является произведением индекса i столбца подматрицы и индекса j строки подматрицы. При этом p всегда является простым числом. Помимо этого, H_p повышает единицы и нули, существующие в матрице, в матрицу pхp и нулевую матрицу, соответственно, чтобы сопоставить ее структуру со структурой H_d.

Далее приводится описание процессов генерирования кода разреженного контроля четности согласно варианту осуществления настоящего изобретения.

(I) Распределение степеней и структура H_d

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

Настоящее изобретение аппроксимирует заранее определенное оптимизированное распределение степеней переменных узлов к распределению степеней переменных узлов матрицы H контроля четности, которая должна быть задана в настоящем изобретении. В этом случае переменные узлы со степенью 2 все назначены соответствующим столбцам в части H_p четности матрицы H, а переменные узлы со степенью больше 2 назначены соответствующим столбцам в информационной части H_d матрицы H. Помимо этого, из структуры кода массива, описанной в разделе A, и структуры подматриц обобщенной двухдиагональной матрицы, описанной в разделе B, степень контрольного узла матрицы H контроля четности всегда имеет только один или два минимизированных типа относительно числа всех данных единиц.

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

В уравнении (13) Xi означает соотношение ребер, существующих в переменном узле, со степенью i. Отношение c_j ребер, существующих в переменном узле, со степенью j в графе множителей для данного X(x) может быть выражено как:

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

λ₂ = 0,23802, λ₃= 0,20997, λ₄= 0,03492, λ₅ = 0,12015, (15)

λ₇ = 0,01587,λ₁₄= 0,00480,λ₁₅= 0,37627

В канале с аддитивным белым гауссовым шумом (AWGN) для обеспечения возможность вероятности ошибок переменных узлов сводиться к нулю, максимальная дисперсия шума параметра канала, σ^* равна 0,9622, и это равно 0,3348 дБ в показателях Eb/No. Т.е. код разреженного контроля четности, заданный посредством графа коэффициентов, имеющего вышеуказанное распределение степеней, показывает производительность, аппроксимирующую ограничение по пропускной способности Шэннона на 0,3348 дБ посредством декодирования распространения убежденности, для которого предполагается бесконечный размер блока и бесконечная итерация. В графе коэффициентов, имеющем вышеуказанное распределение степеней, соотношения переменных узлов, имеющих соответствующие степени, задается как:

c₂=0,47709, c₃=0,28058, c₄=0,034997, c₅=0,096332 (16)

c₇=0,0090386, c₁₄=0,001374, c₁₅=0,100560

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

c₂=1/2=0,5, c₃=8/30=0,26667, c₄=1/30=0,03333, c₅=3/30= 0,1, (17)

c₇=c₁₄=0, c₁₅=3/30=0,1

При использовании соотношений переменных узлов, показанных в уравнении (17), полином распределения степеней X(x) является вычисляемым приростом, и порог в AWGN кода разреженного контроля четности, заданного соответствующим распределением степеней, вычисляется в соответствии с уравнением (18):

σ^* = 0,9352 (Eb/No)* = 0,5819 dB (18)

Значение, определенное уравнением (18), - это значение, соответствующее коду разреженного контроля четности с кодовой скоростью 1/2. Это значение извлекается с помощью методики эволюции плотности на основе значения гауссовой аппроксимации в качестве методики анализа, и если оцененная вероятность ошибки по битам меньше 10^-6, соответствующее значение вычисляется с учетом того, что ошибки нет. Последовательность степеней, назначаемых каждому столбцу подматрицы информационной части H_d с помощью вычисленного значения, может быть задана как:

D = {15, 15, 15, 5, 5, 5, 4, 3, 3, 3, 3, 3, 3, 3, 3} (19)

В настоящем изобретении информационная часть H_d матрицы H контроля четности в разделе A, где описана структура кода массива, может быть задана на основе структуры кода массива согласно последовательности степеней, заданной уравнением (18).

Фиг.7 - это схема, иллюстрирующая пример информационной части H_d матрицы контроля четности, сгенерированной в способе, описанном в разделе A, в котором максимальная степень переменного узла равна 15. В структуре матрицы, проиллюстрированной на Фиг.7, столбцы и строки представляют столбцы подматрицы и строки подматрицы соответственно. Цифры, обозначающие столбцы и строки, представляют циклический сдвиг столбцов подматрицы и строк подматрицы. Каждая из цифр составлена из подматрицы pхp, в которой p=89. Поэтому матрицы информационной части H_d, сгенерированная в вышеуказанном способе, становится матрицей (d_v·p) х (d_v·p).

(II) Повышение и структура H_p

В общем, повышение матрицы относится к способу повышения размера базовой матрицы посредством замены подматрицы для матрицы, имеющей 0 и 1 в конкретной позиции. Это описывается со ссылкой на Фиг.8 Фиг.8 - это схема, иллюстрирующая матрицу 12х12, полученную посредством повышения базовой матрицы 4х4 в способе замены каждого элемента в матрице 4х4 на единичную матрицу 3х3 или нулевую матрицу 3х3.

Как проиллюстрировано на Фиг.8, повышение матрицы формирует квадратную матрицу, имеющую число элементов, равных 0, кратное целевому размеру повышения дл