СПОСОБ И УСТРОЙСТВО ДЕКОДИРОВАНИЯ КОДА ПОРОЖДАЮЩЕЙ МАТРИЦЫ С НИЗКОЙ ПЛОТНОСТЬЮ Российский патент 2012 года по МПК H03M13/05 G06F11/10 

Область техники

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

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

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

LDGC (Low Density Generator Matrix Codes, код порождающей матрицы с низкой плотностью) в широком смысле понимается так: порождающая матрица является кодом первого класса редкой двоичной матрицы (т.е. матричными элементами являются 0 или 1), включая структурированный код LDGC, код Raptor (раптор) и другие неструктурированные коды LDGC.

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

При этом LDGC является одним линейным блочным кодом, все элементы в порождающей матрице (матрице кодирования) происходят из бинарного поля (поле GF(2)), т.е. элементы порождающей матрицы только состоят из 0 и 1; а также ненулевые элементы обычно являются редкими, т.е. в матрице количество «1» только занимает малый процент от количества общих элементов матрицы; кроме того, LDGC еще является одним системным кодом, т.е. первые К биты кодовых слов, образованные с помощью кодирования К битов информации с применением порождающей матрицы LDGC, равны с данными битами информации. Операция, касающаяся процесса кодирования и декодирования LDGC, является операцией на поле GF(2).

Порождающая матрица структурированного LDGC еще обладает другими характеристиками, может получаться из очень малой основной матрицы с помощью расширенной коррекции; в частности, квадратичная матрица, соответствующая первым L строкам, обычно является одной верхней треугольной матрицей или нижней треугольной матрицей. А порождающие матрицы LDGC без структурированных характеристик у кодов Raptor и т.д. являются случайными бинарными матрицами. В дальнейшем Gldgc используется для единого обозначения порождающей матрицы LDGC, при необходимости отдельного обозначения, G_struct используется для обозначения транспонирования порождающей матрицы структурированного LDGC, G_random используется для обозначения транспонирования порождающей матрицы LDGC без структурированных характеристик (можно сокращенно называть как порождающая матрица неструктурированного LDGC), в частности, G_random включает порождающую матрицу кода Raptor.

В дальнейшем описании всякие «векторы» или «матрицы» с нижним индексом в виде t обозначают транспонирование бывших «векторов» или «матриц», вектор или матрица и их транспонирование являются совершенно одинаковыми по содержанию, иногда они могут выражать одинаковый предмет. Например, определение G_ldgct является транспонированием G_ldgc, I_t является транспонированием I, R_t является транспонированием R, поскольку I и R являются вектором строк, где I_t и R_t являются вектором столбцов; в дальнейшем G_struct, G_random используются для отдельного обозначения своих транспонированных порождающих матриц G_ldgct.

Фиг.1 является схемой транспонированной порождающей матрицы LDGC G_ldgct. Как показано на фиг.1а, в структурированной порождающей матрице LDGC G_struct квадратичная матрица, соответствующая первым L строкам, обычно является одной верхней треугольной матрицей или нижней треугольной матрицей. Как показано на фиг.1b, квадратичная матрица кода Raptor, соответствующая первым L строкам, является случайной матрицей без характеристик верхней треугольной матрицы или нижней треугольной матрицы. В т.ч. в схеме х, у может составлять 0.

Кодирование LDGC получается таким образом, сначала определяется промежуточная переменная с помощью относительного отношения между битами информации (данными, подлежащими передаче) и промежуточной переменной в системном коде, затем промежуточная переменная умножается на порождающую матрицу и получается кодированное кодовое слово. В частности, процесс кодирования заключается в том, что сначала исходная информационная последовательность m битов K заполнена известными битами в количестве d=L-K, после этого получается последовательность s битов L, затем в соответствии с отношением системы уравнений: I×G_ldgc(0:L-1,0:L-1)=s, после решения системы уравнений получается последовательность промежуточной переменной битов L, затем промежуточная переменная умножается на порождающую матрицу, т.е. I×G_ldgc(0:L-1,0:N+d-1) и получается последовательность кодовых слов битов N+d (включая заполненные биты в количестве d), для заполненных битов в количестве d передача не требуется, поэтому в самом деле последовательность G_ldgc кодовых слов битов N передается после того, как G_ldgc проходит через канал (стирание является возможным), последовательность кодовых слов, принимаемая приемным терминалом, является R. В т.ч. s является вектором 1×L; I является вектором 1×L; R является вектором 1×N, ее транспонирование R_t является вектором N×1; G_ldgc(0:L-1,0:L-1) является квадратичной матрицей L×L, в обычной случае, данная квадратичная матрица является одной верхней треугольной матрицей или нижней треугольной матрицей, G_ldgc(0:L-1,0:N+d-1) является матрицей L×(N+d). Подробный процесс кодирования приведен в патенте «способ и устройство кодирования и декодирования кода порождающей матрицы с низкой плотностью».

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

