ターボ符号は,1993年の発表以来その卓越した性能が急速に認知され,既に第3世代の移動体通信システムにおいて実用化されるに至った.その他深宇宙通信,衛星通信,そしてディジタルビデオ放送等への無線系システムヘの応用に加えて,非対称ディジタル加入者線(ADSL, Asymmetric digital subscriber line)通信等の有線系システムヘの応用も活発な議論がなされている.本論文は,"Turbo Codes and Turbo Trellis-Coded Modulation:Information-Theoretic limits and Pragmatic Decoding Algorithms"(ターボ符号とターボトレリス符号化変調:情報理論的限界と実践的復号法)と題し,無線通信システムでの最重要課題である周波数帯域の有効利用をターボ符号を用いて実現する手法を提案し,高速通信システムで不可欠の高符号化率のターボ符号に関する幾つかの効率的な復号法を提案する.それを通じて実用的な高帯域無線通信システムの実現を目指している.同時に,現実のシステムで生じる種々の不完全性に起因する性能劣化を理論的に解析することで通信システム特性を情報理論的観点より絶対的な尺度での評価を行い,ターボ符号を備えた実践的な通信システムの構築及びその設計規範の確立を目指している.

　第1章の"Introduction"では,現存する高速無線通信における符号と変調技術の問題点を挙げ,本研究の動機と目的について述べる.

　第2章では"Information-Theoretic Bounds and Channel Coding"と題して,本研究の基礎となる符号化率と理論限界との関係を述べるとともに,ターボ符号および高帯域効率の変調方式について言及する.

　第3章は,"Application of Turbo Codes to High-Rate Codes"と題し,パンクチャリングに基づいた従来のパンクチャドターボ符号(PTC, Punctured Turbo Code)が高符号化率の符号を要する高速通信システムには性能の点から不利であることを理論解析および計算機実験を用いて指摘し,その代わりとして高符号化率の符号器を要素符号器とする非パンクチャドターボ符号(UTC, Unpunctured Turbo Code)を提案する.そして,ある符号語ビットを適当な回数だけ反復することで符号化率を低下させる反復ターボ符号を導入し,UTCを用いた場合においてもなお可変符号化率を実現する手法について述べる.その下で,UTCの復号時における計算量の問題点について言及する.

　第4章の"Heuristically Reduced-Complexity Algorithms for High-Rate Turbo Codes"では,高符号化率UTCの復号の計算量を低減する一方法として,復号結果より得られる情報シンボルの信頼度に基づき送信シンボルのしぼり込みを行うことで,符号トレリス上で表現される符号語数が低減されることにより復号に伴う計算量の削減を図るヒューリステイックな方法を提案する.計算機実験と理論解析を介した計算量と性能のトレード・オフの観点からPTCとの比較を行うことで,その方式の評価がなされる.

　第5章では"Algebraically Reduced-Complexity Algorithm for High-Rate Turbo Codes"と題し,線形符号の双対性を利用することで代数的に高符号化率UPTの復号処理量を削減する1つの方法を提案する.復号時に,通常のターボ符号が生成行列により構成される符号トレリス上で最適な経路を探索するのに対し,提案方法では生成行列と双対の関係にあるパリティ検査行列によるトレリス上で最適経路の探索を実行する.その双対性による符号語数の削減を利用し,結果として計算量の低減がなされることを示す.それと同時に,ターボ符号において実装上の重要課題の1つである,シンボルの信頼度情報を復号過程で記憶するための記憶量も符号化率の上昇に伴って削減されることを述べる.その下で,UTCが高符号化率を要する高速通信システムで今後重要な役割を果たす可能性に言及する.

　第6章の"Application of Turbo Codes to Bandwidth-Efficient Modulation"では,移動通信で特に問題となる周波数逼迫の課題に対して,ターボ符号をトレリス符号化変調(TCM, Trellis-Coded Modulation)へ適用することで,ターボトレリス符号化変調方式(TTCM, Turbo Trellis-Coded Modulation)の1つの実現方法を提案する.この方式により高帯域効率の変調方式且つ強力な誤り訂正符号を有する通信システムが実現される.その復号過程では,シンボル毎の信頼度を巧みに生成し復号に利用することにより特性の劣化なく計算量を抑えることのできる信頼度情報の新しい生成方法を提案する.その特性は,現存の同様な方式と比較され,評価および考察がなされる.

