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

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

1

http://naukovedenie.ru 48TVN114

УДК
621.391

Молчанов Илья Николаевич

ГКОУ ВПО «Академия Федеральной службы охраны Российской Федерации»

Россия, Орёл1

Научный сотрудник

E-Mail: zorro_42@rambler.ru

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

Аннотация: На сегодняшний день в системах спутниковой связи наметилась 

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

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

последовательности бит по сравнению с известными решениями.

Ключевые слова: Низкоплотностный код; двудольный граф Таннера; проверочная 

матрица кода;
короткие циклы;
алгоритм итеративного распространения доверия;

логарифмическое отношение правдоподобия; вероятность битовой ошибки.

Идентификационный номер статьи в журнале 48TVN114

1 302034, г. Орёл, ул. Приборостроительная, д. 35

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

2

http://naukovedenie.ru 48TVN114

Ilia Molchanov

The Academy of the Federal Guard Service of the Russian Federation

Russia, Orel

E-Mail: zorro_42@rambler.ru

The model of the signal with ldpc allowing to reveal essential 

properties of the code and to use them when decoding
for the purpose of minimization of probability error

Abstract: Today the steady tendency of growth of popularity of a LDPC code was outlined in 

systems of satellite communication, it is caused first of all thanks to its good correcting opportunities. 
For decoding of this code broad application was received by algorithm of IBP. Use of algorithm IBP 
allows to receive exact a posteriori estimates of probabilities of symbols of rather accepted code word 
only in case of lack of cycles in the Tanner graph of code that in practice, at synthesis of a test matrix 
of a code, is impracticable. Existence of cycles in the Tanner graph of code is a major factor of decrease 
in correcting ability of algorithm of decoding as cycles result in dependence of decoded value on the 
current iteration from values of decoding of the same symbol on the previous iterations. In article the 
model, allowing to reduce negative influence of cycles of the minimum length is offered and to achieve 
more independence of estimates of decoding and as, it is offered to use statistics of decoding of 
symbols of the code word for additional updating of decisions for the purpose of reduction probability 
of an error of decoding in output sequence of bits in comparison with known decisions.

Keywords: Low density parity check (LDPC) code; Tanner graph; test matrix of a code; short 

cycles; Iterative Belief Propagation (IBP); likelihood ratio (LLR); bit error rate.

Identification number of article 48TVN114

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

3

http://naukovedenie.ru 48TVN114

Широкое распространение спутниковых систем связи обусловило развитие новых 

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

Наиболее распространенным алгоритмом декодирования НПК является алгоритм 

распространения доверия, основанный на итеративном обмене сообщениями
между 

символьными и проверочными вершинами двудольного графа Таннера. Алгоритм 
максимизирует апостериорную вероятность информационных символов относительно 
принятого кодового слова. Основным фактором, снижающим исправляющую способность 
алгоритма, являются наличие циклов в двудольном графе кода [1]. Причем, чем короче цикл, 
тем в большей степени отрицательно его влияние на результат декодирования. Таким образом, 
разработав механизмы борьбы с короткими циклами, можно выполнить модификацию 
алгоритма распространения доверия с целью минимизации вероятности ошибки декодирования 
в выходной последовательности бит.

Процесс формирование сигнала с низкоплотностным кодом

Рассмотрим процесс формирования сигнала с НПК. Пусть на вход кодера НПК 

поступает сформированная скремблером информационная последовательность длины 
:

,
(1)

где 
– алфавит информационной последовательности. Без потери общности можно 

полагать 
.

В 
результате 
кодирования 
НПК 
(операция 
) 
формируется 
кодовая 

последовательность:

,
(2)

где 
– длина кодового слова НПК, 
– информационная часть НПК, 
– единичная 

квадратная матрица размерностью 
, 
– транспонированная проверочная часть 

матрицы размерностью 
, а 
– порождающая матрица НПК, имеющая 

низкую плотностью единичных элементов.

Кодовая последовательность 
разбивается на группы длиной 
символов, и каждой 

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

– синфазная и квадратурная составляющие фазомодулированного сигнала. Число 

называется размерностью сигнального ансамбля и рассчитывается по формуле:

,
(3)

где 
– число элементарных сигналов в сигнальном ансамбле.

k



)
(
,
,...,
,
,
3
2
1
q
GF
u
u
u
u
u
u
i
k

k



q

2

q












T
k
k
n
k
k
k

n

n
P
I
u
c
c
c
c





)
(

2
1
;
,
,...,
,


n
k

k
kI 

k
k 


T
k
k
n
P

 )