201: на соответственном месте принятой последовательности кодовых слов R_t заполняется последовательность известных битов длительностью d=L-K, например: 1, 1, …, 1., при этом вычеркиваются символы кодовых слов, стертые каналом и получается R_e,

где K является длительностью битов исходной информации, L является длительностью кодирования заполненных битов исходной информации;

202: в соответствии с состоянием стирания принятой последовательности кодовых слов R_t проводится обработка стирания (вычеркивания) над G_ldgct и получается порождающая матрица стирания G_e.

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

Допустим, что символы в количестве X_T, заполненные последовательностью известных битов в формуляре R=(r₀, r₁,…… r_N+d-1)^T:{r_i, r_j,…, r_p…r_x}, стираются каналом, где символы в количестве X_L в первых L символах {r_i, r_j,…, r_p} стираются каналом, то Xset={i, j,…, р,…, х}; Xset_L={i, j,… p}. Соответственно, стирать {i-ю, j-ю, …, р-ю, …, х-ю} строку в G_ldgct, то получается G_e, при этом из-за того что некоторые строки стерты, то матрица над G_e не является строгой диагонализацией, как показано на фиг.3 (с),

203: в соответствии с отношением системы уравнений G_e×I_t=R_e решается система уравнений и определяется промежуточная переменная I_t;

204: в соответствии с отношением системы уравнений G_ldgct(0:L-1,0:L-1)×I_t=s_t определяется s_t, а также, если из s_t вычеркивать вышеуказанные заполненные известные биты в количестве d, получается исходная информационная последовательность m битов K и декодирование LDGC выполняется.

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

В процессе определения промежуточной переменной I_t в соответствии с отношением системы уравнений G_ldgct(0:N+d-1,0:L-1)×I_t=R_t (при стирании канала G_ldgct записывается как G_e, R_t записывается как R_e, вышеуказанное отношение системы уравнений является G_e×I_t=R_e), для проведенного исключения Гаусса требуется произвести три типа элементарных преобразований над G_ldgct (при стирании канала является G_e), как «перестановка строк, сложение строки и перестановка столбцов». В соответствии с принципом линейной алгебры, в целях обеспечения правильности системы уравнений, при проведении элементарного преобразования над G_ldgct(G_e), для I_t и R_t (при стирании канала является R_e) нужно проводить следующую соответствующую обработку:

1) перестановка строк, в случае, если проводить перестановку i-й и j-й строк G_ldgct(G_e), то для i-го и j-го бита R_t(R_e) должно проводить перестановку;

2) сложение строки, в случае, если проводить сложение i-й и j-й строк G_ldgct(G_e), то для i-го и j-го бита R_t(R_e) должно проводить сложение (сложение по модулю 2);

3) перестановка столбцов, в случае, если проводить перестановку i-го и j-го столбцов G_ldgct(G_e), то для i-го и j-го бита I_t должно проводить перестановку.

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

Так как эти отношения преобразования являются строго соответствующими, а также сложность исключения Гаусса главным образом выражается в обработке над G_ldgct(G_e), в дальнейшем ради удобства описания всякое элементарное преобразование над G_ldgct(G_e), соответственная обработка над I_t и R_t(R_e) должны быть строго выполнены в соответствии с вышеуказанными тремя состояниями. Для выделения главного, в дальнейшем иногда будет упрощаться описание об обработке I_t и R_t(R_e).

Как правило, сложность (объем вычисления) осуществления исключения Гаусса главным образом выражается в операции «сложение строки» матрицы. Так как все элементы G_ldgct происходят из поля GF(2), поэтому операция сложения двух строк в G_ldgct(G_e) является операцией «сложение по модулю 2», например:

содержание i-й строки row_i является: (1,0,0,0,0,1,0,1);

содержание j-й строки row_j является: (1,1,0,0,0,1,1,1).

При проведении исключения Гаусса выполняется операция исключения row_j с применением row_i, т.е. эквивалентна:

