本文ここから

Study on Multi-Stage Threshold Decoding with Difference Register (ディファレンスレジスタを用いた多段閾値復号法の研究)

氏名 MUHAMMAD AHSAN ULLAH
学位の種類 博士(工学)
学位記番号 博甲第595号
学位授与の日付 平成23年8月31日
学位論文題目 Study on Multi-Stage Threshold Decoding with Difference Register (ディファレンスレジスタを用いた多段閾値復号法の研究)
論文審査委員
 主査 教授 荻原 春生
 副査 教授 吉川 敏則
 副査 准教授 中川 健治
 副査 准教授 武井 由智
 副査 本学名誉教授 島田 正治

平成23(2011)年度博士論文題名一覧] [博士論文題名一覧]に戻る.

Contents p.vii
List of Figures p.xi
List of Tables p.xvi
1 Introduction p.1
2 Multi-Stage Threshold Decoding with Difference Register p.8
 2.1 Introduction p.8
 2.2 Self-Orthogonal Convolutional Codes p.9
 2.3 Approximate Lower Bound of Maximum Likelihood Decoding p.10
 2.3.1 Approximate Lower Bound of ML Decoding for Hard Decision p.10
 2.3.2 Approximate Lower Bound of ML Decoding for AWGN Channel p.13
 2.4 Threshold Decoding p.15
 2.5 Multi-Stage Threshold Decoding p.18
 2.5.1 Hard Decision MTD p.19
 2.5.2 Soft Decision MTD p.24
 2.5.3 Weighted Bit Flipping MTD p.28
 2.5.4 Combined Soft Decoding MTD p.30
 2.5.5 Combined Soft Decoding MTD with Feedback p.33
 2.6 MTD with Parity Check Decoding p.36
 2.7 Decoding Complexity p.39
 2.8 Summary p.41
3 Suitable Self-Orthogonal Convolutional Codes for MTD p.42
 3.1 Introduction p.42
 3.1.1 Self-Orthogonal Convolutional Code Type 1 p.43
 3.1.2 Self-Orthogonal Convolutional Code Type 2 p.46
 3.2 Error-Grouping and Self-Orthogonal Convolutional Codes p.47
 3.2.1 Error-Grouping for SOCC Type 1 p.48
 3.2.2 Error-Grouping for SOCC Type 2 p.49
 3.3 Code Searching Algorithm p.50
 3.4 Symmetric Self-Orthogonal Convolutonal Codes p.52
 3.4.1 Symmetric SOCC:Tp2 p.53
 3.5 Asymmetric Self-Orthogonal Convolutional Codes p.61
 3.5.1 Asymmetric SOCC Type 2 p.61
 3.6 Summary p.67
4 Performance Improvement of Multi-Stage Threshold Decoding p.69
 4.1 Introduction p.69
 4.2 2-Step Decoding p.70
 4.2.1 2-Step Decoding Type 1 p.71
 4.2.2 2-Step Decoding Type 2 p.73
 4.3 Iteration Reduction of 2-Step Decoding Schemes p.79
 4.3.1 Iteration Reduction of 2SD:TP1 p.79
 4.3.2 Iteration Reduction of 2SD:TP2+GF p.81
 4.4 Variable Threshold MTD p.82
 4.5 Parity-Check Decoding in Iteration p.83
 4.6 Summary p.87
5 Higher Rate Cldes for 100 Gb/s Optical Transport Network p.89
 5.1 Introduction p.89
 5.2 Higher Rate Codes p.89
 5.2.1 Higher Rate Symmetric Codes p.90
 5.2.2 Higher Rate Asymmetric Codes p.91
 5.3 MTD for Optical Communications p.93
 5.4 High Speed Decoding p.98
 5.5 Summary p.99
6 Improvement of Code Construction for MTD p.101
 6.1 Introduction p.101
 6.2 Convolutional Codes with Relaxed SOCC Convolution p.102
 6.3 Self-Orthogonal Codes from Golomb Ruler p.105
 6.4 Summary p.111
