Эффективные по использованию памяти способы декодирования кодов с низкой плотностью контроля по четности (ldpc) и устройства для осуществления этих способов

Изобретение относится к передаче данных и может быть использовано в системах передачи данных, в которых используются коды с исправлением ошибок. Технический результат - повышение надежности передачи информации по каналу. Описаны способы и устройство для воплощения эффективных по использованию памяти декодеров кодов с LDPC. В соответствии с изобретением информацию сохраняют в уплотненном состоянии для операций обработки контрольных вершин. Состояние контрольной вершины полностью обновляют, а потом подвергают процессу извлечения для генерирования сообщений от контрольных вершин к вершинам переменных. Знаки сообщений, принимаемых от вершин переменных, можно хранить с помощью блока обработки контрольных вершин согласно изобретению для использования при извлечении сообщений. Процессор контрольных вершин может обрабатывать сообщения в порядке вершин переменных, тем самым обеспечивая обработку сообщений процессором контрольных вершин и процессором вершин переменных в одном и том же порядке, уменьшая или исключая потребность в буферизации и/или переупорядочении сообщений, передаваемых между контрольными вершинами и вершинами переменных. 2 н. и 34 з.п. ф-лы, 8 ил.

 

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

Коды с МПКЧ хорошо отображаются двудольными графами, которые часто называют графами Таннера, такими, как граф 100, показанный на фиг.1. В графах Таннера одно множество вершин - вершины 102 «переменных» - соответствует битам кодового слова, а другое множество вершин - вершины 106 «ограничений», иногда называемые «контрольными» вершинами, - соответствуют множеству ограничений контроля по четности, которые и определяют код. Ребра 104 в графе связывают вершины переменных с вершинами ограничений. Вершина переменной и вершина ограничения называются соседями, если они соединены ребром в графе. Обычно предполагают, что две вершины соединены, по меньшей мере, одним ребром. Коды с МПКЧ можно эквивалентно представить, воспользовавшись матрицей 202 контроля по четности. На фиг.2 приведен пример представления матрицы контроля по четности, при этом вектор “x”, обозначенный позицией 206, является кодовым словом, если и только если Нх=0.

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

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

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

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

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

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

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

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

Доверительное распространение для (двоичных) кодов с LDPC можно выразить следующим образом. Сообщения, передаваемые по ребрам графа, интерпретируются как логарифмические правдоподобия log(p₀/p₁), где р_х обозначает вероятность того, что бит будет принимать значение “x”. Биты мягкого решения, предоставляемые декодеру приемником, также задаются в форме логарифмического правдоподобия. Таким образом, принимаемые значения, т.е. элементы принимаемого слова, представляют собой логарифмические правдоподобия соответствующих битов, обусловленные наблюдением битов, предоставляемых каналом связи. В общем случае сообщение m представляет логарифмическое правдоподобие m, а принимаемое значение “y” представляет логарифмическое правдоподобие “y”. Для проколотых битов принимаемое значение “y” логарифмического правдоподобия задают равным 0, указывая, что p₀=p₁=1/2.

Рассмотрим правила передачи сообщений согласно доверительному распространению. Сообщения обозначаются символом m^C2V, если это сообщения от контрольных вершин к вершинам переменных, и символом m^V2C, если это сообщения от вершин переменных к контрольным вершинам. Рассмотрим вершину переменной с d ребрами. Пусть для каждого ребра j=1,…,d символ m^C2V(i) обозначает входящее сообщение на ребре i. При инициализации процесса декодирования зададим m^C2V=0 для каждого ребра. В общем случае исходящие сообщения из узлов переменных задаются следующим образом:

Исходящее кодированное значение мягкого решения из вершины (не сообщение на ребре), соответствующее этой операции, задается следующим образом: . Исходящее твердое решение, связанное с этим выводимым значением, получается из знака для x_out.

В контрольных вершинах зачастую удобнее представлять сообщения с использованием их «знаков» и модулей. Поэтому пусть для сообщения m выражение m_p ∈ GF[2] обозначает «четность» сообщения, т.е. m_p = 0, если m ≥ 0, и m_p = 1, если m < 0. Кроме того, пусть выражение m_p∈[0,∞] обозначает модуль сообщения m. Таким образом, имеем m = -1^mpm_r. В контрольной вершине обновления для сообщений m_p и m_r разделены. Для контрольной вершины степени d, имеем:

где все сложение производится по GF[2], и

где сложение является действительным, и определяем функцию F(x)=: ln cth(x/2). Отметим, что F представляет собой и собственное обратное значение, т.е. F^-1(x)= F(x).

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

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

В патенте США № 6633856 описана архитектура декодера кодов с LDPC. В этой архитектуре сообщения от контрольных вершин к вершинам переменных хранятся в памяти. Если, например, сообщение содержит 5 бит, а контрольная вершина имеет степень К, то емкость памяти, используемой для этих сообщений, составляет 5К бит.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Знаковый бит для исходящего сообщения можно генерировать многими путями. В одном возможном варианте осуществления значение накопленного знакового бита, соответствующее некоторой контрольной вершине, объединяется, например, посредством операции «исключающее ИЛИ», с хранимым принимаемым значением знакового бита, соответствующим ребру, для которого генерируется исходящее сообщение, чтобы получить значение знакового бита исходящего сообщения для такого ребра. Этот процесс повторяется подобно процессу генерирования исходящего сообщения для каждого ребра, для которого генерируется исходящее сообщение.

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