row_j=row_i+row_j=

(1,0,0,0,0,1,0,1)+(1,1,0,0,0,1,1,1)=(0,1,0,0,0,0,1,0),

где «+» обозначает сложение в поле GF(2) (сложение по модулю 2).

Вышеуказанные примеры показывают, что если все элементы в G_ldgct происходят из поля GF(2), то значение элемента только ограничено в 0 и 1, если прямо сохранять эти элементы 0 и 1, значит то, что каждый элемент бита занимает один блок памяти или одно процессорное слово (обычно занимает 32 битов), то при более большой длине кода G_ldgct(G_e) требует от огромного пространства памяти; а также операция сложения строк требует от проведения сложения по модулю 2 над каждым элементом, расход времени является большим.

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

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

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

S1: в принятой последовательности кодовых слов R заполнять известные биты в количестве L-K, а также вычеркивать символы кодового слова в R, стертые каналом, получается R_e;

S2: из транспонированной матрицы G_ldgct порождающей матрицы LDGC вычеркивать строки, соответствующие символам кодового слова, стертым каналом, получается G_e; в данном процессе, процессорные слова в количестве WNum используются для поочередного хранения полных или частичных матричных элементов с одинаковыми положениями во всех строках G_e, каждое процессорное слово хранит матричный элемент в количестве WWid G_e;

S3: по отношению G_e×I_t=R_e определяется I_t;

S4: по отношению G_ldgct(0:L-1,0:L-1)×I_t=s_t определяется s_t, а также из s_t вычеркивать вышеуказанные заполненные известные биты в количестве L-K, и исходная информационная последовательность битов K получается;

вышеуказанная G_ldgct является матрицей поля GF(2) строки N+L-K и столбца L, WWid является шириной процессорного слова, WNum=ceil(P/WWid), P является количеством матричных элементов, хранящихся одним битом процессорного слова, во всех строках G_e;

причем способ декодирования осуществляют декодером.

Кроме того, в шаге S3 определять I_t с применением исключения Гаусса; а также в процессе исключения Гаусса, для матричных элементов, хранящихся одним битом процессорного слова, во всех строках G_e, осуществляется сложение строк соответствующих строк с помощью операции XOR бита процессорного слова, соответствующего двум строкам в G_e.

Кроме того, квадратичная матрица, которой соответствуют первые L строки G_ldgct, является нижней треугольной матрицей.

Шаг S3 включает в себя следующие подшаги:

S31: проводить перестановку столбцов над G_e и генерировать , в т.ч. А является нижней треугольной матрицей М-го порядка, а также записывать соответствующее отношение по перестановке столбцов G_e и G_a.

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

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

Кроме того, M=L-X_L, X_L является количеством битов, стертых каналом в символах первых L кодовых слов R; P=X_L.

Кроме того, допустим, что Xset_L является множеством номеров символов вычеркнутых кодовых слов в первых L символах кодовых слов R после заполнения известных битов в количестве L-K, количество номеров в данном множестве составляет X_L;

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

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

блок заполнения и стирания предназначен для того, чтобы заполнять известные биты в количестве L-K в принятой последовательности кодовых слов R, а также вычеркивать символы кодового слова, стертые каналом, генерировать и выводить R_e; из транспонированной матрицы G_ldgct порождающей матрицы LDGC вычеркивать строки, соответствующие символам кодового слова, стертым каналом, генерировать и выводить G_e; в данном процессе, процессорные слова в количестве WNum используются для поочередного хранения полных или частичных матричных элементов с одинаковыми положениями во всех строках G_e; каждое процессорное слово хранит матричные элементы в количестве WWid G_e;

блок исключения Гаусса предназначен для того, чтобы проводить исключение Гаусса над G_e в соответствии с отношением G_e×I_t=R_e, определять и выводить I_t;

блок генерации информационной последовательности предназначен для того, чтобы принимать I_t, выведенную блоком исключения Гаусса; в соответствии с отношением G_ldgct(0:L-1,0:L-1)×I_t=s_t получать s_t, а также из s_t вычеркивать известные биты в количестве L-K, и после того выводить исходную информационную последовательность битов K.

Вышеуказанная G_ldgct является матрицей поля GF(2) строки N+L-K и столбца L, WWid является шириной процессорного слова, WNum=ceil(P/WWid), P является количеством матричных элементов, хранящих одним битом процессорного слова, во всех строках G_e.

