Способы и устройство ldpc-кодирования

Способы и устройство ldpc-кодирования

Иллюстрации

Показать все

Реферат

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

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

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

Коды коррекции ошибок повсеместно используются в системах связи и хранения данных. Коды коррекции ошибок компенсируют внутреннюю ненадежность передачи информации в этих системах посредством введения избыточности в поток данных. Недавно возник значительный интерес к классу кодов, известному как коды с низкой плотностью контроля по четности (LDPC). Доказано, что LDPC-коды являются хорошими кодами. Было продемонстрировано в различных каналах, что LDPC-коды действительно близки к пропускной способности канала, т.е. верхнему пределу скорости передачи, установленному Claude Shannon.

LDPC-коды часто представляются посредством двудольных графов, называемых графами Таннера, в которых один набор узлов, узлы переменных, соответствует битам кодового слова, а другой набор узлов, узлы ограничений, иногда называемые проверочными узлами, соответствует набору ограничений контроля по четности, которые задают код. Ребра на графе соединяют узлы переменных с узлами ограничений. Говорят, что узел переменных и узел ограничений являются соседями, если они соединены посредством ребра на графе.

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

Примерный двудольный граф 100, определяющий примерный (3, 6) регулярный LDPC-код с длиной десять и скоростью одна вторая, показан на фиг.1. Длина десять указывает, что существует десять узлов переменных V₁-V₁₀, каждый идентифицируется с помощью одного бита кодового слова X₁-X₁₀. Набор узлов переменных V₁-V₁₀ идентифицируется на фиг.1 посредством ссылки с номером 102. Скорость одна вторая указывает, что проверочных узлов в два раза меньше, чем узлов переменных, т.е. предусмотрено пять проверочных узлов C₁-C₅, идентифицированных посредством ссылки с номером 106. Скорость одна вторая дополнительно указывает, что пять ограничений являются линейно независимыми. Примерный двудольный граф 100 включает в себя ребра 104, при этом примерный (3, 6) регулярный LDPC-код имеет 3 ребра, соединенных с каждым узлом переменных, и 6 ребер, соединенных с каждым узлом ограничений и, самое большее, одно ребро между двумя любыми узлами.

Тогда как фиг.1 иллюстрирует граф, ассоциативно связанный с кодом длиной 10, можно принимать во внимание, что представление графа для кодового слова длиной 1000 должно быть в 100 раз более сложным.

Альтернативой представлению на графе Таннера LDPC-кодов является представление матрицы контроля по четности, как, например, показанная на чертеже 200 по фиг.2. В этом представлении кода матрица H 202, в общем, упоминаемая как матрица контроля по четности, включает в себя соединение релевантных ребер, информацию об узлах переменных и узлах ограничений. В матрице H 202 каждый столбец соответствует одному из узлов переменных, тогда как каждая строка соответствует одному из узлов ограничений. Поскольку предусмотрено 10 узлов переменных и 5 узлов ограничений в примерном коде, матрица H 202 включает в себя 10 столбцов и 5 строк. Элементу матрицы 202, соответствующему конкретному узлу переменных и конкретному узлу ограничений, присваивается значение 1, если ребро присутствует на графе, т.е. если два узла являются соседями, иначе ей присваивается значение 0. Например, поскольку переменный узел V₁ соединен с узлом ограничений C₁ посредством ребра, единица размещается в верхнем левом углу матрицы 202. Тем не менее, узел переменных V₅ не соединен с узлом ограничений C₁, поэтому 0 размещается в пятой позиции первой строки матрицы 202, указывая, что соответствующие узлы переменных и ограничений не соединены. Мы говорим, что ограничения являются линейно независимыми, если строки H 202 являются линейно независимыми векторами по GF[2], где GF[2] - это двоичное поле Галуа.

В случае матричного представления кодовое слово X, которое должно быть передано, может быть представлено как вектор 204, который включает в себя биты X₁-X_n кодового слова, которое должно быть обработано. Последовательность битов X₁-X_n - это кодовое слово, тогда и только тогда произведение матрицы 202 и матрицы 204 равно нулю, т.е.: Hx=0.

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

Чтобы создать кодер для общего LDPC-кода, первый этап заключается в том, чтобы найти перестановку строк и столбцов H таким образом, чтобы вплоть до переупорядочивания мы могли разделить матрицу H mxn на следующие подматрицы:

где T - это верхняя треугольная подматрица txt, т.е. все элементы ниже главной диагонали равны нулю, E - это подматрица gxt, A - это txg, C - это gxg, B - это tx(n-m), D - это gx(n-m) и t+g=m. Более того, матрица gxg ф:= ET^-1 A + C является обратимой (здесь мы предполагаем, что H - это полный строчный ранг).

