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

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

 

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

Настоящее изобретение направлено на способы и устройство кодирования данных для упрощения обнаружения и исправления ошибок, к примеру, посредством использования кодов контроля по четности, таких как коды с низкой плотностью контроля по четности (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). Эта группа также имеет порядок 64. Результирующий расширенный граф, тем не менее, может интерпретироваться как расширение кода размером 4P на 16 или кода размером 16P на 4, или кода размером P на 64.

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

Заявка на патент США серийный номер 10/788115, озаглавленная "METHOD AND APPARATUS FOR PERFORMING LOW-DENSITY PARITY-CFIECK (LDPC) CODE OPERATIONS USING A MULTI-LEVEL PERMUTATION", описывает графы, расширенные посредством произведения, и потенциальные выгоды использования этих графов.

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

Допустим, что имеем расширенный LDPC-граф с коэффициентом расширения Z=KxN. Группа расширения Ψ должна быть группой, расширенной посредством произведения Ψ=Ψ_lxΨ₂, где K - это размерность группы Ψ₁, а N - это размерность группы Ψ₂. Мы можем сформировать микрокод для расширенного графа с коэффициентом расширения Z, который является последовательностью команд, каждая из которых содержит оператор op, число отражения r и ячейку запоминающего устройства a. Кодер 300, реализованный с помощью параллелизма Z, исполняет каждую команду следующим образом: если op указывает считывание, контроллер считывает Z-битный вектор из запоминающего устройства в ячейке a, переупорядочивает его на величину r и накапливает переупорядоченное значение в Z-битном регистре; если op указывает запись, контроллер записывает значение Z-битного регистра в запоминающее устройство в ячейке a. И кодирование осуществляется посредством исполнения всей последовательности команд.

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

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

Чтобы лучше понять процесс кодирования настоящего изобретения, сначала рассмотрим команду, которую считывает Z-битный вектор из ячейки a и переупорядочивает на величину r, а затем накапливает переупорядоченное значение в Z-битном регистре. Мы записываем исходный вектор данных d=(d₁, d₂, …, d_K), каждый d_j - это N-битный вектор, где j - это целое число, используемое в качестве индексов. С учетом того, что группа расширения - это группа, расширенная посредством произведения Ψ=Ψ₁xΨ₂, где Ψ₁ имеет размерность K, а Ψ₂ имеет размерность N, запишем величину переупорядочивания r=(r₁, r₂), где r₁ - это величина переупорядочивания, к примеру величина циклического отражения в группе Ψ₁, а r₂ - это величина переупорядочивания, к примеру величина циклического отражения в группе Ψ₂. Мы используем обозначение Ψ₁(d, r) для того, чтобы представлять переупорядочивание на величину r над вектором d (из K элементов) в группе Ψ₁, и обозначение Ψ₂ (d, r) для того, чтобы представлять переупорядочивание на величину r над вектором d (из N элементов) в группе Ψ₂. Переупорядочивание также может рассматриваться как перестановка позиции, так чтобы элемент d_j в исходной позиции j переходил в новую позицию, обозначенную как Ψ_l,r(j) в переупорядоченных данных. В таком случае переупорядочивание может трактоваться как 2-стадийная процедура переупорядочивания. Первая стадия переупорядочивает в группе Ψ₂ для N (1-битных) элементов, чтобы сформировать вектор d'=(Ψ₂(d₁,r₂), Ψ₂(d₂,r₂), …, Ψ₂(d_K,r₂)). Затем вторая стадия переупорядочивает в группе Ψ₁ для K (N-битных) элементов, чтобы сформировать вектор d''=Ψ₁(d',r₁). Далее переупорядоченные данные d'' накапливаются в Z-битном регистре. Как описано ниже, в реализации фиг.3 Z-битный регистр реализован как набор из K N-битных регистров 332, 334, 336.

Далее мы описываем то, как разложить вышеупомянутое одноэтапное "считывание-упорядочивание-накопление" с помощью параллелизма Z на K этапов "считывания-упорядочивания-накопления" с помощью параллелизма N, чтобы реализовать LDPC-кодер, например LDPC-кодер 300. Именно эта последовательность из этих K шагов используется кодером 300. Допустим, что мы имеем K регистров 332, 334, 336, и допустим, что Z-битный вектор d в ячейке a физически скомпонован как K N-битных векторов (d₁, d₂, …, d_K), где N-битный вектор d_j сохранен в ячейке a в блоке j. Если на этапе j мы считываем данные d_j, где адрес определяется посредством a и j, и переупорядочиваем считанные данные на величину r₂ в группе Ψ₂, к примеру, с помощью управляемого перестановщика 304 N элементов, мы формируем Ψ₂(d₁, r₂). Затем мы накапливаем переупорядоченные данные в Ψ_1,r1(j)-ом регистре из этих K регистров 332, 334, 336. Это завершает j-ый этап. Проходя через j=1, …, K, мы получаем тот же результат, что и при исполнении команды с помощью операций Z-битного вектора, но достигаем этого результата с меньшим параллелизмом N кодера , где N<Z.