Кроме того, блок исключения Гаусса определяет I_t с применением исключения Гаусса; а также в процессе исключения Гаусса, для матричных элементов, хранящихся одним битом процессорного слова, во всех строках G_e, осуществляет сложение строк соответствующих строк с помощью операции XOR биты процессорного слова, соответствующего двум строкам в G_e.

Кроме того, квадратичная матрица, которой соответствуют первые L строки G_ldgct, является нижней треугольной матрицей.

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

блок исключения Гаусса по отношению определяет , а также по информации о соответствующем отношении по перестановке столбцов, выведенной блоком перестановки столбцов, проводит обратную перестановку строк над , получает и выводит I_t;

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

Кроме того, M=L-X_L, X_L является количеством битов, стертых каналом в символах первых L кодовых слов R; Р=X_L.

Кроме того, допустим, что Xset_L является множеством номеров символов вычеркнутых кодовых слов в первых L символах кодовых слов R после заполнения известных битов в количестве L-K, количество номеров в данном множестве составляет X_L;

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

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

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

Фиг.1 является схемой транспонированной порождающей матрицы LDGC G_ldgct;

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

Фиг.3 является схемой проведения обработки стирания порождающей матрицы в соответствии с состоянием стирания принятой последовательности R_t кодовых слов;

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

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

Фиг.6 является схемой перестановки столбцов над порождающей матрицей стирания G_e;

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

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

Из вышеуказанного очевидно, что матричные элементы порождающей матрицы LDGC (включая G_struct или G_random) только состоят из 0 и 1, а также операция сложения строк, которой касается исключения Гаусса, является сложением по модулю 2; поэтому можно только использовать один бит для хранения и выражения одного матричного элемента, а также использовать побитовое исключающее ИЛИ (т.е. XOR) для замены сложения по модулю 2 всех матричных элементов, быстро осуществляется операция сложения строк порождающей матрицы LDGC.

Например:

содержание i-й строки row_i выражается как: 10000101;

содержание j-й строки row_j выражается как: 11000111;

сложение содержания i-й строки и j-й строки эквивалентно:

row_j=row_i⊕row_i=10000101⊕11000111=01000010.

Вышеуказанное «⊕» обозначает операцию с битами-XOR.

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

Фиг.4 является технологической схемой способа декодирования кода порождающей матрицы с низкой плотностью в первом примере осуществления настоящего изобретения; данный пример осуществления является способом декодирования общго назначения для структурированной и неструктурированной порождающей матрицы LDGC (G_struct и G_random). Как показано на фиг.4, данный способ включает в себя следующие шаги:

401: на соответственном месте принятой последовательности кодовых слов R_t, заполнять последовательность известных битов длительностью d=L-K, при этом вычеркивать символы кодовых слов, стертые каналом, и получается R_e;

где K является длительностью битов исходной информации, L является длительностью кодирования заполненных битов исходной информации.

Допустим, что символы в количестве X_T, заполненные последовательностью известных битов в формуляре R=(r₀, r₁,…… r_N+d-1)^T:{r_i, r_j,…, r_p…r_x}, стираются каналом; где символы в количестве X_L в первых L символах {r_i, r_j,…, r_p} стираются каналом; то Xset={i, j,…, р,…, х}; Xset_L={i, j,… p}.

402: в соответствии с состоянием стирания принятой последовательности кодовых слов R_t, проводится обработка стирания (вычеркивания) над G_ldgct, и получается порождающая матрица стирания G_e; где каждая строка G_e выражается в виде процессорного слова (сокращенно как процессорное слово) в количестве WNum, конечно, каждая строка G_ldgct также может быть выражена в виде процессорного слова в количестве WNum.

Допустим, что Xset={i, j,…, р,…, х}; Xset_L={i, j,… p}, соответственно стирать {i-ю, j-ю, …, р-ю, …, х-ю} строку в G_ldgct, то получается G_e.

Так как каждая строка G_e(G_ldgct) включает в себя элементы в количестве L, поэтому WNum=ceil(L/WWid); WWid является шириной процессорного слова (в обычном случае представляет собой 8, 16, 32, 64, измеряется в битах); т.е. одно процессорное слово используется для поочередного хранения и выражения непрерывных элементов в количестве WWid в G_e (G_ldgct).

В случае, если L не является целым кратным WWid, последнее процессорное слово по каждой строке включает в себя последние элементы в количестве mod(L,WWid), для остальных битов в количестве Z=WWid-mod(L,WWid) данных процессорных слов можно обнулить.

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

