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

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

 

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

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

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

Коды коррекции ошибок повсеместно используются в системах связи и хранения данных. В последнее время возник значительный интерес к классу кодов, известному как коды с контролем четности низкой плотности (LDPC). Доказано, что LDPC-коды являются хорошими кодами. По различным каналам было продемонстрировано, что LDPC-коды действительно близки к пропускной способности канала, т.е. верхнему пределу скорости передачи, установленному Шенноном.

LDPC-коды часто представляются посредством двудольных графов (см. приведенный для примера граф 100 на фиг.1), называемых графами Таннера, в которых один набор узлов, узлы 102 переменных, соответствует битам кодового слова, а другой набор узлов, узлы 106 ограничений, иногда называемые проверочными узлами, соответствует набору ограничений контроля четности, которые определяют код. Ребра 104 на графе 100 соединяют узлы 102 переменных с узлами 106 ограничений. Узел переменных и узел ограничений считаются соседями, если они соединены ребром на графе. Альтернативой представлению на графе Таннера LDPC-кодов является представление матрицы контроля четности H 202, фиг.2. Битовая последовательность х 206 представляет собой кодовое слово, если и только если произведение битовой последовательности и H состоит из всех нулей, т.е.: Hx=0.

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

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

Число ребер, присоединенных к узлу, т.е. узлу переменной и узлу ограничения, упоминается как степень узла. Регулярный граф или код - это граф или код, для которого все узлы переменных имеют одинаковую степень, например j, и все узлы ограничений имеют одинаковую степень, например k. В этом случае говорят, что код является регулярным кодом (j,k). Были коды, рассмотренные первоначально Галлагером (1961). В отличие от «регулярного» кода нерегулярный код имеет узлы ограничений или узлы переменных различных степеней. Например, некоторые узлы переменных могут иметь степень 4, другие - степень 3, а еще одни - степень 2.

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

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

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

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

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

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

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

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

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

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

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

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

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

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

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

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

Ниже кратко рассмотрена, приведенная для примера, реализация векторизованного декодера. Предполагается, что память, хранящая сообщения от узла переменных к проверочным узлам и/или сообщения от проверочного узла к узлам переменных, скомпонована в Z×E m-битовых ячеек памяти, где E - это число ребер, а m - это число битов, переносимых в сообщении, целое число больше 1. Доступ к памяти осуществляется в Z m-битовом блоке, другими словами, при каждом доступе считывается или записывается Z m-битовый блок. Этот Z m-битный блок соответствует Z сообщениям по Z расширенным ребрам расширенного графа. Для удобства описания каждый набор из Z m-битовых сообщений ассоциируется с соответствующим ребром в проекции графа. Например, осуществление доступа к сообщениям ребра e в проекции графа фактически соответствует осуществлению доступа к Z m-битовым сообщениям, соответствующим Z ребрам в расширенном графе.

Согласно общему алгоритму передачи сообщений обновление сообщения в узле зависит от всех сообщений от соседних объектов данного узла. Пусть узел в проекции имеет d ребер e₁, e₂,..., e_d. Основанная на ребрах реализация обновления сообщений может считывать сообщения e₁, применять соответствующее переупорядочивание; после чего переупорядоченные сообщения находятся в надлежащих соседних группировках для всех Z узлов расширенного графа. В патенте США 6633856 архитектура декодера имеет Z параллельных блоков обработки для осуществления обработки узлов. В одном или более каскадах сообщения могут подвергаться преобразованию формата для обеспечения эффективной реализации. Например, различные форматы могут использоваться на стороне узлов переменных и на стороне проверочных узлов.

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

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

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

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

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

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

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

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

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

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

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

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

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

Фиг.3 и 4 иллюстрируют идею разложения исполнения простого набора микрокода на K шагов.

Фиг.5 иллюстрирует примерную архитектуру декодера в соответствии с настоящим изобретением.

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

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

ПОДРОБНОЕ ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

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

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

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