Команда, которая записывает Z-битный регистр в ячейку a и сбрасывает Z-битный регистр, также может быть разложена на K этапов в соответствии с настоящим изобретением, действительно гораздо более простым способом. На этапе j мы записываем j-ый регистр из K N-битных регистров 332, 334, 336 в ячейку, определенную посредством j и ячейкой a, и сбрасываем этот регистр 332, 334 или 336. Проходя через j=1, …, K, мы получаем тот же результат, что и при исполнении команды с помощью операций Z-битного вектора.

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

Со ссылкой на фиг.3 далее мы подробнее опишем примерный кодер 300, используемый для того, чтобы реализовать K-шаговый процесс кодирования, который обеспечивает параллелизм N, когда используется коэффициент расширения Z, где Z>N.

На фиг.300 управляющий модуль 312 управляет числом этапов, исполняющих команду, посредством счетчика 370 внутренних циклов. Счетчик 370 увеличивается на 1 на каждом этапе и сбрасывается при достижении максимального значения, определяемого посредством сигнала 348 управления коэффициентом расширения кода. Каждый раз, когда счетчик 370 внутренних циклов достигает максимума, он инициирует счетчик 374 внешних циклов, увеличивая его на 1. Счетчик 374 внешних циклов определяет текущую исполняемую команду кодирования посредством осуществления доступа к модулю 372 сохраненной информации описания кодера. Модуль 372 сохраненной информации описания кодера выводит команду в форме различных сигналов, сформированных согласно команде, которая должна быть применена в позиции, определенной посредством счетчика 374 внешних циклов. Команда содержит оператор op, число переупорядочивания r и ячейку запоминающего устройства a. Операция op задает сигнал 350 считывания и записи в модуль 302 запоминающего устройства, ячейка запоминающего устройства a определяет сигнал 352 управления адресами запоминающего устройства, связанный с модулем 302 запоминающего устройства, а число переупорядочивания r разделяется на две части (r₁, r₂), каждая из которых задает элемент переупорядочивания в группе Ψ₁ и Ψ₂, соответственно. Сигнал r₁ 354 предоставляется в модуль 310 выбора блоков на основе расширения кода для использования при формировании сигнала 358 выбора адресов блоков, используемого для того, чтобы управлять тем, к какому блоку запоминающего устройства в модуле 302 запоминающего устройства осуществляется доступ, тогда как сигнал r₂ 373 предоставляется в перестановщик 304, чтобы управлять перестановкой N элементов блока, считанного из запоминающего устройства 302.

Чтобы принимать сигнал r₁ 354, модуль 310 выбора блоков на основе расширения кода имеет первый сигнал 354 управления модулем выбора, связанный с частью r₁ числа переупорядочивания r в команде от упомянутого управляющего модуля 312. Задаваемый посредством второго сигнала 356 управления выбором, формируемого счетчиком 370 внутренних циклов управляющего модуля 312, и управляемый посредством сигнала 354 управления r₁ модуль 310 выбора блоков на основе расширения кода выводит сигнал 358 выбора адресов блоков, который допускает значения от 1 до K, и сигнал 360 управления выбором блоков, который допускает значения Ψ_1,r1(1), Ψ_1,r1(2), …, Ψ_1,r1(K).

Модуль 302 запоминающего устройства имеет вход для приема сигнала 350 считывания и записи, связанный с выходом оператора op сохраненной информации описания кодера, и еще один вход для приема сигнала 352 управления адресами запоминающего устройства, который соответствует ячейке запоминающего устройства a, содержащейся в инструкции микрокода, сохраненной в модуле 372, которая исполняется в данный момент времени.

Модуль 302 запоминающего устройства включает в себя запоминающее устройство 314, скомпонованное в Kx(NxL) 1-битных ячеек 318, 320, 322 хранения и Kx(Nx1) 1-битных ячеек 319, 321, 323 хранения. Для удобства мы идентифицируем ячейки хранения с K блоками (NxL) 1-битных ячеек как блок 1, …, K, используемый для хранения кодового слова, и идентифицируем ячейки хранения с K блоками (Nx1) 1-битных ячеек хранения как блок 1, …, K, используемый для временного хранения значений. Доступ к запоминающему устройству 314 осуществляется в ячейке, которая является функцией от сигнала управления адресами запоминающего устройства a 352 и сигнала выбора адресов блоков k 358. Модуль 316 логики адресов запоминающего устройства реализует эту функцию. При заданном (a, k) модуль 302 запоминающего устройства считывает или записывает N-битный вектор в ячейку a k-ого блока в зависимости от того, указывает сигнал 350 считывания и записи, что должна быть выполнена операция считывания или записи.

Считывание модуля 302 запоминающего устройства выводит N-битный вектор 340, считанный из запоминающего устройства 314. Этот N-битный вектор предоставляется в модуль 304 N-элементного управляемого перестановщика. Модуль 304 реализует переупорядочивание в группе Ψ₂; его сигнал управления переупорядочиванием связан с выходом сигнала r₂ из модуля 372 сохраненной информации описания кодера. Число переупорядочивания r, из которого извлекается сигнал r₂, используемый в данный момент времени, получается из команды микрокода из модуля 372 информации, которая исполняется в данный момент времени.