Окончательно, двумерный массив можно использоваться для выражения G_e(G_ldgct), один элемент в двумерном массиве является одним процессорным словом. Общее количество элементов данного двумерного массива составляет: (N+d-X_T)×WNum; X_T обозначает количество строк стирания. Отсюда следует, что при применении вышеуказанного способа выражения матрицы в настоящем изобретении можно экономить пространство памяти в большом объеме.

Например, ширина процессорного слова WWid=32, каждая строка G_e(G_ldgct) включает в себя элементы в количестве L=2000, поэтому нужно применять процессорные слова в количестве ceil(2000/32)=63 для выражения каждой строки G_e(G_ldgct); так как 2000 не является целым кратным 32, mod(2000,32)=16, поэтому последнее процессорное слово только обладает 16 действительными битами, остальные биты в количестве 32-16=16 данного процессорного слова бессмысленны, можно обнулить.

403: в соответствии с отношением системы уравнений G_e×I_t=R_e решается система уравнений и определяется промежуточная переменная I_t.

В процессе определения промежуточной переменной I_t с применением исключения Гаусса, команда XOR процессора используется для выполнения касающейся операции «сложения строк»; поэтому одна целая операция сложения строк может быть заменена операцией XOR процессорных слов в количестве WNum, т.е. проводится параллельная обработка операции сложения строк, параллельное измерение составляет WWid, чрезвычайно повышать скорость операции «сложения строк».

404: в соответствии с отношением системы уравнений G_ldgct(0:L-1,0:L-1)×I_t=s_t определяется s_t, а также из s_t вычеркивать вышеуказанные заполненные известные биты в количестве d, получается исходная информационная последовательность m битов К и декодирование LDGC выполняется.

Фиг.5 является технологической схемой способа декодирования кода порождающей матрицы с низкой плотностью во втором примере осуществления настоящего изобретения; данный пример осуществления является способом декодирования для структурированной порождающей матрицы LDGC (G_struct), процессорное слово может только использоваться для хранения частичных элементов каждой строки в G_struct после обработки стирания, перестановки столбцов. Как показано на фиг.5, данный способ включает в себя следующие шаги:

501: на соответственном месте принятой последовательности кодовых слов R_t, заполнять последовательность известных битов длительностью d=L-K, при этом вычеркивать символы кодовых слов, стертые каналом, и получать R_e;

где K является длительностью битов исходной информации, L является длительностью кодирования заполненных битов исходной информации.

Допустим, что символы в количестве X_T, заполненные последовательностью известных битов в формуляре R=(r₀, r₁,…… r_N+d-1)^T:{r_i, r_j,…, r_p…r_x}, стираются каналом; где символы в количестве X_L в первых L символах {r_i, r_j,…, r_p} стираются каналом; то Xset={i, j,…, р,…, х}; Xset_L={i, j,… p}.

502: в соответствии с состоянием стирания принятой последовательности кодовых слов R_t, проводится обработка стирания (вычеркивания) над G_ldgct, и получается порождающая матрица стирания G_e.

Допустим, что Xset={i, j,…, p,…, х}; Xset_L={i, j,… p}, соответственно стирать {i-ю, j-ю, …, p-ю, …, х-ю} строку в G_ldgct, то получается G_e.

503: проводить перестановку столбцов над порождающей матрицей стирания G_e для того, чтобы матрица М-порядка вершиной (0, 0) становилась нижней треугольной матрицей, переставленная матрица G_e записывается как порождающая матрица перестановки G_a; а также записывать соответствующее отношение по перестановке столбцов G_e и G_a для проведения обратной операции порожденного от соответствующей операции перестановки над I_t в процессе вышеуказанной перестановки столбцов

Фиг.6 является схемой проведения перестановки столбцов над порождающей матрицей стирания G_e.

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

,

где матрица А является квадратичной матрицей М-порядка, все элементы на диагоналях которой являются ненулевыми элементами, отличающимися строгими нижними треугольниками; матрица С - матрица размером M×(L-M); матрица D - матрица размером (N-K-(X_T-X_L))×М; матрица В - матрица размером (N-K-(X_T-X_L))(L-M). Вышеуказанное М=L-X_L.

504: каждая строка В и С в G_a выражается процессорными словами в количестве WNum.

Из-за того, что длина каждой строки В и С составляет Xset_L, допустим, что ширина процессорного слова составляет WWid, то:

WNum=ceil(Xset_L/WWid).

В случае, если Xset_L не является целым кратным WWid, последнее процессорное слово по каждой строке включает в себя последние элементы в количестве mod(Xset_L,WWid); для остальных битов в количестве Z=WWid-mod(Xset_L,WWid) данные процессорных слов можно обнулить.

Поэтому двумерный массив отдельно используется для выражения В и С, один элемент в двумерном массиве является одним процессорным словом. Общее количество элементов двумерного массива, которому соответствует матрица С, составляет: M×WNum; общее количество элементов двумерного массива, которому соответствует матрица В, составляет: (N-K-(X_T-X_L))×WNum.

Например, длина строки В и С составляет Xset_L=200; допустим, что ширина процессорного слова WWid=32, то:

WNum=ceil(Xset_L/WWid)=ceil(200/32)=7; т.е. хранение и выражение каждой строки В и С должны быть выполнены 7 процессорными словами.

Потому что 200 не является целым кратным 32, mod(Xset_L,WWid)=mod(200,32)=8, поэтому последнее процессорное слово только содержит 8 действительных битов, остальные биты в количестве 32-8=24 данного процессорного слова бессмысленны, можно обнулить.

Поэтому матрица С может быть сохранена и выражена двумерными массивами с общим количеством элементов М×7, матрица В может быть сохранена и выражена с помощью двумерными массивами с общим количеством элементов (N-K-(X_T-X_L))×7; относительно действующей техники, матрица С выражается двумерными массивами с общим количеством элементов М×200, матрица В выражается двумерными массивами с общим количеством элементов (N-K-(X_T-X_L))×200, тем самым огромное пространство для хранения сэкономлено.

Стоит отметить то, что ненулевые элементы в матрицах А и D могут быть непосредственно вычислены по формуле, определенной структурированной порождающей матрицей при кодировании, поэтому в действительности А и D не требуется хранение, а в процессе исключения А и D только нужно непосредственно вычислить и получать положение ненулевых элементов по формуле, определенной структурированной порождающей матрицей при кодировании, затем в соответствии с положениями этих ненулевых элементов проводится «сложение строки». Конечно, также можно использовать одинаковый способ для хранения и выражения А и D. А можно рассмотреть В и С как случайные редкие матрицы, поэтому операция сложения строки над ними только является последовательными сложениями соответствующего элемента. Одно процессорное слово используется для выражения конструкции данных с элементами в количестве WWid, данный способ позволяет оптимизировать обрабатывающую сложение строк способность программного обеспечения.

505: в соответствии с отношением системы уравнений решается система уравнений и определяется промежуточная переменная ; а также в соответствии с отношением перестановки от I_t до (т.е. отношение перестановки столбцов от G_e до G_a) проводится обратная перестановка, т.е. по определяется I_t.

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

506: в соответствии с отношением системы уравнений G_ldgct(0:L-1,0:L-1)×I_t=s_t определяется s_t, а также из s_t вычеркивать вышеуказанные заполненные известные биты в количестве d, получается исходная информационная последовательность m битов K и декодирование LDGC выполняется.

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

блок заполнения и стирания предназначен для того, чтобы заполнять известные биты в количестве d=L-K в принятой последовательности кодовых слов R, а также вычеркивать символы кодового слова, стертые каналом, генерировать и выводить R_e; из транспонированной матрицы G_ldgct порождающей матрицы LDGC вычеркивать строки, соответствующие символам кодового слова, стертым каналом, генерировать и выводить G_e.

В данном процессе, для структурированной и неструктурированной порождающей матрицы LDGC, блок заполнения и стирания использует процессорное слова в количестве WNum для поочередного хранения полных или частичных матричных элементов с одинаковыми положениями во всех строках G_e; каждое процессорное слово хранит матричные элементы в количестве WWid G_e; WWid является шириной процессорного слова, WNum=ceil(Len/WWid). Len обозначает количество элементов в одной строке, для выражения которых должно применяться процессорное слово.

Блок перестановки столбцов предназначен для проведения перестановки столбцов G_e, выведенной блоком заполнения и стирания, для того, чтобы матрица М-го порядка А, вершина которой является элементом 0-го столбца и 0-й стройки в G_e, стала нижней треугольной матрицей, для генерирования и вывода , а также для вывода информации о соответствующем отношении по перестановке столбцов G_e и G_a;