Рассмотрим, например, случай 5-битовых сообщений, которые включают в себя один знаковый бит и 4 бита модуля. При вышеописанных допущениях выводимую информацию из каждой контрольной вершины можно сжать приблизительно до К+8+log₂K бит, где К - количество входящих и исходящих сообщений. В примере с 5-битовом сообщением К бит памяти будут использоваться для хранения знаковых битов, соответствующих каждому из К вводимых сообщений, 8 бит будут использоваться для хранения каждого из двух возможных значений модулей, которые можно предположить в выводимых сообщениях, например минимальное значение модуля вводимого сообщения и следующее наименьшее значение модуля вводимого сообщения, а log₂K бит используются для указания ребра (сообщения), прием по которому должен происходить со вторым значением надежности, тогда как прием по другим ребрам будет происходить с минимальным значением модуля вводимого сообщения. Если число К велико, как будет в случае кодов с LDPC для больших скоростей передачи, то использование этого метода хранения информации о сообщениях может привести к существенной экономии по сравнению с воплощениями, предусматривающими хранение полных множеств битов, соответствующих каждому принимаемому сообщению, как часть процесса генерирования выводимых сообщений.

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

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

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

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

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

На фиг.2 приведено альтернативное представление кода с LDPC согласно фиг.1, которое показывает код посредством использования матричного представления в качестве альтернативы представлению в виде графа, показанному на фиг.1.

На фиг.3 изображен блок обработки вершин ограничений, воплощенный в соответствии с изобретением.

На фиг.4 изображен декодер кодов с LDPC, воплощенный в соответствии с настоящим изобретением.

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

На фиг.6 изображена возможная структура кода с LDPC, которую можно использовать для управления декодированием, например, в декодере согласно фиг.4.

На фиг.7 изображена еще одна возможная структура кода с LDPC, которую можно использовать для управления декодированием, например, в возможном декодере согласно фиг.4, в соответствии с настоящим изобретением.

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

Подробное описание

Нижеследующие (3) родственные заявки упоминаются в этом описании для справок и должны рассматриваться как часть настоящей заявки: заявка № 09/975331 на патент США, поданная 10 октября 2001 г. под названием “METHODS AND APPARATUS FOR DECODING LDPC CODES” («СПОСОБЫ И УСТРОЙСТВА ДЛЯ ДЕКОДИРОВАНИЯ КОДОВ С LDPC»); заявка № 10/117264 на патент США, поданная 4 апреля 2002 г. под названием “NODE PROCESSORS FOR USE IN PARITY CHECK DECODERS” («ПРОЦЕССОРЫ ВЕРШИН, ПРЕДНАЗНАЧЕННЫЕ ДЛЯ ИСПОЛЬЗОВАНИЯ В ДЕКОДЕРАХ С КОНТРОЛЕМ ПО ЧЕТНОСТИ»); и заявка № 10/618325 на патент США, поданная 11 июля 2003 г. под названием “METHODS AND APPARATUS FOR DECODING LDPC CODES” («СПОСОБЫ И УСТРОЙСТВА ДЛЯ КОДИРОВАНИЯ КОДОВ С LDPC»).

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

В соответствии с изобретением с каждой контрольной вершиной в структуре кода с LDPC, используемой для управления декодированием, связано состояние S. Это состояние будет включать в себя информацию о надежности (модуле сообщения) для входящих сообщений в текущей итерации декодирования, причем эта информация будет использоваться для генерирования исходящих сообщений. Пусть символ S_k обозначает состояние, которое предположительно включает в себя сообщения m₁, …, m_k. Тогда, задав функцию G обновления состояния, состояние для заданной контрольной вершины, возникающее в результате обработки принимаемого сообщения от вершины переменной к контрольной вершине, соответствующего контрольной вершине, можно выразить следующим образом:

S_k+1 = G(m_k+1, S_k).

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

В случае воплощения, в котором используется алгоритм минимальной суммы для хранения информации сообщения в уплотненном формате, хранимое состояние сообщения может быть представлено, например, в форме (m_A, m_B, A, s). Если m_A - минимальная надежность входящего сообщения (его минимальный модуль), рассматривавшаяся до сих пор контрольной вершиной, которой соответствует упомянутое состояние, а m_B - вторая наименьшая надежность, рассматривавшаяся до сих пор, то А обозначает ребро, по которому проходило входящее сообщение надежности m_A, и тем самым указывает, какое ребро сообщения обусловило подачу минимального значения m_A, а s обозначает операцию «исключающее ИЛИ» над знаками входящих сообщений, соответствующих контрольной вершине, которой соответствует информация о состоянии.