Выход переупорядоченного N-битного вектора модуля 304 перестановщика объединяется с первым входом 342 N-битного вектора модуля 306 N-элементного векторного накопителя. Второй вход 346 N-битного вектора модуля 306 накопителя предоставляется из модуля 308 управляемого устройства хранения, который включает в себя K N-битных регистров 332, 334, 336. Модуль 306 накопителя векторов формирует выход N-битного вектора как XOR-сумму двух входов N-битного вектора. В различных вариантах осуществления модуль 306 накопителя векторов реализуется с помощью N XOR-схем, размещенных параллельно, причем каждая XOR-схема объединена с различным сумматором для суммирования результата XOR-операции с самым последним сформированным XOR-результатом, созданным посредством конкретной одной из N XOR-схем. Выход шириной N битов модуля накопителя объединяется с входом 344 модуля 308 управляемого устройства хранения.

Модуль 308 управляемого устройства хранения включает в себя K регистров, причем каждый регистр сохраняет N битов. Сигнал 360 управления выбором блока, связанный с модулем 310 выбора блоков на основе расширения кода, определяет, к какому из K регистров должен быть осуществлен доступ в данный момент времени. Сигнал 350 управления считыванием и записью, связанный с оператором op, содержащимся в команде от управляющего модуля 312, определяет режим осуществления доступа, к примеру режим считывания или записи. Допустим, что сигнал 360 управления выбором блоков сообщает j. Если сигнал управления - это считывание, то N-битный выходной вектор из управляемого устройства 308 хранения берет значение j-ого регистра, и накопленное значение из модуля 306 N-элементного векторного накопителя записывается в j-ый регистр. Другими словами, переупорядоченное значение из N-элементного управляемого перестановщика 304 накапливается в j-ом регистре, указанном посредством сигнала 360 управления выбором блоков. Если сигнал 350 управления считыванием и записью - это запись, то выходной вектор также принимает значение j-ого регистра, и мы сбрасываем j-ый регистр до нуля.

Обобщая, с учетом микрокода для расширенного графа с коэффициентом расширения Z=KxN, различные варианты осуществления настоящего изобретения направлены на кодер, который выполняет операции с N-битными векторами. Каждая операция N-битного вектора влечет за собой исполнение команды в микрокоде, которая описывает структуру кода, которая должна быть использована для кодирования. Чтобы реализовать кодирование кодового слова, включающего в себя Z битов, каждая N-битная команда реализуется в K этапов в последовательности, управляемой посредством части сохраненной информации команд микрокода и одного или более счетчиков.

В различных вариантах осуществления настоящего изобретения предлагаемый кодер может формировать различные коды, которые совместно используют ту же скорость, что и проекции графа, но имеют другую длину кодового слова. Это достигается посредством использования SK, выбранного контрольного значения коэффициента расширения, которое является делителем K, вместо самого K, в качестве числа этапов, исполняемых для каждой команды. Более конкретно, группа Ψ₁ в расширении посредством произведения по-прежнему может быть прямым произведением двух групп Ψ₁=Ψ₁₁xΨ₁₂, и SK - это размерность матрицы Ψ₁₂, а J - это размерность Ψ₁₁, таким образом, K=JxSK. В качестве частного случая Ψ₁₁ может быть группой из одного элемента 1, а Ψ₁₂ - это Ψ₁, так что SK=K и J=1. В любом случае, в расширенном графе, если мы игнорируем компонент Ψ₁₁ внутри группы расширения, то мы имеем расширенный граф с коэффициентом расширения Z/J=SKxN. Другой способ нахождения этого заключается в том, что мы берем исходный граф и проецируем его на группу расширения Ψ₁₁, таким образом, в матрице контроля по четности каждая ненулевая запись, которая указывает матрицу перестановки ZxZ, теперь проецируется на матрицу перестановки Z/JxZ/J. По сути, та же последовательность процесса кодирования, что и матричное умножение в большем графе, по-прежнему выполняется для проекции графа, даже для обращения матрицы ф^-1, посредством основного принципа теории групп.

Таким образом, микрокод, описывающий больший граф с коэффициентом расширения Z, также является микрокодом, описывающим проекцию графа с коэффициентом расширения Z/J=SKxN. Посредством той цепочки рассуждений, что и представленная выше в отношении случая для Z, мы можем использовать тот же кодер с операцией N-битного вектора, чтобы кодировать код с коэффициентом расширения SKxN посредством исполнения каждой команды в рамках микрокода в SK этапах в последовательности, управляемой посредством части информации команд, сохраненной в модуле 372 сохраненной информации описания кодера.

Другие коды другой длины блока, совместно использующие один микрокод, существуют, если Ψ₁ по-прежнему может быть записана как прямое произведение двух других групп Ψ₁=Ψ₁₁'xΨ₁₂', что имеет место в различных реализациях настоящего изобретения. Тот же кодер, в соответствии с настоящим изобретением, с параллелизмом N может кодировать этот код с коэффициентом расширения Z/J', где J' - это размерность Ψ₁₁', посредством задания соответствующего SK. Более того, дополнительная структура в Ψ₁ может приводить к большему числу кодов других длин блоков, кодируемых на тех же аппаратных средствах кодера. Следовательно, посредством управления SK согласно структуре группы кодер может формировать класс LDPC-кодов с различной длиной блоков.

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

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