Затем кодирование продолжается следующим образом. Чтобы закодировать кодовое слово с учетом информационных битов x^S, мы сначала решаем

для y с помощью обратной подстановки. Далее мы решаем

для . Для этого шага матрица ф^-1 заранее вычисляется. Наконец, решаем

для с помощью обратной подстановки. Вектор составляет кодовое слово.

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

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

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

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

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

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

Максимальный поддерживаемый размер кодового слова может быть KxNxL битов, при этом кодовые слова различного размера включают в себя целые кратные числа от (NxL) битов вплоть до максимум K кратных чисел, где K, N и L - это положительные целые числа.

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

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

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

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

В соответствии с настоящим изобретением процедура LDPC-кодирования может, и в различных вариантах осуществления раскладывается, поскольку упорядоченная последовательность операций матричного сложения и умножения может быть переведена в последовательность команд. Для удобства описания мы обозначаем эту последовательность команд кодирования для примерного графа G как микрокод кодирования G. Фактическое кодирование в таком случае осуществляется посредством последовательного исполнения микрокода G с помощью кодера настоящего изобретения, который выполняет различные операции в соответствии с микрокодом в физическом запоминающем устройстве, куда предварительно загружаются информационные биты, к примеру биты, которые должны быть закодированы. Каждая команда содержит оператор op и индикатор ячейки запоминающего устройства. В зависимости от оператора op логика управления кодером либо считывает позицию бита в запоминающем устройстве, определяемую посредством индикатора ячейки запоминающего устройства, и суммирует ее в регистр, либо записывает значение регистра в ячейку a и сбрасывает значение регистра до нуля. Размер микрокода, т.е. число команд в его рамках, по меньшей мере, равен числу ребер в графе G; зачастую они могут примерно совпадать.

Рассмотрим расширенный LDPC-граф с коэффициентом расширения Z. При условии небольшой проекции графа, которая должна быть использована для того, чтобы сформировать больший граф, к примеру проекцию графа, мы можем сформировать в Z раз больший LDPC-граф посредством замены каждого элемента H матрицей ZxZ. Элементы 0 в H заменяются нулевой матрицей, обозначаемой 0. Элементы 1 в H заменяются матрицей из Ψ. Таким образом, мы "расширяем" LDPC-граф графом, в Z раз большим. Сложность представления содержит примерно число битов, требуемых для того, чтобы задать матрицы перестановки, |E_H| log |Ψ|, плюс сложность, требуемая для того, чтобы представить H, где |E_H| обозначает число единиц (1) в H, а |Ψ| обозначает число отдельных перестановок в Ψ. К примеру, если Ψ - это пространство циклических перестановок, то |Ψ|=Z. На практике мы можем иметь, к примеру, Z=16 для n ~1000, где n - это длина блока кодового слова. Пример расширения небольшой матрицы с контролем по четности H показан ниже, где каждый элемент в H, который является единицей, заменяется на проекцию графа, чтобы получить большую проекцию матрицы H, показанную справа.

В матрице H σ_i = 1, …, 16 - это элементы (матрицы) Ψ, показанные здесь, проиндексированные со стороны узлов переменных.

Напомним, что вектор x - это кодовое слово, тогда и только тогда Hx=0. В представлении расширенной матрицы x может трактоваться как вектор элементов в GF(2^{^}Z) вместо вектора двоичного элемента, где GF(2^{^}Z) - это поле Галуа из элементов 2^{^}Z. В этом отношении процесс кодирования как матрично-векторное умножение и векторное сложение, изложенный в разделе уровня техники, может быть смоделирован: каждый ненулевой элемент 1 в матрицы проекции графа заменяется ее соответствующей матрицей перестановки ZxZ; каждый бит в векторе заменяется Z-битным вектором.

Процедура кодирования LDPC-графа с помощью G как проекции графа может быть в значительной степени задана как расширение вышеуказанного процесса кодирования для проекции графа. Это осуществляется посредством замены операций с битами в исходном алгоритме на операции с битовыми векторами в расширенном алгоритме. В одной или более точек обработки кодирования после считывания из запоминающего устройства Z битовых векторов подвергаются операции перестановки, к примеру операции переупорядочивания. Операцией переупорядочивания может быть операция отражения, или для кратности "отражение". Эти операции отражения, в общем, соответствуют отражениям, ассоциативно связанным с ребрами векторов, которые соединяют Z копий проекции графа, чтобы сформировать один крупный граф. Следовательно, в расширенном микрокоде каждая операция содержит оператор op, число отражения r и индикатор ячейки запоминающего устройства.

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

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

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

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

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

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

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