Осуществляя обновления информации о состоянии, соответствующей контрольным вершинам, с использованием функции G, а также обеспечивая воплощение декодера, в котором оказываются возможными хранение и выборка состояния, соответствующего отдельным контрольным вершинам, для обновления входящими сообщениями в зависимости от того, в какую контрольную вершину направлено сообщение, можно сделать порядок сообщений, поступающих в процессор контрольных вершин, по существу, произвольным. Таким образом, в соответствии с изобретением сообщения от вершин переменных к контрольным вершинам могут прибывать в порядке вершин переменных в процессор контрольных вершин, при этом сообщения обрабатываются в том порядке, в котором они принимаются. Это позволяет создать декодеры кодов с LDPC, такие, как декодеры 400 и 500, изображенные на фиг.4 и 5, воплощаемые в соответствии с изобретением, в которых обе стороны (вершин переменных и контрольных вершин), которые воплощаются в виде процессоров вершин переменных и контрольных вершин, соответственно обновляются в порядке вершин переменных. Более того, и элементы обработки вершин переменных, и элементы обработки контрольных вершин могут работать и работают параллельно, например - одновременно, в некоторых вариантах осуществления.

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

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

На фиг.3 изображен блок 300 обработки вершин ограничений, также известный под названием «блок обработки контрольных вершин» и воплощенный в соответствии с настоящим изобретением. Блок 300 принимает сообщения (V2C) от вершин переменных к контрольным вершинам через вход 302, а информацию управления - через вход 324 управляющего сигнала, и генерирует сообщения (C2V) от контрольных вершин к вершинам переменных, которые выводятся через выход 322. Блок 300 обработки контрольных вершин хранит информацию о сообщениях, которую можно использовать для генерирования сообщений от контрольных вершин к вершинам переменных, в уплотненном формате.

Блок 300 обработки контрольных вершин включает в себя блок 310 памяти состояний контрольных вершин, блок 309 управления, элемент 308 обработки контрольных вершин, память 312 знаков сообщений, буферную память 314 состояний контрольных вершин и блок 316 извлечения контрольных вершин, которые соединены друг с другом так, как показано на фиг.3. В иллюстрируемом варианте осуществления значение знака для каждого принимаемого сообщения V2C отделено от значения модуля. Значение модуля сообщения подается в процессор 308 контрольных вершин через вход 304, а значение знака, соответствующее каждому принимаемому сообщению, подается в элемент 308 обработки контрольных вершин, а также сохраняется в памяти 312, которая хранит знаковый бит, который нужно использовать впоследствии при генерировании исходящих сообщений С2V на основании хранимого состояния 321, 323.

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

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

Каждый элемент 321, 323 данных состояния соответствует одной контрольной вершине в структуре графа, используемой для управления декодированием. Каждый элемент 321, 323 данных состояния включают в себя S - одно значение бита, которое является результатом операции «исключающее ИЛИ» на знаковых битах, соответствующих каждому принимаемому сообщению V2C, направленному в контрольную вершину, которой упомянутый элемент данных соответствует, минимальное значение m_A, указывающее минимальный модуль принимаемого сообщения, соответствующий конкретной контрольной вершине, второе минимальное значение m_B модуля сообщения, соответствующее конкретной контрольной вершине, и индекс I_A, указывающий ребро сообщения, по которому было принято наименьшее минимальное значение m_A.

Вход 324 управляющего сигнала принимает управляющий сигнал, который используется для управления работой блока обработки контрольных вершин в зависимости от количества ребер графа, а значит - и сообщений, которые будут переданы между элементами обработки вершин переменных и контрольных вершин. Сигнал 324 управления включает в себя информацию, указывающую, какое ребро, а значит - и какое сообщение V2C, принимается на входе 302 в конкретный момент времени. Этот же сигнал можно использовать для запуска генерирования сообщений C2V в случаях, когда имеется фиксированная или известная взаимосвязь между тактированием вводимых сообщений V2C и тактированием желательных выводимых сообщений C2V, что обычно и бывает. Управляющий сигнал 324 подается в блок 309 управления, память 312 знаков сообщений и считывающий блок 316 извлечения (обработки) контрольных вершин. Блок 309 управления использует принимаемый управляющий сигнал, чтобы определить, какой контрольной вершине соответствует принимаемое сообщение V2C. На основании принимаемой информации управления блок управления определяет, какой набор информации 321, 232 о состоянии контрольных вершин должен считываться из памяти 310 состояний контрольных вершин с целью обновления. Таким образом, блок управления определяет на основании информации о ребре ту контрольную вершину, которой соответствует принимаемое сообщение. Сразу же после того как процессор контрольных вершин обновляет полученную в результате выборки информацию о состоянии с использованием информации о принимаемом сообщении, как будет описано ниже, обновленное состояние записывается обратно в элемент 321, 323 данных состояния контрольной вершины, из которого была произведена информация о состоянии с целью его обновления. Этот процесс будет продолжаться до тех пор, пока блок 309 управления не выдаст в элемент 308 обработки контрольных вершин сигнал, указывающий, что состояние контрольной вершины, связанное с конкретной контрольной вершиной, полностью обновлено с использованием последнего сообщения V2C, направленного в эту контрольную вершину в течение конкретной итерации обработки. При полностью обновленном состоянии контрольной вершины процессор контрольных вершин произведет сброс значений в упомянутом состоянии контрольной вершины, записывая значения по умолчанию в состояние контрольной вершины и выдавая полностью обновленное состояние контрольной вершины в буферную память 314 состояний контрольных вершин, используемую для извлечения сообщений. Буферная память 314 состояний контрольных вершин «узнает» о том, какой элемент данных нужно сохранять в обновленной информации о контрольной вершине, на основании управляющего сигнала, полученного с входа 324.