Таблица 1, которая приведена ниже, содержит сочетание перечней инструкций примерного управляющего кода в таблицах 1A и 1B, к примеру, микрокода, соответствующего структуре кода, имеющей максимальный коэффициент расширения Z=64. В примере код разработан для случая, где N=16, K=4 и L=10. Z=KxN и, таким образом, Z=64=4×16. Максимальная поддерживаемая длина кодового слова составляет KxNxL, что равно 640 в данном примере. Проекция графа, описываемая посредством кода, имеет 4 проверочных узла и 10 узлов переменных. Когда происходит расширение посредством максимального коэффициента расширения Z, это приводит к структуре кода, имеющей 256 (64×4) проверочных узлов и 640 (64×10) узлов переменных. Аппаратные средства предназначены для работы с уровнем параллелизма N, где N=16. Сигнал управления коэффициентом расширения SK, используемый для того, чтобы задавать длину кодового слова, в этом варианте осуществления может быть любым делителем K, где K, как указано выше, - это 4(K=Z/N=64/16), т.е. максимальное поддерживаемое контрольное значение коэффициента расширения. Таким образом, посредством выбора различных сигналов управления коэффициентом расширения, чтобы управлять числом повторов микрокода по таблице 1, можно закодировать кодовые слова, соответствующие 3 различным значениям длины, к примеру когда SK=1, длина кодового слова равна (1×16×10) 160 битов, когда SK=2, длина кодового слова равна (2×16×10) 320 битов, а когда SK=K=4, длина кодового слова равна (4×16×10) 640 битам. В микрокоде, показанном в таблице 1, в столбце op 1 используется, чтобы указывать считывание, тогда как 0 используется, чтобы указывать инструкцию записи. Контрольные значения r1 и r2 сохранены в значении r. r1 определяется из значения r как целый делитель r, когда поделено на N. Т.е. r1=r div N. r2 определяется из значения r посредством взятия модуля r/N. В этом примере N=16. Рассмотрим, например, первую инструкцию 1 43 4. Эта инструкция должна быть интерпретирована как инструкция считывания (op=1), r1= (r div N)=(43 div 16)=2, тогда как r2=(r mod N)=(43 mod 16)=11. Контрольное значение a предоставляется непосредственно из таблицы и, в случае первой инструкции, равно 4. Когда контрольное значение находится в рамках диапазона 0…L-1, к примеру 0…9 для примерного микрокода, запоминающее устройство, к которому осуществляется доступ, используется для хранения кодовых слов, к примеру осуществляется доступ к одному из K блоков 318, 320, 322. Когда контрольное значение a вне диапазона 0…L-1, к примеру 10 для примерного микрокода, запоминающее устройство, к которому осуществляется доступ, используется для временного хранения значений, к примеру осуществляется доступ к одному из K блоков 319, 321, 323.

(Начало)
Op	r	a
1	43	4
1	5	5
1	6	7
1	44	8
1	36	3
0	0	2
1	10	4
1	30	5
1	47	6
1	9	7
1	17	3
0	0	1
1	25	5
1	32	6
1	58	8
1	45	9
1	16	2
0	0	0
1	42	4
1	17	8
1	62	9
1	6	0
1	38	1
0	0	10
1	17	10
1	19	10
1	21	10
1	29	10
1	31	10
Таблица 1A
(Продолжение)
Op	r	A
1	49	10
1	50	10
1	51	10
1	52	10
1	53	10
1	54	10
1	55	10
1	56	10
1	58	10
1	63	10
0	0	3
1	43	4
1	5	5
1	6	7
1	44	8
1	36	3
0	0	2
1	10	4
1	30	5
1	47	6
1	9	7
1	17	3
0	0	1
1	25	5
1	32	6
1	58	8
1	45	9
1	16	2
0	0	0
Таблица 1B

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

Фиг.4 - это чертеж примерного беспроводного терминала (WT) 1000, к примеру мобильного узла, реализованного в соответствии с устройством кодера и декодера LDPC, которое использует способы настоящего изобретения. Примерный WT 1000 включает в себя приемное устройство 1002, антенну 1004 приемного устройства, программируемый LDPC-декодер 1006, передающее устройство 1008, антенну 1010 передающего устройства, программируемый LDPC-кодер 1012, процессор 1014, устройства 1015 пользовательского ввода-вывода и запоминающее устройство 1016. Программируемый LDPC-декодер 1006, программируемый LDPC-кодер 1012 (который может быть реализован с помощью кодера 300 по фиг.3), процессор 1014, устройства 1015 пользовательского ввода-вывода и запоминающее устройство 1016 соединяются посредством шины 1018, по которой различные элементы могут обмениваться данными и информацией.

