Устройство декодирования, устройство хранения данных, система обмена данными и способ декодирования

Устройство декодирования, устройство хранения данных, система обмена данными и способ декодирования

Иллюстрации

Показать все

Реферат

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

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

Предшествующий уровень техники

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

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

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

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

Если каждый элемент из принятых данных выражается b битами (b представляет собой положительное целое число), то требуется область хранения b × N битов, для запоминания блока из N принятых данных. Поскольку запоминается столько же сообщений как количество ненулевых элементов проверочной матрицы, то требуется область хранения из b × (количество ненулевых элементов) для запоминания в ней сообщений. Ненулевые элементы относятся к элементам, имеющим значение 1, но не 0.

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

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

<Список Документов>

Документ 1: JP 2007-089064 A.

Документ 2: Robert Gallager, “Low-Density Parity-Check Codes”, IEEE Transactions on Information Theory, January 1962, страницы с 21 по 28.

Документ 3: D. J. C. MacKay, “Good Error-Correcting Codes Based on very sparse matrices”, IEEE Transactions on Information Theory, March 1999, страницы с 399 по 431.

Документ 4: Eran Sharon, Simon Litsyn, Jacob Goldberger, “An Efficient Message-Passing Schedule for LDPC Decoding”, Proceedings 2004 IEEE Convention of Electrical and Electronics Engineers in Israel, September 2004, страницы с 223 по 226.

Документ 5: E Yeo, P. Pakzad, B. Nikolic, V Anantharam, “High Throughput Low-Density Parity-Check Decoder Architecture”, 2001 IEEE Global Telecommunications Conference, November 2001, страницы с 3019 по 3024.

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

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

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

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

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

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

первое средство хранения для хранения стольких же элементов данных как количество векторов-столбцов проверочной матрицы упомянутого кода с малой плотностью проверок на четность;

второе средство хранения для хранения того же самого количества данных как в упомянутом первом средстве хранения;

средство преобразования данных; и

средство обработки проверочного узла;

в котором упомянутое средство преобразования данных создает первые промежуточные данные, находящиеся во взаимно-однозначном соответствии с упомянутыми векторами-столбцами, из данных, хранящихся в упомянутом первом средстве хранения, и данных, хранящихся в упомянутом втором средстве хранения;

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

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

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

В соответствии с аспектом настоящего изобретения предоставляется устройство хранения данных, содержащее:

устройство кодирования для кодирования данных, которые следует сохранить в устройстве хранения, согласно коду с малой плотностью проверок на четность; и

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

В соответствии с аспектом настоящего изобретения предоставляется система обмена данными, содержащая:

устройство передачи для передачи данных, кодированных посредством кода с малой плотностью проверок на четность;

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

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

хранят столько же элементов данных как количество векторов-столбцов проверочной матрицы упомянутого кода с малой плотностью проверок на четность в первом средстве хранения;

хранят то же самое количество данных как в упомянутом первом средстве хранения во втором средстве хранения;

создают первые промежуточные данные, запомненные во взаимно-однозначном соответствии с упомянутыми векторами-столбцами, из данных, хранящихся в упомянутом первом средстве хранения, и данных, хранящихся в упомянутом втором средстве хранения;

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

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

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

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

На фиг.1А изображена блок-схема конфигурационного примера устройства декодирования согласно примерному варианту осуществления настоящего изобретения.

На фиг.1В изображена последовательность операций функционального примера устройства декодирования согласно примерному варианту осуществления.

На фиг.2 изображена блок-схема конфигурационного примера преобразователя 13 данных, показанного на фиг.1А.

На фиг.3 изображена блок-схема конфигурационного примера процессора 14 проверочного узла, показанного на фиг.1А.

На фиг.4 изображена блок-схема конфигурационного примера блока (F) 11 запоминающего устройства, показанного на фиг.1А.