Память 310 состояний контрольных вершин включает в себя вход 327 сообщений об обновленном состоянии контрольных вершин, предназначенный для приема информации о состоянии, которую надо сохранить, и вход 327 управления для приема управляющего сигнала, указывающего, к какому набору информации 321, 323 о состоянии контрольных вершин надо осуществить доступ, а также надо ли сохранять или считывать обновленную информацию о состоянии из указанного набора информации о состоянии контрольных вершин. Информация 321 или 323 о состоянии контрольных вершин, считываемая из памяти состояния контрольных вершин, выводится через выход 329 и подается на вход состояния элемента 308 обработки контрольных вершин, где она используется на операции обновления состояния.

Операция обновления состояния, осуществляемая процессором 308 контрольных вершин на наборе информации о состоянии контрольных вершин, выборка которой осуществлялась из памяти в зависимости от информации, включенной в принимаемое сообщение V2C, является следующей: модуль m_r принимаемого сообщения C2V сравнивается с минимальным модулем m_A в полученной в результате выборки информации о состоянии, соответствующей контрольной вершине, к которой направлено принимаемое сообщение.

Если m_r меньше m_A, то m_B задают равным m_A, чтобы создать обновленное значение m_A, а m_A задают равным m_r, вследствие чего m_r становится обновленным минимумом, а предыдущий минимум становится текущим вторым минимумом для контрольной вершины. Кроме того, индекс I указывает ребро сообщения, которому соответствует минимум m_A, чтобы указать то ребро сообщения, по которому было принято сообщение, подлежащее обработке, например сообщение, обеспечивающее обновленное минимальное значение модуля.

Если m_r меньше m_B, но больше m_A, то m_B задают равным m_r, не изменяя m_A или I.

Если m_r равно или больше m_B, то считанные из памяти значения m_A, m_B и I не изменяются, а обновленное состояние будет включать в себя значения этих элементов, которые считаны из памяти.

Независимо от относительной величины значения принимаемого сообщения и хранимых минимумов накопленный знаковый бит S для контрольной вершины будет обновляться с каждым получаемым в результате выборки сообщением за счет осуществления операции «исключающее ИЛИ» над знаковым битом в принимаемом сообщении, причем этот знаковый бит считывается из сохраненного элемента данных состояния контрольной вершины. Результат операции «исключающее ИЛИ» становится знаковым битом S обновленного элемента данных для контрольной вершины, который записываются обратно в память в случае контрольной вершины, которая не была полностью обновлена, или подается в буферную память 314 состояний контрольных вершин в случае полностью обновленного элемента данных контрольной вершины. Как упоминалось выше, в случае полностью обновленного элемента данных контрольной вершины в элемент 321, 323 данных контрольной вершины, из которого было считано состояние контрольной вершины, будут записаны значения по умолчанию, что приведет к сбросу информации для другой итерации обработки графа. Значения по умолчанию для минимума m_A и второго минимума m_B обычно будут максимальными значениями, которые могут быть присвоены этим элементам.

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

Поскольку полностью обновленная информация о состоянии для контрольной вершины присутствует в виде представления информации, необходимой для генерирования выводимых сообщений C2V, в уплотненном формате, для построения реальных сообщений C2V, выдаваемых через выход 322, используется дополнительная обработка. Считывающий блок 316 обработки, например извлечения контрольных вершин, генерирует полные сообщения C2V исходя из состояния, хранимого в памяти 314 состояний контрольных вершин и хранимых значений знаков, которые хранятся в памяти 312, причем одно значение 313, 315 знака сохраняется для каждого принимаемого сообщения V2C.

Таким образом, по сравнению с воплощениями, где сообщения не хранятся в уплотненном формате, для «считывания» сообщения C2V требуется дополнительная обработка, чтобы осуществить разуплотнение, которое не потребовалось бы, если бы не использовался уплотненный формат хранения. Хранимые значения 313, 315 знаков входящих сообщений считываются непосредственно из памяти знаков. Каждое значение знака, считываемое из памяти 312, подвергается операции «исключающее ИЛИ» с полностью обновленной суммой S, соответствующей контрольной вершине, для получения знака исходящего сообщения, соответствующего ребру сообщения, связанному в исходящим сообщением C2V. Таким образом, знак исходящего сообщения для ребра сообщения генерируется исходя из знака сообщения, принятого по ребру сообщения, а накапливаемое значение S знака, соответствующее операции «исключающее ИЛИ» для полного набора сообщений, соответствует контрольной вершине, с которой соединено упомянутое ребро сообщения в графе кода с МПКЧ. Надежность, например модульная часть сообщения, извлекается из минимального значения, второго минимального значения и значения индекса сообщения, включенных в хранимое состояние для контрольной вершины. Если считываемый индекс ребра соответствует А, то выдается надежность m_A, в противном случае выдается надежность m_B. Существует много возможностей представления индекса А, который служит в качестве идентификатора ребра сообщения. Хотя простое число ребер является одним возможным путем представления индекса А, можно также использовать и другие схемы нумерации и/или способы индексации ребер.