M=L-X_L, X_L является количеством битов, стертых каналом в символах первых L кодовых слов R.

Блок перестановки столбцов может перемещать столбцы в G_e, номер которых принадлежит к Xset_L к самой правой стороне G_e, свободные места соответствующих столбцов поочередно заполнены столбцами, дальнейшие номера которых не принадлежат к Xset_L, и определять G_a. Для неструктурированной порождающей матрицы LDGC данный блок является выборочным.

Блок исключения Гаусса предназначен для того, чтобы проводить исключение Гаусса над G_e, выведенной блоком заполнения и стирания в соответствии с отношением G_e×I_t=R_e, определять и выводить I_t; или проводить исключение Гаусса над G_a, выведенной блоком перестановки столбцов в соответствии с отношением , определять а также по информации о соответствующем отношении по перестановке столбцов, выведенной блоком перестановки столбцов, проводить обратную перестановку строк над , получать и выводить I_t.

Блок генерации информационной последовательности предназначен для того, чтобы принимать I_t, выведенную блоком исключения Гаусса; в соответствии с отношением G_ldgct(0:L-1,0:L-1)×I_t=s_t получать s_t, а также из s_t вычеркивать известные биты в количестве d, и после того выводить исходную информационную последовательность битов K.

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

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

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

Изобретение относится к области кодирования и декодирования данных, в частности к способу и устройству декодирования кода порождающей матрицы с низкой плотностью. Для принятой последовательности битов информации, переданных после кодирования LDGC, проводится декодирование, при этом способ включает в себя следующее содержание: S1: в принятой последовательности кодовых слов R заполнять известные биты в количестве L-K, а также вычеркивать символы кодового слова в R, стертые каналом, получается R_e; S2: из транспонированной матрицы G_ldgct порождающей матрицы LDGC вычеркивать строки, соответствующие символам кодового слова, стертым каналом, получается G_e; S3: по отношению G_e×I_t=R_e определяется I_t; S4: по отношению G_ldgct(0:L-1,0:L-1)×I_t=s_t определяется s_t, а также из s_t вычеркивать вышеуказанные заполненные известные биты в количестве L-K, и исходная информационная последовательность битов К получается. Технический результат обеспечивает снижение расходов памяти декодера, а также ускорение скорости декодирования, тем самым LDGC более гибко использоваться в системе коммуникации высокой скорости. 2 н. и 8 з.п. ф-лы, 7 ил.

1. Способ декодирования кода порождающей матрицы с низкой плотностью для принятой последовательности битов информации, переданных после кодирования LDGC, проводится декодирование, отличающийся тем, что способ включает в себя следующее:
S1: в принятой последовательности кодовых слов R заполнять известные биты в количестве L-K, а также вычеркивать символы кодового слова в R, стертые каналом, получается R_e;
S2: из транспонированной матрицы G_ldgct порождающей матрицы LDGC вычеркивать строки, соответствующие символам кодового слова, стертым каналом, получается G_e; в данном процессе, процессорные слова в количестве WNum используются для поочередного хранения полных или частичных матричных элементов с одинаковыми положениями во всех строках G_e, каждое процессорное слово хранит матричный элемент в количестве WWid G_e;
S3: по отношению G_e×I_t=R_e определяется I_t;
S4: по отношению C_ldgct(0:L-1,0:L-1)×I_t=s_t определяется s_t, а также из s_t вычеркивать указанные заполненные известные биты в количестве L-K, и исходная информационная последовательность битов К получается;
указанное G_ldgct является матрицей поля GF(2) строки N+L-K и столбца L, WWid является шириной процессорного слова, WNum=ceil(P/WWid), P является количеством матричных элементов, хранящих одним битом процессорного слова, во всех строках G_e;
причем способ декодирования осуществляют декодером.

2. Способ по п.1, отличающийся тем, что на шаге S3 определять I_t с применением исключения Гаусса; а также в процессе исключения Гаусса, для матричных элементов, хранящих одним битом процессорного слова, во всех строках G_e, осуществляется сложение строк соответствующих строк с помощью операции XOR биты процессорного слова, соответствующего двум строкам в G_e.

