Кодирование и декодирование ldpc пакетов переменных размеров

Кодирование и декодирование ldpc пакетов переменных размеров

Иллюстрации

Показать все

Реферат

Для настоящей заявки испрашивается приоритет на основании предварительной патентной заявки США № 60/886496 под названием “LDPC HARMONIZATION”, поданной 24 января 2007 г., принадлежащей правообладателю настоящей заявки и включенной в настоящий документ путем ссылки.

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

Изобретение относится в общем к области связи и, в частности, к методам кодирования и декодирования данных.

Уровень техники

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

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

Для кодирования можно использовать различные типы кода FEC. Некоторые общие типы кода FEC включают в себя сверточный код, турбокод и код контроля четности низкой плотности (LDPC). Сверточный код или турбокод может кодировать пакет из k информационных битов и генерировать кодированный пакет из приблизительно r умноженное на k битов кода, где 1/r - кодовая скорость сверточного или турбокода. Сверточный код может легко кодировать пакет любого размера, пропуская каждый информационный бит через кодер, который может каждый раз оперировать на одном информационном бите. Турбокод также может поддерживать разные размеры пакета с использованием двух составных кодеров, которые могут каждый раз оперировать на одном информационном бите, и перемежителя кода, который может поддерживать разные размеры пакета. Код LDPC может в определенных условиях работы иметь более высокую производительность, чем сверточный и турбокоды. Однако код LDPC обычно предназначен для конкретного размера пакета и может не иметь возможности быстро реагировать на пакеты изменяющихся размеров.

Поэтому в технике существует необходимость в методах поддержки эффективного кодирования и декодирования LDPC пакетов изменяющихся размеров.

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

В настоящем документе описаны методы поддержки кодирования и декодирования LDPC. Согласно одному аспекту кодирование и декодирование LDPC пакетов изменяющихся размеров можно эффективно поддерживать с помощью множества базовых матриц контроля четности разных размеров и множества значений поднятия, равных разным степеням 2. Базовую матрицу G контроля четности размером m_B×n_B можно использовать для кодирования пакета до k_B = n_B - m_B информационных битов для получения кодированного пакета или кодового слова из n_B битов кода. Эту базовую матрицу G контроля четности можно «поднимать» на значение поднятия L для получения поднятой матрицы H контроля четности размером L·m_B×L·n_B. Поднятую матрицу H контроля четности можно использовать для кодирования пакета до L·k_B информационных битов для получения кодового слова из L·n_B битов кода. Широкий диапазон размеров пакета может поддерживаться с помощью сравнительно малого множества базовых матриц контроля четности и сравнительно малого множества значений поднятия. Поднятие также может обеспечивать эффективное параллельное кодирование и декодирование, что может повышать производительность. Кроме того, поднятие может снижать сложность описания для больших кодов LDPC.

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

Различные аспекты и признаки раскрытия более подробно описаны ниже.

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

Фиг.1 - система беспроводной связи.

Фиг.2 - блок-схема базовой станции и терминала.

Фиг.3 - граф Таннера для иллюстративного кода LDPC.

Фиг.4 - поднятие базовой матрицы контроля четности.

Фиг.5 - множество из четырех матриц циклической перестановки.

Фиг.6 - поднятая матрица контроля четности.

Фиг.7 - другое представление поднятой матрицы контроля четности.

Фиг.8 - граф для поднятой матрицы контроля четности.

Фиг.9 - процесс для обработки данных.

Фиг.10 - устройство для обработки данных.

Фиг.11 - процесс обработки пакета.

Фиг.12 - другой процесс обработки пакета.

Фиг.13 - устройство для обработки пакета.

Фиг.14 - еще один процесс обработки пакета.

Фиг.15 - еще одно устройство для обработки пакета.

Осуществление изобретения

Описанные в настоящем документе методы можно использовать для различных областей применения, например связь, вычисления, построение сетей и т.д. Методы также можно использовать для различных систем связи, в том числе беспроводных систем, проводных систем и т.д. Для ясности некоторые аспекты методов описаны ниже для системы беспроводной связи.