　第7章は"Performance of Turbo Trellis-Coded Modulation over Practical Channels"と題し,現実に則した幾つかの通信路の通信速度の限界を理論的に算出し,ターボ符号等の強力な誤り訂正符号を用いることで理論的限界に迫る性能が達成可能か否かについて議論する.まず,同期系無線システムでの送受信器間で位相誤差が発生する場合の通信路容量を算出し,どの程度の位相誤差に対してどこまで通信速度を上げることができるかを示すと共に,SN比の劣化量を定量的に求める.さらに,レーリーフェージング通信路でフェージング複素ゲインが受信器側で正確に推定できない場合の実情に即した無線システムを考え,位相誤差の場合と同様に通信路容量を求めることにより最大通信速度とSN比の劣化量を求める.その正当性はターボ符号を用いた計算機実験を通じて評価される.

　第8章の"Conclusions"では,本研究の総括を行い,今後のターボ符号を搭載する通信システムについての展望を述べる.

英文

High-speed digital communication over wireless channels raises the challenging problem that simultaneously accomplishes a severely power- and bandwidth-limited data transmission with an error rate kept as small as possible. One very successful method of the conventional techniques for meeting the requirements is to employ trellis-coded modulation (TCM) [UI76], [Ung82], [Ung87a], [Ung87b]. The TCM is a method of combining channel coding and modulation such that both the components are interacted in a friendly way so as to gain noise immunity over uncoded transmission without expanding the signal bandwidth or increasing the transmitted power. A typical construction of TCM is to employ both a convolutional code and a bandwidth-efficient modulation, say, 16-ary quadrature amplitude modulation (16-QAM) and hence is capable of offering a great coding gain over uncoded schemes as far as the synchronization and the channel estimation are both perfect. However, it has turned out that even the most complex TCM scheme is still about 2 dB away from the theoretical limits [Sha48] at a bit error rate (BER) of 10-5 despite many researchers' best endeavors. Furthermore, the TCM scheme as well as other previously presented schemes is found out to be quite sensitive to errors of the synchronization and the estimation, both of which confront communications engineers, particularly in the mobile applications field [LP87], [HS88], [VD95]. Consequently, constructing a powerful and insensitive coded system is becoming the challenging problem, along with the simplification of the system.

The turbo codes technique [BGT93], [BG96] introduced in 1993 has recently received a lot of attention since it shows performance close by 0.5 dB to the Shannon capacity limit [WJ65] at a BER of 10-5 with spectral efficiency of 0.5. Hence it has been standardized for many wireless and wired transmission systems such as the third generation mobile communications, satellite communications, deep-space communications, and digital subscriber line transmission, in all of which strictly power-limited transmission is desired. A notable structural feature of turbo codes is in the form of the encoder. A turbo encoder consists of the parallel concatenation of two identical convolutional codes in a systematic feedback form and a pseudorandom interleaver of size N between the two encoders, and therefore its form can make the whole turbo encoder behave as if a block code with 2N codewords. Irrespective of the seemingly high complexity of the block code with maximum-likelihood (ML) decoding, a turbo decoder accomplishes decoding operations with no sweat by means of an ingenious iterative decoder that consists of the two component decoders that produce reliability information on data bits and mutually deliver it between them [HOP96]. Still better, turbo codes can be decoded in the similar way as convolutional codes with soft-decision Viterbi decoding, apart from soft-input/soft-output mechanism incorporated in each component decoder. Therefore, an advantage of turbo codes is that they can be readily implemented in the existing very large scale integration (VLSI) and high-speed logic circuits with an additional piece of hardware.

There are some very critical disadvantages in the turbo codes [FK98]. First, even if the turbo decoder is materialized in simple hardware, one of the disadvantages is the delay attendant upon the iterative decoding; that is, the turbo decoder usually necessitates more than ten iterations in a serial manner, so as to use the potential decoding talent to the full. The latency period is unacceptable, especially for the Internet and multimedia interactive applications. It is therefore necessary that an arduous effort should be made with the aim of simplifying the decoding procedure. This effort is also useful in ameliorating a severe penalty of the power-limited mobile terminals. Second, there is another fundamental disadvantage in the turbo codes. Since turbo codes have been originally developed in conjunction with binary phase-shift keying (BPSK), the spectral efficiency is insufficient [GGB94], [RW98], [BDMP96], [WFH99], [AR99] (the turbo codes are referred to as binary turbo codes thereafter). Therefore, in order to apply the turbo codes to the system such as cellular and satellite communications systems using battery-driven portable terminals, the systems needs more bandwidth efficiency as well as power-consumption efficiency.