7 Future Research Plan p.12
8 Conclusion p.114
 A Analysis of Threshold Decoding with Feedback p.118
 A1 Feedback Decoding p.118
 A2 Definite Decoding p.119
 A3 Genie Decoding p.119
 A4 Performance Analysis of Threshold Decoding with Feedback p.120
 A4.1 p.120
 A4.2 p.123
 A4.3 p.124
 A4.4 p.128
 A5 Summary p.129
 B ML Decoding Performance for SOCC with PC Code p.130
 C Variable Threshold MTD p.121
 C1 Variable Threshold Hard Decision MTD p.121
 C2 Variable Threshold SMTD p.133
 C3 Variable Threshold WMTD p.135
 C4 Variable Threshold CMTD p.135
 C5 Variable Threshold CMTDF p.136
 D Self-Orthogonal Convolutional Code type 1 p.138
 D1 Symmetric SOCC:Tp1 p.138
 D2 Asymmetric SOCC Type 1 p.139
 D3 Higher Rate Symmetric SOCC Type 1 p.140
 D4 Higher Rate Asymmetric SOCC Type 1 p.140
 E Some Convolutional Codes for MTD p.142

 For an error correcting code, a low complex high performance decoding scheme is always desirable. Threshold decoding (TD), which is a kind of least complex decoding, has been presented in 1963. The decoding performance of TD was not attractive. Based on the TD, Russian scientists have been proposed iterative threshold decoding with difference register called multitheshold decoding (MTD). Except for simulation results, necessary information to rebuild the system is absent in their publications. Moreover, their analytical procedure can hardly understandable.