На фиг.1 показана система беспроводной связи 100, которую также можно именовать сетью доступа (AN). Для простоты на фиг.1 показаны только одна базовая станция 110 и два терминала 120 и 130. Базовая станция - это станция, которая осуществляет связь с терминалами, а также может именоваться точкой доступа, Узлом B, усовершенствованным Узлом B и т.д. Терминал может быть стационарным или мобильным, а также может именоваться терминалом доступа (AT), мобильной станцией, пользовательским оборудованием, абонентским блоком, станцией и т.д. Терминал может представлять собой сотовый телефон, карманный персональный компьютер (КПК), беспроводное устройство связи, беспроводной модем, карманное устройство, портативный компьютер, беспроводной телефон и т.д. Терминал может осуществлять связь с базовой станцией по прямой и/или обратной линиям связи в любой данный момент времени. Прямая линия связи (или нисходящая линия связи)- это линия связи от базовых станций к терминалам, и обратная линия связи (или восходящая линия связи) - это линия связи от терминалов к базовым станциям. Согласно фиг.1 терминал 120 может принимать данные от базовой станции 110 по прямой линии связи 122 и может передавать данные по обратной линии связи 124. Терминал 130 может принимать данные от базовой станции 110 по прямой линии связи 132 и может передавать данные по обратной линии связи 134. Описанные в настоящем документе методы можно использовать для передачи по прямой линии связи, а также по обратной линии связи.

На фиг.2 показана блок-схема варианта осуществления базовой станции 110 и терминала 120, показанных на фиг.1. В этом варианте осуществления базовая станция 110 снабжена S антеннами 224a - 224s, и терминал 120 снабжен T антеннами 252a - 252t, где в общем случае S ≥ 1 и T ≥ 1.

На прямой линии связи, на базовой станции 110, процессор 210 данных передачи (TX) может принимать пакет данных из источника данных 208, обрабатывать пакет (например, кодировать, перемежать и отображать в символы), на основании формата пакета выдавать символы данных, которые являются символами модуляции для данных. Процессор MIMO TX 220 может мультиплексировать символы данных с контрольными символами, осуществлять пространственную обработку (например, предварительное кодирование), если применимо, и выдавать S выходных символьных потоков на S передатчиков (перед.) 222a - 222s. Каждый передатчик 222 может обрабатывать свой выходной символьный поток (например, для OFDM) для получения выходного чипового потока. Каждый передатчик 222 может дополнительно преобразовывать (например, преобразовывать в аналоговый вид, фильтровать, усиливать и повышать частоту) свой выходной чиповый поток и генерировать сигнал прямой линии связи. S сигналов прямой линии связи от передатчиков 222a - 222s могут передаваться через S антенн 224a - 224s, соответственно.

На терминале 120 T антенн 252a - 252t могут принимать сигналы прямой линии связи от базовой станции 110, и каждая антенна 252 может выдавать принятый сигнал на соответствующий приемник (прием.) 254. Каждый приемник 254 может обрабатывать (например, фильтровать, усиливать, понижать частоту и цифровать) свой принятый сигнал для получения выборок, дополнительно обрабатывать выборки (например, для OFDM) для получения принятых символов и выдавать принятые символы на детектор MIMO 256. Детектор MIMO 256 может осуществлять детектирование MIMO на принятых символах, если применимо, и выдавать детектированные символы. Процессор 260 данных приема (RX) может обрабатывать (например, снимать отображение в символы, отменять перемежение и декодировать) детектированные символы и выдавать декодированные данные на приемник данных 262. В общем случае обработка посредством детектора MIMO 256 и процессора 260 данных RX комплементарна обработке посредством процессора 220 MIMO TX и процессора 210 данных TX на базовой станции 110.

На обратной линии связи, на терминале 120, пакет данных может обеспечиваться источником данных 278 и обрабатываться (например, кодироваться, перемежаться и отображаться в символы) процессором 280 данных TX. Символы данных от процессора 280 данных TX могут мультиплексироваться с контрольными символами и подвергаться пространственной обработке процессором 282 MIMO TX и дополнительно обрабатываться передатчиками 254a - 254t, которые генерируют T сигналов обратной линии связи, которые могут передаваться через антенны 252a - 252t. На базовой станции 110 сигналы обратной линии связи от терминала 120 могут приниматься антеннами 224a - 224s, обрабатываться приемниками 222a - 222s, детектироваться детектором MIMO 238 и дополнительно обрабатываться процессором 240 данных RX для восстановления пакета, переданного терминалом 120.

