林茂昭Lin, Mao-Chao臺灣大學:電信工程學研究所陳信溢Chen, Hsin-YiHsin-YiChen2010-07-012018-07-052010-07-012018-07-052009U0001-1108200919573200http://ntur.lib.ntu.edu.tw//handle/246246/188248摘要本篇論文中，我們研究持續長度限制碼 (Run-Length-Limited code, RLL code) 與錯誤更正碼 (Error-Correcting Coding, ECC) 在儲存記錄系統中的應用，首先，我們介紹一些記錄系統的通道特性與模型 (model)，包含磁記錄通道、光記錄通道、部分響應通道，接著我們更描述一些本論文研究所使用的錯誤更正碼在記錄系統中的應用，論文中主要有兩個研究主題，分別說明如下:第一個研究主題，我們使用二位元的RLL (d, k) 限制碼與傳統錯誤更正碼應用在記錄系統上，包含使用RLL (d, k) 限制碼來避免符號間干擾 (inter-symbol interference, ISI) 的不好效應與幫助同步 (synchronization) 的運作，我們提出兩種低密度同位檢查碼 (low-density parity-check, LDPC) 編解碼技術以應用於具有RLL限制功能的部分響應通道 (Partial Response Channel) 上，第一種技術是修正過的選擇翻轉 (selective flipping) 技術，這種技術主要是不再需要附帶資訊 (side information) 第二種技術是基於針對選擇翻轉技術中被翻轉位元的位置做估測，比起單純的選擇翻轉技術 (不管是具有附帶資訊或沒有附帶資訊) 這個估測技術都可以達到顯著的效能改善，此外；我們更整合這兩種技術於一種已知的技術中來設計使用LDPC編解碼的記錄系統，以滿足更嚴謹的RLL (d, k) 限制功能，並且不會降低效能。 層次 (multilevel) 記錄技術在不改變光學和機械單元下，可以用來增加傳統二位元記錄系統的儲存容量，例如標準CD和可重複寫入的DVD系統。為了改善多層次記錄系統的效能並增加資料儲存容量與密度，我們進一步研究非二位元(non-binary) 或多層次 (multilevel, M-level) RLL限制碼的編解碼技術在多層次記錄系統的應用，因此，在第二個研究主題上，我們研究一些接近最高容量 (capacity)的M-level RLL限制碼應用於多層次記錄系統，我們一開始藉由尋找容量逼近 (capacity-approaching) 基本碼 (primitive code) 的建造方法來進行我們的研究並推導有限長度M-level RLL限制碼可達到的編碼率 (coding rate)，接著；我們提出兩種編碼率非常接近最高容量之多層次RLL方塊碼的實用碼 (practical code) 建造，對每一個實用建造碼，我們更提出變化使得具有低複雜度的編解碼優點，僅管對於推導的編碼率與我們所建造之M-level RLL碼的編碼率，兩者都可以接近最高容量 (capacity)，我們用兩種記錄系統模型 (model) 來模擬，為的是要看通道編碼與所建造的RLL限制碼在部分響應通道與光記錄通道上的結合效果。Abstractn this thesis, we study the run-length-limited (RLL) constrained coding and error-correcting coding (ECC) for storage recording systems. First, we introduce the characteristics and models of recording channel such as magnetic recording channel, optical recording channel and partial response channel. Then, we describe the ECC which be used in this thesis for the recording systems. There are two main research topics to be illustrated as follows.he first research topic, we use the binary RLL (d, k) coding with traditional ECC coding to apply to the recording systems, including the RLL (d, k) coding is needed to avoid the adverse effect of inter-symbol interference (ISI) and to facilitate the operation of synchronization. We propose two techniques for the low-density parity-check (LDPC) coded partial response channel with run-length-limited (RLL) constraints. The first is a modification of the selective flipping technique so that side information is not needed. The second is based on the estimation of flipped bits for the selective flipping technique. The second technique can achieve significant performance improvement over the simple selective flipping technique either with side information or without side information. We also incorporate these two techniques into a known technique to design LDPC coded recording systems that can meet strict RLL constraints without performance degradation.ultilevel recording technology increases the capacity of traditional binary recording systems such as standard compact disc (CD) and digital versatile disc (DVD) rewritable systems with no change to the optical/mechanical unit. In order to improve the performance of multilevel recording systems and increase the data storage capacity and density, we further investigate non-binary, or multilevel, M-level RLL coding techniques for multilevel recording system. Therefore, in second research topic, we investigate some capacity approaching M-level RLL codes for multilevel recording systems. We begin our study by searching for capacity-approaching primitive code constructions and derive the achievable rates of M-level RLL codes of finite code lengths. Then, we propose two practical code constructions for multilevel RLL block codes for which the rates are very close to the capacity. For each code construction, we propose a variation which has the merit of low complexity of encoding and decoding. Both the derived coding rates and coding rates of the constructed M-level RLL codes can closely approach the capacity. Simulation for two recording system models is implemented to see the combined effect of channel coding and the constructed RLL coding over a partial response channel and an optical recording channel. eywords: constrained codes, low-density parity-check (LDPC) codes, magnetic recording channel, multilevel, M-level, optical recording channel, partial response channel, run-length-limited (RLL) codes, Reed-Solomon (RS) codes.Abstract iiiist of Figures ixist of Tables xiv Introduction 1 Recording Channels 9.1 Introduction ……………………………………………………9.2 Magnetic Recording Channel …………………………………11.2.1 Magnetic Media/Write/Read…………………………………12.2.2 Lorentzian Channel Model …………………………………13.3 Optical Recording Channel …………………………………17.3.1 Optical Recording Channel Model…………………………20.3.2 Pulse Length Modulation……………………………………20.3.3 Optical Multilevel RLL Recording ………………………22.3.4 Optical Recording Channel with Electronics and Transition Noises……………………………………………………26.4 Partial Response Channels……………………………………30.4.1 Capacity of Partial Response Channel …………………34.4.2 Partial Response Equalization……………………………36.4.3 Decision of PR Channel Model ……………………………38.4.4 Partial Response Channel Detection ……………………40.5 Concluding Remarks ……………………………………………41 Some Error Correcting Codes For Recording Systems 43.1 Introduction ……………………………………………………43.2 LDPC Codes for Recording Systems …………………………45.2.1 Representation of LDPC Codes ……………………………45.2.2 Encoding Methods of LDPC Codes …………………………46.2.3 Decoding Methods of LDPC Codes …………………………48.2.4 Gallager''s Codes ……………………………………………51.2.5 Mackay''s Codes ………………………………………………52.2.6 LDPC Codes Based on the PEG Algorithm…………………53.3 Reed-Solomon Codes for Recording Systems ………………56.3.1 Reed-Solomon Codes Based on Galois Fields (GF) ……57.3.2 Reed-Solomon Systematic Encoding ………………………59.3.3 Reed-Solomon Decoding ……………………………………60.3.4 Reed-Solomon Error Probability …………………………64.4 Concluding Remarks ……………………………………………65 Low-Density Parity-Check Coded Recording Systems With Run-Length-Limited Constraints 66.1 Introduction ……………………………………………………66.2 Selective Flipping Techniques………………………………69.2.1 Systems Using Side Information …………………………70.2.2 Systems Without Side Information ………………………74.3 Estimation of the Flipped Bits ……………………………78.3.1 Flipped Bits Estimation for Side-Information Free Techniques ……………………………………………………………78.3.2 Flipped Bits Estimation Along With Side Information81.4 Convergence Analysis Based on EXIT Charts …………… 83.4.1 Extrinsic Information Transfer Analysis………………85.4.2 Convergence Analysis for Algorithms NSIEST and SIEST 87.5 Flipped Bits Estimation for Strict RLL Constraints …92.5.1 Flipped Bits Estimation for Strict (0,6) RLL Constraints……………………………………………………………92.5.2 Flipped Bits Estimation for Strict (0,4) RLL Constraints……………………………………………………………94.5.3 Flipped Bits Estimation for Strict (0,3) RLL Constraints……………………………………………………………98.6 Concluding Remarks……………………………………………102 Some Capacity Approaching RLL Codes For Multilevel Recording Systems 103.1 Introduction …………………………………………………103.2 Achievable Rates of (M; 0; k) RLL Codes of Finite Lengths ………………………………………………………………107.2.1 Primitive Construction I…………………………………107.2.2 Primitive Construction II ………………………………110.3 Practical Code Constructions………………………………113.3.1 Practical Construction I ………………………………113.3.2 Practical Construction Iext ……………………………117.3.3 Practical Construction II ………………………………120.3.4 Practical Construction IIext …………………………126.4 System Performance Over the Precoded Partial Response Channel and Optical Recording Channel ………………………130.4.1 ECC-RLL System………………………………………………134.4.2 RLL-ECC System………………………………………………138.5 Concluding Remarks……………………………………………143 Conclusions 145ibliography 1481026808 bytesapplication/pdfen-US限制碼低密度同位檢查碼磁記錄通道多層次M-層次光記錄通道部分響應通道持續長度限制碼里德所羅門碼.constrained codeslow-density parity-check (LDPC) codesmagnetic recording channelmultilevelM-leveloptical recording channelpartial response channelrun-length-limited (RLL) codesReed-Solomon (RS) codes.thesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/188248/1/ntu-98-D91942008-1.pdf