An Improved LDPC Decoding Algorithm

An Improved LDPC Decoding Algorithm Based on
Min-sum Algorithm
Yue Cao
College of Information Science and Engineering
Northeastern University
Shenyang, China
Abstract—Low density parity check code is a kind of high-
performance linear block code. It has excellent performance
which is near the Shannon limit. LDPC has low decoding
complexity, free structure and receives extensive attention. The
typical decoding algorithm of LDPC is LLR BP algorithm, which
is also called “sum-product algorithm”. LLR BP algorithm is the
best algorithm at present. But it needs complex computation,
which causes great difficulty in its hardware design. To solve this
problem, an algorithm that gets approximation of LLR BP
algorithm is put forward, which is called min-sum algorithm.
Min-sum algorithm greatly reduces the computation and makes
the hardware design simpler, but its accuracy has a wide gap
with BP algorithm. This article analyzes the reason why min-sum
algorithm has errors, and puts forward an improved algorithm
called min-sum linear approximation algorithm based on min-
sum algorithm.
Keywords- LDPC Decoding Algorithm, Min-sum Algorithm, BP
Algorithm
algorithm has better performance than min-sum algorithm and
is much easier to realize than BP algorithm.
II.
BP ALGORITHM
BP algorithm, also called sum-product algorithm, is a well
performed decoding algorithm. Its decoding procedure is as
follows:
A.Initialization
Calculate the initial likelihood ratio of probability that is
transferred from the channel to the variable nodes L(Pi),
i=1,2,…,n. For variable node i and its neighboring check node
j, the initial information that is transferred from the variable
node to check node in AWGN channel is:
2 ri
1exp( 2 )

L( 0) ( qij ) L ( Pi ) ln
2 ri
1exp( −2 )

2 ri 2 ri
ln exp( 2 ) 2(1)

I.
INTRODUCTION
Low density parity check code is one kind of linear block
code. It was first promoted by Gallager[1] in 1960s. In 1981, in
Tanner’s article, he explained LDPC in a new way with graph
model. For a long time, this code was ignored. In 1990s,
Mackay[2] and others researched on it and found that LDPC
code has strong error correction capacity. From then on, LDPC
was widely researched and spread. It has been proved that the
performance of LDPC code is quite near the Shannon limit.
The difference is as low as a few tenths of dB[3].
The high performance of LDPC code is resulted from its
soft-judgment decoding algorithm. Gallager put forward an
iterative decoding algorithm based on probability domain:
Belief Propagation, which is also called sum-product
algorithm. When the Tanner graph does not have any short
loop, this algorithm performs best. But the computation of this
algorithm is huge, and it’s hard to put it in the hardware. Min-
sum algorithm is a good approximation of BP algorithm. It can
reduce a large number of computations and is easy to realize.
But the accuracy of min-sum algorithm is much lower than BP
algorithm.
This article mainly studies LDPC decoding algorithm, and
analyzes BP algorithm and min-sum algorithm, and then puts
forward an improved min-sum algorithm using linear
approximation and least mean square algorithm. The improved
B.

