СПОСОБ И УСТРОЙСТВО ДЕКОДИРОВАНИЯ КОДА ПОРОЖДАЮЩЕЙ МАТРИЦЫ С НИЗКОЙ ПЛОТНОСТЬЮ
METHOD AND APPARATUS FOR DECODING LOW-DENSITY GENERATOR MATRIX CODE

Область техники
Настоящее изобретение касается области кодирования и декодирования данных, в частности способа и устройства декодирования кода порождающей матрицы с низкой плотностью.
Уровень техники
Цель кодирования канала заключается в обеспечении надежной передаче информации, сложность осуществления схемы кодирования канала главным образом сосредоточена в стороне декодирования, в обычном случае декодер является основной частей схемы кодирования канала. Декодер может быть выполнен аппаратным обеспечением, т.е. применять логический блок аппаратного обеспечения для создания декодера; также может быть выполнен программным обеспечением, т.е. применять процессор общего назначения (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).
struct
random
random
Порождающая матрица структурированного LDGC еще обладает другими характеристиками, может получаться из очень малой основной матрицы с помощью расширенной коррекции; в частности, квадратичная матрица, соответствующая первым L строкам, обычно является одной верхней треугольной матрицей или нижней треугольной матрицей. А порождающие матрицы LDGC без структурированных характеристик у кодов Raptor и т.д. являются случайными бинарными матрицами. В дальнейшем Gldgc используется для единого обозначения порождающей матрицы LDGC, при необходимости отдельного обозначения, G используется для обозначения транспонирования порождающей матрицы структурированного LDGC, G используется для обозначения транспонирования порождающей матрицы LDGC без структурированных характеристик (можно сокращенно называть как порождающая матрица неструктурированного LDGC), в частности, G включает порождающую матрицу кода Raptor.
ldgct
ldgc
t
t
t
t
struct
random
ldgct
В дальнейшем описании всякие «векторы» или «матрицы» с нижним индексом в виде t обозначают транспонирование бывших «векторов» или «матриц», вектор или матрица и их транспонирование являются совершенно одинаковыми по содержанию, иногда они могут выражать одинаковый предмет. Например, определение G является транспонированием G, I является транспонированием I, R является транспонированием R, поскольку I и R являются вектором строк, где I и R являются вектором столбцов; в дальнейшем G, G используются для отдельного обозначения своих транспонированных порождающих матриц G.
ldgct
struct
Фиг.1 является схемой транспонированной порождающей матрицы LDGC G. Как показано на фиг.1а, в структурированной порождающей матрице LDGC G квадратичная матрица, соответствующая первым L строкам, обычно является одной верхней треугольной матрицей или нижней треугольной матрицей. Как показано на фиг.1b, квадратичная матрица кода Raptor, соответствующая первым L строкам, является случайной матрицей без характеристик верхней треугольной матрицы или нижней треугольной матрицы. В т.ч. в схеме х, у может составлять 0.
ldgc
ldgc
ldgc
ldgc
t
ldgc
ldgc
Кодирование LDGC получается таким образом, сначала определяется промежуточная переменная с помощью относительного отношения между битами информации (данными, подлежащими передаче) и промежуточной переменной в системном коде, затем промежуточная переменная умножается на порождающую матрицу и получается кодированное кодовое слово. В частности, процесс кодирования заключается в том, что сначала исходная информационная последовательность m битов K заполнена известными битами в количестве d=L-K, после этого получается последовательность s битов L, затем в соответствии с отношением системы уравнений: I×G(0:L-1,0:L-1)=s, после решения системы уравнений получается последовательность промежуточной переменной битов L, затем промежуточная переменная умножается на порождающую матрицу, т.е. I×G(0:L-1,0:N+d-1) и получается последовательность  кодовых слов битов N+d (включая заполненные биты в количестве d), для заполненных битов в количестве d  передача не требуется, поэтому в самом деле последовательность G кодовых слов битов N передается после того, как G проходит через канал (стирание является возможным), последовательность кодовых слов, принимаемая приемным терминалом, является R. В т.ч. s является вектором 1×L; I является вектором 1×L; R является вектором 1×N, ее транспонирование R является вектором N×1; G(0:L-1,0:L-1) является квадратичной матрицей L×L, в обычной случае, данная квадратичная матрица является одной верхней треугольной матрицей или нижней треугольной матрицей, G(0:L-1,0:N+d-1) является матрицей L×(N+d). Подробный процесс кодирования приведен в патенте «способ и устройство кодирования и декодирования кода порождающей матрицы с низкой плотностью».
Фиг.2 является технологической схемой способа декодирования кода порождающей матрицы с низкой плотностью. Как показано на фиг.2, процесс декодирования включает в себя следующие шаги:
t
e
201: на соответственном месте принятой последовательности кодовых слов R заполняется последовательность известных битов длительностью d=L-K, например: 1, 1, …, 1., при этом вычеркиваются символы кодовых слов, стертые каналом и получается R,
где K является длительностью битов исходной информации, L является длительностью кодирования заполненных битов исходной информации;
t
ldgct
e
202: в соответствии с состоянием стирания принятой последовательности кодовых слов R проводится обработка стирания (вычеркивания) над G и получается порождающая матрица стирания G.
t
e
Фиг.3 является схемой проведения обработки стирания порождающей матрицы в соответствии с состоянием стирания принятой последовательности кодовых слов R. Как показано на фиг.3, после обработки стирания первые L строки порождающей матрицы G больше не являются нижней треугольной матрицей.
T,
0
1
N+d-1
i
j
p
x
L
i
j
p
L
ldgct
e
e
T
Допустим, что символы в количестве X заполненные последовательностью известных битов в формуляре R=(r, r,…… r):{r, r,…, r…r}, стираются каналом, где символы в количестве X в первых L символах {r, r,…, r} стираются каналом, то Xset={i, j,…, р,…, х}; Xset={i, j,… p}. Соответственно, стирать {i-ю, j-ю, …, р-ю, …, х-ю} строку в G, то получается G, при этом из-за того что некоторые строки стерты, то матрица над G не является строгой диагонализацией, как показано на фиг.3 (с),
e
t
e
t
203: в соответствии с отношением системы уравнений G×I=R решается система уравнений и определяется промежуточная переменная I;
ldgct
t
t
t
t
204: в соответствии с отношением системы уравнений G(0:L-1,0:L-1)×I=s определяется s, а также, если из s вычеркивать вышеуказанные заполненные известные биты в количестве d, получается исходная информационная последовательность m битов K и декодирование LDGC выполняется.
t
В вышеуказанном процессе декодирования самым ключевым шагом является определение промежуточной переменной I, это требуется от решения крупной системы двоичных линейных уравнений. По проекту, для решения линейных уравнений можно использовать исключение Гаусса или итерацию, в соответствии с характеристиками LDGC, исключение Гаусса более подходит к декодированию LDGC, поэтому скорость процесса исключения Гаусса прямо влияет на скорость декодирования LDGC.
t
ldgct
t
t
ldgct
e
t
e
e
t
e
ldgct
e
ldgct
e
t
t
e
В процессе определения промежуточной переменной I в соответствии с отношением системы уравнений G(0:N+d-1,0:L-1)×I=R (при стирании канала G записывается как G, R записывается как R, вышеуказанное отношение системы уравнений является G×I=R), для проведенного исключения Гаусса требуется произвести три типа элементарных преобразований над G (при стирании канала является G), как «перестановка строк, сложение строки и перестановка столбцов». В соответствии с принципом линейной алгебры, в целях обеспечения правильности системы уравнений, при проведении элементарного преобразования над G(G), для I и R (при стирании канала является R) нужно проводить следующую соответствующую обработку:
ldgct
e
t
e
1) перестановка строк, в случае, если проводить перестановку i-й и j-й строк G(G), то для i-го и j-го бита R(R) должно проводить перестановку;
ldgct
e
t
e
2) сложение строки, в случае, если проводить сложение i-й и j-й строк G(G), то для i-го и j-го бита R(R) должно проводить сложение (сложение по модулю 2);
ldgct
e
t
3) перестановка столбцов, в случае, если проводить перестановку i-го и j-го столбцов G(G), то для i-го и j-го бита I должно проводить перестановку.
t
ldgct
e
t
t
t
t
Так как окончательный результат требует получения I, а при проведении перестановки столбцов G(G) для элементов в I соответственно проводится перестановка, поэтому нужно записать состояние перестановки I, чтобы использовать в дальнейшем процессе определения обратной перестановки. По проекту, можно проводить запись состояния перестановки I с помощью одного массива. A R не является окончательными требуемыми данными, можно прямо обрабатывать их без необходимости записи состояния обработки.
ldgct
e
ldgct
e
t
t
e
t
t
e
Так как эти отношения преобразования являются строго соответствующими, а также сложность исключения Гаусса главным образом выражается в обработке над G(G), в дальнейшем ради удобства описания всякое элементарное преобразование над G(G), соответственная обработка над I и R(R) должны быть строго выполнены в соответствии с вышеуказанными тремя состояниями. Для выделения главного, в дальнейшем иногда будет упрощаться описание об обработке I и R(R).
ldgct
ldgct
e
Как правило, сложность (объем вычисления) осуществления исключения Гаусса главным образом выражается в операции «сложение строки» матрицы. Так как все элементы G происходят из поля GF(2), поэтому операция сложения двух строк в G(G) является операцией «сложение по модулю 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).
ldgct
ldgct
e
Вышеуказанные примеры показывают, что если  все элементы в G происходят из поля GF(2), то значение элемента только ограничено в 0 и 1, если прямо сохранять эти элементы 0 и 1, значит то, что каждый элемент бита занимает один блок памяти или одно процессорное слово (обычно занимает 32 битов), то при более большой длине кода G(G) требует от огромного пространства памяти; а также операция сложения строк требует от проведения сложения по модулю 2 над каждым элементом, расход времени является большим.
Раскрытие изобретения
Настоящее изобретения предназначено для решения такой технической проблемы, как преодолеть недостатки в действующей технике, предоставлять способ и устройство декодирования кода порождающей матрицы с низкой плотностью, предназначенное для экономии пространства памяти, занятой порождающей матрицей LDGC, а также для повышения скорости операции.
Для решения вышеуказанных проблем настоящее изобретение предоставляет способ декодирования кода порождающей матрицы с низкой плотностью для принятой последовательности битов информации, переданных после кодирования LDGC, проводится декодирование, данный способ включает в себя следующее содержание:
e
S1: в принятой последовательности кодовых слов R заполнять известные биты в количестве L-K, а также вычеркивать символы кодового слова в R, стертые каналом, получается R;
ldgct
e
e
e
S2: из транспонированной матрицы G порождающей матрицы LDGC вычеркивать строки, соответствующие символам кодового слова, стертым каналом, получается G; в данном процессе, процессорные слова в количестве WNum используются для поочередного хранения полных или частичных матричных элементов с одинаковыми положениями во всех строках G, каждое процессорное слово хранит матричный элемент в количестве WWid G;
e
t
e
t
S3: по отношению G×I=R определяется I;
ldgct
t
t
t
t
S4: по отношению G(0:L-1,0:L-1)×I=s определяется s, а также из s вычеркивать вышеуказанные заполненные известные биты в количестве L-K, и исходная информационная последовательность битов K получается;
ldgct
e
вышеуказанная G является матрицей поля GF(2) строки N+L-K и столбца L, WWid является шириной процессорного слова, WNum=ceil(P/WWid), P является количеством матричных элементов, хранящихся одним битом процессорного слова, во всех строках G;
причем способ декодирования осуществляют декодером.
t
e
e
Кроме того, в шаге S3 определять I с применением исключения Гаусса; а также в процессе исключения Гаусса, для матричных элементов, хранящихся одним битом процессорного слова, во всех строках G, осуществляется сложение строк соответствующих строк с помощью операции XOR бита процессорного слова, соответствующего двум строкам в G.
ldgct
Кроме того, квадратичная матрица, которой соответствуют первые L строки G, является нижней треугольной матрицей.
Шаг S3 включает в себя следующие подшаги:
e
e
a
S31: проводить перестановку столбцов над G и генерировать , в т.ч. А является нижней треугольной матрицей М-го порядка, а также записывать соответствующее отношение по перестановке столбцов G и G.
t
S32: по отношению  определяется , а также по вышеуказанному соответствующему отношению по перестановке столбцов проводить обратную перестановку строк над  и получать I;
где Р является количеством столбцов матриц С и В, процессорное слово используется для поочередного хранения матричных элементов во всех строках С и В, все биты каждого процессорного слова поочередно хранят матричные элементы в количестве WWid С и В.
L
L
L
Кроме того, M=L-X, X является количеством битов, стертых каналом в символах первых L кодовых слов R; P=X.
L
L
Кроме того, допустим, что Xset является множеством номеров символов вычеркнутых кодовых слов в первых L символах кодовых слов R после заполнения известных битов в количестве L-K, количество номеров в данном множестве составляет X;
e
L
e
L
a
В шаге S31, столбцы в G, номер которых принадлежат к Xset, перемещаются к самой правой стороне G, свободные места соответствующих столбцов поочередно заполнены столбцами, дальнейшие номера которых не принадлежат к Xset, и определять G.
Настоящее изобретение еще представляет одно устройство декодирования кода порождающей матрицы с низкой плотностью, данное устройство содержится в декодере и включает в себя: блок заполнения и стирания, блок исключения Гаусса, блок генерации информационной последовательности, в т.ч.:
e
ldgct
e
e
e
блок заполнения и стирания предназначен для того, чтобы заполнять известные биты в количестве L-K в принятой последовательности кодовых слов R, а также вычеркивать символы кодового слова, стертые каналом, генерировать и выводить R; из транспонированной матрицы G порождающей матрицы LDGC вычеркивать строки, соответствующие символам кодового слова, стертым каналом, генерировать и выводить G; в данном процессе, процессорные слова в количестве WNum используются для поочередного хранения полных или частичных матричных элементов с одинаковыми положениями во всех строках G; каждое процессорное слово хранит матричные элементы в количестве WWid G;
e
e
t
e
t
блок исключения Гаусса предназначен для того, чтобы проводить исключение Гаусса над G в соответствии с отношением G×I=R, определять и выводить I;
t
ldgct
t
t
t
t
блок генерации информационной последовательности предназначен для того, чтобы принимать I, выведенную блоком исключения Гаусса; в соответствии с отношением G(0:L-1,0:L-1)×I=s получать s, а также из s вычеркивать известные биты в количестве L-K, и после того выводить исходную информационную последовательность битов K.
ldgct
e
Вышеуказанная G является матрицей поля GF(2) строки N+L-K и столбца L, WWid является шириной процессорного слова, WNum=ceil(P/WWid), P является количеством матричных элементов, хранящих одним битом процессорного слова, во всех строках G.
t
e
e
Кроме того, блок исключения Гаусса определяет I с применением исключения Гаусса; а также в процессе исключения Гаусса, для матричных элементов, хранящихся одним битом процессорного слова, во всех строках G, осуществляет сложение строк соответствующих строк с помощью операции XOR биты процессорного слова, соответствующего двум строкам в G.
ldgct
Кроме того, квадратичная матрица, которой соответствуют первые L строки G, является нижней треугольной матрицей.
e
e
a
Устройство еще включает в себя блок перестановки столбцов, предназначен для проведения перестановки столбцов над G, выведенной блоком заполнения и стирания, и для генерирования , в т.ч. А является нижней треугольной матрицей М-го порядка, а также для вывода информации о соответствующем отношении по перестановке столбцов G и G;
t
блок исключения Гаусса по отношению  определяет , а также по информации о соответствующем отношении по перестановке столбцов, выведенной блоком перестановки столбцов, проводит обратную перестановку строк над , получает и выводит I;
где Р является количеством столбцов матриц С и В, процессорное слово используется для поочередного хранения матричных элементов во всех строках С и В, все биты каждого процессорного слова поочередно хранят матричные элементы в количестве WWid С и В.
L
L
L
Кроме того, M=L-X, X является количеством битов, стертых каналом в символах первых L кодовых слов R; Р=X.
L
L
Кроме того, допустим, что Xset является множеством номеров символов вычеркнутых кодовых слов в первых L символах кодовых слов R после заполнения известных битов в количестве L-K, количество номеров в данном множестве составляет X;
e
L
e
L
a
блок перестановки столбцов перемещает столбцы в G, номер которых принадлежит к Xset к самой правой стороне G, свободные места соответствующих столбцов поочередно заполнены столбцами, дальнейшие номера которых не принадлежат к Xset, и определять G.
Применяя представленный способ декодирования LDGC в настоящем изобретении, в полном объеме используя характеристики порождающей матрицы LDGC и параллельной обработкой процессором много битов, применяя одно «слово» процессора (сокращенно как процессорное слово) для хранения и выражения элементов в количестве «ширины слова процессора» декодирования порождающей матрицы LDGC, сравнивая со структурой памяти и способом выражения данных прямого хранения элементов порождающей матрицы LDGC, настоящее изобретение снизит расходы памяти декодера в большой степени, а также ускорит скорость декодирования, тем самым LDGC может более гибко использоваться в системе коммуникации высокой скорости.
Краткое описание чертежей
ldgct
Фиг.1 является схемой транспонированной порождающей матрицы LDGC G;
Фиг.2 является технологической схемой способа декодирования кода порождающей матрицы с низкой плотностью;
t
Фиг.3 является схемой проведения обработки стирания порождающей матрицы в соответствии с состоянием стирания принятой последовательности R кодовых слов;
Фиг.4 является технологической схемой способа декодирования кода порождающей матрицы с низкой плотностью в первом примере осуществления настоящего изобретения;
Фиг.5 является технологической схемой способа декодирования кода порождающей матрицы с низкой плотностью во втором примере осуществления настоящего изобретения;
e
Фиг.6 является схемой перестановки столбцов над порождающей матрицей стирания G;
Фиг.7 является схемой устройства декодирования кода порождающей матрицы с низкой плотностью в примере осуществления настоящего изобретения.
Осуществление изобретения
struct
random
Из вышеуказанного очевидно, что матричные элементы порождающей матрицы LDGC (включая G или G) только состоят из 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.
В дальнейшем, с учетом приложенных схем и примеров осуществления проводится подробное описание настоящего изобретения, стоит отметить то, что настоящее изобретение только обратит внимание на способ осуществления программного или программно-аппаратного декодера.
struct
random
Фиг.4 является технологической схемой способа декодирования кода порождающей матрицы с низкой плотностью в первом примере осуществления настоящего изобретения; данный пример осуществления является способом декодирования общго назначения для структурированной и неструктурированной порождающей матрицы LDGC (G и G). Как показано на фиг.4, данный способ включает в себя следующие шаги:
t
e
401: на соответственном месте принятой последовательности кодовых слов R, заполнять последовательность известных битов длительностью d=L-K, при этом вычеркивать символы кодовых слов, стертые каналом, и получается R;
где K является длительностью битов исходной информации, L является длительностью кодирования заполненных битов исходной информации.
T,
0
1
N+d-1
i
j
p
x
L
i
j
p
L
T
Допустим, что символы в количестве X заполненные последовательностью известных битов в формуляре R=(r, r,…… r):{r, r,…, r…r}, стираются каналом; где символы в количестве X в первых L символах {r, r,…, r} стираются каналом; то Xset={i, j,…, р,…, х}; Xset={i, j,… p}.
t
ldgct
e
e
ldgct
402: в соответствии с состоянием стирания принятой последовательности кодовых слов R, проводится обработка стирания (вычеркивания) над G, и получается порождающая матрица стирания G; где каждая строка G выражается в виде процессорного слова (сокращенно как процессорное слово) в количестве WNum, конечно, каждая строка G также может быть выражена в виде процессорного слова в количестве WNum.
L
ldgct
e
Допустим, что Xset={i, j,…, р,…, х}; Xset={i, j,… p}, соответственно стирать {i-ю, j-ю, …, р-ю, …, х-ю} строку в G, то получается G.
e
ldgct
e
ldgct
Так как каждая строка G(G) включает в себя элементы в количестве L, поэтому WNum=ceil(L/WWid); WWid является шириной процессорного слова (в обычном случае представляет собой 8, 16, 32, 64, измеряется в битах); т.е. одно процессорное слово используется для поочередного хранения и выражения непрерывных элементов в количестве WWid в G (G).
В случае, если L не является целым кратным WWid, последнее процессорное слово по каждой строке включает в себя последние элементы в количестве mod(L,WWid), для остальных битов в количестве Z=WWid-mod(L,WWid) данных процессорных слов можно обнулить.
Вышеуказанное ceil обозначает округление вверх, mod обозначает операцию определения модуля.
e
ldgct
T
T
Окончательно, двумерный массив можно использоваться для выражения G(G), один элемент в двумерном массиве является одним процессорным словом. Общее количество элементов данного двумерного массива составляет: (N+d-X)×WNum; X обозначает количество строк стирания. Отсюда следует, что при применении вышеуказанного способа выражения матрицы в настоящем изобретении можно экономить пространство памяти в большом объеме.
e
ldgct
e
ldgct
Например, ширина процессорного слова WWid=32, каждая строка G(G) включает в себя элементы в количестве L=2000, поэтому нужно применять процессорные слова в количестве ceil(2000/32)=63 для выражения каждой строки G(G); так как 2000 не является целым кратным 32, mod(2000,32)=16, поэтому последнее процессорное слово только обладает 16 действительными битами, остальные биты в количестве 32-16=16 данного процессорного слова бессмысленны, можно обнулить.
e
t
e
t
403: в соответствии с отношением системы уравнений G×I=R решается система уравнений и определяется промежуточная переменная I.
t
В процессе определения промежуточной переменной I с применением исключения Гаусса, команда XOR процессора используется для выполнения касающейся операции «сложения строк»; поэтому одна целая операция сложения строк может быть заменена операцией XOR процессорных слов в количестве WNum, т.е. проводится параллельная обработка операции сложения строк, параллельное измерение составляет WWid, чрезвычайно повышать скорость операции «сложения строк».
ldgct
t
t
t
t
404: в соответствии с отношением системы уравнений G(0:L-1,0:L-1)×I=s определяется s, а также из s вычеркивать вышеуказанные заполненные известные биты в количестве d, получается исходная информационная последовательность m битов К и декодирование LDGC выполняется.
struct
struct
Фиг.5 является технологической схемой способа декодирования кода порождающей матрицы с низкой плотностью во втором примере осуществления настоящего изобретения; данный пример осуществления является способом декодирования для структурированной порождающей матрицы LDGC (G), процессорное слово может только использоваться для хранения частичных элементов каждой строки в G после обработки стирания, перестановки столбцов. Как показано на фиг.5, данный способ включает в себя следующие шаги:
t
e
501: на соответственном месте принятой последовательности кодовых слов R, заполнять последовательность известных битов длительностью d=L-K, при этом вычеркивать символы кодовых слов, стертые каналом, и получать R;
где K является длительностью битов исходной информации, L является длительностью кодирования заполненных битов исходной информации.
T,
0
1
N+d-1
i
j
p
x
L
i
j
p
L
T
Допустим, что символы в количестве X заполненные последовательностью известных битов в формуляре R=(r, r,…… r):{r, r,…, r…r}, стираются каналом; где символы в количестве X в первых L символах {r, r,…, r} стираются каналом; то Xset={i, j,…, р,…, х}; Xset={i, j,… p}.
t
ldgct
e
502: в соответствии с состоянием стирания принятой последовательности кодовых слов R, проводится обработка стирания (вычеркивания) над G, и получается порождающая матрица стирания G.
L
ldgct
e
Допустим, что Xset={i, j,…, p,…, х}; Xset={i, j,… p}, соответственно стирать {i-ю, j-ю, …, p-ю, …, х-ю} строку в G, то получается G.
e
e
a
e
a
t
503: проводить перестановку столбцов над порождающей матрицей стирания G для того, чтобы матрица М-порядка вершиной (0, 0) становилась нижней треугольной матрицей, переставленная матрица G записывается как порождающая матрица перестановки G; а также записывать соответствующее отношение по перестановке столбцов G и G для проведения обратной операции порожденного  от соответствующей операции перестановки над I в процессе вышеуказанной перестановки столбцов
e
Фиг.6 является схемой проведения перестановки столбцов над порождающей матрицей стирания G.
e
L
e
L
В частности, для получения нижней треугольной матрицы, перемещают столбцы в G, номер которых принадлежат к Xset к самой правой стороне G, свободные места соответствующих столбцов поочередно заполнены столбцами, дальнейшие номера которых не принадлежат к Xset, и получают порождающую матрицу перестановки:
,
T
L
T
L
L
где матрица А является квадратичной матрицей М-порядка, все элементы на диагоналях которой являются ненулевыми элементами, отличающимися строгими нижними треугольниками; матрица С - матрица размером M×(L-M); матрица D - матрица размером (N-K-(X-X))×М; матрица В - матрица размером (N-K-(X-X))(L-M). Вышеуказанное М=L-X.
a
504: каждая строка В и С в G выражается процессорными словами в количестве WNum.
L
Из-за того, что длина каждой строки В и С составляет Xset, допустим, что ширина процессорного слова составляет WWid, то:
L
WNum=ceil(Xset/WWid).
L
L
L
В случае, если Xset не является целым кратным WWid, последнее процессорное слово по каждой строке включает в себя последние элементы в количестве mod(Xset,WWid); для остальных битов в количестве Z=WWid-mod(Xset,WWid) данные процессорных слов можно обнулить.
T
L
Поэтому двумерный массив отдельно используется для выражения В и С, один элемент в двумерном массиве является одним процессорным словом. Общее количество элементов двумерного массива, которому соответствует матрица С, составляет: M×WNum; общее количество элементов двумерного массива, которому соответствует матрица В, составляет: (N-K-(X-X))×WNum.
L
Например, длина строки В и С составляет Xset=200; допустим, что ширина процессорного слова WWid=32, то:
L
WNum=ceil(Xset/WWid)=ceil(200/32)=7; т.е. хранение и выражение каждой строки В и С должны быть выполнены 7 процессорными словами.
L
Потому что 200 не является целым кратным 32, mod(Xset,WWid)=mod(200,32)=8, поэтому последнее процессорное слово только содержит 8 действительных битов, остальные биты в количестве 32-8=24 данного процессорного слова бессмысленны, можно обнулить.
T
L
T
L
Поэтому матрица С может быть сохранена и выражена двумерными массивами с общим количеством элементов М×7, матрица В может быть сохранена и выражена с помощью двумерными массивами с общим количеством элементов (N-K-(X-X))×7; относительно действующей техники, матрица С выражается двумерными массивами с общим количеством элементов М×200, матрица В выражается двумерными массивами с общим количеством элементов (N-K-(X-X))×200, тем самым огромное пространство для хранения сэкономлено.
Стоит отметить то, что ненулевые элементы в матрицах А и D могут быть непосредственно вычислены по формуле, определенной структурированной порождающей матрицей при кодировании, поэтому в действительности А и D не требуется хранение, а в процессе исключения А и D только нужно непосредственно вычислить и получать положение ненулевых элементов по формуле, определенной структурированной порождающей матрицей при кодировании, затем в соответствии с положениями этих ненулевых элементов проводится «сложение строки». Конечно, также можно использовать одинаковый способ для хранения и выражения А и D. А можно рассмотреть В и С как случайные редкие матрицы, поэтому операция сложения строки над ними только является последовательными сложениями соответствующего элемента. Одно процессорное слово используется для выражения конструкции данных с элементами в количестве WWid, данный способ позволяет оптимизировать обрабатывающую сложение строк способность программного обеспечения.
t
e
a
t
505: в соответствии с отношением системы уравнений  решается система уравнений и определяется промежуточная переменная ; а также в соответствии с отношением перестановки от I до  (т.е. отношение перестановки столбцов от G до G) проводится обратная перестановка, т.е. по  определяется I.
В процессе определения промежуточной переменной  с применением исключения Гаусса, команда XOR процессора используется для выполнения касающейся матрицы В и С операции «сложения строк»; поэтому одна целая операция сложения строк может быть замена операцией XOR процессорных слов в количестве WNum, т.е. проводится параллельная обработка операции сложения строк, параллельное измерение составляет WWid, чрезвычайно повышать скорость операции «сложения строк».
ldgct
t
t
t
t
506: в соответствии с отношением системы уравнений G(0:L-1,0:L-1)×I=s определяется s, а также из s вычеркивать вышеуказанные заполненные известные биты в количестве d, получается исходная информационная последовательность m битов K и декодирование LDGC выполняется.
Фиг.7 является схемой устройства декодирования кода порождающей матрицы с низкой плотностью в примере осуществления настоящего изобретения. Как показано на фиг.7, данное устройство включает в себя: блок заполнения и стирания, блок перестановки столбцов, блок исключения Гаусса, блок генерации информационной последовательности, в т.ч.:
e
ldgct
e
блок заполнения и стирания предназначен для того, чтобы заполнять известные биты в количестве d=L-K в принятой последовательности кодовых слов R, а также вычеркивать символы кодового слова, стертые каналом, генерировать и выводить R; из транспонированной матрицы G порождающей матрицы LDGC вычеркивать строки, соответствующие символам кодового слова, стертым каналом, генерировать и выводить G.
e
e
В данном процессе, для структурированной и неструктурированной порождающей матрицы LDGC, блок заполнения и стирания использует процессорное слова в количестве WNum для поочередного хранения полных или частичных матричных элементов с одинаковыми положениями во всех строках G; каждое процессорное слово хранит матричные элементы в количестве WWid G; WWid является шириной процессорного слова, WNum=ceil(Len/WWid). Len обозначает количество элементов в одной строке, для выражения которых должно применяться процессорное слово.
e
e
e
a
Блок перестановки столбцов предназначен для проведения перестановки столбцов G, выведенной блоком заполнения и стирания, для того, чтобы матрица М-го порядка А, вершина которой является элементом 0-го столбца и 0-й стройки в G, стала нижней треугольной матрицей, для генерирования и вывода , а также для вывода информации о соответствующем отношении по перестановке столбцов G и G;
L
L
M=L-X, X является количеством битов, стертых каналом в символах первых L кодовых слов R.
e
L
e
L
a
Блок перестановки столбцов может перемещать столбцы в G, номер которых принадлежит к Xset к самой правой стороне G, свободные места соответствующих столбцов поочередно заполнены столбцами, дальнейшие номера которых не принадлежат к Xset, и определять G. Для неструктурированной порождающей матрицы LDGC данный блок является выборочным.
e
e
t
e
t
a
t
Блок исключения Гаусса предназначен для того, чтобы проводить исключение Гаусса над G, выведенной блоком заполнения и стирания в соответствии с отношением G×I=R, определять и выводить I; или проводить исключение Гаусса над G, выведенной блоком перестановки столбцов в соответствии с отношением , определять  а также по информации о соответствующем отношении по перестановке столбцов, выведенной блоком перестановки столбцов, проводить обратную перестановку строк над , получать и выводить I.
t
ldgct
t
t
t
t
Блок генерации информационной последовательности предназначен для того, чтобы принимать I, выведенную блоком исключения Гаусса; в соответствии с отношением G(0:L-1,0:L-1)×I=s получать s, а также из s вычеркивать известные биты в количестве d, и после того выводить исходную информационную последовательность битов K.
Из вышеуказанного следует, что для порождающей матрицы LDGC применение представленного способа и устройства декодирования в настоящем изобретении позволяет ускорить обработку исключения Гаусса.
В соответствии с основным принципом настоящего изобретения, у вышеуказанных примеров осуществления есть много видов преобразований.
Для порождающих матриц LDGC с другими формами, например, первые L строки являются верхней треугольной матрицей, после того как преобразуют их в нижнюю треугольную матрицу, можно применять способ декодирования в настоящем изобретении.