3. Способ по п.1, отличающийся тем, что
указанная квадратичная матрица, которой соответствуют первые L строки G_ldgct, является нижней треугольной матрицей;
шаг S3 включает в себя следующие подшаги:
S31: проводить перестановку столбцов над G_e и генерировать , где А является нижней треугольной матрицей М-го порядка, а также записывать соответствующее отношение по перестановке столбцов G_e и G_a.
S32: по отношению определяется , а также по указанному соответствующему отношению по перестановке столбцов проводить обратную перестановку строк над и получать ;
где Р является количеством столбцов матриц С и В, указанное процессорное слово используется для поочередного хранения матричных элементов во всех строках С и В, все биты каждого процессорного слова поочередно хранят матричные элементы в количестве WWid С и В.

4. Способ по п.3, отличающийся тем, что M=L-X_L, X_L является количеством битов, стертых каналом в символах первых L кодовых слов R; P=X_L.

5. Способ по п.3, отличающийся тем, что
допустим, что Xset_L является множеством номеров символов вычеркнутых кодовых слов в первых L символах кодовых слов R после заполнения известных битов в количестве L-K, количество номеров в данном множестве составляет x₁;
на шаге S31, столбцы в G_e, номер которых принадлежат к Xset_L, перемещаются к самой правой стороне G_e, свободные места соответствующих столбцов поочередно заполнены столбцами, дальнейшие номера которых не принадлежат к Xset_L, и определять G_a.

6. Устройство декодирования кода порождающей матрицы с низкой плотностью, содержащееся в декодере, отличающееся тем, что устройство включает в себя блок заполнения и стирания, блок исключения Гаусса, блок генерации информационной последовательности, причем
указанный блок заполнения и стирания предназначен для того, чтобы заполнять известные биты в количестве L-K в принятой последовательности кодовых слов R, а также вычеркивать символы кодового слова, стертые каналом, генерировать и выводить R_e; из транспонированной матрицы G_ldgct порождающей матрицы LDGC вычеркивать строки, соответствующие символам кодового слова, стертым каналом, генерировать и выводить G_e; в данном процессе, процессорные слова в количестве WNum используются для поочередного хранения полных или частичных матричных элементов с одинаковыми положениями во всех строках G_e; каждое процессорное слово хранит матричные элементы в количестве WWid G_e;
указанный блок исключения Гаусса предназначен для того, чтобы проводить исключение Гаусса над G_e в соответствии с отношением G_e×I_t=R_e, определять и выводить I_t;
указанный блок генерации информационной последовательности предназначен для того, чтобы принимать I_t, выведенную блоком исключения Гаусса; в соответствии с отношением G_ldgct(0:L-1,0:L-1)×I_t=s_t получать s_t, а также из s_t вычеркивать известные биты в количестве L-K, и после того выводить исходную информационную последовательность битов К;
указанное G_ldgct является матрицей поля GF(2) строки N+L-K и столбца L, WWid является шириной процессорного слова, WNum=ceil(P/WWid), P является количеством матричных элементов, хранящих одним битом указанного процессорного слова, во всех строках G_e.

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

8. Устройство по п.6, отличающееся тем, что
указанная квадратичная матрица, которой соответствуют первые L строки G_ldgct; является нижней треугольной матрицей;
указанное устройство включает в себя блок перестановки столбцов, предназначенный для проведения перестановки столбцов G_e, выведенный указанным блоком заполнения и стирания, и для генерирования , где А является нижней треугольной матрицей М-го порядка, а также для вывода информации о соответствующем отношении по перестановке столбцов G_e и G_a;
указанный блок исключения Гаусса по отношению определяет , а также по информации о соответствующем отношении по перестановке столбцов, выведенной блоком перестановки столбцов, проводит обратную перестановку строк над , получает и выводит I_t;
где Р является количеством столбцов матриц С и В, указанное процессорное слово используется для поочередного хранения матричных элементов во всех строках С и В, все биты каждого процессорного слова поочередно хранят матричные элементы в количестве WWid С и В.

9. Устройство по п.8, отличающееся тем, что M=L-X_L, X_L является количеством битов, стертых каналом в символах первых L кодовых слов R; P=X_L.

10. Устройство по п.8, отличающееся тем, что
допустим, что Xset_L является множеством номеров символов вычеркнутых кодовых слов в первых L символах кодовых слов R после заполнения известных битов в количестве L-K, количество номеров в данном множестве составляет X_L;
указанный блок перестановки столбцов перемещает столбцы в G_e, номер которых принадлежат к Xset_L к самой правой стороне G_e, свободные места соответствующих столбцов поочередно заполнены столбцами, дальнейшие номера которых не принадлежат к Xset_L, и определяет G_a.