Более того, в соответствии с настоящим изобретением векторный LDPC-кодер с параллелизмом реализации, равным N, допускает формирование, к примеру, кодирование данных, чтобы создать кодовые слова, соответствующие классу LDPC-кодов, с одинаковой скоростью, но различными размерами блоков, из того же микрокода, описывающего расширенный граф с коэффициентом расширения Z. Конкретно, в качестве примера предположим, что если Z может быть разложено на K_lxK₂xN и проекция графа имеет n узлов переменных, то новый кодер может формировать три различных кода различных размеров кодового слова Nxn, K₂xNxn и K₁xK₂xNxn.

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

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

Фиг.1 иллюстрирует представление двудольного графа примерного регулярного LDPC-кода с длиной, равной десяти.

Фиг.2 - это матричное представление кода, графически проиллюстрированного на фиг.1.

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

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

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

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

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

Фиг.3 иллюстрирует примерный LDPC-кодер 300, реализованный в соответствии с настоящим изобретением. Кодер включает в себя модуль 302 запоминающего устройства, управляющий модуль 312, модуль 310 выбора блоков на основе расширения кода, N-элементный управляемый перестановщик 304, модуль 306 N-элементного векторного вектора и управляемое устройство 308 хранения, которые соединены так, как показано на фиг.3. Отметим, что термины перестановщик и пермутатор используются взаимозаменяемо в данной заявке, чтобы ссылаться на одно и то же. Различные элементы LDPC-кодера 300 и их функция подробнее описываются ниже.

Как описано выше, кодер 300 по настоящему изобретению может поддерживать различные коды с помощью различных описаний кода и с помощью различных значений длины кода, как указано посредством различных коэффициентов расширения, для одного описания кода. Модуль 302 запоминающего устройства включает в себя набор из KxNxL ячеек (318, 320, 322) запоминающего устройства, где KxNxL - это максимальный поддерживаемый размер кодового слова. Вход 301 позволяет данным, которые должны быть закодированы, быть записанным в упомянутое запоминающее устройство. Выход 303 позволяет кодовому слову, сохраненному в запоминающем устройстве 314, быть считанным после того, как кодирование выполнено. Модуль 302 запоминающего устройства также включает в себя набор из KxNx1 ячеек (319, 321, 323) запоминающего устройства, используемых для того, чтобы сохранять временные значения. Другие варианты осуществления могут не требовать и могут не использовать временные сохраненные значения. Кодовые слова меньших размеров также могут поддерживаться с помощью запоминающего устройства 314. Ячейки в запоминающем устройстве 314 скомпонованы в K NxL блоков, используемых для того, чтобы сохранять значения кодового слова Blk 1 318, Blk 2 230, Blk K 322, и K Nx1 блоков, используемых для того, чтобы сохранять временные значения Blk 1 319, Blk 2 321, Blk K 323. Каждая из KxNxL ячеек запоминающего устройства обычно составляет 1 бит. Каждая из KxNx1 ячеек запоминающего устройства также обычно составляет 1 бит. Считывание из и запись в ячейки запоминающего устройства 314 управляется посредством логики 316 адресов запоминающего устройства, которая формирует сигнал 324 доступа к запоминающему устройству (адрес и сигнал считывания и записи) в ответ на различные входы, формируемые другими компонентами запоминающего устройства. N битов обычно считываются и записываются в модуль 314 запоминающего устройства за раз. Шина 340 шириной в N битов связывает выход считывания шириной в N битов модуля 302 запоминающего устройства с входом шириной в N битов N-элементного управляемого перестановщика 304, который может переупорядочивать биты перед их предоставлением в N-элементный векторный накопитель 306 посредством шины 342 шириной в N битов. N-элементный управляемый перестановщик 304 принимает сигнал 373 управления переупорядочиванием r2, который формируется как функция от сохраненной информации описания кода, к примеру управляющего кода, такого как микрокод. Сигнал 373 r2 управляет тем, какое (если требуется) переупорядочивание битов должно быть выполнено для N битов, получаемых из запоминающего устройства, до предоставления битов в модуль 306 N-элементного векторного накопителя.