Контроллеры/процессоры 230 и 270 могут управлять работой базовой станции 110 и терминала 120, соответственно. Контроллеры/процессоры 230 и 270 могут определять размеры пакетов, подлежащих передаче и/или приему. Контроллеры/процессоры 230 и 270 могут затем управлять кодированием посредством процессоров 210 и 280 данных TX, соответственно, и/или управлять декодированием посредством процессоров 240 и 260 данных RX, соответственно. В блоках памяти 232 и 272 могут храниться данные и программные коды для базовой станции 110 и терминала 120, соответственно.

Согласно одному аспекту кодирование и декодирование LDPC пакетов изменяющихся размеров можно эффективно поддерживать с помощью множества базовых матриц контроля четности разных размеров и множества значений поднятия, равных разным степеням 2. Базовые матрицы контроля четности могут предназначаться для базовых кодов LDPC разных скоростей (k_B, n_B), где k_B - количество информационных битов и n_B - количество битов кода. Каждый базовый код LDPC можно поднимать, как описано ниже, для получения множества поднятых кодов LDPC, которые можно использовать для кодирования или декодирования пакетов разных размеров. Диапазон размеров пакета может поддерживаться путем удлинения или сокращения кодов LDPC за счет добавления или удаления битов четности в базовом графе.

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

На фиг.3 показан граф Таннера 300 для иллюстративного базового кода LDPC. В этом примере граф Таннера 300 включает в себя семь вершин-переменных V₁ - V₇, представленные семью кружками, и четыре контрольные вершины C₁ - C₄, представленные четырьмя квадратиками. Каждая вершина-переменная представляет собой бит кода, который может либо передаваться, либо перфорироваться (т.е. не передаваться). Семь битов кода для вершин-переменных V₁ - V₇ образуют кодовое слово. Каждая контрольная вершина представляет ограничение, и четыре контрольные вершины C₁ - C₄ представляют четыре ограничения, которые задают базовый код LDPC. Вершины-переменные соединены с контрольными вершинами ребрами. В этом примере 16 ребер a - p соединяют семь вершин-переменных с четырьмя контрольными вершинами. Степень вершины равна количеству ребер, соединенных с этой вершиной. В этом примере вершины-переменные V₁ и V₂ являются вершинами 3 степени, и вершины-переменные V₃ - V₇ являются вершинами 2 степени. Для каждой контрольной вершины все биты кода в вершинах-переменных, соединенных с этой контрольной вершиной, подчиняются ограничению, состоящему в том, что их сумма должна быть равна 0 (по модулю 2).

На фиг.3 также показана базовая матрица H _b контроля четности, соответствующая графу Таннера 300. H _b включают в себя семь столбцов для семи вершин-переменных V₁ - V₇ и четыре строки для четырех контрольных вершин C₁ - C₄. Каждый столбец H _b включает в себя 1 элемент для каждого ребра, соединенного с вершиной-переменной, соответствующей этому столбцу. Например, столбец 1 включает в себя три 1 в строках 1, 2 и 3 для трех ребер a, b и c, соединяющих соответствующую вершину-переменную V₁ с контрольными вершинами C₁, C₂ и C₃ в графе Таннера 300. Каждый из остальных столбцов H _b включает в себя две или три 1 для двух или трех ребер, соединяющих соответствующую вершину-переменную с двумя или тремя контрольными вершинами.

Ограничения для кода LDPC можно выразить в матричной форме как:

, Уравнение (1)

где H - матрица контроля четности m_B×n_B для кода LDPC,

x - вектор-столбец n_B×1 из n_B битов кода для кодового слова, и

0 - вектор-столбец из одних нулей.

Для простоты 0 может обозначать вектор или матрицу из одних нулей в нижеследующем описании. Матричное умножение в уравнении (1) осуществляется согласно арифметике по модулю 2. Кодовое слово считается верным, если ограничения в уравнении (1) выполняются. Кодирование пакета на основании матрицы H контроля четности для получения кодового слова x описано ниже.

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

На фиг.4 показан пример поднятия для базовой матрицы H _b контроля четности, показанной на фиг.3. Каждый ненулевой элемент H _b (который соответствует ребру в графе Таннера) заменяется матрицей перестановки σ L×L для получения поднятой матрицы H _l контроля четности 16 матриц перестановки для 16 ненулевых элементов H _b обозначаются σ _a - σ _p, где σ _a - матрица перестановки для ребра a на фиг.3.

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