To see the power and bandwidth efficiencies of binary turbo codes, performance of a binary turbo code system along with deep-space communications systems over an additive white Gaussian noise (AWGN) channel is illustrated in Fig. 1 as a function of signal-to-noise ratio (SNR) per bit, represented by Eb/N0. In the figure, all the systems' performance are depicted for a BER of 10-5 and the systems are employing low bandwidth-efficient BPSK modulation due to no necessity of spectral efficiency for deep-space applications. As a fundamental criterion, the famous Shannon bound [WJ65], [DJCHIW98] shows the absolute best possible for a digital communication system on the AWGN channel from the spectral- and the power-efficient points of view. Of course, uncoded BPSK system has the best spectral efficiency R=1 and can achieve a BER of 10-5 at Eb/N0=9.6 dB, whereas the Shannon limit is a 7.74 dB away from the system performance. So far the advance of coding theory has been narrowing this gap between system performance and limit at the sacrifice of bandwidth efficiency. For examples, by reducing the spectral efficiency by 80%, the Mariner employing a rate-6/32 Reed-Muller code achieved a coding gain of 3.2 dB. By contrast, a well-designed Bose-Chaudhuri-Hocquenghem (BCH) code achieves a few more coding gain, making the spectral efficiency less by 50%. Yet more coding gains were achieved by the following missions. The Pioneer missions in 1972 and 1973, both used a 231-state nonsystematic convolutional code (CC) and sequential decoding, achieve a coding gain of 6.9 dB for the spectral efficiency of 50%, though the sequential decoding requires high computational cost. Then, the Voyager spacecraft in 1977, used a 64-state convolutional code in concatenation with a (255,233) Reed-Solomon (RS) code, achieves an excellent tradeoff such that coding gain is 0.2 dB more and spectral efficiency is 12.5% less than the Pioneer. Further power efficiency has been done by the big Viterbi decoders for larger constraint convolutional codes. The Galileo mission, which used a 16384-state convolutional code concatenated by the same Reed-Solomon code, achieves a 8.6 dB coding gain 0.9 dB larger than the Voyager. However, the Galileo's performance is brought at a great cost to spectral efficiency and computational burden due to the big Viterbi decoding. From the above comparison, it is obvious that binary turbo codes are the best possible method among previously known systems in terms of required Eb/No to achieve the Shannon limit, whereas the spectral efficiency in the turbo codes leaves much room for improvement.

The critical problem also arises in the ancillary function at the receiver. In every coherent transmission system, the synchronization and the estimation abilities are much more important than the decoder performance. It is not until both the synchronization and the estimation are accurately established that the subsequent decoder is able to reconstruct corrupted data sequences. Therefore, those processes prior to decoding are becoming more and more important as more high-bandwidth efficient modulation is employed; nevertheless, only a few theoretical bounds for such processes have been unveil thus far, though study on the cutoff rate that limits the performance of a given code has been done for some cases [WJ65], [ZK91]. Now that the performance of a system employing turbo codes lies behind the cutoff rate, the criterion based on cutoff rate is no longer useful in designing a communication system. Instead, the Shannon bound, otherwise called the capacity bound, is becoming increasingly important, even though it still remains veiled.

This thesis is devoted to the construction of turbo-based trellis-coded modulation, shortly TTCM, and the simplification of the decoding algorithm along with the development of the analysis of the receiver's imperfectness. The goal of the thesis is to develop the efficient transmission system that has both power and spectral efficiencies. Consequently, in discussing how best to decode, we will focus on the tradeoff between performance and complexity.

I. THESIS OUTLINE

Chapter 2 starts with the review of properties underlying the turbo codes that may form the basis for the rest of the thesis. In particular, the relationship between the code rate and the theoretical limits is described.

In Chapter 3, the structure of high-rate turbo codes and their decoding algorithms are described. An unpunctured turbo code (UTC) is proposed as a way of constructing such high-rate turbo codes in comparison with the conventional way on the basis of a punctured turbo code (PTC). The performance of the UTC is compared with that of the PTC not only by theoretically deriving the weight distribution of the codes, but also by experimentally using computer simulations. Accordingly, the problem arises as to how the decoding complexity of the UTC is reduced.

In Chapter 4, a heuristic strategy to reduce the decoding complexity of the UTC is proposed. The concept of this strategy is to reduce the number of branches entering each state in such a way that some of the less reliable branches, which are chosen out based on the soft-output of the decoder, are eliminated every cycle of iteration. The performance of the proposed strategy is evaluated with computer simulation in terms of the performance/complexity tradeoff.