Модуль 306 N-элементного векторного накопителя включает в себя N накопительных схем, размещенных параллельно. Каждая из N накопительных схем формирует однобитную двоичную сумму, соответствующую одному из N входных битов из N-элементного управляемого перестановщика 304 и соответствующую одному из N битов, считываемых из контролируемого устройства 308 хранения. Это эффективный способ реализации XOR-операции. Таким образом, каждая накопительная схема выполняет XOR-операцию. Таким образом, N-элементный векторный накопитель 306 параллельно формирует N накопленных значений. N значений, формируемых модулем 306 накопителя, предоставляются параллельно посредством шины 344 шириной N битов в управляемое устройство 308 хранения. Управляемое устройство 308 хранения включает в себя входной MUX 328, выходной MUX 308 и набор из K N-битных регистров 326. Входной MUX 328 управляется сигналом 360 управления выбором блоков, чтобы определить, в какой из K N-битных регистров 332, 334, 336 записывается N-битный блок, когда сигнал 350 считывания и записи указывает, что выход из модуля накопителя векторов должен быть сохранен в управляемом устройстве 308 хранения. Выходной MUX 330 соединяется с шиной 346 шириной в N битов и выводит N-битный блок, указанный сигналом 360 управления выбором блоков, когда сигнал 350 управления считыванием и записью указывает, что операция считывания должна быть выполнена. Каждый набор из N битов, считанных из управляемого устройства 308 хранения, предоставляется в модуль 302 запоминающего устройства и во второй вход модуля 306 N-элементного векторного накопителя. N битов записываются в запоминающее устройство в конце последовательности операций накопителя, к примеру, как определено посредством сохраненного описания кода.

Управляющий модуль 312 отвечает за формирование множества сигналов управления как функции от конкретного описания кода, к примеру кода управления как микрокода, сохраненного в модуле 372 информации описания кодера, выбранном для того, чтобы быть использованным в конкретный момент времени. В программируемых вариантах осуществления информация описания кода может быть загружена в модуль 372 сохраненной информации описания кодера, к примеру, из оперативной памяти устройств посредством входа 371. В вариантах осуществления, где одно описание кода предварительно загружается и используется, к примеру, для кодовых слов различной длины, соответствующих одной структуре коде, вход 371 может быть опущен. Формирование сигналов, создаваемых посредством модуля 372 информации описания кода, задается посредством сигнала 375 управления, формируемого счетчиком 374 внешних циклов. Счетчик 374 внешних циклов управляется посредством сигнала 377 управления внутренними циклами, формируемого счетчиком 370 внутренних циклов. Счетчик 370 внутренних циклов формирует второй сигнал 356 управления модулем выбора и сигнал 377 управления внутренними циклами как функцию от сигнала управления коэффициентом расширения кода SK 348, который предоставляется в счетчик 370 внутренних циклов в качестве контрольного значения. Сигнал управления коэффициентом расширения кода может быть использован для того, чтобы задавать длину кодового слова, которое должно быть сформировано, и может допускать значения от 1 до K, где K означает общее число NxL-битных блоков в запоминающем устройстве 314. Таким образом, посредством использования различных коэффициентов расширения кода кодовые слова различных размеров могут быть сформированы, где каждый из различных поддерживаемых размеров кодовых слов является целым числом, кратным NxL. В случаях, когда SK<K, один или более блоков в запоминающем устройстве 314 и один или более регистров в наборе регистров 326 обычно остается неиспользованным.

Модуль 372 сохраненной информации описания кодера включает в себя код управления, к примеру микрокод. Этот код, когда исполняется в ответ на сигнал 375 управления внешними циклами, формирует сигнал 350 считывания и записи, задаваемый посредством значения op, включенного в исполняемую строку микрокода. Сигнал 350 предоставляется в модуль 302 запоминающего устройства и управляемое устройство 308 хранения. Модуль 372 сохраненной информации описания кодера также формирует сигнал 352 управления адресами запоминающего устройства, который предоставляется в модуль 302 запоминающего устройства, когда операция считывания и записи должна быть выполнена, первый сигнал 354 управления модулем выбора r1, который предоставляется в модуль 310 выбора блоков на основе расширения кода, и сигнал 373 управления переупорядочиванием r2, который предоставляется в управляемый перестановщик 304, чтобы управлять переупорядочиванием значений, считываемых из модуля 302 запоминающего устройства.

Модуль 310 выбора блоков на основе расширения кода принимает первый сигнал 354 управления модулем выбора r1 из модуля 372 сохраненной информации описания кодера и второй сигнал 356 управления модулем выбора, формируемый посредством счетчика 370 внутренних циклов. Модуль 310 выбора блоков на основе расширения кода формирует сигнал 358 выбора адресов блоков, который предоставляется в логику 316 адресов запоминающего устройства, чтобы указывать конкретный блок запоминающего устройства 314, доступ к которому должен быть осуществлен в конкретный момент времени. Модуль 310 выбора блоков на основе расширения кода также формирует сигнал 360 управления выбором блоков, который используется для того, чтобы управлять тем, к какому блоку информации, к примеру к каким битам регистров 332, 334, 336, должен осуществляться доступ в управляемом устройстве 308 хранения в конкретный момент времени.