Приемное устройство 1002 подключено к антенне 1004 приемного устройства, через которую WT 1000 может принимать сигналы от других устройств, к примеру кодированные сигналы нисходящей линии связи от базовой станции. Приемное устройство 1002 также соединено с программируемым LDPC-декодером 1006, который может декодировать принимаемые сигналы нисходящей линии связи в соответствии с изобретением. Принимаемые сигналы могут включать в себя, к примеру, помимо LDPC-кодированных данных, сигналы, к примеру управляющую информацию, используемую для того, чтобы указывать структуру кода LDPC, используемую для того, чтобы кодировать данные, которые принимаются, или длину кодовых слов, включенных в принимаемую информацию. Принимаемые данные могут включать в себя кодовые слова, соответствующие различным приложениям. В соответствии с изобретением декодер может переключаться от декодирования данных, соответствующих первой структуре кода и длине кодового слова, к декодированию данных, соответствующих второй структуре кода и второй длине кодового слова. Первая и вторая структура кодового слова может быть различной с декодером, загружаемым с соответствующей информацией о структуре кода, к примеру контрольного кода в форме микрокода, в ответ на информацию, включенную в принимаемую информацию. Управляющая информация обычно не кодируется с помощью LDPC-кодов, чтобы упростить быстрое обнаружение и интерпретацию управляющей информации. Первая и вторая длина кодового слова также может отличаться. В некоторых случаях первая и вторая структура кода одинакова, но длина кодового слова данных, соответствующих различным приложениям, может отличаться. В этом случае информация структуры кода не обязательно должна обновляться, чтобы декодировать кодовые слова различного размера, и просто информация о длине кодового слова, к примеру информация коэффициента расширения, должна предоставляться в декодер в качестве длины кодового слова принимаемых изменений данных. Информация о длине кодового слова может быть задана как коэффициент расширения кода для используемой структуры кода. Как описано ниже, информация о структуре кода, к примеру управляющего кода, может быть использована для того, чтобы управлять программируемым LDPC-декодером, тогда как информация о длине кодового слова может быть использована для того, чтобы задавать длину кодового слова для целей декодирования. Эта информация может передаваться в декодер 1006 из запоминающего устройства 1016 посредством шины 1018.

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

Информация о структуре кода или информация о длине кодового слова может быть передана из запоминающего устройства 1016 в программируемый LDPC-кодер 1012 по шине 1018. Устройства 1015 пользовательского ввода-вывода, к примеру клавишные панели, громкоговорители, микрофоны, дисплеи и т.д., предоставляют интерфейсы для пользователя, чтобы вводить данные и информацию, к примеру данные и информацию, которая должна быть закодирована и передана в другой WT, и для пользователя, чтобы выводить и отображать принимаемые данные и информацию, к примеру принимаемые данные и информацию от равноправного узла, который декодирован. Устройства 1015 пользовательского ввода-вывода предоставляют интерфейс, позволяющий пользователю выбирать или задавать код, ассоциативно связанный с набором данных, индикатором длины кода или наборами информации описания кода, которая должна быть использована посредством программируемого LDPC-декодера 1006 или программируемого LDPC-кодера 1012.

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

Запоминающее устройство 1016 включает в себя группу 1025 наборов 1026, 1028 информации описания кода кодера и группу 1029 наборов 1030, 1032 информации описания кода декодера. Каждый набор 1026, 1028 информации описания кода кодера включает в себя управляющие коды, к примеру микрокод, который отражает структуру кода, которая должна быть использована для кодирования данных. Каждый набор 1026, 1028 информации соответствует различной структуре кода. Информация описания кода кодера может быть загружена в модуль управления программируемого LDPC-кодера 1012 и использована, к примеру, в качестве сохраненной информации описания кодера, чтобы управлять кодированием данных. Аналогично, каждый из наборов 1030, 1032 информации описания кода декодера включает в себя управляющие коды, к примеру микрокод, который отражает структуру кода, которая должна быть использована для декодирования данных. Каждый набор 1030, 1032 информации описания кода декодера соответствует различной структуре кода. Информация описания кода декодера может быть загружена в модуль управления программируемого LDPC-декодера 1006 и использована, к примеру, в качестве сохраненной информации описания декодера, чтобы управлять декодированием данных.

Запоминающее устройство 1016 включает в себя процедуры 1020 связи, процедуру 1022 выбора длины кодового слова и кода кодера и процедуру 1024 выбора длины кодового слова и кода декодера. Процедуры 1020 связи могут управлять общей связью и взаимодействием с другими беспроводными устройствами. Процедура связи, реализованная для данного приложения, может задавать структуру кода и длину кодового слова, которая должна быть использована для конкретного приложения связи при кодировании и декодировании данных с помощью LDPC-кодов. Процедура 1022 выбора кодового слова и кода кодера отвечает за выбор структуры кода и, следовательно, соответствующей информации 1026, 1028 описания кода кодера, которая должна быть использована для конкретного приложения. Этот выбор может выполняться на основе информации, принимаемой от процедуры 1020 связи, информации, принимаемой посредством приемного устройства 1002, или от пользовательского ввода. Процедура 1022 выбора длины кодового слова и кода кодера отвечает за загрузку в программируемый LDPC-кодер 1012 выбранной информации описания кода и за предоставление информации, к примеру выбранного коэффициента расширения кода, в программируемый кодер 1012, если он еще не сконфигурирован для того, чтобы выполнять кодирование в соответствии с выбранным кодом и длиной кодового слова. Процедура 1024 выбора длины кодового слова и кода декодера отвечает за загрузку в программируемый LDPC-декодер 1006 выбранной информации описания кода и за предоставление информации, к примеру выбранного коэффициента расширения кода, в программируемый декодер 1006, если он еще не сконфигурирован для того, чтобы выполнять декодирование в соответствии с выбранным кодом и длиной кодового слова.