Рассмотрим расширенный LDPC-граф с коэффициентом Z=K×N расширения. Группа Ψ расширения должна быть группой Ψ=Ψ_l×Ψ₂, расширенной посредством произведения, где K - размерность группы Ψ₁, а является N - размерность группы Ψ₂. Таким образом, общее расширение является произведением двух меньших расширений.

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

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

Запишем исходный вектор сообщений как d=(d₁, d₂,... d_k), где каждое d_i - N m-битовый вектор. При условии, что группа расширения является расширением Ψ=Ψ×Ψ₂ посредством произведения, запишем информацию переупорядочивания r=(r₁,r₂), переносимую в каждом описании декодера, где r_i - это величина переупорядочивания в группе Ψ_l, а r₂ - это величина переупорядочивания в группе Ψ₂. Обозначение Ψ_i(d,r) представляет переупорядочивание на величину r для вектора d (элемента K_j) в группе Ψ_i. Переупорядочивание также может рассматриваться как перестановка позиции, так чтобы элемент d_j в исходной позиции j переходил в новую позицию, обозначенную как Ψ_l,r(j) в переупорядоченных данных. Затем переупорядочивание может трактоваться как 2-уровневая процедура переупорядочивания. Первый уровень переупорядочивает в группе Ψ₂ для N (m-битовых) элементов, чтобы сформировать вектор d'= (Ψ₂(d₁,r₂), Ψ₂(d₂,r₂),..., Ψ₂(d_K,r₂)). Затем второй уровень переупорядочивает в группе Ψ₁ для K (N m-битовых) элементов, чтобы сформировать вектор d"=Ψ₁(d',r₁). После этого переупорядоченные данные d" вводятся в блоки обработки узлов. Для удобства Ψ^-1 _1,r(j) обозначает инверсию функции Ψ_1,r(j).

Следовательно, для j-тых N копий их позиция внутри исходного Z m-битового вектора соответствует . Поэтому для ребра в j-том проходе декодирования считываются данные , где адрес является функцией от a и j, и переупорядочиваются считанные данные на величину r₂ в группе Ψ₂, формируя Ψ₂(d₁,r₂). Этот набор сообщений соответствует набору сообщений надлежащим образом упорядоченных ребер, связанных с N узлами при обработке.

Ниже представлен пояснительный пример. Представление 700 на фиг.3 иллюстрирует процесс декодирования для примерного расширенного графа с максимальным коэффициентом расширения Z=64, использующего уровень параллелизма, соответствующий этому коэффициенту расширения. Группа расширения является прямым произведением циклической группы 4 и циклической группы 16. Для целей пояснения изобретения описана процедура декодирования для набора из 64 узлов переменных, соответствующих узлу v в проекции графа, использующего уровень параллелизма, который равен Z=64, где узел v имеет степень 2. Процедура декодирования для степени, отличной от 2, или проверочных узлов имеет ту же характеристику. Сообщения от двух ребер, соединенных с v, считываются в два такта, a = (a₀,a₁,a₂,a₃) 701, b=(b₀,b₁,b₂,b₃) 702, каждый a_j(b_j) является вектором 711 из 16 m-битных элементов. Прохождение времени указывается стрелкой 710. Эти две порции данных 701, 702 из 64 элементов проходят через 64-элементный перестановщик 703, управляемый посредством информации 708 переупорядочивания, указанной как (r1,r2), где r1 представляет информацию перестановки для первой циклической группы, а r2 представляет информацию перестановки для второй циклической группы. В рассматриваемом примере информация переупорядочивания для данных a 701 - это (3, 4), а информация переупорядочивания для данных b 702 - это (1, 6). Таким образом, после переупорядочивания a'=(a⁴ ₁, a⁴ ₂, a⁴ ₃, a⁴ ₀) 704, а b'=(b⁶ ₃, b⁶ ₀, b⁶ ₁, b⁶ ₂) 705, где dⁱ представляет результат перестановки данных d на величину i в циклической группе 16. Переупорядоченные данные 704, 705 после этого проходят через модуль обработки узлов, включающий в себя 64 параллельных конфигурируемых блока 706 обработки узлов, где параллельная обработка, выполняемая каждым из узлов, является взаимно независимой. Следовательно, в результирующих данных c = (c₀, c₁, c₂, c₃) 707 c₀ зависит только от a₁ и b₃, c₁ - от a₂ и b₀, c₂ - от a₃ и b₁, c₃ - от a₀ и b₂. Команда микрокода декодера переносит информацию r=(r1,r2) 708 переупорядочивания и информацию 709 узлов.