Модуль сообщения, генерируемый блоком 316 извлечения сообщений, выдается на выходе 318 модуля, а знак исходящего сообщения выдается на выходе 320, которые объединены для формирования полного сообщения, выдаваемого через выход 322.

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

На фиг.4 показан возможный декодер 400 кодов с LDPC, воплощенный с использованием блока 300 обработки контрольных вершин, показанного на фиг.3. Декодер 400 осуществляет и обработку вершин переменных, и обработку контрольных вершин в порядке ребер вершин переменных. Декодер 400 включает в себя помимо блока 300 обработки контрольных вершин блок 402 управления декодером, элемент 404 обработки вершин переменных, буфер 406 ввода мягких решений, буфер 412 вывода мягких и жестких решений, блок 408 контроля ограничений и логическую схему 410 управления итерациями.

Вводимые значения, которые надо декодировать, подаются в буфер 406 ввода мягких решений перед загрузкой в элемент 404 обработки вершин переменных. Блок 402 управления декодером реагирует на генерирование управляющих сигналов декодера в соответствии с сохраняемой информации об управлении декодированием, соответствующей структуре графа кода с LDPC, используемой на операциях управления декодированием. Блок управления декодером генерирует управляющие сигналы, используемые для управления работой блока обработки контрольных вершин, рассмотренной выше в связи с фиг.3, а также работой элемента обработки вершин переменных. Под управлением блока управления декодером элемент обработки вершин переменных последовательно загружается частями вводимых данных, подлежащих обработке, например значением принимаемого сообщения, включающим в себя информацию о модуле и знаковый бит. Во время начальной итерации сообщения ограничений, которые должны быть обработаны элементом 404 обработки вершин переменных, не существуют, а сообщения V2C генерируются путем обработки вводимых данных. Сообщения V2C генерируются и выдаются исходя из вводимых данных в порядке ребер сообщений вершин переменных. Генерируемые сообщения V2C, включающие в себя значение модуля и знака, подаются на вход 302 сообщений V2C блока 300 обработки контрольных вершин. Эти сообщения также подаются в блок 408 контроля ограничений, а буфер вывода мягких и жестких решений с попеременным переключением принимает знаковый бит, связанный с каждым генерируемым сообщением V2C. Блок 408 контроля ограничений осуществляет контроль, определяя, удовлетворяют ли значения знаков принимаемых сообщений, соответствующие одной итерации графа декодера, предварительно определенному ограничению декодирования, например осуществляет контроль по четности. Если это происходит в конце итерации передачи сообщения, на протяжении которой было генерирован один полный набор сообщений V2C и C2V, блок 408 контроля ограничений определяет, удовлетворителен ли контроль по четности. Блок 408 генерирует сигнал завершения декодирования, если обнаруживает, что текущая итерации декодирования передачи сообщения привела к успешному декодированию, или, если декодирование не определено как успешное, генерирует сигнал завершения итерации. Сигнал, генерируемый блоком 408 контроля ограничений, подается в логическую схему 410 управления итерациями. В конце каждой итерации сохраненные значения знаков, соответствующие ребрам графа, могут быть выданы из буфера 412 вывода в качестве мягких решений в предположении, что контроль ограничений привел к неудовлетворительному результату, или в качестве жестких решений - в случае, если контроль ограничений привел к удовлетворительному результату.

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

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

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

Блок 300 обработки контрольных вершин согласно настоящему изобретению и обычную систему декодера кодов с LDPC, показанную на фиг.4, можно легко адаптировать в соответствии с настоящим изобретением для поддержки использования многочисленных элементов обработки вершин ограничений и вершин переменных, которые скомпонованы и работают параллельно. На фиг.5 показано, что декодер 500 работает с использованием N вершин ограничений, схем извлечения состояний и элементов обработки вершин переменных, работающих параллельно. Показанные на фиг.5 блок 308' контроля ограничений, логическая схема 310' управления итерациями и буферы 312' и 306' работают так же или аналогично тому, как работают элементы со сходными позициями, описанные в связи с фиг.4. Другие элементы в блоке 300' обработки контрольных вершин тоже работают так же или аналогично тому, как работают элементы со сходными позициями, не включающими в себя символ «'», описанные в связи с фиг.4. Однако в варианте осуществления, показанном на фиг.5, элемент 308' включает в себя N процессоров 308 ограничений, расположенных параллельно, а память 324 состояний вершин ограничений также предназначено для работы с увеличенным в N раз количеством наборов состояний контрольных вершин, тогда как блок 316' извлечения состояний вершин ограничений включает в себя N схем извлечения сообщений. Отметим, что память 310', поддерживая доступ к N наборам информации о состоянии одновременно, не обязательно должна включать в себя все дополнительные элементы данных состояний по сравнению с вариантом осуществления согласно фиг.4, поскольку количество элементов данных состояния определяется количеством контрольных вершин в графе, а не тем, сколько вершин воплощено параллельно.