Помимо вышеописанных процедур и информации, связанной с кодированием и декодированием, запоминающее устройство 1016 может быть использовано для того, чтобы сохранять принимаемую информацию 1038 декодера, к примеру принимаемую информацию, используемую процедурой 1024 выбора длины кодового слова и кода декодера, которая указывает структуру кода и длину кодового слова, которая должна быть использована для декодирования. Помимо этого, принимаемая информация 1044 кодера, к примеру принимаемая информация, используемая процедурой 1022 выбора длины кодового слова и кода кодера, которая указывает структуру кода и длину кодового слова, которая должна быть использована для кодирования, может быть сохранена в запоминающем устройстве 1016. Информация 1036 пользовательского ввода, связанная с декодированием, и информация пользовательского ввода, связанная с кодированием 1042, также может быть сохранена в запоминающем устройстве 1016. Эта информация может быть такой же или аналогичной информации 1038 декодера и информации 1044 кодера, но получается от пользователя посредством устройства 1015 пользовательского ввода-вывода, а не посредством приемного устройства 1002.

Подробное описание примерного программируемого LDPC-декодера, который может (и в некоторых вариантах осуществления используется) использоваться в качестве программируемого LDPC-декодера 1006, см. в Патентной заявке (США) серийный номер 10/895645, озаглавленной "LDPC DECODING METHODS AND APPARATUS", зарегистрированной 21 июля 2005 года, которая заявляет в качестве авторов изобретения Tom Richardson, Hui Jin и Vladimir Novichkov и которая явно содержится в данном документе по ссылке. Кроме того, явно содержится по ссылке для предоставления исходной информации Патент (США) номер 6633856.

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

Различные понятия, связанные со структурами LDPC-кодов, на которых базируется настоящее изобретение, описаны и пояснены в Патентной заявке (США), серийный номер 10/618325, озаглавленной "METHODS AND APPARATUS FOR ENCODING LDPC CODES", зарегистрированной 11 июля 2003 года, которая явно содержится в данном документе по ссылке. Лучшее понимание методик и преимуществ способов и устройства настоящего изобретения может быть получено при рассмотрении в свете описания, находящегося во вложенной Патентной заявке.

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

На этапе 1104 WT 1000 функционирует так, чтобы принимать информацию кодирования и декодирования и формировать управляющую информацию из принимаемых данных. Информация кодирования и декодирования, к примеру управляющая информация для программируемого LDPC-кодера 1012 и программируемого LDPC-декодера, может приниматься посредством принимаемого сигнала, обрабатываемого приемным устройством 1002, или как пользовательский ввод, принимаемый устройством 1015 пользовательского ввода-вывода. Помимо этого, принимаемые кодированные данные могут обрабатываться, чтобы формировать управляющую информацию. Например, несколько попыток при декодировании может быть выполнено с помощью различной информации структуры коды или различной длины кодового слова. После успешного декодирования в некоторых вариантах осуществления формируется управляющая информация, указывающая структуру кода и длину кодового слова, которая должна быть использована для того, чтобы декодировать входящие данные и, в некоторых вариантах осуществления, также кодировать выходящие данные. Процесс переходит от этапа 1104 посредством соединяющего узла A 1110 к этапу 1112. На этапе 1112 WT 1000 функционирует так, чтобы определять тип принимаемой управляющей информации кодирования/декодирования. На основе определения на этапе 1112 процесс переходит к этапу 1114, 1116, 1118 или 1120.

Если на этапе 1112 определено, что тип управляющей информации - это информация о структуре кода кодера, то процесс переходит к этапу 1114. На этапе 1114 WT 1000 функционирует так, чтобы загрузить в кодер 1012 набор информации описания кода, к примеру управляющий код, соответствующий информации о структуре кода, указанной посредством управляющей информации. Процесс переходит от этапа 1114 к соединяющему узлу B 1122.

Если на этапе 1112 определено, что тип управляющей информации - это информация о длине кодового слова кодера, то процесс переходит к этапу 1116. На этапе 1116 WT 1000 работает так, чтобы предоставить в кодер 1012 индикатор длины кодового слова, к примеру выбранный коэффициент расширения, соответствующий длине кода, указанной посредством управляющей информации. Процесс переходит от этапа 1116 к соединяющему узлу B 1122.

Если на этапе 1112 определено, что тип управляющей информации - это информация о структуре кода декодера, то процесс переходит к этапу 1118. На этапе 1118 WT 1000 функционирует так, чтобы загрузить в декодер 1006 набор информации описания кода, к примеру управляющий код, соответствующий структуре кода, указанной посредством управляющей информации. Процесс переходит от этапа 1118 к соединяющему узлу B 1122.

Если на этапе 1112 определено, что тип управляющей информации - это информация о длине кодового слова декодера, то процесс переходит к этапу 1120. На этапе 1120 WT 1000 функционирует так, чтобы предоставить в декодер 1006 индикатор длины кодового слова, к примеру выбранный коэффициент расширения, соответствующий тому, чтобы указать длину кодового слова. Процесс переходит от этапа 1120 к соединяющему узлу B 1122.