Фиг.4, на которой показано представление 800, иллюстрирует возможность реализации той же процедуры декодирования, показанную на фиг.3, с помощью параллелизма 16 (N=16) реализации вместо параллелизма 64 (в перестановщике и блоке параллельной обработки) после микрокода, который поддерживает общий коэффициент расширения Z=64. Декодирование осуществляется при исполнении микрокода в 4 (K=4) циклах, где Z=N×K. Доступ к данным осуществляется как функция от счетчика циклов и управляющей информации r1, заданной посредством микрокода, используемого для управления декодированием согласно изобретению.

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

В первом цикле 827, например в первой итерации обработки, декодер осуществляет доступ к данным a₁ 801 и b₃ 802; во втором цикле 828 декодер осуществляет доступ к данным a₂ 803 и b₀ 804; в третьем цикле 829 декодер осуществляет доступ к данным a₃ 805 и b₁ 806; и в четвертом цикле 830 декодер осуществляет доступ к a₀ 807 и b₂ 808, где a_i и b_i представляют наборы 16 m-битовых элементов, например сообщение, проходящее как часть процесса декодирования. Каждое сообщение обычно включает в себя несколько битов, например, мягких значений, включающих в себя информацию надежности, которая может передаваться в некоторых из сообщений. Приведенные для примера 4 набора данных могут не быть непрерывными, поскольку существуют другие узлы переменных и цикл, используемый для завершения полного набора микрокода, используемого для выполнения обработки декодирования, например обработки полного набора узлов переменных, соответствующих структуре кода, которая должна использоваться для управления декодированием. Эти 16 элементов каждого блока (801, 802, 803, 804, 805, 806, 807, 808) данных, к которым осуществляется доступ, проходят через 16-элементный перестановщик 810, который управляется посредством информации переупорядочивания r2 825. Затем переупорядоченные данные (a⁴ ₁ 811, b⁶ ₃ 812, a⁴ ₂ 813, b⁶ ₀ 814, a⁴ ₃ 815, b⁶ ₁ 816, a⁴ ₀ 817, b⁶ ₂ 818) проходят через модуль обработки узлов, включающий в себя 16 параллельных блоков 820 обработки узлов, которые управляются посредством информации 826 узлов, переносимой в команде декодирования. Последовательность c₀ 821, c₁ 822, c₂ 823, c₃ 824 формируется из команды. Следовательно, тот же результат прохождения сообщения, что и на фиг.3, достигается посредством структуры на фиг.4, но с помощью в 4 раза большего времени обработки при аппаратной сложности примерно в 1/4. Т.е. декодер по фиг.4 может быть реализован с помощью уровня параллелизма, равного 16 вместо 64.

Вышеприведенное описание поясняет использование параллелизма N для декодирования с помощью микрокода с коэффициентом Z расширения, где Z=N×K.

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

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

LDPC-декодер 900 включает в себя исходный модуль 902 памяти, модуль 904 управляемого N-элементного перестановщика, модуль 906 обработки узлов (N параллельных процессоров узлов), управляющий модуль 910 и модуль 908 выбора блоков на основе расширения кода. Исходный модуль 902 памяти включает в себя память ((N×K×L) ячеек памяти) 912, где каждая ячейка памяти может сохранять множество битов, модуль 916 формирования адресов и, в некоторых вариантах осуществления, необязательный модуль 914 восстановления. Модуль 914 восстановления используется в вариантах осуществления, где сообщения, передаваемые как часть процесса декодирования между узлами, сохраняются в сжатом формате. В этом случае они могут формироваться и сохраняться в сжатом формате и затем подвергаться восстановлению перед дополнительной обработкой. Сжатие не является обязательным и не используется в некоторых вариантах осуществления, но сжатие сообщений позволяет снизить потребности в памяти и поэтому используется в некоторых вариантах осуществления.