We use the basic idea of MTD and give various hard and soft decoding algorithms in this thesis. In actual case, the naming ``multithreshold decoding'' was not appropriate with the decoding algorithm. So, we rename the system as `` multi-stage threshold decoding with difference register (MTD)''. The decoding scheme works on reducing the Hamming and Euclidean distances between a received word and a decoded codeword, generated from decoded information bits, after every flipping. A self-orthogonal convolutional code (SOCC) is used.
This thesis shows that, SOCC type 1 (SOCC:Tp1) makes an unavoidable error grouping in the decoded information bit sequence by the MTD. To overcome of error-grouping problem, SOCC type 2 (SOCC:Tp2) is proposed.
In this thesis, an approximate lower bound of maximum likelihood (ML) decoding (abbreviated as ML decoding) is formulated for hard and soft decision decoding. MTD realizes the ML decoding performance in the error floor region at the higher Eb/N0. To improve the waterfall performance, a 2-step decoding (2SD) is also proposed. The 2SD produces 0.50 dB more coding gain in the waterfall region compared to conventional MTD.
In many applications higher rate code is necessary. Finding a code with larger number of parity sequences is a difficult task. We give a code construction procedure from Golomb ruler. MTD for the code with rate of 5/6 produces coding gain of 10.60 dB at the bit error rate of 10-15. This decoding scheme will be a vital competitor for 100 Gb/s optical transport network. Moreover the MTD can usable for shorter and longer codes with impressive coding gain. Therefore, as a least complex decoding, MTD will be a strong member in the era of error correction coding.
Chapter 1 represents the main goal of our research. This chapter also gives about related previous works of iterative decoding.
Chapter 2 gives the basics of the proposed decoding method and self-orthogonal convolutional code. An approximate lower bound of ML decoding for hard and soft decision decoding is also given. Hard and soft decisions MTDs are formulated. Hard decision MTD (HMTD) achieves the ML decoding performance in the error floor region whereas soft decision MTD (SMTD) does not. Nevertheless, SMTD gives better decoding performance in error floor region compared to HMTD. Another soft decision decoding called weighted bit flipping MTD (WMTD) is proposed. The WMTD improves the coding gain in waterfall region compared to both HMTD and SMTD, but the error floor performance is degraded.
This chapter gives a decoding method that concatenates WMTD and SMTD serially. This decoding scheme is called combined soft decision MTD (CMTD). The CMTD achieves the ML decoding result in the error floor region as well as improves the waterfall performance compared to other MTD schemes. To further improve the waterfall performance, CMTD with feedback (CMTDF) is proposed. The CMTDF gives 0.40 dB more coding gain in waterfall region compared to CMTD. To improve the error floor performance, a parity check (PC) code is used prior to SOCC encoding. The MTD gives the bit error rate of less than 1/100 times than that of the ML decoding for the code without PC code in error floor region. Still there is a performance gap between MTD with PC code and ML decoding for SOCC with PC code in the error floor region. The decoding complexity is also given.
Chapter 3 discusses about the SOCCs which are suitable for MTD. The MTD for SOCC:Tp1 makes an unavoidable error-grouping in the decoded information bit sequences. So, SOCC:Tp2 is proposed. MTD gives better decoding results for the SOCC:Tp2 with larger number of parity sequences.Experiment shows that, the SOCC with larger number of orthogonal parity-check equations (OPEs) gives better decoding performance in error floor region, but degrades the performance in waterfall.
Opposite incident is happened for the code with smaller number of OPEs. By using this concept, a new decoding scheme called 2-step decoding (2SD) is presented in chapter 4. The 1st decoding step uses a part of the parity sequences, as if decoding is done by the smaller number of OPEs of the code. The 2nd decoding step works like as conventional MTD. The 2SD achieves of 0.50 dB more coding in the waterfall region compared to CMTDF.
Chapter 5 gives decoding results of MTD based decoding systems for higher rate codes. Code with rate at least 4/5 is called higher rate in this thesis. In terms of decoding complexity and latency, CMTDF is a good choice for higher rate code. High speed decoding technique is also given in this chapter.
Chapter 6 gives a relaxed self-orthogonal convolutional code (RSOCC) for MTD. The RSOCC allows a few number of cycle 4 in its parity-check matrix. This type of code gives the similar decoding performance of SOCC with the MTD. Moreover, the RSOCC can reduce the constraint length as well as code length even if the number of parity sequences of the code is comparatively larger. This chapter also gives an idea to construct SOCC:Tp2 from a Golomb ruler. The SOCC from Golomb ruler has comparatively shorter constraint length compared to SOCC, which is found by the code searching algorithm. It is seen that, MTD for SOCC:Tp2 with rate of 5/6 gives 10.60 dB more coding gain at the BER of 10-15. It indicates that, the MTD will be a strong candidate for the 100 Gb/s optical transport network.
Chapter 7 gives some ideas to do research in future.
Chapter 8 concludes this dissertation.

 本論文は「Study on Multi-Stage Threshold Decoding with Difference Register(ディファレンスレジスタを用いた多段閾値復号法の研究)」と題し誤り訂正符号の復号法を論じたもので、8章で構成されている。
 第1章では、閾値復号を繰り返し行い、少ない復号処理量で、高い復号性能を実現するという本研究の目的とそれに関連した従来研究とその問題点について述べている。
 第2章では、従来の閾値復号器にdifference registerを付加した提案手法の基本原理を説明している。そこでは、復号した符号語のビット反転ごとに受信語からのハミング距離(硬判定の場合)あるいは2乗ユークリッド距離(軟判定の場合)が減少することを理論的に示している。さらに、この手法が有効に作用する自己直交畳み込み符号を用いた場合のビット誤り率(BER)の理論限界を導出し、実用領域で提案手法がこの限界を実現することを計算機実験により示している。
 第3章では、提案手法に適した自己直交畳み込み符号の構造を理論的・実験的に明らかにし、少なくとも2系列のパリティビット系列が必要であることを示している。 第4章では、2段階復号法を提案し、BER特性が急減する領域で要求される信号対雑音比を0.5dB改善すること、また、パリティチェック符号と組み合わせることにより、BER特性が緩やかに変化する領域でBERを、パリティチェック符号を用いない場合に比べさらに1/100にできることを示している。
 第5章では、次世代の高速光通信への適用を想定した符号化率4/5の符号への提案手法の適用結果を示し、そこで要求されるBER=10-12で符号化利得10dBを実現できることを示している。さらに、これらの応用で必要な高速復号を実現する並列復号処理法を示している。
 第6章では、符号構成の自由度を増すため、自己直交の条件を少し緩めると、BER特性の大きな劣化を伴わずに符号長を短縮できることを示している。さらに、数学で研究されているGolumb Rulerの結果を使うと、自己直交条件を満たしながら符号長の短い符号を構成できることを示し、これらにより次世代光通信の要求により適合する符号化率5/6の符号で符号化利得10dBを実現できることを示している。
 第7章では、提案手法をさらに拡張するための今後の研究指針を示している。
 第8章は結論であり、本研究の結果をまとめている。
 以上のように、本論文は新規の誤り訂正処理の原理を提案し、その特性を理論的・実験的に解明すると共に、 実際の応用可能性を示したもので、 工学上および産業上貢献することが大きく博士(工学)の学位論文として十分な価値を有するものと認める。

平成23(2011)年度博士論文題名一覧

お気に入り

マイメニューの機能は、JavaScriptが無効なため使用できません。ご利用になるには、JavaScriptを有効にしてください。

ページの先頭へ戻る