In Chapter 5, a novel algorithm that drastically reduces both the computation and the storage requirements of the UTC at the same time are proposed through use of the duality of the codes. The reduction is done such that the decoding of the UTC uses the parity-check matrix, whereas that of the PTC utilizes the generator matrix. To see the advantages of this algorithm, the computational load and the memory requirements are evaluated and compared with those of the PTC. It is demonstrated that the algorithm becomes quite useful particularly for the high-speed-data applications that require high-rate coding.

In Chapter 6, turbo codes are applied to a bandwidth-efficient modulation. The structure of the turbo codes with high spectral efficiency, so-called turbo trellis-coded modulation (TTCM), is described. In particular, the structure of the decoder is illustrated with great circumstances to make a clear-cut distinction from previously known schemes. The performance is evaluated by computer simulations and compared with the other schemes that have been developed thus far.

In Chapter 7, the effect of errors in the synchronization and the estimation processes are theoretically analyzed. To be specific, the maximum rate at which reliable transmission is possible is calculated for each process. Through computer simulation, the required SNR to achieve a BER of 10-5 with a specific power and spectral efficiency, TTCM definitely, is examined as a function of each parameter.

Finally, conclusions of this study along with discussions for possibility of further applications of the TTCM scheme are given in Chapter 8.

REFERENCES

[AR99] O.F.Acikel and W.E.Ryan. Punctured turbo-codes for bpsk/qpsk channels. IEEE Trans. Commun., 47(9):1315-1323, Sept. 1999.

[BDMP96] S.Benedetto, D.Divsalar, G.Montorsi, and F.Pollara. Parallel concatenated trellis coded modulation. In Proc. IEEE Int. Conf. on Commun. (ICC), pages 974-978, June 1996.

[BG96] C.Berrou and A.Glavieux. Near optimum error correcting coding and decoding: Turbo codes. IEEE Trans. Commun., 44(10):1261-1271, Oct. 1996.

[BGT93] C.Berrou, A.Glavieux, and P.Thitimajshima. Near shannon limit error-correcting coding and decoding: Turbo codes. In Proc. IEEE Int. Conf. on Commun. (ICC), pages 1064-1070, May 1993.

[DJCHIW98] Jr.D.J.Costello, J.Hagenauer, H.Imai, and S.B.Wicker. Application of error-control coding. IEEE Trans. Inform. Theory, 44(6):2531-2560, Oct. 1998.

[FK98] B.J.Frey and F.R.Kshschang. Early detection and trellis splicing: Reduced-complexity iterative decoding. IEEE J.Select. Areas Commun., 16(2):153-159, Feb. 1998.

[GGB94] S.Le Goff, A.Glavieux, and C.Berrou. Turbo-codes and high spectral efficiency modulation. In Proc. IEEE Int. Conf. on Commun. (ICC), pages 645-649, May 1994.

[HOP96] J.Hagenauer, E.Offer, and L.Papke. Iterative decoding of binary block and convolutional codes. IEEE Trans. Inform. Theory, 42(2):429-445, Mar. 1996.

[HS88] J.Hagenauer and C.-E.W.Sundberg. On the performance evaluation of trellis coded 8PSK systems with carrier phase offset. AEU, Band 42, 1988.

[LP87] H.Leib and S.Pasupathy. Trellis-coded MPSK with reference phase errors. IEEE Trans. Commun., COM-35:888-900, Sep.1987.

[RW98] P.Robertson and T.Wort. Bandwidth-efficient turbo trellis-coded modulation using punctured component codes. IEEE J.Select. Areas Commun., 16:206-218, Feb. 1998.

[Sha48] C.E.Shannon. A mathematical theory of communications. Bell Syst. Tech.J., 27:379-423, 1948.

[UI76] G.Ungerboeck and I.Csajka. On improving data-link performance by increasing channel alpabet and introducing sequence coding. June 1976. Ronneby, Sweden.

[Ung82] G.Ungerboeck. Channel coding with multilevel/phase signals. IEEE Trans. Inform. Theory, IT-28(l):55-67, June 1982.

[Ung87a] G.Ungerboeck. Trellis-coded modulation with redundant signal sets, Part I: Introduction. IEEE Commun. Mag., 25(2):5-11, Feb. 1987.

[Ung87b] G.Ungerboeck. Trellis-coded modulation with redundant signal sets, Part II: State of the art. IEEE Commun. Mag., 25(2):12-21, Feb. 1987.

[VD95] B.Vucetic and J.Du. The effect of phase noise on trellis coded modulation over Gaussian and fading channels. IEEE Trans. Commun., 43:252-260, Feb. 1995.

[WFH99] U.Wachsmann, R.F.H.Fischer, and J.B.Huber. Multilevel codes: Theoretical concepts and practical design rules. IEEE Trans. Inform. Theory, IT-45(5) : 1361-1391, July 1999.