Вариант осуществления согласно фиг.5 включает в себя блок 502 управления декодером, предназначенный для поддержки N операций широкого декодирования на основе использования описания малых графов и информации управления, указывающей, как изменить малый граф, чтобы генерировать больший граф, предназначенный для управления декодированием. Изменения, вносимые в малый граф, могут быть воплощены в виде переупорядочений, например циклических сдвигов, сообщений, передаваемых между элементами обработки вершин ограничений и контрольных вершин, при этом передача наборов из N сообщений проходит параллельно. В частности, в варианте осуществления согласно фиг.5 переключатели 530, 526, 528 используются для управления переупорядочением сообщений, когда те передаются между различными элементами декодера 500. Переупорядочение зависит от информации описания графа, хранимой в управляющей логической схеме 518, а сигналы циклического сдвига, генерируемые памятью 522 карты перестановок, зависят от счетчика 520 столбцов, запускаемого управляющей логической схемой 518. Управляющие сигналы циклического сдвига, используемые для управления переупорядочением сообщений, подаваемых в блок 300' обработки контрольных вершин, генерируются путем задержки посредством линии 524 задержки некоторых сигналов циклического сдвига, используемых для управления изменяемым переупорядочением сообщений, подаваемых на вход элементов 504 обработки вершин переменных.

Описав блок 300 обработки контрольных вершин и различные декодеры 400 и 500 кодов с LDPC, воплощаемые в соответствии с настоящим изобретением, перейдем теперь к рассмотрению различных признаков, касающихся схемы графа, структуры кода LDPC и воплощений декодирования с использованием конкретных структур графов в декодерах, воплощающих настоящее изобретение.

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

Вместе с тем благодаря разумной схеме графа можно смягчить проблему задержки независимо от того, где - в декодере 400 или параллельном декодере 500 - она возникает.

Предположим, что множество проектируемых вершин V переменных можно разделить на несколько множеств, например, по меньшей мере, на множества SV1 и SV2, где SV1 предшествует SV2, а множество проектируемых контрольных вершин С можно разделить, по меньшей мере, на два множества SC1 и SC2 таким образом, что контрольные вершины в SC1 соединены ребрами в графе только с вершинами переменных в SV1. Затем, если обработка осуществляется в порядке вершин переменных, то первыми будут обрабатываться сообщения, соответствующие вершине V1 переменной, затем - сообщения, соответствующие вершине V2 переменной, затем - сообщения, соответствующие вершине V3 переменной, и так далее. В таком случае обработка сообщений, соответствующих первому множеству SC1 контрольных вершин, будет завершена к моменту, когда будет обработана последняя вершина переменной в SV1, или до этого момента, если последняя контрольная вершина в SC1 не соединена с последним ребром последней вершины переменной в SV2. Получаемое состояние полного завершения, соответствующее контрольным вершинам во множестве SC1, можно хранить в памяти состояний контрольных вершин для использования при генерировании сообщений V2C, когда начинается обработка сообщений V2C из вершины V1 переменной для следующей итерации графа. Таким образом, следующую итерацию обработки графа можно начинать, когда блок 300 обработки вершин ограничений еще обрабатывает сообщения V2C, соответствующие незавершенной итерации обработки графа.

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

На фиг.6 показаны код с LDPC и соответствующая структура 600 графа с такими свойствами. Показанный на фиг.6 граф включает в себя 8 контрольных вершин 602, обозначенных символами С₁-С₈, и 16 вершин переменных, обозначенных символами V₁-V₁₆. Отметим, что к моменту, когда сообщения из вершин V₁-V₁₂ переменных, включенных во множество SV1 вершин переменных, обрабатываются блоком 300 обработки вершин ограничений, состояние, соответствующее первым 4-м вершинам С₁-С₄ ограничений, будет полностью обновлено. Это полностью обновленное состояние будет передано в буферную память 314 вершин ограничений с удалением элементов данных вершин ограничений, соответствующих вершинам С₁-С₄ ограничений, которые надо использовать на следующей итерации обработки графа. Таким образом, поскольку обработка применительно к вершинам ограничений во множестве SC2, т.е. вершинам С5, С6, С7 и С8 ограничений, продолжается в течение одной итерации, сообщения C2V для этой итерации, соответствующие вершинам во множестве SC1, будут генерироваться, и в то же время возникнет возможность начать обработку вершин ограничений для следующей итерации, перекрывающуюся с происходящей обработкой, связанной с текущей итерацией.

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

Фиг.7 иллюстрирует относительно простой граф, который будет использоваться для пояснения обработки посредством декодера, например обработки, которая происходит, когда декодер 400 согласно фиг.4 используется для декодирования возможного набора вводимых данных, имеющих значения 0, -1, 5 и 4 сообщений, которые загружаются в вершины переменных во время первой итерации обработки графа.

Показанный на фиг.7 граф 700 включает в себя в общей сложности три контрольных вершины 702 и четыре вершины 706 переменных, соединенные друг с другом ребрами, количество которых составляет 9, в порядке вершин переменных от 0 до 8. Отметим, что если бы ребра были пронумерованы со стороны контрольных вершин, то ребра имели бы другую последовательность нумерации, потому что они появляются в контрольных вершинах в другом порядке, нежели в вершинах переменных. Сообщения передаются назад и вперед между вершинами 706 переменных и контрольными вершинами 702 по изображенным ребрам. Контрольные вершины 702 включают в себя с первой по третью контрольные вершины 710, 712, 714, а вершины 706 переменных включают в себя с первой по четвертую вершины 720, 722, 724, 726 переменных.

