New Automorphism Group Decoder for Erasure Channel and Constructions of LRCs and Generalized RP LDPC Codes

김찬기 서울대학교 대학원 2019 국내박사

In this dissertation, three main contributions are given as; i) new two-stage automorphism group decoders (AGD) for cyclic codes in the erasure channel, ii) new constructions of binary and ternary locally repairable codes (LRCs) using cyclic codes and existing LRCs, and iii) new constructions of high-rate generalized root protograph (GRP) low-density parity-check (LDPC) codes for a nonergodic block interference and partially regular (PR) LDPC codes for follower noise jamming (FNJ), are considered. First, I propose a new two-stage AGD (TS-AGD) for cyclic codes in the erasure channel. Recently, error correcting codes in the erasure channel have drawn great attention for various applications such as distributed storage systems and wireless sensor networks, but many of their decoding algorithms are not practical because they have higher decoding complexity and longer delay. Thus, the AGD for cyclic codes in the erasure channel was introduced, which has good erasure decoding performance with low decoding complexity. In this research, I propose new TS-AGDs for cyclic codes in the erasure channel by modifying the parity check matrix and introducing the preprocessing stage to the AGD scheme. The proposed TS-AGD is analyzed for the perfect codes, BCH codes, and maximum distance separable (MDS) codes. Through numerical analysis, it is shown that the proposed decoding algorithm has good erasure decoding performance with lower decoding complexity than the conventional AGD. For some cyclic codes, it is shown that the proposed TS-AGD achieves the perfect decoding in the erasure channel, that is, the same decoding performance as the maximum likelihood (ML) decoder. For MDS codes, TS-AGDs with the expanded parity check matrix and the submatrix inversion are also proposed and analyzed. Second, I propose new constructions of binary and ternary LRCs using cyclic codes and existing two LRCs for distributed storage system. For a primitive work, new constructions of binary and ternary LRCs using cyclic codes and their concatenation are proposed. Some of proposed binary LRCs with Hamming weights 4, 5, and 6 are optimal in terms of the upper bounds. In addition, the similar method of the binary case is applied to construct the ternary LRCs with good parameters. Also, new constructions of binary LRCs with large Hamming distance and disjoint repair groups are proposed. The proposed binary linear LRCs constructed by using existing binary LRCs are optimal or near-optimal in terms of the bound with disjoint repair group. Last, I propose new constructions of high-rate GRP LDPC codes for a nonergodic block interference and anti-jamming PR LDPC codes for follower jamming. The proposed high-rate GRP LDPC codes are based on nonergodic two-state binary symmetric channel with block interference and Nakagami-$m$ block fading. In these channel environments, GRP LDPC codes have good performance approaching to the theoretical limit in the channel with one block interference, where their performance is shown by the channel threshold or the channel outage probability. In the proposed design, I find base matrices using the protograph extrinsic information transfer (PEXIT) algorithm. Also, the proposed new constructions of anti-jamming partially regular LDPC codes is based on follower jamming on the frequency-hopped spread spectrum (FHSS). For a channel environment, I suppose follower jamming with random dwell time and Rayleigh block fading environment with M-ary frequnecy shift keying (MFSK) modulation. For a coding perspective, an anti-jamming LDPC codes against follower jamming are introduced. In order to optimize the jamming environment, the partially regular structure and corresponding density evolution schemes are used. A series of simulations show that the proposed codes outperforms the 802.16e standard in the presence of follower noise jamming. 이 논문에서는, i) 소실 채널에서 순환 부호의 새로운 이단 자기동형 군 복호기 , ii) 분산 저장 시스템을 위한 순환 부호 및 기존의 부분 접속 복구 부호(LRC)를 이용한 이진 혹은 삼진 부분 접속 복구 부호 설계법, 및 iii) 블록 간섭 환경을 위한 고부효율의 일반화된 근 프로토그래프(generalized root protograph, GRP) LDPC 부호 및 추적 재밍 환경을 위한 항재밍 부분 균일 (anti-jamming paritally regular, AJ-PR) LDPC 부호가 연구되었다. 첫번째로, 소실 채널에서 순환 부호의 새로운 이단 자기동형 군 복호기를 제안하였다. 최근 분산 저장 시스템 혹은 무선 센서 네트워크 등의 응용으로 인해 소실 채널에서의 오류 정정 부호 기법이 주목받고 있다. 그러나 많은 복호기 알고리즘은 높은 복호 복잡도 및 긴 지연으로 인해 실용적이지 못하다. 따라서 낮은 복호 복잡도 및 높은 성능을 보일 수 있는 순환 부호에서 이단 자기 동형 군 복호기가 제안되었다. 본 연구에서는 패리티 검사 행렬을 변형하고, 전처리 과정을 도입한 새로운 이단 자기동형 군 복호기를 제안한다. 제안한 복호기는 perfect 부호, BCH 부호 및 최대 거리 분리 (maximum distance separable, MDS) 부호에 대해서 분석되었다. 수치 분석을 통해, 제안된 복호 알고리즘은 기존의 자기 동형 군 복호기보다 낮은 복잡도를 보이며, 몇몇의 순환 부호 및 소실 채널에서 최대 우도 (maximal likelihood, ML)과 같은 수준의 성능임을 보인다. MDS 부호의 경우, 확장된 패리티검사 행렬 및 작은 크기의 행렬의 역연산을 활용하였을 경우의 성능을 분석한다. 두 번째로, 분산 저장 시스템을 위한 순환 부호 및 기존의 부분 접속 복구 부호 (LRC)를 이용한 이진 혹은 삼진 부분 접속 복구 부호 설계법을 제안하였다. 초기 연구로서, 순환 부호 및 연접을 활용한 이진 및 삼진 LRC 설계 기법이 연구되었다. 최소 해밍 거리가 4,5, 혹은 6인 제안된 이진 LRC 중 일부는 상한과 비교해 보았을 때 최적 설계임을 증명하였다. 또한, 비슷한 방법을 적용하여 좋은 파라미터의 삼진 LRC를 설계할 수 있었다. 그 외에 기존의 LRC를 활용하여 큰 해밍 거리의 새로운 LRC를 설계하는 방법을 제안하였다. 제안된 LRC는 분리된 복구 군 조건에서 최적이거나 최적에 가까운 값을 보였다. 마지막으로, GRP LDPC 부호는 Nakagami-$m$ 블록 페이딩 및 블록 간섭이 있는 두 상태의 이진 대칭 채널을 기반으로 한다. 이러한 채널 환경에서 GRP LDPC 부호는 하나의 블록 간섭이 발생했을 경우, 이론적 성능에 가까운 좋은 성능을 보여준다. 이러한 이론 값은 채널 문턱값이나 채널 outage 확률을 통해 검증할 수 있다. 제안된 설계에서는, 변형된 PEXIT 알고리즘을 활용하여 기초 행렬을 설계한다. 또한 AJ-PR LDPC 부호는 주파수 도약 환경에서 발생하는 추적 재밍이 있는 환경을 기반으로 한다. 채널 환경으로 MFSK 변복조 방식의 레일리 블록 페이딩 및 무작위한 지속 시간이 있는 재밍 환경을 가정한다. 이러한 재밍 환경으로 최적화하기 위해, 부분 균일 구조 및 해당되는 밀도 진화 (density evolution, DE) 기법이 활용된다. 여러 시뮬레이션 결과는 추적 재밍이 존재하는 환경에서 제안된 부호가 802.16e에 사용되었던 LDPC 부호보다 성능이 우수함을 보여준다.