Управляющий модуль 910 включает в себя модуль 942 сохраненной информации описания декодера, счетчик 940 внутренних циклов и счетчик 944 внешних циклов. Модуль 942 сохраненной информации описания декодера включает в себя информацию (например, управляющий код типа микрокода), которая отражает структуру кода, который использовался для управления формированием кодовых слов, которые должны декодироваться, и, таким образом, который также должен быть использован для управления декодированием принимаемых кодированных кодовых слов LDPC. Управляющий код обычно включает в себя последовательность команд, число реализации которых указано выбранным коэффициентом SK расширения кода вплоть до максимального поддерживаемого коэффициента K кода, где K и SK - целые числа.

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

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

op r a nci,

где op указывает операцию записи;

r - число, представляющее информацию перестановки, например чередования сообщений, используемое в качестве сжатого представления отдельных значений чередования r1, r2, которые альтернативно могут быть включены в команду без объединения в одно значение r и обычно обрабатываются посредством модуля 942 описания декодера, чтобы сформировать сигналы r1 и r2 информации перестановки;

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

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

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

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

Ниже описана работа декодера 900. Модуль 942 сохраненной информации описания декодера сохраняет информацию описания кодов, используемую для управления декодированием. Управляемый счетчиком 940 внутренних циклов модуль 942 сохраненной информации описания декодера исполняется, например, посредством вывода соответствующих управляющих сигналов для реализации команды, например команды декодирования. В каждом тактовом цикле, в котором модуль N-элементного перестановщика обрабатывает набор данных, набор из N элементов считывается из памяти 912. Данные записываются в память, когда сигнал 928 записи активируется, например, в ответ на сигнал op, формируемый из сохраненного управляющего кода, указывающего на выполнение записи. Считывание и запись могут осуществляться в одном тактовом цикле перестановщика. Это происходит, когда сигнал 928 записи активирован с учетом того, что считывание обычно осуществляется в каждом тактовом цикле перестановщика в зависимости от значения сигнала 928 записи. Это может выполняться посредством двухпортовой памяти или работы модуля 902 памяти с частотой, в два раза превышающей частоту перестановщика 904, что позволяет выполнять считывание и запись в память 912 в тактовом цикле перестановщика 904. Обычно каждый из элементов декодера 900 управляется посредством общего тактового сигнала. Однако в некоторых вариантах осуществления память 912 может тактироваться с более высокой частотой для обеспечения считывания и записи в периоде перестановщика 904 и модуля 906 обработки узлов. Как описано выше, команда включает в себя, например, оператор op, указатель a ячейки памяти, информацию r переупорядочивания и информацию nci конфигурации узлов.

