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

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

Иллюстрации

Показать все

Реферат

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