На фиг.5 показано множество из четырех матриц циклической перестановки для L = 4. В этом примере каждая матрица перестановки имеет размер 4×4. Матрица перестановки σ ₀ для значения циклического сдвига, равного нулю, равна единичной матрице I, имеющей единицы вдоль диагонали и нули во всех остальных местах. Матрица перестановки σ ₁ для значения циклического сдвига, равного единице, получается из единичной матрицы путем перемещения или сдвига самой нижней строки в верхнюю позицию. Матрица перестановки σ ₂ для значения циклического сдвига, равного 2, получается из единичной матрицы путем перемещения двух самых нижних строк в верхнюю позицию. Матрица перестановки σ ₃ для значения циклического сдвига, равного трем, получается из единичной матрицы путем перемещения трех самых нижних строк в верхнюю позицию. В общем случае матрица перестановки σ _s L×L для значения циклического сдвига, равного s, получается из единичной матрицы путем перемещения s самых нижних строк в верхнюю позицию, где 0 ≤ s ≤ L-1.

На фиг.6 показан пример поднятой матрицы H _l контроля четности, показанной на фиг.4, в которой каждая из 16 матриц перестановки σ _a - σ _p заменена одной из четырех матриц циклической перестановки σ ₀ - σ ₃, показанных на фиг.5. В нижней части фиг.6 показана поднятая матрица H _l контроля четности, в которой каждая матрица циклической перестановки заменена соответствующей матрицей 4×4 из единиц и нулей.

Замена каждого ненулевого элемента базовой матрицы H _b контроля четности матрицей перестановки 4×4 дает четыре копии базового графа для генерируемого базового кода LDPC. Для матрицы перестановки 4×4, соответствующей данной вершине-переменной V_u и данной контрольной вершине C_v, четыре столбца этой матрицы перестановки соответствуют вершине-переменной V_u в четырех копиях графа, и четыре строки этой матрицы перестановки соответствуют контрольной вершине C_v в четырех копиях графа. Единицы в матрице перестановки соответствуют ребрам, соединяющим вершину-переменную V_u в четырех копиях графа с контрольной вершиной C_v в четырех копиях графа. В частности, 1 в столбце x строки y означает, что вершина-переменная V_u в копии графа x соединена с контрольной вершиной C_u в копии графа y. Например, матрица циклической перестановки σ ₁ используется для ненулевого элемента для вершины-переменной V₁ и контрольной вершины C₁ в H _l. Матрица σ ₁ включает в себя 1 в столбце 1 строки 2, что означает, что вершина-переменная V₁ в копии графа 1 соединена с контрольной вершиной C₁ в копии графа 2.

На фиг.7 показано представление поднятой матрицы H _l контроля четности, сгенерированной на основании базовой матрицы H _b контроля четности, показанной на фиг.3, при L = 8. В этом представлении сетка 710 8×16 хранит ребра для семи вершин-переменных во всех восьми копиях графа. Каждая строка сетки 710 соответствует одной копии графа. 16 блоков в каждой строке соответствуют 16 ребрам a - p для семи вершин-переменных в одной копии графа. Сетка 720 8×16 хранит ребра для четырех контрольных вершин во всех восьми копиях графа. Каждая строка сетки 720 соответствует одной копии графа. 16 блоков в каждой строке соответствуют 16 ребрам a - p для четырех контрольных вершин в одной копии графа.

На фиг.7 также показаны соединения между восемью копиями вершины-переменной V₂ и восемью копиями контрольной вершины C₂ для ребра d, которое имеет матрицу циклической перестановки σ ₃ в этом примере. Таким образом, восемь копий ребра d подвергаются циклическому сдвигу вниз на три позиции согласно матрице σ ₃, каждое из оставшихся ребер может циклически сдвигаться на значение в пределах от 0 до 7 для L = 8.

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

На фиг.3-6 показан иллюстративный базовый код LDPC с базовой матрицей H _b контроля четности, показанной на фиг.3, и поднятие этого базового кода LDPC для получения более крупного кода LDPC с поднятой матрицей H _l контроля четности, показанной на фиг.6. Поднятия разных размеров можно добиться, используя матрицы циклической перестановки разных размеров. Ребра базовой матрицы H _b контроля четности могут циклически сдвигаться на значение в пределах от 0 до L-1. Значения циклического сдвига для ребер базовой матрицы контроля четности можно выбирать на основании производительности кодирования.