От соединяющего узла B 1122 процесс возвращается к этапу 1104, где WT 1104 ждет, чтобы принять другую информацию кодирования/декодирования, к примеру информацию, чтобы завершить конфигурирование программируемого декодера 1006 или программируемого кодера 1012, или информацию, чтобы изменить выбранные настройки, к примеру настройки длины кодового слова декодера 1006 или кодера 1012.

На этапе 1106 WT 1000, включающий в себя ранее сконфигурированный программируемый декодер 1006, функционирует так, чтобы принимать посредством приемного устройства 1002 данные, которые должны быть закодированы, к примеру закодированные пользовательские данные от равноправного узла WT 1000. Принимаемые данные перенаправляются в декодер 1006. Процесс переходит от этапа 1106 к этапу 1124. На этапе 1124 декодер 1006 функционирует так, чтобы декодировать данные согласно сохраненной информации описания кода в декодере 1006 и информации индикатора длины кодового слова, которая предоставлена в декодер. Процесс переходит от этапа 1124 к этапу 1106, где принимаются дополнительные данные, которые должны быть декодированы.

На этапе 1108 WT 1000, включающий в себя ранее сконфигурированный программируемый кодер 1012, функционирует так, чтобы принимать посредством устройств 1015 пользовательского ввода-вывода данные, которые должны быть закодированы, к примеру входные данные от пользователя WT 1000, предназначенные для того, чтобы быть закодированными и переданными равноправному узлу WT 1000. Принимаемые данные перенаправляются в кодер 1012. Процесс переходит от этапа 1108 к этапу 1126. На этапе 1126 кодер 1012 функционирует так, чтобы закодировать данные согласно сохраненной информации описания кода и информации индикатора длины кодового слова, предоставленной в кодер.

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

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

Нижеследующие заявки на патент и Патент предоставляют информацию о кодировании и декодировании LDPC-кодов и тем самым явно содержатся в данном документе по ссылке. Заявка на патент США, серийный номер 10/788115, зарегистрированная 26 февраля 2004 года; Заявка на патент США, серийный номер 10/117264, зарегистрированная 4 апреля 2002 года; заявка на патент США, серийный номер 10/618325 и Патент США №6633856.

Возможны различные вариации способа и устройства настоящего изобретения. Таким образом, модули, используемые для того, чтобы реализовать настоящее изобретение, могут быть реализованы в качестве программного обеспечения, аппаратных средств или сочетания программного обеспечения и программных средств. Например, различные признаки настоящего изобретения могут быть реализованы в аппаратных средствах или программном обеспечении. Например, некоторые аспекты изобретения могут быть реализованы как машиноисполняемые программные инструкции. Альтернативно или помимо этого, некоторые аспекты настоящего изобретения могут быть реализованы как интегральные схемы, такие как, например, ASIC. Устройство настоящего изобретения направлено на программное обеспечение, аппаратные средства или сочетание программного обеспечения и программных средств. Машиночитаемый носитель, используемый для того, чтобы управлять машиной или реализовывать один или более этапов способа в соответствии с изобретением, предполагается и должен рассматриваться как не выходящий за рамки области применения некоторых вариантов осуществления изобретения.

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

1. Кодер с низкой плотностью контроля по четности (LDPC), содержащий
модуль запоминающего устройства, включающий в себя, по меньшей мере, N×L×K ячеек запоминающего устройства, где N и L положительные целые числа, а К целое число больше 1;
управляемый перестановщик для выполнения операций переупорядочивания элементов для, по меньшей мере, N элементов, соединенный с модулем запоминающего устройства;
модуль векторного накопителя, включающий в себя N накопителей, размещенных параллельно, причем модуль векторного накопителя включает в себя
i) первый вход шириной, по меньшей мере, N битов, соответствующий выходу управляемого перестановщика,
ii) второй вход шириной, по меньшей мере, N битов, и
iii) выход векторного накопителя шириной, по меньшей мере, N битов;
управляемое устройство хранения, включающее в себя N×K ячеек хранения, причем управляемое устройство хранения включает в себя вход сигнала управления выбором блоков для приема сигнала, указывающего блок из, по меньшей мере, N ячеек хранения, к которому должен осуществляться доступ, и выход устройства хранения шириной, по меньшей мере, N битов для выхода значений, считываемых из устройств хранения; и
модуль выбора блоков, соединенный с управляемым устройством хранения, для предоставления сигнала управления выбором блоков в управляемое устройство хранения.

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

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

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

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

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

7. Кодер по п.6, в котором управляющий модуль также формирует сигнал управления адресами запоминающего устройства, который подается в модуль запоминающего устройства.

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

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

10. Кодер по п.1, в котором выход устройства хранения управляемого устройства хранения объединяется с вторым входом модуля накопителя векторов и входом модуля запоминающего устройства.

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

12. Кодер по п.7, в котором сигнал управления адресами запоминающего устройства представляет собой целое значение больше 0 и меньше L+1, и циклически проходит через каждое представленное целое значение от 1 до L в ходе операции кодирования, где L положительное целое число.

13. Кодер по п.6, в котором коэффициент расширения кода, который должен быть использован, представляет собой выбранное пользователем контрольное значение SK, которое является коэффициентом от К.

14. Кодер по п.13, в котором, когда коэффициент расширения кода SK меньше К, N×L×(K-SK) ячеек хранения в модуле запоминающего устройства остаются неиспользованными в ходе кодирования.