Различные компоненты кодера 300 управляются посредством общего тактового сигнала, с тем чтобы различные операции и увеличение счетчиков 370, 374 осуществлялись синхронизированно.

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

Чтобы получить высокий уровень устойчивости к ошибкам, часто используются относительно длинные кодовые слова. Например, одно кодовое слово, сформированное посредством выполнения операции кодирования, может включать в себя общее число битов T, где T может быть несколькими сотнями или даже тысячами битов. Для целей пояснения изобретения следует понимать, что биты, которые должны быть закодированы, могут быть скомпонованы в KxLxN-битные векторы, где N - это положительное целое число, а K - это положительное целое число больше 1. Каждый N-битный вектор может считываться из запоминающего устройства. Вектор, считанный из запоминающего устройства, затем может быть обработан посредством использования N блоков обработки параллельно. В отличие от существующих систем, которые используют параллелизм реализации N, равный Z, в кодере, который кодирует кодовые слова с помощью конкретного расширенного LDPC-кода с коэффициентом расширения Z, настоящее изобретение дает возможность уровню параллелизма в кодере быть отличным от общего поддерживаемого коэффициента расширения Z. Более конкретно, Z=KxN, где K - это целое число больше 1. Таким образом, в соответствии с настоящим изобретением в различных реализациях уровень параллелизма N меньше коэффициента расширения Z. Более того, в некоторых вариантах осуществления кодовые слова различного размера могут быть сформированы с помощью одного набора информации описания кода. Посредством задания контрольного значения коэффициента расширения кода SK, которое меньше K, максимального контрольного значения коэффициента расширения кода, кодовые слова меньше максимального размера кодового слова для данной реализации (LxKxN) могут создаваться. Различные размеры кодовых слов являются числами, кратными NxL битам.

Заявка на патент США серийный номер 10/788115, озаглавленная "METHOD AND APPARATUS FOR PERFORMING LOW-DENSITY PARITY-CHECK (LDPC) CODE OPERATIONS USING A MULTI-LEVEL PERMUTATION", зарегистрированная 2/26/2004, и соответствующая PCT-заявка PCT/US 2004/005783, которая имеет то же заглавие и дату регистрации, содержатся в данном описании по ссылке. Эти заявки на патент описывают способ расширения посредством произведения LDPC-кодов. Данные расширения посредством произведения ограничивают группу матриц перестановки ZxZ, используемых в расширениях, группами, которые могут быть разложены на прямое произведение подгрупп. Например, мы допускаем, что Ψ - это прямое произведение трех подгрупп, т.е. Ψ=Ψ₁xΨ₂xΨ₃. Размерность Ψ равна произведению размерностей Ψ_i, где Ψ_i - это группа матриц перестановки K_ixK_i. Таким образом, большое расширение может быть реализовано как несколько меньших последовательных расширений. Предполагается, что размерность группы Ψ_i равна размерности матрицы внутри группы, т.е. Z=K₁xK₂xK₃, где K₁, K₂, K₃ - это размерности Ψ₁, Ψ₂, Ψ₃, соответственно.

В соответствии с настоящим изобретением мы ограничиваем группу расширения Ψ, чтобы быть группой, расширенной посредством произведения. Как упоминалось выше, расширение посредством произведения альтернативно может рассматриваться как многомерное расширение. Следовательно, настоящий кодер 300 настоящего изобретения использует расширения, которые могут быть реализованы как многомерные расширения. Допустим, что проекция кода имеет размер P, т.е. с P узлами переменных. Можно выбрать циклическую группу размером 64 для расширения. Альтернативной в соответствии с изобретением должно быть произведение циклической группы размером 16 и циклической группы размером 4 (заметим, что 16×4=64). Эта группа может быть представлена следующим образом. Рассмотрим индексацию L=0, …, 63 с помощью пар (a, b), a=0, …, 15 и b=0, …, 3 посредством обратимого отображения L=4a+b. Элемент этой группы произведения - это пара (c, d), c=0, …, 15 и d=0, …, 3. Действие (c, d) на (a, b) состоит в том, чтобы переставить пару (a, b) с (a+c mod 16, d+b mod 4). Эта группа также имеет поряд