В одном варианте осуществления можно задать множество из шести базовых кодов LDPC для разных значений k_B в пределах от 6 до 11. В Таблице 1 приведены различные параметры шести базовых кодов LDPC согласно одному варианту осуществления. В одном варианте осуществления шесть базовых кодов LDPC можно реализовать, как описано в опубликованном документе 3GPP2 C.S0084-001 под названием “Physical Layer for Ultra Mobile Broadband (UMB) Air Interface Specification”, август 2007. Базовые коды LDPC также можно реализовать согласно другим вариантам осуществления.

Таблица 1
Индекс кода i	Количество информа-ционных битов kB	Количество битов четности mB	Количество битов кода nB	Количество переменных состояния sB	Базовая матрица контроля четности
0	6	27	33	3	G 0
1	7	31	38	3	G 1
2	8	35	43	3	G 2
3	9	39	48	3	G 3
4	10	43	53	3	G 4
5	11	47	58	3	G 5

В одном варианте осуществления может поддерживаться множество из девяти значений поднятия 4, 8, 16, 32, 64, 128, 256, 512 и 1024. В этом варианте осуществления наименьшее значение поднятия L_min = 4 и наибольшее значение поднятия L_max = 1024. Эти значения поднятия являются разными степенями 2, что может обеспечивать определенные преимущества. Всего 54 разных размеров пакета в пределах от 24 до 11,264 битов может поддерживаться с помощью шести базовых кодов LDPC с k_B в пределах от 6 до 11 и девяти значений поднятия в пределах от 4 до 1024. В общем случае может поддерживаться любой диапазон значений поднятия, и L_min и L_max могут принимать любые подходящие значения.

В Таблице 2 приведены параметры базовой матрицы G ₀ контроля четности согласно одному варианту осуществления. Согласно Таблице 1 G ₀ имеет размер 27×33 и включает в себя 27 строк с индексами от 0 до 26 и 33 столбца с индексами от 0 до 32. Для каждой строки во втором столбце Таблицы 2 указана степень строки, которая соответствует количеству ненулевых элементов в строке. В третьем столбце Таблицы 2 указаны позиции столбцов для ненулевых элементов в каждой строке. В четвертом столбце указано значение циклического сдвига для каждого ненулевого элемента в каждой строке. Для L_max = 1024 значения циклического сдвига составляют в пределах от 0 до 1023. Иллюстративные варианты осуществления базовых матриц G ₁ - G ₅ контроля четности описаны в вышеупомянутом 3GPP2 C.S0084-001.

Таблица 2
Базовая матрица G 0 контроля четности
Индекс строки	Степень строки	Позиция столбца для ненулевых элементов в строке	Значения циклического сдвига ненулевых элементов в строке
0	6	1, 2, 3, 4, 8, 9	110, 680, 424, 180, 0, 0
1	6	0, 2, 3, 6, 9, 10	702, 768, 863, 0, 0, 0
2	6	0, 1, 3, 4, 7, 10	360, 259, 652, 753, 0, 0
3	4	1, 4, 8, 20	402, 948, 0, 0
4	4	0, 5, 6, 20	318, 0, 767, 0
5	4	2, 5, 6, 7	154, 1023, 768, 0
6	3	0, 1, 11	885, 323, 0
7	3	0, 2, 12	617, 220, 0
8	4	1, 2, 3, 13	799, 519, 669, 0
9	4	0, 1, 4, 14	900, 72, 669, 0
10	4	0, 2, 6, 15	574, 253, 352,0
11	4	1, 2, 7, 16	848, 280, 920, 0
12	4	0, 1, 5, 17	548, 928, 355, 0
13	4	0, 2, 3, 18	17, 376, 147, 0
14	4	0, 1, 4, 19	795, 823, 473, 0
15	4	0, 2, 8, 21	519, 424, 712, 0
16	3	1, 6, 22	952, 449, 0
17	3	2, 7, 23	887, 798, 0
18	4	0, 1, 9, 24	256, 93, 348, 0
19	3	2, 3, 25	492, 856, 0
20	4	1, 2, 10, 26	589, 1016, 705, 0
21	3	0, 4, 27	26, 166, 0
22	4	1, 2, 5, 28	525, 584, 845, 0
23	3	0, 8, 29	10, 331, 0
24	3	1, 9, 30	125, 310, 0
25	3	2, 10, 31	239, 641, 0
26	4	0, 1, 6, 32	557, 609, 448, 0