A note on Quasi-Cyclic codes over Zpm

지미연 이화여자대학교 대학원 2003 국내박사

Modulo p^(m)상에서의 codes에 관해서는 P.Kanware and S.R.Lopez-Permouth의해 연구가 되어졌고, Z_(4)상에서의 cyclic codes에 대해서는 N.Aydin and D.K.Ray-Chaudhuri에 의해서 연구가 되어졌다. 이 논문에서는 N.Aydin and D.K.Ray-Chaudhuri의 Quasi-cyclic Z_(4)-codes를 Quasi-cyclic Z_(pr)-code로 일반화시켜 보았다. 좀 더 일반화된 경우에 대해서는, 예를 통해 살펴보았다. Codes over the integers modulo p^(m) were studied by P.Kanware and S.R.Lopez-Permouth. Cyclic code over Z_(4) was studied by Nuh Aydin and Dijen K.Ray-Chaudhuri.In this thesis, we generalize the results of N.Aydin and D.K.Ray-Chaudhuri for Quasi-cyclic Z_(4)-codes to Quasi-cyclic Z_(pr)-codes. For more gen-eral cases, we give some examples.

Efficiently encodable low-density codes and generalization of tanner's bounds

신민호 Graduate School, Yonsei University 2005 국내박사

Cyclic Codes over Finite Chain Rings

김성진 강원대학교 대학원 2008 국내박사