[WJ65] J.M.Wozencraft and I.M.Jacobs. Principles of communication engineering. New York: Wiley, 1965.

[ZK91] E.Zehavi and G.Kaplan. Phase noise effects on M-ary PSK trellis codes. IEEE Trans. Commun., 39:373-379, Mar. 1991.

Fig. 1. Milestones in deep-space communications systems that evolved toward achieving the Shannon bound per dimension over the past 40 years; all points refer to the performance at a bit error rate of 10-5.

　本論文は,「Turbo Codes and Turbo Trellis-Coded Modulation : Information-Theoretic limits and Pragmatic Decoding Algorithms(ターボ符号とターボトレリス符号化変調:情報理論的限界と実践的復号法)」と題し,高い帯域効率と優れた誤り率特性を備えた無線通信システムの実現を目的として,ターボ符号を多値変調方式に適用する手法を提案したものである.同時に,このために不可欠な高符号化率ターボ符号に関する効率的な復号法を提案し,その性能を理論解析およびシミュレーションにより明らかにしている.さらに,実際のシステムで生じる種々の不完全性に起因する性能劣化を情報理論的観点から解析することで実際的通信システムの特性を評価するための基礎理論を導いている.論文の構成は8章からなる.

　第1章の「Introduction(序論)」では,本研究の背景を明らかにした上で,研究の動機と目的について言及し,研究の位置付けについて述べている.

　第2章では「Information-Theoretic Bounds and Channel Coding(情報理論限界と通信路符号化)」と題して,ターボ符号の基本原理を概括し,その高帯域効率変調への適用の効果を明確にしている.

　第3章は,「Application of Turbo Codes to High-Rate Codes(ターボ符号の高符号化率符号への応用)」と題し,高符号化率の要素符号器からなるターボ符号の高速通信システムの構成について述べている.特に,従来のパンクチャドターボ符号(PTC, Punctured Turbo Code)と提案の非パンクチャドターボ符号(UTC, Unpunctured Turbo Code)を理論解析およびシミュレーションにより比較することでUTCの利点を示している.また,UTCの計算量の問題を指摘している.

　第4章の「Heuristically Reduced-Complexity Algorithms for High-Rate Turbo Codes Using Reliability Information(高符号化率ターボ符号の信頼度情報に基づく計算量削減アルゴリズム)」では,UTCの復号問題に対し,シンボルの信頼度に基づいて計算量を低減するアルゴリズムを提案している.シミュレーションと理論解析により,そのアルゴリズムが計算量と性能の優れたトレード・オフを有することを示している.

　第5章では「Algebraically Reduced-Complexity Algorithm for High-Rate Turbo Codes Using a Syndrome Trellis(高符号化率ターボ符号の双対性を利用する計算量削減アルゴリズム)」と題し,線形符号の双対性を利用し,代数的に符号語数を低減させることで計算量の削減を図る手法を提案している.それにより,符号化率の上昇に伴って計算量と記憶量が大幅に削減されるという特徴が示されている.

　第6章の「Application of Turbo Codes to Bandwidth-Efficient Modulation(ターボ符号の高効率帯域変調方式への応用)」では,無線通信での周波数逼迫の課題に対し,ターボ符号を多値変調方式に適用するため一方式として,ターボトレリス符号化変調方式(TTCM, Turbo Trellis-Coded Modulation)を提案するとともに,効率的な新しい復号アルゴリズムを提案している.

　第7章は「Information-Theoretic Limits of System Imperfectness and Performance of Turbo Trellis-Coded Modulation(システムの不完全性による情報量的限界とターボトレリス符号化変調の性能)」と題し,現実により近い通信システムに対して,通信路容量とTTCMの性能を明らかにしている.特に,位相雑音とフェージング伝送路の通信路容量を算出し,ある誤差に対する通信速度の上限を示すと共に,SN比の劣化量を定量的に求めている.さらに,TTCMがそれらの理論限界に迫ることを明らかにしている.

　第8章の「Conclusions(結論)」では,本研究の総括を行い,今後のターボ符号を搭載する通信システムについての展望に言及している.

　以上これを要するに,本論文は,ターボ符号を用いた高速無線通信システムの二つの新たな方式を提案し,その特性の詳細な解析を行って,これらが通信システムの理論限界に迫ることを示したものであり,無線通信工学の広範な応用分野,例えば移動通信,衛星通信等の研究分野に貢献するところが少なくない.

　よって本論文は博士(工学)の学位請求論文として合格と認められる.