В одном варианте осуществления базовую матрицу контроля четности и значение поднятия можно выбирать для пакета размером k следующим образом. Прежде всего значение поднятия L можно выбирать на основании размера пакета k следующим образом:

, Уравнение (2)

где k_B,max - максимальное количество информационных битов для всех базовых кодов LDPC, и

“   ” обозначает оператор верхнего целочисленного приближения.

k_B,max = 11 для множества базовых кодов LDPC, показанного в Таблице 1, может быть равно другим значениям для других множеств базовых кодов LDPC.

Затем базовую матрицу контроля четности можно выбрать на основании размера пакета k и выбранного значения поднятия L следующим образом:

. Уравнение (3)

Индекс выбранной базовой матрицы контроля четности можно задать как i = k_B - 6. Выбранная базовая матрица контроля четности обозначается G в нижеследующем описании.

Выбранная базовая матрица G контроля четности и выбранное значение поднятия L могут кодировать до k_B·L информационных битов и обеспечивать n_B·L битов кода. Пакет можно заполнить нулями до длины k_B·L путем присоединения z_P = k_B·L - k нулей к концу пакета. Заполненный нулями пакет можно кодировать с поднятой матрицей контроля четности для получения n_B·L битов кода. Для кода (n, k), z_p нулей заполнения, а также n_B·L - n - z_P битов четности можно перфорировать для получения кодового слова из n битов кода.

Чтобы кодировать пакет, можно сначала генерировать поднятую матрицу H контроля четности на основании выбранной базовой матрицы G контроля четности и выбранного значения поднятия L. Затем можно кодировать пакет на основании поднятой матрицы H контроля четности.

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

, Уравнение (4)

где g - значение циклического сдвига для ненулевого элемента G при условии поднятия на L_max, и

g′ - значение циклического сдвига для ненулевого элемента G при условии поднятия на L.

В четвертом столбце 2 указаны значения циклического сдвига для ненулевых элементов G ₀ для L_max = 1024. Значения циклического сдвига для ненулевых элементов других базовых матриц контроля четности можно генерировать и сохранять в аналогичных таблицах. В общем случае значения циклического сдвига для ненулевых элементов G можно генерировать для L_max и можно использовать для всех значений поднятия от L_min до L_max. Это может упростить вариант осуществления, поскольку только одно множество значений циклического сдвига можно сохранять для G и использовать для всех значений поднятия. Уравнение (4), в сущности, удаляет нуль или более младших битов (LSB) из g для получения g′ для выбранного значения поднятия L. Для варианта осуществления с L_max = 1024 можно удалить один LSB, если L = 512, можно удалить два LSB, если L = 256, и т.д. Удаление LSB может сохранять соотношение между разными параметрами сдвига, например, s′ = s + L/4, описанное ниже, что может упрощать кодирование. В другом варианте осуществления нуль или более старших битов (MSB) из g можно удалить путем осуществления операции по модулю L для получения g′. g′ также можно получить другими средствами.

В одном варианте осуществления каждый ненулевой элемент G можно заменить матрицей циклической перестановки σ_g′ для получения поднятой матрицы H контроля четности. σ_g′ можно получить путем циклического сдвига единичной матрицы I на g′. В другом варианте осуществления каждый ненулевой элемент G можно заменить матрицей 2×2 для получения матрицы G′. Эта матрица 2×2 может иметь вид , если g′ имеет четное значение, или , если g′ имеет нечетное значение. Каждый ненулевой элемент G′ затем можно заменить матрицей циклической перестановки, полученной циклическим сдвигом на g′/2, (g′-1)/2 или (g′+1)/2, для получения поднятой матрицы H контроля четности. H также можно генерировать на основании G другими средствами.

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

, Уравнение (5)

где M ₁ - матрица M×N, где N = M + k_B·L,

M ₂ - матрица (m_B·L-M)×N, и

0 - матрица M×(n_B·L-N) из одних нулей.

Единичную матрицу в нижнем правом углу H можно заменить нижней треугольной матрицей, которая может иметь ненулевые элементы под диагональю.