Оператор op определяет значение сигнала 928 записи, например значение «1» может быть использовано для указания разрешения записи, тогда как «0» может указывать на блокирование записи. Сигнал 928 записи выводится из модуля 942 сохраненной информации описания декодера и вводится в исходный модуль 902 памяти. Информация a ячеек памяти используется для формирования первого сигнала управления адресацией (a) 930, который подается из модуля 942 в исходный модуль 902 памяти. Таким образом, модуль 916 формирования адресов исходного модуля 902 памяти принимает информацию a, соответствующую команде, которая должна быть реализована. Номер r переупорядочивания разделен на две части (r₁,r₂). В различных вариантах осуществления каждое из значений (r₁,r₂) определяет переупорядочивание в группе Ψ₁ и Ψ₂ соответственно, которые являются группами, в которые скомпонованы узлы, чтобы реализовать расширение графа как функцию от двух меньших расширений. Управляющие значения r1 и r2 сохраняются в значении r. В одном варианте осуществления r1, определяемое посредством r для данной реализации, определяется из значения r как целый делитель r, при делении на N, которое указывает реализованный уровень параллелизма узлов. Т.е. r1 = r div N. r2 в этом варианте осуществления определяется из значения r посредством взятия модуля значения r/N. Например, N=16. Если r = 43 и N = 16, то r1 = (r div N) = (43 div 16) = 2, r2 = (r mod N) = (43 mod 16) = 11. Часть r₁ переупорядочивания, которая формируется из r посредством модуля 942, определяет сигнал (r₁) 934 информации упорядочивания блоков, выводимый из модуля 942 сохраненного описания декодера. Сигнал r₁ подается на вход модуля 908 выбора блоков расширения кода, а часть r₂ переупорядочивания определяет значение управляющего сигнала (r₂) 950 переупорядочивания, выводимого из модуля 942. Сигнал r₂ подается на вход в модуль 904 N-элементного управляемого перестановщика.

Информация конфигурации узлов, включенная в исполняемую команду, определяет управляющий сигнал 952 конфигурации узлов, выводимый из модуля 942. Сигнал 952 информации конфигурации узлов подается на вход модуля 906 обработки узлов, который включает в себя N конфигурируемых процессоров узлов, размещенных параллельно. Во многих, но не обязательно во всех вариантах осуществления, информация конфигурации узлов приводит к одинаковому конфигурированию каждого из N процессоров узлов в модуле 906 в один и тот же момент времени. Процессоры узлов могут переключаться между конфигурированием как узлы переменных и проверочные узлы.

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

Сигнал 946 счетчика внутренних циклов, формируемый посредством счетчика 940 внутренних циклов, подается как управляющий сигнал приращения в счетчик 944 внешних циклов. Когда счетчик 940 внутренних циклов достигает максимального значения счетчика внутренних циклов, например числа ребер в проекции графа, он активирует счетчик 944 внешних циклов, увеличивая его на 1, и перезапускает подсчет с 0, например счетчик циклически возвращается к началу. Счетчик 944 внешних циклов определяет то, какой цикл, от 1 до SK, исполняется в полной итерации, где SK - выбранный коэффициент расширения, который может варьироваться от 1 до K, причем K и SK - целые числа. После того как счетчик 944 внешних циклов достигает максимума, заданного посредством сигнала (SK) 948 управления коэффициентом расширения кода, декодер 900 завершает полную итерацию, и счетчик 944 внешних циклов сбрасывается в нуль. В некоторых вариантах осуществления, где коэффициент расширения является фиксированным, ввод сигнала SK опускается, и значение счетчика внешних циклов задается равным K.

Модуль 908 выбора блоков на основе расширения кода принимает сигнал (r₁) 934 информации упорядочивания блоков из модуля 942 сохраненной информации декодера управляющего модуля 910, который определяется из компонента r₁ числа r переупорядочивания в команде из упомянутого управляющего модуля 910. Запускаемый счетчиком 944 внешних циклов управляющего модуля 910 посредством сигнала 936 управления внешними циклами и управляемый сигналом (r₁) 934 информации упорядочивания блоков модуль 908 выбора блоков на основе кода расширения формирует и выводит второй сигнал 932 управления адресацией (сигнал выбора адреса блока).