На фиг.8 показаны разные результирующие значения использования декодера 400 и структуры кода, показанной на фиг.7. Фиг.8 иллюстрирует результаты двух полных итераций обработки посредством декодера, следующих за начальной итерацией, используемой для загрузки принимаемых сообщений (0, -1, 5 и 4) в декодер 400 и начальной обработки этих сообщений. Знак «минус» используется перед вторым вводимым значением, чтоб указать отрицательный знаковый бит, эквивалентный биту «1» и связанный с сообщением, тогда как отсутствие знака «минус» указывает положительный знаковый бит, эквивалентный биту «0». Таким образом, второе сообщение -1 имеет отрицательный знаковый бит, тогда как первое, третье и четвертое сообщения имеют положительный знаковый бит. В конце первой итерации обработки элементы данных памяти состояний, соответствующие С1, С2 и С3, будут включать в себя значения, показанные вверху фиг.8, в наборе значений 802 элементов данных памяти состояний.

Итерация начинается извлечением сообщений V2C. На начальной итерации выделяемые сообщения C2V задаются равными 0. В качестве части текущей итерации эти сообщения суммируются в вершинах переменных и генерируются сообщения V2C. Эти сообщения принимаются процессором контрольных вершин, который обновляет состояние контрольных вершин, связанное с текущей итерацией. Итерация завершается, когда обновлены все состояния контрольных вершин.

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

Вообще говоря, столбцы 810, 812, 816 и 820 иллюстрируют извлечение сообщений C2V с использованием результатов, которые проявились на предыдущей итерации декодирования. Столбец 822 показывает суммы вершин переменных, которые являются суммами всех сообщений, входящих в вершину переменной, и принимаемого значения, связанного с вершиной переменной.

Столбец 824 показывает сообщение V2C, которое будут генерироваться по соответствующему ребру в итерации. Оно равно сумме вершин переменных за вычетом входящего сообщения C2V. Эти сообщения C2V будут приниматься процессором вершин ограничений и использоваться для обновления информации о состоянии, как показано в столбцах 826, 828, 830. Столбцы 826, 828, 830 показывают, как обрабатываемое состояние контрольной вершины обновляется во время текущей итерации обработки в ответ на прием каждого сообщения V2C, показанного в столбце 824.

Информация 810 показывает состояние контрольных вершин, генерированное во время предыдущей итерации обработки графа, считанной из буферной памяти 314 состояний вершин ограничений, для генерирования сообщений С2V. Это полностью обновленное состояние, соответствующее каждой контрольной вершине, которое генерируется во время предыдущей итерации обработки, используется для генерирования сообщений C2V, которые обрабатываются процессором 304 вершин переменных на текущей итерации графа для генерирования сообщений V2C. Столбец 812 иллюстрирует знаковый бит, соответствующий сообщению V2C из предыдущей итерации, который идет по ребру и выборка которого осуществляется из памяти 312 знаковых битов для построения сообщения C2V в текущей итерации обработки, которое будет введено в процессор вершин переменных, генерирующий сообщение V2C для текущей итерации обработки. Столбец 814 иллюстрирует обновленный знаковый бит, генерируемый состоянием вершины ограничения, извлекаемым посредством операции «исключающее ИЛИ» над хранимым знаковым битом 812 из предыдущего принимаемого сообщения V2C и хранимым накопленным знаковым битом S, генерируемым на предыдущей итерации и получаемым из состояния, соответствующего контрольной вершине (С1, С2 или С3), которой соответствует ребро сообщения, связанное с сообщением C2V. Столбец 816 указывает результат контроля, проводимого блоком извлечения состояний вершин ограничений для того, чтобы определить, следовало ли выдавать первый минимум m_A или второй минимум m_B во время предыдущей итерации обработки. Упомянутый контроль предусматривает сравнение индекса ребра сообщения C2V, генерируемого с индексом I ребра, соответствующим хранимому первому минимуму. Здесь «Y» указывает результат «Да», означающий, что индекс ребра соответствует ребру, которое обеспечивало передачу минимального модуля в предыдущей итерации, а «N» указывает результат «Нет», означающий, что индекс ребра не соответствует ребру, которое обеспечивало передачу минимального модуля в предыдущей итерации. Столбец 812 иллюстрирует результат выбора значения m_A или m_B, которое должно быть использовано в качестве модуля исходящего сообщения C2V. Столбец 820 показывает реальное сообщение C2V, которое будет передано по указанному ребру для использования процессором 304 вершин переменных во время текущей итерации. Процессор 304 вершин переменных генерирует сумму сообщений C2V, принимаемых во время итерации обработки. Результирующая сумма вершин переменных, показанная в столбце 822, затем используется для генерирования сообщения C2V, подаваемого в блок 300 обработки вершин ограничений по ребру сообщения, например, для обработки вершины ограничения во время текущей итерации.

По изображению блока обработки вершин ограничений можно сказать, что информация, показанная в столбцах 810, 812, 814, 816, 818, 820 и 822, отображает операции, которые происходят на основании результата, вычисленного на предыдущей операции обработки графа. Как сказано выше, при условии тщательной проработки схемы графа в нем может быть обеспечено некоторое перекрытие, когда эти операции проходят на протяжении одной итерации обработки графа и когда происходит обновление состояния сообщения для следующей итерации обработки вершин ограничений.