This thesis studies cyclic codes over finite chain rings. Let R be a finite chain ring and <θ> be its maximal ideal. K=Rl<θ> be its residue field of q elements and let p be the characteristic of K. The main purpose of this thesis is to study cyclic codes over R of length N=nq^(k) divisible by q. Let □ be the primitive (q^(m) - 1)th root of unity, S=R[□]$, $ = S[u]/<u^(q^(k))-1> and R=R[u]/<u^(q^(k))-1>. Then $\S$ is a Galois extension of R. We obtain isomorphisms Ψ: R^(n)→ R^(N) and γ: R^(N) → □_(i∈I)S_(i) where S_(i)= /<u^(q^(k))-1>, and S_(i) = R[□_([mi])◁수식 삽입▷(원문을 참조하세요) using the Frobenius automorphism and Discrete Fourier transform. From these isomorphisms we obtain the decomposition of an ideal C of R^(N) as ◁수식 삽입▷(원문을 참조하세요) where C_(i) is the ideal◁수식 삽입▷(원문을 참조하세요). We also prove that all ideals of R have representation as ◁수식 삽입▷(원문을 참조하세요) where either r_(i)=O, or r_(i)=(u-1)^(ti)+Θ◁수식 삽입▷(원문을 참조하세요). Finally dual codes are studied.S_(i)〔u]/<u^(q^(k))-1>, and S_(i) = R[□_([mi])◁수식 삽입▷(원문을 참조하세요) using the Frobenius automorphism and Discrete Fourier transform. From these isomorphisms we obtain the decomposition of an ideal C of R^(N) as ◁수식 삽입▷(원문을 참조하세요) where C_(i) is the ideal◁수식 삽입▷(원문을 참조하세요). We also prove that all ideals of R have representation as ◁수식 삽입▷(원문을 참조하세요) where either r_(i)=O, or r_(i)=(u-1)^(ti)+Θ◁수식 삽입▷(원문을 참조하세요). Finally dual codes are studied. 이 논문은 유한체인환 위에서의 순환부호에 대한 연구이다. R를 유한체인환 이라하고 <θ>를 이환에서의 최대 이데알이라고 하자. K=Rl<θ>>은 characteristic 이 p이고, 원소의 개수가 q인 체가 된다. 이 논문의 목적은 R 위에서 q에 의하여 나누어지는 길이가 ◁수식 삽입▷(원문을 참조하세요) 이 두 개의 isomorphism을 이용하면 R^(N)상에서의 이데알 Csms ◁수식 삽입▷(원문을 참조하세요) R^(N)상에서의 이데알 C는 ◁수식 삽입▷(원문을 참조하세요)와 동치임을 알 수 있다. ◁수식 삽입▷(원문을 참조하세요)여기서 Ci는 S_(i)◁수식 삽입▷(원문을 참조하세요). 이 두 개의 isomorphis을 이용하면 R^(N)상에서의 이데알 ◁수식 삽입▷(원문을 참조하세요)마지막으로 쌍호부호에 대하여 연구하고 마친다.

On cyclic codes

김선옥 西江大學校 大學院 1991 국내박사

On the generator polynomials of some cyclic codes

이수미 慶尙大學校 1997 국내석사

(The)Principle and applications of a cyclic wavelength shifter using a dual-band holographic grating

정승환 서울大學校 大學院 2006 국내박사

Optimization and WDM-PON application of optical time domain reflectometry based on simplex coding techniques

이정환 서울대학교 대학원 2008 국내박사

Cyclic hamming code의 error 訂正에 관한 硏究

박춘식 漢陽大學校 大學院 1982 국내석사

Multilevel 부호화를 적용한 Quasi-Cyclic LDPC 부호

마역단 전북대학교 대학원 2007 국내석사

이 논문에서 처음으로 Quasi-Cyclic(QC) LDPC 부호를 보인다. 이러한 QC부호는 순환 행렬의 블록으로 구성된 저밀도 패리티 검사 부호로 표현된다. 이 논문은 그런 부호의 설계 방법을 소개하고 거스 특성을 분석 및 성능에 대한 시뮬레이션 결과를 보인다. 그리고 멀티레벨 부호(Multi-Level Coding)가 소개된다. 멀티레벨 코딩의 목적은 각 신호 점의 레벨에서 파워와 대역폭 한계를 가진 개별 이진 코드에 의한 비트를 보호하기 위함이다. 다중 스테이지 복호(Multistage Decoding)와 병렬 독립 복호(Parallel Independent Decoding)가 또한 소개된다. 그 후에 기존의 모델과는 다른 QC-LDPC 부호를 사용한 새로운 MLC/PID 설계를 제안한다. 그리고 수학적 분석과 시뮬레이션 결과로써 새로운 모델에 대해 성능을 보인다. In this thesis, first the Quasi-Cyclic (QC) Low Density Parity Check (LDPC) codes are presented. The QC codes are described by sparse parity-check matrices comprised of blocks of circulant matrices. This work introduces the construction of such codes, analyzes the girth property and presents the simulation results of the performance. Then the multilevel coding (MLC) scheme is presented. The idea of MLC is to protect the bit at each level of the signal point by an individual binary code with the power and bandwidth constraints. The Multistage Decoding (MSD) and Parallel Independent Decoding (PID) are introduced as well. After that we propose a new MLC/PID scheme using QC LDPC codes different from conventional models. And the mathematical analysis and simulation results show the performance of this proposed new model.