Модуль 902 памяти принимает сигнал 928 записи и первый сигнал (a) 930 управления адресацией, переносящий оператор и указатель а ячейки памяти из управляющего модуля 910. Первый сигнал (a) 930 управления адресацией и второй сигнал 932 управления адресацией принимаются посредством модуля 916 формирования адресов исходного модуля 902 памяти. Модуль 916 формирования адресов формирует сигнал 920 доступа к памяти, задаваемый посредством информации в принимаемых первом и втором сигнале 930, 932 управления адресацией, и направляет сигнал 920 доступа к памяти в память 912. Сигнал 920 является сигналом адреса считывания. Информация считывается из памяти 912 один раз для каждого цикла обработки управляемого N-элементного перестановщика 904. Сигнал 920 адреса памяти задерживается посредством задержки 954 для формирования сигнала 956 управления адресом записи. Число циклов, задерживаемых между 956 и 920, может управляться частью сигнала 952 управления конфигурацией узлов. Выходной сигнал 955 управления записью может быть таким же, как и сигнал 956, и указывать адрес, в который записывается результат декодирования. Сигнал управления адресом записи управляет ячейкой, в которую записывается вывод модуля 906 обработки узлов в памяти, когда сигнал 928 записи активирован.

Как показано, модуль 902 памяти принимает вывод модуля 906 обработки узлов посредством ввода 928 данных или начальный ввод посредством ввода 901. Начальным вводом может быть, например, принимаемое кодовое слово или часть кодового слова, которая должна декодироваться.

Модуль 902 памяти включает в себя память 912, скомпонованную в K ×(N×L) m-битовых ячеек памяти, где m представляет число битов в сохраненном сообщении, например мягкое значение, передаваемое между узлами. Для удобства ячейки памяти с K блоками из (N×L) m-битовых ячеек идентифицированы как блок 1,..., K. Доступ к памяти 912 осуществляется в ячейке, которая является функций от первого сигнала a 930 управления адресацией и второго сигнала k 932 управления адресацией. Модуль 916 формирования адресов памяти указывает эту функцию. С учетом (a, k) исходный модуль 902 памяти считывает N-элементный вектор, соответствующий ячейке a в k-том блоке. С учетом задержанного (a, k) и в зависимости от сигнала записи исходный модуль 902 памяти записывает ввод N-элементного вектора в ячейку a в k-том блоке. Операция считывания и записи в память 912 может осуществляться одновременно при использовании двухпортовой памяти или при функционировании памяти с удвоенной скоростью. Память 912 может включать в себя дополнительную память для временного хранения значений в некоторых вариантах осуществления.

Сообщения считываются и записываются в память 912 в блоках по N элементов, где каждый элемент включает в себя m битов. В качестве набора из N блоков сигнал 922 считывается из памяти и подается на вход модуля 904 управляемого N-элементного перестановщика. В некоторых вариантах осуществления, где используется сжатие сообщений, модуль 914 восстановления принимает N элементов 918, считанных из памяти 912, выполняет восстановление и выводит N элементов в управляемый перестановщик, где в результате восстановления каждый из N элементов в сигнале 922 включает в себя больше бит, чем первоначально считано из памяти. В вариантах осуществления, где модуль 914 восстановления не используется, N-элементный блок 918, считанный из памяти 912, подается на вход модуля 904 перестановщика. Варианты осуществления, которые поддерживают возможность восстановления и формирование в модуле обработки узлов сообщений в сжатом формате, обеспечивают сохранение сообщений с использованием m битов, что меньше, чем число битов, включенных в каждое сообщение после восстановления. Модуль 904 управляемого N-элементного перестановщика реализует переупорядочивание поданных на него N сообщений. Это представляет переупорядочивание в группе Ψ₂.

Сигнал r₂ 950 управления переупорядочиванием, который управляет перестановщиком 904 для выполнения переупорядочивания N элементов, считанных из памяти, до подачи их в модуль 906 обработки узлов, подается посредством управляющего модуля 910 и формируется из сохраненной команды исполняемого модуля 942.

Переупорядоченный вывод N элементного вектора из модуля 904 перестановщика подается на вход 924 N-элементного вектора модуля 906 обработки узлов N элементов. Модуль 906 обработки узлов управляется посредством сигнала 952 управления конфигурацией узлов, переносимого посредством команды из упомянутого управляющего модуля 910. В проиллюстрированном варианте осуществления вывод 926 модуля 906 обработки узлов подается в модуль 902 памяти или какую-либо другую память, например, используемую для сохранения результата после успешного завершения декодирования.

