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

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

Иллюстрации

Показать все

Реферат

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

Настоящее изобретение направлено на способы и устройство для выполнения операций декодирования с контролем по четности низкой плотности (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, к которой должен быть осуществлен дост