(

k
k
n

 )
(





T
k
k
n
k
k
P
I



)
(
;

nc
m



Q
I;
I

Q
m

M
m
2
log


M

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

4

http://naukovedenie.ru 48TVN114

Затем последовательность точек 
подается на вход 

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

.
(4)

Далее сигнальная последовательность 
проходит через физическую среду передачи, 

где в результате воздействия шумов и помех искажается:

,
(5)

где 
– последовательность отчетов шума в канале связи.

Демодулятор должен по искаженной последовательности 
принять решение 

относительно кодовой последовательности 
. Таким решением является логарифмическое 

отношение правдоподобия (ЛОП) канала:

.
(6)

Вычисление ЛОП осуществляется по формуле:

,
(7)

где 
– условная вероятность приема 
, если передавалась единица, а 

– условная вероятность приема 
, если передавался ноль.

На декартовой плоскости нулевому биту соответствует по оси значение «1», а 

единичному биту значение «-1». На рисунке 1 представлено как рассчитывается демодулятором 
ЛОП символа относительно канала связи при использовании модуляции ФМ-2.

Рис. 1. Формирование демодулятором ЛОП при модуляции ФМ-2









m
n
Q
I
Q
I
Q
I
)
,
(
,...,
)
,
(,
)
,
(
2
1

m
n

Z



m
c
Z
Z
Z
Z
n

m
n

m
n

,
,...,
,
2
1




m
n

Z

m
n

m
n

m
n

m
n

Z
Z
Z














~

m
n



m
n

Z~

m
n

Z



n
channel
channel
channel

m
n

n
channel
LLR
LLR
LLR
Z
LLR
,
2
,
1,

1
,...,
,
~



























)
(

)1
/
(
log
0
u/
x
P

u
x
P
LLRchannel

)1
/
(

u
x
P
x

)
0
/
(

u
x
P
x

I = -1
I 
I = 1

I 

-1
1

∆1
∆2

P

,
1

2
1

1

1








P
,
1

2
1

2

1







P

P1

P-1

x

x













1

1
log
P
P
LLR

1
1



I
x


1
1

I
x


Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

5

http://naukovedenie.ru 48TVN114

На рисунке 2 приведен пример расчета ЛОП в случае использования ФМ-4.

Рис. 2. Формирование демодулятором ЛОП при модуляции ФМ-4

– Евклидово расстояние на декартовой плоскости от принятой точки до 

точек с координатами (1;1), (1;-1), (-1;-1) и (-1;1) соответственно, рассчитанное по формуле:

.
(8)

Каждой точке на декартовой плоскости с координатами 
ставится в соответствие 

группа символов. Для каждого символа группы рассчитывается ЛОП. Для примера, 
показанного на рисунке 2, группа состоит из двух символов. Вероятность того, что для первого 
символа переданное значение является -1 равно

,

а вероятность того, что его переданное значение является 1

.

Тогда для первого символа ЛОП равно

.

Для второго символа соответствующие вероятности и ЛОП равны:

Для других фазомодулированных сигналов с большей размерностью сигнального 

ансамбля логика получения ЛОП канальных символов сохраняется. Обобщенная формула 
расчета ЛОП канальных символов рассчитывается по формуле:

,                                              (9)

где

I 

Q

I 

Q

(1; 1)

(1; -1)
(-1; -1)

(-1; 1)

I = -1
I = 1

Q = -1
Q = 1

I 

Q

(1; 1)

(1; -1)
(-1; -1)

(-1; 1)

∆1

∆2

∆3

∆4
∆1

∆2
∆3

∆4

P

P


1
1



I
x


1
1


I
x










1
1
Q
x








1
1
Q
x


4
3
2
1
,
,
,










2
2

A
B
A
B
AB
y
y
x
x






)
,
(
Q
I

4
3
2
1

2
1

4
3
2
1

4
3

1
1


























P

4
3
2
1

4
3

4
3
2
1

2
1

1
1

























P































4
3

2
1

1

1

,
log
log P

P
LLR
I
channel

,

4
3
2
1

4
1

1













P
,

4
3
2
1

3
2

1












P



















3
2

4
1

,
log
Q
channel
LLR





 































1
)
(

1
)
(

,
log

j
sym
k

k

j
sym
k

k

j
channel

k

k
LLR

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

6

http://naukovedenie.ru 48TVN114

– означает, что берется евклидово расстояние от принятой точки до 

точки, соответствующей k-му символу, в котором j-ый бит равен 1;

– означает, что берется евклидово расстояние от принятой точки до 

точки, соответствующей k-му символу, в котором j-ый бит равен 0.

Таким образом, с выхода демодулятора поступают на вход декодера НПК так 

называемые «мягкие» решения в виде последовательности логарифмических отношений 
правдоподобия канальных символов.

В канальном декодере принимается решение 
о переданной информационной 

последовательности 
на 
основе 
последовательности 
ЛОП канальных 
символов, 

сформированной демодулятором:

.
(10)

Таким образом, входом модели сигнала с НПК является информационная 

последовательность 
, а выходом – последовательность 

.

Влияние циклов разной длины на результат декодирования
алгоритмом распространения доверия

Наиболее удобной формой описания НПК является представление его в виде 

двудольного графа Таннера. Данная форма представления позволяет наглядно описать процесс 
декодирования НПК при использовании алгоритма распространения доверия [2]. Рассмотрим 
влияние циклов разной длины на процесс декодирования. На рисунке 3 представлен фрагмент 
проверочной матрицы кода, определяющий цикл длины 4 в двудольном графе Таннера 
(рисунок 3).

Рис. 3. Фрагмент матрицы, определяющий цикл длиной шесть

ребер в двудольном графе Таннера

На рисунке 4 представлен цикл длины 4 в виде развернутого по итерациям 

декодирования графа Таннера относительно символьной вершины 
.

 


1



j
sym
k
k

 


1


j
sym
k
k

^
k
u

k
u


 



























)
(
)
(
)
(
1
1

^

;
,
~
k
n
k
n
k
k
n
m
n

k
I
P
Z
u




 



)
(
)
(
)
(

,
2
,
1,

1
;
,
,...,
,
k
n
k
n
k
k
n

n
channel
channel
channel
I
P
LLR
LLR
LLR










k

k
u
u
u
u
u
,...,
,
,
3
2
1




n
channel
channel
channel

n
channel
LLR
LLR
LLR
LLR
,
2
,
1,
,...,
,


1V

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

7

http://naukovedenie.ru 48TVN114

Рис. 4. Цикл длиной четыре, представленный развернутым по итерациям

декодирования графом Таннера

Рассчитаем в рамках данного цикла декодируемое значение символа кодового слова, 

соответствующего символьной вершине графа 
, на второй итерации декодирования. 

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

, несущее информацию о возможном значении символа, соответствующего вершине 

будет рассчитываться следующим образом:

,
(11)

где

–
– внешняя информация на первой итерации декодирования для вершины 
, 

рассчитанная по проверочному уравнению, соответствующему вершине 
;

–
– значение принимаемое символьной вершиной 
;

– функционал, определяющий правило расчета внешней информации

–
– вектор, частными компонентами которого являются все слагаемые проверочного 

уравнения, соответствующего вершине 
, кроме символа, соответствующего вершине 
.

Аналогично рассчитывается и сообщение, передаваемое от символьной вершины 
к 

проверочной вершине 
:

,
(12)

где

–
– вектор, частными компонентами которого являются все слагаемые проверочного 

уравнения, соответствующего вершине 
, кроме символа, соответствующего вершине 
.

Тогда декодируемое значение символа, соответствующего вершине 
, после первой 

итерации декодирования можно определить выражением

'
1P

''

1P

''

2P

1
V

2
V

'
1
V
''

1
V

''

2
V

Первая итерация
Вторая итерация

'
2P

'
2
V








a
v
F
p
;
1

'
1








b
v
F
p
;
1

'
2








c
v
F
p
;
'
2

''
1








d
v
F
p
;
'
2

''
2

1
V

1
V

1P
1
V








a
v
F
p
;
1

'
1

'
1p
1
V

1P

1v
1
V


a

1P
1
V

1
V

2P








b
v
F
p
;
1

'
2


b

2P
1
V

2
V

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

8

http://naukovedenie.ru 48TVN114

(13)

Из выражения (3) следует, что после первой итерации на декодируемое значение 

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

символа, соответствующего вершине 
. Таким образом, в случае возникновения ошибки в 

сообщении, принадлежащем вершине 
, при итеративном декодировании ошибка будет 

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

первой итерации.

Аналогичным образом рассчитаем внешнюю информацию для вершины 
на второй 

итерации декодирования по проверочным уравнениям, соответствующим вершинам 
и 
:

, 
,
(14)

где

–
– вектор, частными компонентами которого являются все слагаемые проверочного 

уравнения, соответствующего вершине 
, за исключением символа, соответствующего 

вершине 
;

–
– вектор, частными компонентами которого являются все слагаемые проверочного 

уравнения, соответствующего вершине
, за исключением символа, соответствующего 

вершине 
.

Согласно алгоритму декодируемое значение символа, соответствующего вершине 
, 

после второй итерации декодирования определятся выражением

(15)

Из выражения (5) следует, что после второй итерации на декодируемое значение 

символа, соответствующего вершине 
, четыре раза оказывает влияние начальное значение 

этого же символа.

Таким образом, в случае формирования демодулятором неверного значения канального 

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






 .
v
Y
b
v
F
a
v
F
p
LLR

p
p
p
LLR
p
p
Z
v

k
n

j
j
H

i

j
channel

k
n

j
j
H

i

j
channel

j

j

1

2

1
1

2
,1
,1

,1

'

2
,

'
2

'
1

2
,1
,1

,1

'

2
,

'
2

'
1

'
2

;
;

;

,
2

,
2






















































































2
V

1
V

1
V

2
V

2
V

1P
2P








c
v
F
p
;
'
2

''
1







d
v
F
p
;
'
2

''
2


c

1P

2
V


d

2P

2
V

1
V






 
 


 
1

4

1

2
2
'
2

2
'
2

'
2

2
,1
,1

,1

''

1,

''
2

''
1

2
,1
,1

,1

''

1,

''
2

''
1

''
1

;
с
;

;

,1

,1

v
Y
v
Y
Y
v
Y
d
v
F
v
F
p
LLR

p
p
p
LLR
p
p
Z
v

k
n

j
j
H

i

j
channel

k
n

j
j
H

i

j
channel

j

j
























































































1
V

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

9

http://naukovedenie.ru 48TVN114

На рисунках 5 – 6 представлены в виде развернутого двудольного графа Таннера циклы 

длиной шесть и восемь ребер соответственно.

Рис. 5. Цикл длины шесть в развернутом графе Таннера

Рис. 6. Цикл длины восемь в развернутом графе Таннера

Представленные обстоятельства позволяют сделать вывод, что в случае возникновения 

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

1
V

2
V

3
V

1
P

2P

3P

1
V

2
V

3
V

1
P

2P

3P

1
V

2
V

3
V

1
P

2P

3P

1
V

2
V

3
V

Первая итерация
Вторая итерация
Третья итерация

1
V

2
V

3
V

1
P

2P

3P

1
V

2
V

3
V

1
P

2P

3P

1
V

2
V

3
V

1
P

2P

3P

1
V

2
V

3
V

1
P

2P

3P

1
V

2
V

3
V

4
V
4P
4
V
4P
4
V
4P
4
V
4P
4
V

Четвертая итерация
Первая итерация
Вторая итерация
Третья итерация

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

10

http://naukovedenie.ru 48TVN114

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

графе Таннера цикл длины 6 (рисунок 7).

Рис. 7. Фрагмент матрицы, определяющий цикл длиной шесть ребер

в двудольном графе Таннера

Из рисунка 7 заметно, что в формировании цикла участвуют три линейно-зависимых 

столбца. Из определения кода следует, что код содержит ненулевое кодовое слово веса 
Хемминга не более 
тогда и только тогда, когда проверочная матрица 
содержит множество 

из 
линейно зависимых столбцов [3]. Таким образом, фрагмент матрицы, представленный на 

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

Таннера, определяет то же линейно-векторное подпространство, что и проверочная матрица 
систематического линейного кода с параметрами 
, способного исправить 

ошибок, 
возникших 
в 
символьных 
вершинах 
цикла. 
Следовательно, 
применение 

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

Выявленное свойство, появляющееся на этапе кодирования, позволяет исключать из 

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

Рис. 8. Возможные варианты преобразования цикла длиной шесть ребер

Следует отметить, что символьные и проверочные вершины графа Таннера участвуют в 

формировании циклов минимальной длины с разной частотой. Поэтому, наибольший интерес 



































1
1

1
1

1
1

Н

Vi
Vj
Vk

Pm

Pn

Pq

Vi
Vj
Vk

Pm
Pn
Pq


H





2
2

d
d



1
,
d

 2
1

 d
t