15. Кодер по п.13, в котором, когда коэффициент расширения кода SK меньше К, часть N×K ячеек хранения в управляемом устройстве хранения остается неиспользованными в ходе кодирования.

16. Кодер по п.1, в котором каждая из N×L×K ячеек хранения в модуле запоминающего устройства представляет собой однобитную ячейку хранения; и
в котором каждая из N×К ячеек хранения в управляемом устройстве хранения представляет собой однобитную ячейку хранения.

17. Кодер по п.1, в котором управляющий модуль также включает в себя набор инструкций микрокода, которые описывают структуру кода, которая должна быть использована для кодирования данных, причем каждая инструкция микрокода соответствует структуре кода, исполняемой К раз, чтобы закодировать кодовое слово, имеющее общую длину в K×N×L битов.

18. Способ выполнения обработки кодирования с низкой плотностью контроля по четности (LDPC), содержащий этапы, на которых
предоставляют кодер, включающий в себя
модуль запоминающего устройства, включающий в себя N×L×K ячеек хранения, где N и L это положительные целые числа, а К это целое число больше 1;
управляемый перестановщик для выполнения операций переупорядочивания элементов для, по меньшей мере, N элементов, соединенный с модулем запоминающего устройства;
модуль векторного накопителя, включающий в себя N накопителей, размещенных параллельно, причем модуль векторного накопителя включает в себя
i) первый вход шириной, по меньшей мере, N битов, соответствующий выходу управляемого перестановщика,
ii) второй вход шириной, по меньшей мере, N битов, и
iii) выход векторного накопителя шириной, по меньшей мере, N битов;
управляемое устройство хранения, включающее в себя N×K ячеек хранения, причем управляемое устройство хранения включает в себя вход сигнала управления выбором блоков для приема сигнала, указывающего блок из, по меньшей мере, N ячеек хранения, к которому должен осуществляться доступ, и выход устройства хранения шириной, по меньшей мере, N битов для выхода значений, считываемых из устройств хранения;
модуль выбора блоков на основе расширения кода, соединенный с управляемым устройством хранения, для предоставления сигнала управления выбором блоков в управляемое устройство хранения;
формируют первый сигнал управления модулем выбора как функцию от сохраненного описания кода и тактового сигнала, используемого для того, чтобы управлять синхронизацией операций кодирования;
предоставляют первый сигнал управления модулем выбора в модуль выбора блоков на основе расширения кода; и
управляют модулем выбора блоков на основе расширения кода, чтобы выбрать блок ячеек памяти, к которым должен осуществляться доступ, в управляемом устройств хранения, как функцию для первого сигнала управления модулем выбора.

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

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

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

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

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

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

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

26. Способ по п.21, в котором коэффициент расширения кода, который должен быть использован, представляет собой выбранное пользователем значение SK, которое является коэффициентом от К.

27. Способ по п.26, содержащий также этап, на котором оставляют некоторые из ячеек хранения N×L×K в модуле запоминающего устройства неиспользованными в ходе кодирования, когда коэффициент расширения кода SK представляет собой целое число меньше К.

28. Способ по п.27, в котором каждая из N×L×K ячеек хранения в модуле запоминающего устройства представляет собой однобитную ячейку хранения, и в котором оставление некоторых из ячеек хранения N×L×K неиспользованными включает в себя оставление неиспользованными K-SK ячеек хранения.

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

30. Способ по п.29, в котором каждая из N×K ячеек хранения в управляемом устройстве хранения это однобитная ячейка хранения, и в котором оставление некоторых из ячеек хранения N×K в управляемом устройстве хранения неиспользованными в ходе кодирования включает в себя оставление неиспользованными K-SK ячеек хранения.

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

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

33. Способ по п.32, в котором информация длины первых кодовых слов представляет собой первый сигнал выбранного коэффициента расширения кода.

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

35. Способ по п.34, содержащий также этап, на котором
сохраняют второй набор информации описания структуры кода в модуле кодера, причем второй набор информации описания структуры кода соответствует LDPC-коду, имеющему структуру, отличную от структуры кода, которой соответствует первый набор информации структуры кода.

36. Способ по п.35, содержащий также этапы, на которых
кодируют данные с помощью первого набора информации о структуре кода при обмене данными с первым устройством; и
кодируют данные с помощью второго набора информации о структуре кода при обмене данными со вторым устройством.

37. Способ по п.36, в котором первый набор информации структуры кода используется в момент времени, отличный от момента времени, когда используется второй набор информации структуры кода,

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

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

40. Способ по п.34, в котором первый набор информации описания кода включает в себя инструкции управления кодером.

41. Способ по п.40, в котором каждая инструкция управления кодером включает в себя один из индикаторов операции считывания и записи.

42. Способ по п.41, в котором каждая инструкция управления кодером также включает в себя информацию управления отражением.

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

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

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

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

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

48. Способ по п.44, в котором первый набор информации описания кода включает в себя инструкции управления кодером.

49. Способ по п.48, в котором каждая инструкция управления кодером включает в себя один из индикаторов операции считывания и записи.

50. Способ по п.49, в котором каждая инструкция управления кодером также включает в себя информацию управления отражением.

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