Размер M ₁ может зависеть от выбранной базовой матрицы контроля четности и может быть функцией индекса кода i. M ₁ может иметь следующий вид:

, где обратима, Уравнение (6)

где A - матрица (M-L/2)×(k_B·L),

B - матрица (M-L/2)×(L/2),

C - матрица (L/2)×(k_B·L),

D - матрица (L/2)×(L/2),

E - матрица (L/2)×(N-k_B·L), и

T - нижняя треугольная матрица (M-L/2)×(M-L/2), имеющая единицы вдоль диагонали и нули над диагональю.

Ограничения для поднятого кода LDPC можно выразить в виде:

, где , Уравнение (7)

где x ₁ - вектор-столбец N×1 информационных битов и битов четности, и

p ₃ - (n_B·L-N)×1 вектор-столбец битов четности.

Ввиду наличия нулевой матрицы 0 в верхнем правом углу H в уравнении (5) часть уравнения (7) можно выразить как:

, где ,Уравнение (8)

где s - вектор-столбец (k_B·L)×1 информационных битов в пакете,

p ₁ - (L/2)×1 вектор-столбец битов четности, и

p ₂ - (M-L/2)×1 вектор-столбец битов четности.

Для решения уравнения (8) M ₁ можно предварительно перемножить с следующим образом:

, Уравнение (9)

где ϕ = - ET ^-1 B + D.

Уравнения (8) и (9) можно объединить для получения:

, и Уравнение (10)

.Уравнение (11)

Тогда биты четности p ₁, p ₂ и p ₃ можно вычислить следующим образом:

, Уравнение (12)

, и Уравнение (13)

,Уравнение (14)

где x ₁ включают в себя s, p ₁ и p ₂, как показано в уравнении (8). Если единичную матрицу в нижнем правом углу H заменить нижней треугольной матрицей, то уравнение (14) можно решить с использованием обратной подстановки (сверху вниз).

Вычисление p ₁, p ₂ и p ₃ можно упростить, выполняя матричное умножение в уравнениях (12) и (13) поэтапно, сохраняя промежуточные результаты и используя промежуточные результаты на дальнейших этапах.

Поднятая матрица H контроля четности предназначена для самой низкой кодовой скорости, которую можно задать как r = k_B/n_B. H можно перфорировать для получения более высоких скоростей. Коды LDPC структурированы как внутренний “сердцевинный” код LDPC высокой скорости с внешними битами четности. Кодирование можно осуществлять последовательно для получения нужного количества битов кода. Например, сначала можно вычислять биты четности p ₁, как показано в уравнении (12), затем (при необходимости) можно вычислять биты четности p ₂, как показано в уравнении (13), и, наконец, (при необходимости) можно вычислять биты четности p ₃, как показано в уравнении (14).

Система может поддерживать режим смешанного автоматического запроса повторной передачи (HARQ). Для HARQ передатчик может посылать первую передачу пакета на приемник и затем может, при необходимости, посылать одну или несколько дополнительных передач (или повторных передач), пока пакет не будет правильно декодирован приемником, или не будет отправлено максимальное количество передач, или не будет выполнено какое-либо другое условие окончания передачи. HARQ может повысить надежность передачи данных. Для каждого базового кода LDPC можно генерировать последовательность расширений HARQ для охвата всех кодовых скоростей, поддерживаемых системой. Расширения HARQ можно задать путем перфорации битов четности. Перфорации можно, в основном, подвергать третьи биты четности P ₃, но и вторые биты четности P ₂ также можно подвергать некоторой перфорации.

На фиг.8 показан базовый граф 800 базовой матрицы G контроля четности, которая может иметь вид, показанный в уравнениях (5) и (6). Граф 800 используется только в целях иллюстрации и не соответствует никаким базовым матрицам контроля четности, описанным выше. Базовый граф 800 включают в себя несколько квадратных блоков, причем каждый квадратный блок представляет элемент в базовой матрице контроля четности. Каждый ненулевой элемент базовой матрицы контроля четности представлен помеченным блоком. Каждый помеченный блок связан со значением циклического сдвига, которое определяет величину циклического сдвига для L копий ребра, полученных за счет поднятия базовой матрицы контроля четности на значение поднятия L.

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

Базовый граф 800 содержит информационные биты s, п