На фиг.5 изображена блок-схема конфигурационного примера блока (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства, показанного на фиг.1А.

На фиг.6 изображена блок-схема конфигурационного примера процессора параллельных проверочных узлов.

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

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

Лучший вариант для выполнения изобретения

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

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

Как показано на фиг.1А, устройство 10 декодирования включает в себя блок (F) 11 запоминающего устройства, блок (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства, преобразователь 13 данных, процессор 14 проверочного узла и сумматор 15. На устройство 10 декодирования подается входной сигнал, содержащий последовательность принятых данных из канала связи (не показан). Последовательность принятых данных закодирована посредством кода с малой плотностью проверок на четность. Обычно принятые данные включают в себя ошибки из-за шума и тому подобного. Устройство 10 декодирования оценивает последовательность битов передачи из принятых данных и выводит оцененную последовательность битов передачи.

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

[Уравнение 1]

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

[Уравнение 2]

Уравнение (2) представляет собой блочную матрицу r × n (r = R/m, n = N/m), имеющую элементы матрицы m × m (m представляет собой кратный делитель N). Каждая из матриц m × m I_s,t(0 ≤ s < r, 0 ≤ t < n) представляет собой матрицу с циклической перестановкой или матрицу, чьи элементы - все нули.

Полагается, что последовательность принятых данных из канала связи представлена посредством F₀, F₁, …, F_N-1, и что каждый символ F₁ последовательности принятых данных представлен b битами, где i представляет собой целое число, изменяющееся от 0 до N-1, и b - положительное целое число.

Блок (F) 11 запоминающего устройства является устройством для хранения последовательности F₀, F₁, …, F_N-1 принятых данных, и требуется, чтобы он имел емкость хранения b × N.

Блок (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства является устройством для хранения данных L₀ ⁽¹⁾, L₁ ⁽¹⁾, …, L_N-1 ⁽¹⁾, L₀ ⁽²⁾, L₁ ⁽²⁾, …, L_N-1 ⁽²⁾, которые должны быть временно запомнены в процессе декодирования, и требуется, чтобы он имел емкость хранения 2 × b × N битов. Данные L₀ ⁽¹⁾, L₁ ⁽¹⁾, …, L_N-1 ⁽¹⁾, L₀ ⁽²⁾, L₁ ⁽²⁾, …, L_N-1 ⁽²⁾ будут описаны далее.

Каждый из R векторов-строк (h_i,0, h_i,1, …, h_i,N-1) (i представляет собой целое число в диапазоне 0 ≤ i < R) проверочной матрицы согласно уравнению (1) имеет ненулевые элементы, чьи позиции можно указать согласно уравнению (3) ниже посредством частного множества U(i) множества N целых чисел, изменяющегося от 0 до N-1. Другими словами, U(i) представляет собой множество, указывающее позиции ненулевых элементов i-ого вектора-строки проверочной матрицы. В блоке (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства запомнены данные адресов, определенных посредством U(i). Конкретные операции преобразователя 13 данных, процессора 14 проверочного узла и сумматора 15 будут описаны далее.

[Уравнение 3]

На фиг.2 изображена блок-схема конфигурационного примера преобразователя 13 данных, показанного на фиг.1А. Как показано на фиг.2, преобразователь 13 данных включает в себя соединители 21А, 21В битов, делители 22А, 22В битов, сумматор 23, схему 24 вычитания, схемы 25, 27 выбора и устройство 36 задержки.

На преобразователь 13 данных подаются входные сигналы, представленные посредством 2b-битных данных, считанных из блока (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства, показанного на фиг.1А, и выходные сигналы b-битных данных от процессора 14 проверочного узла. 2b-битные данные, считанные из блока (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства, преобразуются делителем 22А битов, схемой 24 вычитания и схемой 25 выбора в 2b-битные данные, которые выводятся на сумматор 15, показанные на фиг.1А.

b-битные данные доставляются через соединитель 21А, устройство 26 задержки и делитель 22В битов в сумматор 23, который суммирует b-битные данные и b-битные данные, выведенные от процессора 14 проверочного узла. Суммарные данные преобразуются соединителем 21А битов в 2b-битные данные, которые выводятся в блок (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства. 2b-битные данные записываются в блок (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства.

Конфигурация, показанная на фиг.2, применяется там, где 2b-битные данные запомнены по одинаковым адресам в блоке (F) 11 запоминающего устройства, показанном на фиг.1А. Если 2b-битные данные делятся и запомнены в качестве 2b-битных данных, то обходятся без делителей 22А, 22В битов и соединителей 21А, 22А битов.

На фиг.3 изображена блок-схема конфигурационного примера процессора 14 проверочного узла, показанного на фиг.1А. Как показано на фиг.3, процессор 14 проверочного узла включает в себя делители с 31А по 31С битов, таблицы с 32А по 32С преобразования данных, сумматор 33, схемы с 34А по 34С вычитания, таблицы с 35А по 35С преобразования данных, соединители с 36А по 36С битов и арифметические блоки 37, с 38А по 38С исключающего-ИЛИ.

На процессор 14 проверочного узла подается входной сигнал, представленный выходным сигналом от сумматора 15, показанного на фиг.1А. Выходной сигнал от процессора 14 проверочного узла является входным сигналом для преобразователя 13 данных, показанного на фиг.1А. Процессор 14 проверочного узла выполняет обработку этапа 103 в последовательности операций, показанной на фиг.1В.

Согласно примеру функций, используемых при обработке этапа 103, функция f(Z~) представлена уравнением (4) ниже, а обратная функция f^-1(Z~) - уравнением (5) ниже.

[Уравнение 4]

Функция f(Z~) согласно уравнению (4) является функцией для возвращения двух значений, т.е. результата знака функции, который возвращает 1, когда Z~ является Z~ < 0, и возвращает 0 в противном случае, значения, соответствующего логарифму функции гиперболического тангенса. Обратная функция f^-1(Z~) функции f(Z~) согласно уравнению (4) является функцией, в которую подаются входные значения, представленные двумя численными значениями S, Z и возвращает значение, представленное правой частью уравнения (5).

[Уравнение 5]

Процессор 14 проверочного узла повторяет обновление данных в блоке (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства заданное количество раз. Логарифм функции гиперболического тангенса в уравнении (4) вычисляется посредством таблицы 32 преобразования данных, а функция правой части уравнения (5) вычисляется посредством таблицы 35 преобразования данных.

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

На фиг.4 изображена блок-схема конфигурационного примера блока (F) 11 запоминающего устройства, показанного на фиг.1А. Как показано на Фиг.4, блок (F) 11 запоминающего устройства содержит n (n = N/m) RAM 41. Каждое из RAM 41 имеет битовую длину в bp с количеством слов, представленных посредством m/p. Полная емкость хранения n RAM 41 представлена bN битами.

По каждому адресу каждого RAM 41 запоминается p принятых данных. По k-му (0 ≤ k < m/p) адресу j-ого (0 ≤ j < n) RAM 41 находится p принятых данных, представленных уравнением (6) ниже.

[Уравнение 6]

К принятым данным, запомненным в блоке (F) 11 запоминающего устройства, повторно обращаются во время выполнения процесса декодирования. Процесс создания адресов для считывания для каждого RAM 41 будет описан позже.

На фиг.5 изображена блок-схема конфигурационного примера блока (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства, показанного на фиг.1А. Как показано на фиг.5, блок (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства содержит n RAM 51. Каждое из RAM 51 имеет битовую длину в 2bp с количеством слов, представляемых посредством m/p. Полная емкость хранения n RAM 51 представлена bN битами.

По каждому адресу каждого RAM 51 запоминается 2р промежуточных данных. k-ый (0 ≤ k < m/p) адрес j-ого (0 ≤ j < n) RAM запоминает 2p данных, представленных уравнением (7) ниже.

[Уравнение 7]

К данным, запомненным в блоке ((L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства, повторно обращаются и обновляют их в течение процесса декодирования. Процесс создания адресов для считывания и адресов для записи для каждого RAM 51 будет описан ниже.

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

Как показано на фиг.1В, устройство 10 декодирования выполняет процесс инициализации (этап 101). При процессе инициализации устройство 10 декодирования записывает последовательность F₀, F₁, …, F_N-1 принятых данных в блок (F) 11 запоминающего устройства. Каждый символ F₁ из последовательности принятых данных представлен b битами (0 ≤ i < N, b представляет собой целое число). Устройство 10 декодирования инициализирует все данные L₀ ⁽¹⁾, L₁ ⁽¹⁾, …, L_N-1 ⁽¹⁾, L₀ ⁽²⁾, L₁ ⁽²⁾, …, L_N-1 ⁽²⁾ в блоке (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства как 0. Устройство 10 декодирования инициализирует счетчик для счета количества раз, которое повторяется (t = 1) процесс декодирования. Поскольку структура счетчика очевидна, он пропущен на иллюстрации в блок-схеме фиг.1А для того, чтобы избежать иллюстративных сложностей.

После процесса декодирования устройство 10 декодирования устанавливает переменную i, которая представляет собой индекс векторов-строк проверочной матрицы в начальное значение 0 (этап 102).

Затем устройство 10 декодирования обновляет L_j ⁽¹⁾ относительно каждого элемента j в множестве U(i) (см. уравнение (3)), которое указывает позиции ненулевых элементов в i-том векторе (этап 103). В это время устройство 10 декодирования считывает данные F_j из блока (F) 11 запоминающего устройства и считывает данные L_j ⁽¹⁾, L_j ⁽²⁾ из блока (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства. Затем устройство 10 декодирования вычисляет F_j + L_j ⁽¹⁾, используя сумматор 15. Устройство 10 декодирования вычисляет F_j + L_j ⁽¹⁾ относительно всех j, включенных в U(i), и вводит вычисленные суммы в процессор 14 проверочного узла. Процессор 14 проверочного узла обрабатывает все целые числа j, включенные в U(i), и обновляет L_j ⁽¹⁾ в обработанные результаты в качестве новых значений. Новые значения записываются в блок (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства. В течение этого времени к данным F_j, L_j ⁽¹⁾, L_j ⁽²⁾ осуществляют доступ для каждого j = 0, 1, …, N-1 столько же раз, каково количество ненулевых элементов в j-ом векторе-столбце проверочной матрицы.

Устройство 10 декодирования выполняет обработку этапа 103 успешно относительно i = 0, 1, …, R-1, соответствующих векторам-строкам проверочной матрицы (этапы 104, 105).

Затем устройство 10 декодирования определяет x_j так, что x_j=1, когда F_j + L_j ⁽¹⁾ представляет собой отрицательное значение, и x_j = 0 в противном случае (этап 106). Устройство 10 декодирования повторяет обработку этапа с 102 по 106, пока не выполнено (этапы с 107 по 109) одно из двух условий, что произведение Нх_Т проверочной матрицы и (x₀, x₁, …, x_N-1) является Нх_Т = 0 и t = Tmax (максимальное значение t).

Операция обработки (этап 109) преобразователя 13 данных, показанного на фиг.2, которая в действительности выполняется за раз, будет описана позже.

Если синдром, вычисленный посредством произведения (x₀, x₁, …, x_N-1) и проверочной матрицы, полученного посредством вышеупомянутой обработки, является 0, то устройство 10 декодирования оценивает (x₀, x₁, …, x_N-1) в качестве последовательности данных передачи, выводит последовательность данных передачи, и завершает процесс декодирования (этап 110). Устройство для вычисления произведения (x₀, x₁, …, x_N-1) и проверочной матрицы пропущено на иллюстрации в блок-схеме на фиг.1А для того, чтобы избежать иллюстративных сложностей.

Работа преобразователя 13 данных на этапе 109 описана ниже.

Обработка этапа 109 является процессом для обновления данных L_j ⁽¹⁾, L_j ⁽²⁾ в блоке (L⁽¹⁾, L⁽²⁾) запоминающего устройства соответственно в данные L_j ⁽¹⁾-L_j ⁽²⁾, L_j ⁽¹⁾-L_j ⁽²⁾ относительно j = 0, 1, …, N-1. Процесс обновления выполняется однократно каждый раз, когда повторяется процесс декодирования. Каждый раз, когда повторяется процесс декодирования, к данным L_j ⁽¹⁾, L_j ⁽²⁾ осуществляют доступ столько же раз, каково количество ненулевых элементов в j-ом векторе-столбце проверочной матрицы. Только когда преобразователь 13 данных считывает данные L_j ⁽¹⁾, L_j ⁽²⁾ за один доступ (обращение), преобразователь 13 данных обновляет их в L_j ⁽¹⁾ = L_j ⁽¹⁾-L_j ⁽²⁾, L_j ⁽²⁾ = L_j ⁽¹⁾-L_j ⁽²⁾ и выводит обновленные данные.

На фиг.2 изображена конфигурация преобразователя 13 данных, когда в блоке (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства запомнены 2b-битные данные по каждому адресу со старшими b битами, представляемыми посредством L_j ⁽¹⁾, и младшими b битами посредством L_j ⁽²⁾. На Фиг.2 2b-битные данные считываются из адресов j (0 ≤ j < N9) блока (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства и вводятся в преобразователь 13 данных, причем 2b-битные данные имеют старшие b битов, представленных посредством L_j ⁽¹⁾, и младшие b битов посредством L_j ⁽²⁾. 2b-битные данные делят посредством делителя 22А битов на старшие b битов (L_j ⁽¹⁾) и младшие b битов (L_j ⁽²⁾). L_j ⁽¹⁾ и L_j ⁽¹⁾-L_j ⁽²⁾ из схемы 24 вычитания вводятся в схему 25 выбора.

Как описано выше, каждый раз, когда повторяется процесс декодирования, схема 25 выбора выбирает L_j ⁽¹⁾-L_j ⁽²⁾, когда осуществляют доступ по адресу j в первый раз, и выбирает L_j ⁽¹⁾ в противном случае. Выходной сигнал схемы 25 выбора выводится в сумматор 15. L_j ⁽²⁾ соединен с младшими b битами посредством соединителя 21А битов, который вводит соединенные данные в устройство 26 задержки.

Устройство 26 задержки задерживает входной сигнал на время, требуемое операцией обработки процессора 14 проверочного узла, и вводит задержанный сигнал в делитель 22В битов. Делитель 22В битов делит входной сигнал на старшие b биты и младшие b биты и вводит их обоих в схему 27 выбора. Старшие b битов представлены посредством либо L_j ⁽¹⁾ или L_j ⁽¹⁾-L_j ⁽²⁾, а младшие b битов посредством L_j ⁽²⁾. Старшие b битов также вводятся в сумматор 23, который добавляет старшие b битов к данным из процессора 14 проверочного узла. Суммарные данные из сумматора 23 и b битов, выведенных из схемы 27 выбора, соединяются друг с другом посредством соединителя 21В битов, и соединенные данные сохраняются по адресу j в блоке (L⁽¹⁾, L⁽²⁾) запоминающего устройства.

Таким образом, преобразователь 13 данных создает данные, которые следует отправить в сумматор 15, посредством выбора либо данных L_j ⁽¹⁾, либо данных, полученных вычитанием L_j ⁽²⁾ из L_j ⁽¹⁾. Преобразователь 13 данных обновляет данные L_j ⁽²⁾ посредством выбора либо данных L_j ⁽¹⁾, либо данных, полученных вычитанием L_j ⁽²⁾ из L_j ⁽¹⁾.

Согласно настоящему примерному варианту осуществления, как описано выше, данные, запомненные в блоке (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства, преобразуются и обрабатываются для получения декодированного результата. Поскольку только полные 2b-битные данные, сделанные из b-битных данных L_j ⁽¹⁾, и поскольку b-битные данные могут запоминаться относительно каждого вектора-столбца проверочной матрицы, то емкость запоминающего устройства для запоминания в ней данных может быть меньше, чем в существующем способе декодирования.

В частности, согласно настоящему примерному варианту осуществления полные 2b-битные данные L_j ⁽¹⁾, L_j ⁽²⁾ запоминают относительно j-ого вектора (j = 0, 1, …, N-1), например, и обновляются и обрабатываются. Способ декодирования согласно настоящему примерному варианту осуществления требует меньшей емкости хранения для запоминания в ней данных, чем существующий способ декодирования, в котором запомнены b-битные данные относительно каждого вектора-строки, например i-ый вектор (i = 0, 1, …, R-1), и элементов множества U(i), а также обновляет и обрабатывает данные.

Устройство 10 декодирования согласно настоящему примерному варианту осуществления осуществляет запоминание принятых данных в блоке (F) 11 запоминающего устройства само по себе и обрабатывает принятые данные. Однако настоящее изобретение не ограничивается такой конфигурацией. Согласно другому варианту осуществления носитель записи с записанными на нем данными, кодированными посредством кода с малой плотностью проверок на четность, может загружаться в устройство 10 декодирования, и устройство 10 декодирования может обращаться к данным и декодировать данные, записанные в носителе записи. В этом случае, обходятся без блока (F) 11 запоминающего устройства.

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

Последовательность параллельной обработки, которая применяется к процессу декодирования для декодирования квазициклического кода с малой плотностью проверок на четность, имеющего проверочную матрицу, указанную посредством уравнения (2), описана ниже. Полагается, что количество p операций параллельной обработки представляется посредством кратного делителя m, который представляет собой размер циклических матриц в качестве элементов проверочной матрицы, указанной посредством уравнения (2). В этом случае блок (F) 11 запоминающего устройства и блок (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства являются идентичными по конфигурации к тем, что показаны на фиг.4 и 5, соответственно. Структуры данных в RAM в блоках запоминающего устройства являются теми же самыми, что те, что представлены уравнениями (6), (7). Количество RAM, включенных в каждый блок запоминающего устройства, равно n. Процесс создания адресов для осуществления доступа к каждому RAM является тем же самым для блока (F) 11 запоминающего устройства и блока (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства как в случае вышеупомянутого примерного варианта осуществления для последовательной обработки. Поэтому только блок (L⁽¹⁾, L⁽²⁾) 12 запоминающего устройства будет описываться ниже. Значения A(i,j) r начальных адресов (0 ≤ i < r, 0 ≤ j <n) назначаются каждому из n RAM. Значение A(i,j) i-ого начального адреса j-ого RAM определяется следующим образом:

[Уравнение 8]

где k^(i,j) представляет собой целое число, указывающее позиции ненулевых элементов в первом векторе-столбце матрицы I_i,j m × m с циклической перестановкой, которая является (i,j) элементом проверочной матрицы согласно уравнению (2) (0 ≤ k^(i,j) < m). Значение A(i,j) адреса находится в соответствии с остатком, полученным от деления k^(i,j) на m/p. Адреса для считывания данных из и записи данных в каждый RAM создаются в r образцах. r образцов являются идентичными в том смысле, что только значения начальных адресов отличаются, а последующие адреса создаются просто добавлением 1.

Каждый образец для создания адресов меняется через периоды в единицу времени в m/p. Например, значение первого начального адреса j-ого RAM является A(0,j), и считываются данные согласно уравнению (7), где k = A(0,j). Затем считываются данные по значению A(0,j)+1 адреса согласно уравнению (7), где k = A(0,j)+1. Впоследствии 1 добавляет