Столбец 824 иллюстрирует сообщение V2C, которое будет принято и обработано во время второй и третьей итераций, проводимых блоком обработки вершин ограничений и соответствующих обработке возможных вводимых данных с использованием структуры графа, показанной на фиг.7. Каждая итерация графа предусматривает обработки девяти сообщений V2C, соответствующих сообщениям, передаваемым по ребрам Е0-Е8. Обработка сообщений блоком 300 обработки вершин ограничений происходит в порядке ребер вершин переменных. В начале этой обработки произойдет повторная инициализация памяти ограничений, соответствующей контрольным вершинам. В предположении отсутствия перекрытия на итерациях обработки состояние каждой из контрольных вершин С1, С2 и С3 будет повторно инициализировано для приема первого сообщения V2C, соответствующего ребру Е0. Каждый из столбцов 826, 828, 830 показывает хранимое состояние, соответствующее одной из контрольных вершин С1, С2, С3 соответственно, после его обновления принимаемым сообщением V2C, при этом каждая строка соответствует обработке отличающегося сообщения V2C. Содержимое состояния, обновленное в ответ на некоторое конкретное сообщение, например сообщение, передаваемое по ребру, которому соответствует строка, показано полужирным шрифтом. Символы Х используются в столбцах 826, 828, 830, чтобы показать значения, которые заданы равными начальному значению. Эти значения являются «безразличными» значениями, поскольку они не будут использоваться в генерируемом выводимом сообщении С2V.

Отметим, что в конце второй итерации полностью обновленные состояния С1, С2, С3 сообщения будут обновлены с достижением значений (m_A=0, m_B=4, I=2, S=0) для С1, (m_A=1, m_B=3, I=1, S=1) для С2, и (m_A=1, m_B=3, I=3, S=1) для С3. В конце третьей итерации полностью обновленные состояния С1, С2, С3 сообщения будут обновлены с достижением значений (m_A=1, m_B=3, I=2, S=0) для С1, (m_A=0, m_B=3, I=1, S=0) для С2, и (m_A=3, m_B=3, I=3, S=0) для С3.

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

При задании различных структур кодов, с которыми можно использовать декодер и способы согласно настоящему изобретению, оказывается возможной значительная гибкость применительно к величине перекрытия, которое может возникать между итерациями обработки. Чтобы уменьшить задержки при декодировании в связи с перекрытиями применительно к проведению обработки контрольных вершин в соответствии с различными итерациями декодирования, структуру кода можно выбрать обеспечивающей перекрытие в итерациях обработки графа, составляющее 10%, 20%, 30%, 40% или более.

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

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

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

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

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

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

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

Возможны многочисленные варианты вышеописанных способов и устройств, остающиеся в рамках объема притязаний изобретения. Например, хотя применительно к сообщениям речь шла об уплотненном состоянии, информацию знака для сообщений C2V можно генерировать немного не так, как описано выше, но это все равно будет в рамках объема притязаний изобретения. Альтернативное воплощение предусматривает использование структуры с попеременным переключением, при наличии которой одна память используется как память состояний, а другая содержит полные состояния с предыдущей итерации, причем в конце итерации буферные памяти меняются ролями друг с другом. В таком варианте осуществления со знаковым битом нужно обращаться следующим образом. Сохраняют знаки сообщений V2C. В дополнение к информации о надежности поддерживают в качестве части состояния результат операции «исключающее ИЛИ» для входящих знаковых битов. При извлечении сообщений C2V подвергают хранимый знак сообщения V2C операции «исключающее ИЛИ» с накопленным результатом операции «исключающее ИЛИ» в этом состоянии, получая знаковый бит сообщения C2V. Отметим, что сразу же после считывания знаковый бит сообщения V2C больше не нужен, так что поверх него можно впоследствии записать знаковый бит сообщения V2C, который вскоре будет генерирован процессором вершин переменных.

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

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

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

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

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

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

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

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

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

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

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

11. Устройство по п.10, которое также содержит
блок управления декодером, соединенный с блоком обработки контрольных вершин и с блоком обработки вершин переменных, причем блок управления декодером управляет и блоком обработки контрольных вершин, и блоком обработки вершин переменных, для обработки сообщений в порядке вершин переменных.

12. Устройство по п.11, в котором процессор вершин переменных включает в себя множество параллельно расположенных элементов обработки вершин переменных.

13. Устройство по п.12, в котором блок обработки контрольных вершин включает в себя множество параллельно расположенных элементов обработки контрольных вершин.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

31. Способ по п.30, в котором первый и второй периоды времени одинаковы по продолжительности.

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

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

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

35. Способ по п.30, в котором первый период времени составляет менее 40% того времени, которое требуется для обработки N сообщений от вершин переменных к контрольным вершинам, где N равно суммарному количеству ребер сообщений в графе, соответствующем коду с LDPC, используемому для управления декодированием.

36. Способ по п.30, в котором первый период времени составляет менее 20% того времени, которое требуется для обработки N сообщений от вершин переменных к контрольным вершинам, где N равно суммарному количеству ребер сообщений в графе, соответствующем коду с LDPC, используемому для управления декодированием.