Iterative processing of LLR BP algorithm
1 Update the check nodes
For any check node j and its neighboring variable node
i, in its kth iteration, the formula of the information of
check nodes is:
L( k ) (rji ) 
⎧⎫
⎪⎪k −12 tanh ⎨∏tanh[0.5L (qi ' j )]⎬
⎪⎪⎩i '∈N( j ) / i '⎭
−1
(2)

2 Update the variable nodes
For any variable node i and its neighboring check node
j, in its kth iteration, the formula of the information of
variable nodes is:
L( k ) ( qij ) L( Pi ) 
j '∈M ( i ) / j '
∑
L( k ) ( rj ' i )
(3)
978-1-4577-1295-1/11/$26.00©2011IEEE
26


3 Decision decoding
Calculate the decision information of all variable
nodes:
L (qi ) L( Pi ) 
(k )
j∈M ( i )
∑
It can be seen from the graph of ( x) that, when x>0, ( x) >0,
and it decreases as x increases. When x is huge, ( x) is almost
0, and ∑( i ' j ) is approximately equal to (min i ' j ) . So
i '∈N ( j )/ i '
L (rji )
(k )
(4)
[
i '∈N ( j ) / i '
∑
( i ' j )]
(9)
0 L( k ) (qi ) 0
ci {
1 L( k ) (qi ) ≤0

4 Stop
≈[(min i ' j )] min i ' j
(5)
L(rji ) (
i '∈N( j ) / i '
∏
i ' j ) min i ' j
(10)
If HC 0 or if the program has reached its
maximum iteration, stop iterating. Else, go back to
procedure (2), until it gets the maximum iteration.
III.
MIN-SUM ALGORITHM
T
In this way, the number of computation is decreased. The
simplified decoding algorithm is generally called min-sum
algorithm [4].
IV.
IMPROVED ALGORITHM
From formula (2), we can get the follow formula:
tanh(0.5 L ( rji ))

i '∈N ( j ) / i '
Analyze the graph of ( x ) , it can be seen that
(6)
i '∈N( j )/i '
∏
tanh[0.5 L(qi ' j )]
∑
( i ' j ) (min i ' j ) .So
[
i '∈N ( j ) / i '
Let L(qi ' j ) ij ij , in the formula,
∑
( i ' j )]
(11)
ij sign( L(qi ' j )) , ij L(qi ' j ) . So formula (6) becomes
tanh(0.5L(rji ))

i '∈N ( j ) / i '
[(min i ' j )] min i ' j
Formula (11) shows that the value of L ( rji ) in min-sum
algorithm is larger than that of BP algorithm. To reduce the
error brought by approximation in min-sum algorithm, we
need to reduce the value of L ( rji ) .
One way to solve the problem is normalized algorithm[4].
But it’s not good enough. Based on this, and based on the
work of paper[5], an improved algorithm is put forward.
Assume that L ( rji ) of min-sum algorithm is Lmin , and that
∏
i ' j
i '∈N ( j ) / i '
∏
tanh[0.5i ' j ]
(7)
Identify the assist Auxiliary function
ex 1
( x) log tanh(0.5 x) log( x ) . Its main feature is
e −1
−1that ( x)=( x) . So formula (7) becomes
L (rji )
(
i '∈N ( j ) / i '
∏
i ' j )[
i '∈N( j ) / i '
∑
( i ' j )]
(8)
L(rji ) of BP algorithm is LBP , and that L(rji ) of improved
algorithm is L . Introduce parameters a and b, assume
that L aLmin b , 0

ผลลัพธ์ (ไทย) 1:

การปรับปรุงขั้นตอนวิธีการถอดรหัส ldpc ตาม
นาทีผลรวมขั้นตอนวิธี

yue cao วิทยาลัยวิทยาการสารสนเทศและวิศวกรรมมหาวิทยาลัยภาคตะวันออกเฉียงเหนือ

เฉิ่นหยาง, จีน
ความหนาแน่นต่ำนามธรรมรหัสการตรวจสอบความเท่าเทียมกันเป็นชนิดของรหัสบล็อกสูง
ประสิทธิภาพเชิงเส้น ก็มีประสิทธิภาพที่ดีเยี่ยม
ซึ่งอยู่ใกล้ขีด จำกัด shannon ldpc มีการถอดรหัส
ความซับซ้อนของโครงสร้างฟรีต่ำและได้รับความสนใจอย่างกว้างขวาง
ขั้นตอนวิธีการถอดรหัสทั่วไปของ ldpc เป็นวิธี bp LLR ซึ่ง
จะเรียกว่า "ขั้นตอนวิธีการรวมผลิตภัณฑ์" ขั้นตอนวิธี bp LLR เป็นขั้นตอนวิธีการที่ดีที่สุด
ในปัจจุบัน แต่จะต้องคำนวณที่ซับซ้อน
ซึ่งทำให้เกิดความยากลำบากในการออกแบบฮาร์ดแวร์ เพื่อแก้ปัญหานี้
อัลกอริทึมที่ได้รับการประมาณของ LLR bp
ขั้นตอนวิธีการที่วางอยู่ข้างหน้าซึ่งเป็นขั้นตอนวิธีการที่เรียกว่านาทีรวม.
ขั้นตอนวิธีการรวมนาทีช่วยลดการคำนวณและทำให้
การออกแบบฮาร์ดแวร์ที่เรียบง่าย แต่ความถูกต้องที่มีช่องว่างกว้าง
ด้วยวิธี bp บทความนี้วิเคราะห์เหตุผลนาที
ผลรวมขั้นตอนวิธีการมีข้อผิดพลาดและทำให้หน้าขั้นตอนวิธีการปรับปรุงขั้นตอนวิธีการที่เรียกว่า
ประมาณเชิงเส้นนาทีขึ้นอยู่กับผลรวมนาที
ผลรวมขั้นตอนวิธี.
ขั้นตอนวิธีการถอดรหัสคำหลัก ldpc อัลกอริทึมนาทีผลรวม, bp
ขั้นตอนวิธีการ
ขั้นตอนวิธีการที่มีประสิทธิภาพที่ดีขึ้นกว่าขั้นตอนวิธีนาทีผลรวมและ
ง่ายมากที่จะตระหนักถึงกว่าขั้นตอนวิธี bp.
ii.

ขั้นตอนวิธี bp bp ขั้นตอนวิธีการที่เรียกว่าขั้นตอนวิธีการรวมผลิตภัณฑ์เป็นขั้นตอนวิธีการดำเนินการที่ดี
ถอดรหัส ขั้นตอนการถอดรหัสที่เป็น
ดังนี้

a.initialization คำนวณอัตราส่วนเริ่มต้นโอกาสของความน่าจะเป็นที่เป็น
โอนมาจากช่องทางที่จะโหนดตัวแปรลิตร (ปี่)
i = 1,2, ... , nโหนดตัวแปร i และตรวจสอบที่อยู่ใกล้เคียงโหนด
เจข้อมูลเบื้องต้นที่จะถูกโอนจากตัวแปร
โหนดโหนดในการตรวจสอบในช่อง AWGN คือ:
2 ri
1  exp (2)

 ลิตร (0) (qij) ลิตร (ปี่)  LN
2 ri
1  exp (-  2)

  2 ri 2 ri
 LN exp (2)  2 (1)

i.

แนะนำความหนาแน่นต่ำรหัสตรวจสอบความเท่าเทียมกันเป็นหนึ่งในชนิดของบล็อกเส้น
รหัส มันได้รับการเลื่อนครั้งแรกโดย Gallager [1] ในปี 1960 ในปี 1981 ในบทความ
ฟอกหนังของเขาอธิบาย ldpc ในรูปแบบใหม่ที่มีรูปแบบกราฟ
เป็นเวลานานรหัสนี้ก็ไม่สนใจ ในปี 1990, mackay
[2] และอื่น ๆ ที่เกี่ยวกับการวิจัยและพบว่า ldpc
รหัสมีความสามารถแก้ไขข้อผิดพลาดที่แข็งแกร่ง จากนั้น ldpc
ได้รับการวิจัยอย่างกว้างขวางและการแพร่กระจายมันได้รับการพิสูจน์ให้เห็นว่าการปฏิบัติงานของ
รหัส ldpc ค่อนข้างใกล้ขีด จำกัด shannon.
แตกต่างคือเป็นต่ำเป็นไม่กี่สิบของฐานข้อมูล [3].
ที่มีประสิทธิภาพสูงของรหัส ldpc เป็นผลมาจากการที่
นุ่มตัดสินถอดรหัส ขั้นตอนวิธี Gallager ประกวดราคา
ขั้นตอนวิธีการถอดรหัสซ้ำขึ้นอยู่กับความน่าจะเป็นโดเมน:
ความเชื่อการขยายพันธุ์ที่เรียกว่านอกจากนี้ยังมีผลรวมผลิตภัณฑ์
ขั้นตอนวิธีการเมื่อกราฟฟอกหนังไม่ได้สั้น
ห่วงใด ๆ ขั้นตอนวิธีนี้มีประสิทธิภาพที่ดีที่สุด แต่การคำนวณนี้
ขั้นตอนวิธีการเป็นอย่างมากและเป็นเรื่องยากที่จะนำมันในฮาร์ดแวร์ นาที
ผลรวมขั้นตอนวิธีการเป็นประมาณการที่ดีของขั้นตอนวิธี bp ก็สามารถ
ลดเป็นจำนวนมากของการคำนวณและง่ายต่อการตระหนัก.
แต่ความถูกต้องของขั้นตอนวิธีนาทีรวมเป็นต่ำกว่าขั้นตอนวิธี bp
.
บทความนี้ส่วนใหญ่ขั้นตอนวิธีการถอดรหัสการศึกษา ldpc และขั้นตอนวิธีการวิเคราะห์
bp ขั้นตอนวิธีการและนาทีรวมแล้วทำให้
ข้างหน้าการปรับปรุงขั้นตอนวิธีนาทีรวมใช้เส้น
ประมาณและน้อยหมายถึงขั้นตอนวิธีการตาราง การปรับปรุง
ข.

การประมวลผลซ้ำของขั้นตอนวิธี bp LLR
1 การปรับปรุงการตรวจสอบโหนด
โหนดตรวจสอบใด ๆ เจและโหนดตัวแปรของเพื่อนบ้าน
i ในการย้ำ KTH ของสูตรของข้อมูลของโหนด
ตรวจสอบคือ l
(k) (RJI) 
⎧⎫
⎪⎪ k -12 TANH ⎨Π TANH [ 0.5L (ฉี 'ญ)] ⎬
⎪⎪⎩ i' ∈ n (ญ) / i '⎭

-1 (2)

2 ปรับปรุงโหนดตัวแปร
ตัวแปรใด ๆ โหนด i และตรวจสอบโหนดเพื่อนบ้าน
เจในการย้ำ KTH ของสูตรของข้อมูลของ
โหนดตัวแปรคือ l
(k) (qij) ลิตร (ปี่) 
เจ '∈ m (i) / เจ'
Σ l
(k) (rj 'i)
(3)
978-1-4577-1295-1/11 / $ 26,00 © 2011ieee 26



3 การตัดสินใจ ถอดรหัส
คำนวณข้อมูลการตัดสินใจของโหนดตัวแปร
ทั้งหมด: l
(ฉี) ลิตร (ปี่) 
(k)
เจ∈ m (i)

Σมันสามารถเห็นได้จากกราฟของ (x ) ว่าเมื่อ x> 0  (x)> 0,
และจะลดลงขณะที่ x เพิ่ม เมื่อ x เป็นอย่างมาก (x) เป็นเกือบ
0,และΣ ( i 'เจ) จะประมาณเท่ากับ (นาที i' ญ) ดังนั้น
i '∈ n (ญ) / i'
ลิตร (RJI)
(k)
(4)
 [
i '∈ n (ญ) / i'

Σ ( i 'ญ) ]
(9)
0 ลิตร (k) (ฉี)  0
CI  {
1 ลิตร (k) (ฉี) ≤ 0

4 หยุด
≈ [ (นาที  i 'ญ)] นาที i' เจ
(5) l
(RJI)  (
i '∈ n (ญ) / i'

Π i 'ญ) นาที i' เจ
(10)
ถ้าไง 0 หรือถ้าโปรแกรมได้ถึง
ของย้ำสูงสุดหยุด iterating อื่นกลับไป
ขั้นตอนไป (2), จนกว่าจะได้รับการย้ำสูงสุด.
iii.
ขั้นตอนวิธีนาทีผลรวม

เสื้อในลักษณะนี้จำนวนของการคำนวณจะลดลง
ขั้นตอนวิธีการถอดรหัสง่ายโดยทั่วไปจะเรียกว่านาทีผลรวมขั้นตอนวิธีการ
[4]

iv การปรับปรุงขั้นตอนวิธี
จากสูตร (2) เราจะได้รับตามสูตร..
TANH (0.5 ลิตร (RJI))

i  '∈ n (ญ) / i'
วิเคราะห์กราฟของ (x) ก็จะเห็นได้ว่า
(6)
i '∈ n (ญ) / i'

Π TANH [0.5 ลิตร (ฉี 'ญ)]

Σ ( i 'ญ)  (นาที i' ญ). ดังนั้น
[
i '∈ n (ญ) / i'
ให้ลิตร (ฉี 'ญ)  ij  ij ใน สูตร

Σ ( i 'ญ)]
(11)
 ij สัญญาณ (l (ฉี' ญ))  ij ลิตร (ฉี 'ญ) ดังนั้นสูตร (6) กลายเป็น
TANH (0.5L (RJI))

 i '∈ n (ญ) / i'
 [ (นาที i 'ญ)] นาที i'
ญสูตร (11) แสดงให้เห็นว่าค่าของลิตร (RJI) ในนาทีรวม
อัลกอริทึมมีขนาดใหญ่กว่าที่ของขั้นตอนวิธี bp . เพื่อลดข้อผิดพลาด
มาโดยในขั้นตอนวิธีการประมาณนาทีรวมเรา
จำเป็นต้องลดค่าของลิตร (RJI).
วิธีหนึ่งที่จะแก้ปัญหาเป็นวิธีปกติ [4].
แต่ก็ยังไม่ดีพอ ตามนี้และขึ้นอยู่กับการทำงานของ
กระดาษ [5]ขั้นตอนวิธีการที่ดีขึ้นเป็นที่วางอยู่ข้างหน้า.
สมมติว่าลิตร (RJI) ของขั้นตอนวิธีนาทีรวมเป็น lmin และที่

Π i 'ญ
i' ∈ n (ญ) / i '

Π TANH [0.5  i 'j]
(7)
ระบุฟังก์ชั่นช่วยเสริม
อดีต 1
 (x) เข้าสู่ระบบ TANH (0.5 x) เข้าสู่ระบบ (x) คุณสมบัติหลักคือ
อี -1
-1that  (x) =  (x) ดังนั้นสูตร (7) กลายเป็น l
(RJI)
 (
i '∈ n (ญ) / i'

Π i 'ญ)  [
i' ∈ n (ญ) / i '

Σ ( i 'ญ)]
(8) l
(RJI) ของขั้นตอนวิธี bp เป็น LBP และที่ลิตร (RJI) ของขั้นตอนวิธีการที่ดีขึ้น
เป็นลิตร แนะนำพารามิเตอร์และ b สมมติ l
ที่ Almin  b, 0 <<1 เพื่อให้ค่าของลิตรได้ใกล้ชิด
LBP จะใช้น้อยหมายถึงขั้นตอนวิธีการตารางและทำให้ lmin
ใกล้ LBP.
คิดว่าหมายถึงฟังก์ชัน f ตาราง (a, b) เป็นฟังก์ชั่นของ
a และ b
ฉ (a, b) อี [(l -  LBP) 2]
ที่จะได้รับค่าของ a และ b, คำนวณอนุพันธ์ของฉ
∂ฉ (a, b) / ∂ 0
มะเดื่อ 1 กราฟของ
(12)
 (x)
∂ f (ข ) / ∂ b  0
จากสูตร (13) ก็สามารถเป็นที่รู้จักกันว่า

ผลลัพธ์ (ไทย) 2:

การปรับปรุง LDPC ถอดรหัสอัลกอริทึมตาม
นาทีผลอัลกอริทึม
Cao เยว่
วิทยาลัยข้อมูลวิทยาศาสตร์และวิศวกรรมศาสตร์
มหาวิทยาลัยเฉียง
เสิ่นหยาง จีน
นามธรรม — โค้ดตรวจสอบพาริตี้ความหนาแน่นต่ำเป็นชนิดสูง
รหัสบล็อกเชิงประสิทธิภาพ มีประสิทธิภาพยอดเยี่ยม
ซึ่งอยู่ใกล้ขีดจำกัดของแชนนอน LDPC ได้ถอดรหัสต่ำ
ฟรีโครงสร้างซับซ้อน และได้รับความสนใจมากมาย ใน
ขั้นตอนวิธีการถอดรหัสโดยทั่วไปของ LDPC เป็นอัลกอริทึม LLR BP ซึ่ง
ยังเรียกว่า "ผลคูณ-อัลกอริทึม" เป็นอัลกอริทึม LLR BP
อัลกอริทึมที่ดีที่สุดในปัจจุบัน แต่ต้องคำนวณซับซ้อน,
ซึ่งทำให้เกิดความยากลำบากมากในการออกแบบฮาร์ดแวร์ การแก้ปัญหานี้
ปัญหา เป็นอัลกอริทึมที่ได้รับประมาณ LLR BP
อัลกอริทึมจะนำ ซึ่งเรียกว่าอัลกอริทึมรวมนาที.
นาทีผลอัลกอริทึมการคำนวณลด และทำให้มาก
ออกแบบฮาร์ดแวร์ที่เรียบง่าย แต่ความถูกต้องของมีช่องว่างมากมาย
กับอัลกอริทึม BP บทความนี้วิเคราะห์เหตุผลทำไมนาทีรวม
อัลกอริทึมมีข้อผิดพลาด และทำให้ขั้นตอนวิธีการปรับปรุงหน้า
เรียกตามนาที - อัลกอริทึมเชิงประมาณนาทีรวม
รวมอัลกอริทึมการ
คำ - LDPC ถอดรหัสอัลกอริธึม อัลกอริทึมรวม Min, BP
อัลกอริทึม
อัลกอริทึมมีประสิทธิภาพดีกว่านาทีผลอัลกอริทึม และ
ง่ายมากตระหนักกว่า BP อัลกอริทึมการ
II
อัลกอริทึม BP
BP อัลกอริธึม เรียกว่าผลคูณ-อัลกอริทึม จะดี
ดำเนินการขั้นตอนวิธีการถอดรหัส ขั้นตอนการถอดรหัสเป็น as
follows:
A.Initialization
Calculate โอกาสเริ่มต้นอัตราส่วนของความน่าเป็นที่
โอนย้ายมาจากช่องสัญญาณให้โหนตัวแปร L (ปี่),
ฉัน = 1, 2,..., n สำหรับโหนตัวแปร ฉันและเพื่อนบ้านของดูโหน
เจ ข้อมูลเบื้องต้นที่จะถูกโอนย้ายจากตัวแปร
โหนต้องโหนในช่อง AWGN:
2 ri
1exp (2)

L (0) (qij) ln L (Pi)
2 ri
1exp (−2)

2 ri 2 ri
ln ประสบการณ์ (2) 2(1)

I.
แนะนำ
รหัสตรวจสอบพาริตี้ความหนาแน่นต่ำเป็นประเภทหนึ่งของบล็อกเส้น
รหัส ก่อนจะถูกส่งเสริม โดย Gallager [1] ใน 1960s ในปี 1981 ใน
บทความของแทนเนอร์ชำรุด เขาอธิบาย LDPC วิธีใหม่กับกราฟ
รุ่น เป็นเวลานาน รหัสนี้ถูกละเว้น ในปี 1990,
แมคเคย์ [2] และผู้อื่นทำวิจัยไว้ และพบว่า LDPC
รหัสมีกำลังแข็งแรงข้อผิดพลาดการแก้ไข จากนั้น LDPC
ทำวิจัยกันอย่างแพร่หลาย และแพร่กระจาย มันได้รับการพิสูจน์ที่การ
ประสิทธิภาพของรหัส LDPC จะดีกว่าวงเงินแชนนอน
ข้อแตกต่างคือต่ำสุดหนึ่งกี่ตำแหน่งของ dB [3]
ประสิทธิภาพสูงของรหัส LDPC เป็นผลจากของ
ขั้นตอนวิธีการถอดรหัสคำพิพากษาอ่อน Gallager นำการ
ซ้ำขั้นตอนวิธีการถอดรหัสโดยใช้ความน่าเป็นโดเมน:
เผยแพร่ความเชื่อ ซึ่งจะเรียกว่าผลคูณ-
อัลกอริทึมการ เมื่อกราฟ Tanner ได้สั้นใด ๆ
วน อัลกอริทึมนี้ทำดีที่สุด แต่การคำนวณนี้
อัลกอริทึมเป็นอย่างมาก และยากที่จะใส่ในฮาร์ดแวร์ นาที-
ผลอัลกอริทึมเป็นการประมาณที่ดีของอัลกอริทึม BP สามารถ
ลดจำนวนหนึ่ง และจะทราบได้
แต่ความถูกต้องของอัลกอริทึมนาทีผลมากกว่า BP
อัลกอริทึมการ
บทความนี้ส่วนใหญ่ศึกษาอัลกอริทึม การถอดรหัส LDPC และ
วิเคราะห์ BP อัลกอริทึมและอัลกอริทึมนาทีผล และทำให้แล้ว
ส่งอัลกอริทึมปรับ min-ผลการใช้เส้น
ประมาณและขั้นตอนวิธีค่าเฉลี่ยกำลังสองน้อยที่สุด การปรับปรุง
B.

ประมวลผลซ้ำของอัลกอริทึม LLR BP
1 ปรับปรุงโหนเครื่อง
ใด ๆ ตรวจสอบโหนด j และโหนตัวแปรของเพื่อนบ้าน
ฉัน ในการเกิดซ้ำของ kth สูตรของข้อมูล
ตรวจสอบโหน:
L (k) (rji) 
⎧⎫
⎪⎪k −12 tanh ⎨∏tanh [0.5 L (คี ' เจ)] ⎬
⎪⎪⎩i ' ∈N (เจ) / ฉัน ' ⎭
−1
(2)

2 ปรับปรุงโหนดที่ตัวแปร
สำหรับโหนตัวแปร ฉันและเพื่อนบ้านของดูโหน
j ในการเกิดซ้ำของ kth สูตรของข้อมูล
เป็นโหนดที่ตัวแปร:
L (k) (qij)  L (Pi)
เจ ' ∈M (i) / เจ '
∑
L (k) (rj ' ฉัน)
(3)
978-1-4577-1295-1/11/$26.00©2011IEEE
26


ตัดสินใจถอดรหัส 3
คำนวณข้อมูลการตัดสินใจของตัวแปรทั้งหมด
โหน:
 L (Pi) L (ชี่)
(k)
j∈M (i)
∑
ดังจะเห็นได้จากกราฟของ (x) ที่ เมื่อ x > 0  (x) > 0,
และก็ลดลงขณะที่ x เพิ่มขึ้นได้ เมื่อ x เป็นอย่างมาก  (x) เป็นเกือบ
0 และ∑ (i ' j) ประมาณเท่ากับ (min i ' เจ) ดังนั้น
ฉัน ' ∈N (เจ) / ฉัน '
L (rji)
(k)
(4)
 [
ฉัน ' ∈N (เจ) / ฉัน '
∑
 (i ' เจ)]
(9)
L 0 (k) (ชี่) 0
ci  {
L 1 (k) (ชี่) ≤0

หยุด 4
≈ [ (i นาที ' เจ)] min i ' เจ
(5)
 L (rji) (
i ' ∈N (เจ) / ฉัน '
∏
i ' เจ) i นาที ' เจ
(10)
0 HC ถ้าหรือถ้าโปรแกรมแล้วของ
เกิดซ้ำสูงสุด หยุดวน อื่น ไปกลับ
กระบวนงาน (2), จนกว่าจะได้รับสูงสุดเกิดซ้ำ
III.
MIN ผลอัลกอริทึม
T
วิธีนี้ หมายเลขการคำนวณจะลดลง
ภาษาขั้นตอนวิธีการถอดรหัสโดยทั่วไปเรียกว่าผลรวมนาที
อัลกอริทึม [4] .
IV.
ปรับปรุงอัลกอริทึม
จากสูตร (2), เราได้ทำตามสูตร:
tanh (0.5 L (rji))

ฉัน ' ∈N (เจ) / ฉัน '
วิเคราะห์กราฟของ (x) สามารถเห็นที่
(6)
ฉัน ' ∈N (เจ) /i '
∏
tanh [0.5 L(qi ' j)]
∑
 (i ' j)  (i นาที ' เจ)ดังนั้น
 [
ฉัน ' ∈N (เจ) / ฉัน '
ให้ L(qi ' j) ij ij ในสูตร,
∑
 (i ' j)]
(11)
ij sign (L(qi ' j)), ij L(qi ' j) จึงกลายเป็นสูตร (6)
tanh (0.5 L (rji))

ฉัน ' ∈N (เจ) / ฉัน '
 [ (min i ' เจ)] min i ' j
สูตร (11) แสดงที่ค่าของ L (rji) ในนาทีรวม
อัลกอริทึมมีขนาดใหญ่กว่าของอัลกอริทึม BP ลด
ข้อผิดพลาดโดยประมาณในอัลกอริทึมรวมนาที เรา
ต้องการลดค่าของ L (rji) .
เที่ยวการแก้ไขปัญหาเป็นอัลกอริทึมมาตรฐาน [4] .
แต่ไม่ดีพอ ตามนี้ และตาม
ทำกระดาษ [5], ใส่ขั้นตอนวิธีการปรับปรุงไป
สมมติว่า L (rji) ของอัลกอริทึมนาทีรวม Lmin และที่
∏
i ' j
ฉัน ' ∈N (เจ) / ฉัน '
∏
tanh [0.5i ' เจ]
(7)
ระบุช่วยเสริมฟังก์ชัน
อดีต 1
ล็อก tanh (0.5 x) (x) log  (x) คุณสมบัติหลักคือ
e −1
−1that  (x) = (x) จึงกลายเป็นสูตร (7)
L (rji)
 (
i ' ∈N (เจ) / ฉัน '
∏
i ' j)  [
ฉัน ' ∈N (เจ) / ฉัน '
∑
 (i ' j)]
(8)
L (rji) ของอัลกอริทึม BP เป็นแอลบีพี และ L (rji) ของการปรับปรุง
L เป็นอัลกอริทึมการ แนะนำพารามิเตอร์ และ b สมมติ
ที่ L aLmin b, 0 < เป็น < 1 เพื่อให้ค่าของ L ได้ปิด
แอลบีพี ใช้อัลกอริทึมค่าเฉลี่ยกำลังสองน้อยที่สุด และทำให้ Lmin
ใกล้เคียงกับแอลบีพี
ประมาณที่เป็นค่าเฉลี่ยกำลังสองฟังก์ชัน F (a, b)
ฟังก์ชันของตัว และ b,
E F (a, b) [(L −LBP) 2]
การรับค่าของเป็น และ b คำนวณอนุพันธ์ของ F
∂F (a, b) / ∂a 0
กราฟฟิก 1
(12)
 (x)
∂F (a, b) / ∂b 0
จากสูตร (13), จะสามารถทราบที่

ผลลัพธ์ (ไทย) 3:

ได้รับการปรับปรุงการถอดรหัส ldpc อัลกอริธึมที่ใช้
ตามมาตรฐานต่ำสุด - เงินอัลกอริธึม

Yue Cao College of ข้อมูลด้านวิศวกรรมและวิทยาศาสตร์มหาวิทยาลัย ภาค ตะวันออกเฉียงเหนือ

Shenyang ,จีน
นามธรรม - ต่ำความหนาแน่นการตรวจสอบ Parity รหัสเป็น ประเภท ของสูง -
การบล็อครหัส. มี ประสิทธิภาพ การทำงานที่ดีเยี่ยม
ซึ่งอยู่ใกล้กับน้ำตก Shannon ที่จำกัด ldpc มีระดับต่ำการถอดรหัส
ซึ่งจะช่วยลดความยุ่งยากซับซ้อนโครงสร้างแบบไม่เสียค่าบริการและได้รับความสนใจที่หลากหลายอัลกอริทึมการถอดรหัสแบบดั้งเดิมที่
ของ ldpc คือ llr BP อัลกอริธึมที่
เรียกว่า"อัลกอริธึมจำนวนเงิน - ผลิตภัณฑ์ " llr BP อัลกอริธึมที่
ซึ่งจะช่วยอัลกอริธึมที่ดีที่สุดในปัจจุบัน แต่ความต้องการคำนวณคอมเพล็กซ์
ซึ่งจะทำให้เกิดความยุ่งยากที่ดีเยี่ยมในการออกแบบฮาร์ดแวร์ของพื้นที่
ซึ่งจะช่วยในการแก้ไขปัญหานี้อัลกอริธึมที่ได้รับประมาณของอัลกอริธึม BP
llr คือการนำส่งต่อซึ่งมีชื่อว่าอัลกอริธึมนาที - จำนวนเงิน.
อัลกอริธึมนาที - จำนวนมากช่วยลดคำนวณและทำให้การออกแบบฮาร์ดแวร์
ซึ่งจะช่วยให้ง่ายขึ้นแต่ความแม่นยำของมันมีช่องว่างที่หลากหลายพร้อมด้วยอัลกอริธึม BP
ข้อนี้จะทำการวิเคราะห์ให้เหตุผลว่าทำไมนาที - จำนวนเงิน
อัลกอริธึมมีข้อผิดพลาดและจะทำให้ส่งต่อที่ได้รับการปรับปรุงอัลกอริธึม
เรียกว่านาที - จำนวนเงินตามแนวยาวประมาณอัลกอริธึมที่ใช้นาที -
จำนวนอัลกอริธึม.
คีย์เวิร์ด - ldpc อัลกอริธึมการถอดรหัส,ต่ำสุด - จำนวนเงินอัลกอริธึม, BP

อัลกอริธึมอัลกอริธึมมี ประสิทธิภาพ การทำงานที่ดีขึ้นกว่าอัลกอริธึมนาที - เงินและ
ซึ่งจะช่วยได้ง่ายมากที่จะได้รับมากกว่าอัลกอริธึม
BP อัลกอริธึม BP อัลกอริธึม.

BP II ยังอัลกอริธึมจำนวนเงิน - ผลิตภัณฑ์ เรียกว่ามีอัลกอริธึมการถอดรหัสดี
ซึ่งจะช่วยทำให้ ขั้นตอนการถอดรหัสมีพื้นที่ที่มีอัตรา
ซึ่งจะช่วยคำนวณความเป็นไปครั้งแรกที่เริ่มการทำงาน
A :
ในโอกาสที่เป็น
ซึ่งจะช่วยถ่ายโอนจากช่องที่จะโหนดได้ที่ L ( pi )
ผม= 1,2 ........................ nสำหรับแบบปรับได้หลายระดับโหนดและอยู่ในบริเวณใกล้เคียงของการตรวจสอบโหนด
j ,แรกข้อมูลที่ได้รับการถ่ายโอนจากตัวแปร
โหนดในการตรวจสอบโหนดใน awgn channel คือ:

ตามมาตรฐาน 2 , RI , 1 exp ( 2 )

 l ( 0 )( qij ) l ( pi ) ln

ตามมาตรฐาน 2 , RI , 1 exp ( -  2 )

  2 , RI , 2 , RI ,
ln EXP ( 2 )  2 ( 1 )

 I .

ตามมาตรฐานการแนะนำรหัสการตรวจสอบ Parity ความหนาแน่นต่ำอย่างหนึ่งของตามแนวยาวบล็อค
รหัส มันเป็นการส่งเสริมโดย gallager [ 1 ]ในช่วงทศวรรษที่ 1960 s เป็นครั้งแรก ในปี 1981 ใน
เครื่องอาบแดดของข้อเขาอธิบาย ldpc ในรูปแบบใหม่กับรุ่นกราฟ
เป็นเวลายาวนานรหัสนี้ถูกเพิกเฉย ในช่วงปีทศวรรษที่ 1990 s
ใน[ 2 ]และอื่นๆวิจัยและพบว่ารหัส ldpc
มีความสามารถในการรองรับการแก้ไขข้อผิดพลาด Strong จากที่ ldpc
ซึ่งจะช่วยนั้นได้รับการยอมรับอย่างกว้างขวางวิจัยและกระจายตัวอยู่โดยรอบโรงแรมได้รับการพิสูจน์แล้วว่า
ซึ่งจะช่วยเพิ่ม ประสิทธิภาพ ของรหัส ldpc มีอยู่ค่อนข้างใกล้กับจำกัด, Shannon ได้.
ความแตกต่างที่มีระดับต่ำเป็นหนึ่งส่วนสิบสองถึงสามแห่ง dB [ 3 ]..
ประสิทธิภาพ สูงของรหัส ldpc มีผลมาจาก
แบบไม่มีแอลกอฮอล์การถอดรหัสคำพิพากษาของอัลกอริธึม gallager ใส่ส่งต่ออัลกอริธึมการถอดรหัส
ฝึกฝนตามที่ตั้งอยู่บนแพร่กระจาย:
ความเชื่อโดเมนมีโอกาสที่เรียกว่าจำนวนเงิน - ผลิตภัณฑ์
อัลกอริธึมยังเมื่อกราฟเครื่องอาบแดดที่ไม่มีในระยะทางสั้นๆเพื่อไป
ซึ่งจะช่วยการต่อพ่วงใดอัลกอริธึมนี้จะทำให้มีการปฏิบัติที่ดีที่สุด แต่คำนวณของ
อัลกอริธึมแห่งนี้มีขนาดใหญ่และมันเป็นเรื่องยากในการวางไว้ในฮาร์ดแวร์ อัลกอริธึมต่ำสุด -
จำนวนเงินคืออ ภิรมย์ ที่ดีของอัลกอริธึม BP
ซึ่งจะช่วยให้สามารถลดขนาดใหญ่จำนวนมากที่มีการคำนวณและเป็นเรื่องง่ายที่จะทำให้เป็นจริงได้.
แต่ความถูกต้องของอัลกอริธึมนาที - จำนวนเงินต่ำเกินกว่า BP
อัลกอริธึม.
ข้อนี้เป็นหลักการศึกษา ldpc อัลกอริธึมการถอดรหัสและ
ซึ่งจะช่วยวิเคราะห์ BP อัลกอริธึมและต่ำสุด - จำนวนเงินอัลกอริธึม,และจากนั้นจะทำให้
ซึ่งจะช่วยส่งต่อที่ได้รับการปรับปรุงนาที - จำนวนเงินอัลกอริธึมการใช้ตามแนวยาว
อ ภิรมย์ และอย่างน้อยหมายความว่า Square อัลกอริธึม. ที่ได้รับการปรับปรุง

.
ฝึกฝนตามการประมวลผลของ llr BP อัลกอริธึม
1 :ปรับปรุงให้ตรวจสอบโหนด
ซึ่งจะช่วยในการตรวจสอบโหนด J และที่อยู่ในบริเวณใกล้เคียงได้โหนด
i ,ใน kth ย้ำ,สูตรของข้อมูลของ
การตรวจสอบโหนดคือ:
L ( K )( rji )

⎧⎫ ⎪⎪k - 12 Tanh ⎨∏tanh [ 0.5 L ( QI ' J )]⎬
⎪⎪⎩i ' ∈n ( J )/ I '⎭
- 1
( 2 )

 2 การปรับปรุงปรับเปลี่ยนโหนด
ซึ่งจะช่วยในการปรับเปลี่ยนโหนดและอยู่ในบริเวณใกล้เคียงของการตรวจสอบโหนด
j ,ใน kth ย้ำ,สูตรของข้อมูลของ
ซึ่งจะช่วยปรับเปลี่ยนโหนดคือ:
L ( K )( qij ) l ( pi )
J ' ∈m ( i )/ J '

∑ L ( K )( RJ "ฉัน)
( 3 )
978-1-4577-1295-1/11 /$ 26.00 © 2011 IEEE
26


 3 การตัดสินใจการถอดรหัส
ซึ่งจะช่วยคำนวณที่การตัดสินใจปรับเปลี่ยนข้อมูลของโหนด
:
L ( QI ) l ( pi )
( K )
j∈m ( i )

∑จะสามารถเห็นได้จากกราฟของ  ( X )ที่เมื่อ x > 0 ,  ( X )> 0 ,
และจะลดลงเป็น x เพิ่มขึ้น. เมื่อ X มีขนาดใหญ่  ( X )เกือบจะ
0และ ∑ ( J i ')คือประมาณเท่ากับ J ' i  (นาที)
ซึ่งจะช่วยให้ผม' ∈n ( J )/ I '
L ( rji )
( K )
( 4 )
[
ฉัน' ∈n ( J )/ I '

∑  ( i ' J )]
( 9 )
0 L ( K )( QI )  0
CI  {
1 L ( K )( QI ) ≤ 0


≈ 4 หยุด[  (นาที i ' J )] min i ' J
( 5 )
L ( rji )  (
ฉัน' ∈n ( J )/ I '

∏ i ' J )นาที i ' J
( 10 )
หาก HC  0 หรือหากจะมีโปรแกรมไปถึงมือ
ย้ำสูงสุด iterating หยุด ไม่เช่นนั้นจะกลับมา
ขั้นตอน( 2 )จนกว่าจะสามารถย้ำสูงสุด.

นาที III - เงินอัลกอริธึม

ตามมาตรฐาน T ในทางนี้จำนวนมาตรวัดคือลดลง
ประยุกต์การถอดรหัสอัลกอริธึมที่เรียกว่านาที - เงิน
อัลกอริธึม[ 4 ].อัลกอริธึม
IV

ซึ่งจะช่วยปรับปรุงจากสูตร( 2 )โดยทั่วไปแล้วเราจะได้รับทำตามสูตร:
Tanh ( 0.5 L ( rji ))

ฉัน' ∈n ( J )ผม'
วิเคราะห์ที่กราฟของ  ( X ),คุณสามารถเห็นว่า
( 6 )
ฉัน' ∈n ( J )/ I '

∏ Tanh [ 0.5 L ( QI ' J )]

∑  ( i ' J )  (นาที i ' J )ดังนั้น
[
ฉัน' ∈n ( J )/ I '
ปล่อยให้ L ( QI ' J ) ij ij ,ในสูตร,

∑  ( i ' J )]
( 11 )
ij sign ( L ( QI ' J )), ij l ( QI ' J ) ดังนั้นสูตร( 6 )จะกลายเป็น
Tanh ( 0.5 L ( rji ))

ฉัน' ∈n ( J )ผม'
 [  (นาที i ' J )] min i ' J
สูตร( 11 )จะแสดงให้เห็นว่าค่าของ L ( rji )ในนาที - เงิน
อัลกอริธึมมีขนาดใหญ่กว่าที่ BP อัลกอริธึม. อัลกอริธึม
ซึ่งจะช่วยลดการเกิดข้อผิดพลาดขณะนำโดยประมาณในนาที - จำนวนเงินที่เรา
จำเป็นต้องลดค่าของ L ( rji )..
ทางหนึ่งในการแก้ไขปัญหาที่เป็นอัลกอริธึมเทียบ[ 4 ]..
แต่มันไม่ดีพอ ตามนี้และมีพื้นฐานอยู่บน
ซึ่งจะช่วยงานของกระดาษ[ 5 ]อัลกอริทึมที่ได้รับการปรับปรุงคือการนำส่งต่อ.
สันนิษฐานว่า L ( rji )ของนาที - เงินอัลกอริธึมคือ lmin ,และ

∏ i ' J
ฉัน' ∈n ( J )/ I '

∏ Tanh [ 0.5 i ' J ]
( 7 )
ระบุที่ช่วยเสริมฟังก์ชัน
EX  1
 ( X ) log Tanh ( 0.5 x )ล็อกอิน( x ) คุณลักษณะที่สำคัญของโรงแรมคือ

E - 1 - 1 ที่  ( X )=  ( x ) ดังนั้นสูตร( 7 )จะกลายเป็น
L ( rji )
(
ฉัน' ∈n ( J )/ I '

∏ i ' J )[
ฉัน' ∈n ( J )/ I '

∑ ( J i ')]
( 8 )
L ( rji )ของอัลกอริธึม BP คือ LBP และว่า L ( rji )ของดีขึ้น
อัลกอริธึมคือ L . แนะนำพารามิเตอร์ A และ B จะต้องเป็นผู้รับผิดชอบ
L almin b 0 << 1 จะทำให้มูลค่าของ L ได้รับอยู่ใกล้
ซึ่งจะช่วยในการ LBP ,การใช้อย่างน้อยหมายความว่า Square และทำให้อัลกอริธึม lmin
อยู่ใกล้กับ LBP .
สันนิษฐานได้ว่าหมายความว่าอะไร? Square ,ฟังก์ชัน F ( A , B )เป็น
ฟังก์ชันของ A และ B ,
F ( A , B ) e [( L - lbp ) 2 ]
ในการได้รับความคุ้มค่าของ A และ B คำนวณดัดแปลงจากของ F
∂f ( B ) ∂a  0
รูปที่ 1 กราฟของ
( 12 )
 ( X )
∂f ( B ) ∂b  0
จากสูตร( 13 )ซึ่งสามารถเป็นที่ทราบกันดีว่า