Следует отметить, что один вариант описанного варианта осуществления декодера заключается в использовании структуры декодера, аналогичной реализации декодера, описанной в патентной заявке США 10/895547, озаглавленной "LDPC ENCODING METHODS AND APPARATUS", от 21 июля 2004 года, и идентифицированной на первой странице дела поверенного номер [Flarion-108], которая включена в настоящий документ посредством ссылки. Такой декодер, реализованный в соответствии с изобретением, должен использовать повторяемость внутренних циклов и должен включать в себя K N-элементных регистров, чтобы хранить временные результаты обработки узлов. Этот вариант должен быть очевиден специалистам в данной области техники и рассматривается как входящий в объем настоящего изобретения. Такая реализация должна включать в себя большинство из признаков, таких как модуль 902 памяти, модуль 904 перестановщика и модуль 942 сохраненной информации описания декодера, описанных в данном документе.

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

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

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

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

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

В LDPC-декодере 900 по фиг.5 коэффициент расширения кода может быть задан посредством сигнала (SK) 948 управления коэффициентом расширения кода. Сигнал 948 подается на счетчик 944 внешних циклов, определяя максимальное значение счета для счетчика 944 внешних циклов.

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

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

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

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

Информация о структуре кода или информация о длине кодового слова, например, в форме набора управляющих команд может быть передана из запоминающего устройства 1016 в программируемый LDPC-декодер 1006 и в программируемый LDPC-кодер 1012 по шине 1018. Устройства 1015 пользовательского ввода-вывода, например клавишные панели, громкоговорители, микрофоны, дисплеи и т.д., предоставляют интерфейсы для пользователя, чтобы вводить данные и информацию, например данные и информацию для кодирования и передачи в другой терминал, и чтобы выводить и отображать принимаемые данные и информацию, например принимаемые данные и информацию от равноправного узла, которые были декодированы. Устройства 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 выбора кодового слова и кода декодера отвечает за выбор структуры кода и, следовательно, соответствующей информации 1030, 1032 описания кода декодера, которая должна использоваться для конкретного приложения. Этот выбор может выполняться на основе информации, принимаемой из процедуры 1020 связи, информации, принимаемой посредством приемного устройства 1002, или от пользовательского ввода. Процедура 1024 выбора длины кодового слова и кода декодера отвечает за загрузку в программируемый LDPC-декодер 1006 выбранной информации описания кода, например управляющего кода, и за предоставление информации, например выбранного коэффициента расширения кода, в программируемый декодер 1006, если он еще не был конфигурирован для выполнения декодирования в соответствии с выбранным кодом и длиной кодового слова.

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

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

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

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

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

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

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

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

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

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

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

Подробное описание программируемого LDPC-кодера, который может использоваться (и в некоторых вариантах осуществления используется) в качестве программируемого LDPC-кодера 1012, содержится в вышеупомянутой патентной заявке США 10/895547.

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

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

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

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

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

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

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

4. Декодер по п.3, в котором упомянутый выбранный коэффициент SK расширения меньше или равен максимальному расширению K, соответствующему максимальному коэффициенту расширения, поддерживаемому упомянутым управляющим модулем.

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

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

7. Декодер по п.6, в котором упомянутый источник сообщений включает в себя память, включающую в себя, по меньшей мере, N раз по K ячеек памяти.

8. Декодер по п.7, в котором каждая из N раз по K ячеек памяти сохраняет, по меньшей мере, 2 бита.

9. Декодер по п.1, в котором источник сообщений дополнительно включает в себя модуль восстановления для восстановления сообщений, сохраненных в упомянутой памяти перед выдачей упомянутых сообщений в упомянутый управляемый блок перестановки.

10. Декодер по п.1, в котором каждый из упомянутых процессоров узлов является процессором узлов переменных.

11. Декодер по п.1, в котором каждый из упомянутых процессоров узлов является процессором проверочных узлов.

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

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

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

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

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

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

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