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

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

줄여서 만든 부호에 대하여 : On Codes Obtained by the Shortening Method

박현정 경상대학교 대학원 2008 국내석사

1940년대 후반 Shannon의 논문에 의해 체계화된 코드 이론은 비교적 짧은 역사를 가졌지만 대수학뿐만 아니라 조합론, 확률론을 토대로 하여 발전하고 있으며, 최근에는 암호학 및 정보이론과 긴밀한 관련을 맺으면서 그 중요성이 점차 증대되고 있다. shortening은 기존의 부호에서 새로운 부호를 만들어내는 유용한 방법 중의 하나로서, 기존의 부호에서 동일한 좌표에 같은 기호가 있는 것들을 모아 집합을 만든 후 같은 기호가 있는 좌표를 제거하여 새로운 부호를 만드는 방법을 말한다. 번째 위치에 가 있는 것들을 모아 shortening 한 것을 라고 한다. 본 논문에서는 이진 선형부호에 대하여 shortening의 방법으로 얻어진 부호인 와 에 대하여 연구하였다. 제 2장에서는 본 논문에서 사용되는 정의와 잘 알려진 정리들을 소개하였다. 제 3장에서는 먼저 shortening한 부호 와 사이의 관계를 다루었다. 임의의 의 원소 에 대하여 이고, 임을 알 수 있었다. 이 결과로부터 차원이 2 이상인 부호를 shortening 했을 때, 과 는 같음을 알 수 있었다. 다음으로 살펴본 것은 제거하는 번째 자리에 따라 달라지는 부호들 간 및 간의 동치성 이었다. 순환부호 및 순환부호와 동치인 부호에서는 제거하는 좌표에 관계없이 및 들은 모두 동치임을 알았다. 마지막으로, 잘 알려진 부호들의 와 에 대해서 살펴보았다. constant weight code에서는 가중치 다항식을 구하였다. simplex code 에서는 와 을 찾고, 이들의 가중치 다항식을 얻었다. Hamming code 에서는 와 을 찾고, 이들의 가중치 다항식을 얻었다. 또한 Golay code에서는 제거하는 좌표에 관계없이 및 들은 모두 동치임을 증명하였다.

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)상에서의 이데알 ◁수식 삽입▷(원문을 참조하세요)마지막으로 쌍호부호에 대하여 연구하고 마친다.

Efficient design of LDPC code using circulant matrix and eIRA code

배슬기 Graduate School, Yonsei University 2005 국내석사

For reliable data transmission or storage system, channel coding is necessary. LDPC codes are defined as parity-check matrices thatconsist almost entirely of zeros and small number of ones. Liketurbo codes, LDPC codes can achieve near Shannon limit. But unlikevery simple encoder of turbo codes, that of LDPC code is muchcomplex.In this dissertation, we concentrate on reducing the complexityfor efficient encoder. We design structural LDPC code usingcirculant matrix and permutation matrix and eIRA code. It ispossible to design low complex encoder by using shift register anddifferential encoder and interleaver than general LDPC encoderthat use matrix multiplication and addition operation. The codedesigned by this structure shows better performance than randomcode. And the proposed method can considerably reduce a number ofXOR gates. And the proposed code shows a property such that thereis less degradation than randomly generated parity-check matrixwhen the codeword length becomes shorter. However this code showserror floor effect and performance degradation in high SNR region.We can improve its performance by design short cycle free codes. 신뢰성 있는 데이터 통신이나 저장장치를 위해서는 채널 코딩은 필수적이다. LDPC 부호는 패리티 검사 행렬이 대부분 0인 선형 블록부호로서 터보 부호처럼 Shannon의 채널 용량의 한계의 거의 근접하는성능을 보인다. 그러나 터보 부호의 간단한 부호화기와를 달리 LDPC부호화기는 매우 복잡하다.본 논문에서는 효율적인 부호화기의 설계를 위하여 패리티 행렬을 순환행렬과 행치환 행렬, 그리고 eIRA 부호를 이용하여 패리티 검사 행렬을구조적으로 설계하였다. 순환 행렬은 Shift Register, eIRA 부호는차등 부호화기, 치환 행렬은 인터리버로 각각 구현이 가능하므로 행렬곱을 사용하는 일반적인 LDPC 부호화기보다 복잡도가 작은 부호화기의설계가 가능하였다. 본 논문에서 제시하는 방법은 기존에 제시된부호화기 보다 계산량은 같지만 XOR 회로의 수를 훨씬 많이 줄였다.그리고 이 구조로 설계된 부호는 짧은 길이와 높은 부호율을 가질때랜덤하게 생성된 패리티 검사 행렬보다 좋은 성능을 보인다. 그러나순환 행렬을 사용함으로 랜덤성의 상실로 인해 높은 SNR에서는 오류마루 현상이 생겨 성능 열화가 생겼다. 이런 오류 마루 현상을해결하기 위해서는 짧은 주기가 없는 잘 설계된 행렬로 성능을향상시킬 수 있다.

Efficient design of structured LDPC codes

정비웅 Graduate School, Yonsei University 2006 국내석사

LDPC 부호는 선형 복호 복잡도를 가지고 확률적 반복 복호 기법으로 채널 용량 한계에 근접하는 성능을 보인다. LDPC 부호의 커다란 단점인 부호화 과정의 복잡도는 구조적 패리티 검사 행렬을 적용하여 해결할 수 있다. LDPC 부호의 패리티 검사 행렬이 같은 유형의 부행렬로 구성된다면 복호기 구현이 간단해 지고 구조적 복호를 할 수 있으며 효과적인 메모리 사용이 가능하다.본 논문에서는 모든 부행렬이 순환행렬이나 영행렬로 정의되는 구조에 대해 고려하였다. 이러한 행렬은 shift-value로 표현될 수 있고 부호화기 복잡도를 낮게 설계할 수 있다. 본 논문에서는 girth 조건과 PEG 알고리즘, 노드 연결성을 이용하여 짧은 길이의 균일, 비균일 LDPC 부호의 생성 알고리즘을 제안하였다. 이 방법으로 생성된 부호는 큰 girth를 가지고 구조적 제한이 없이 생성된 다른 부호와 비교하여 낮은 SNR에서는 비슷한 성능을, 높은 SNR에서는 더 우수한 성능을 보인다. 이 부호는 오류 마루 현상이 작게 나타나기 때문에 특히 비균일 부호의 설계에 유용하다. 다양한 종류의 부호를 만들었고 제안한 알고리즘이 블럭 타입 부호 생성에 효과적임을 보였다. Low-Density Parity-Check (LDPC) codes have linear decoding complexity and capacity achieving performance when decoded using an iterative probabilistic decoding algorithm. The high encoding complexity, which is one major drawback of LDPC codes, can be solved by applying a structured parity-check matrix. If the parity-check matrix of LDPC codes is composed of same type blocks, decoder implementation can be reduced and allowed structured decoding. Also this type provides efficient memory utilization.In this thesis, we only consider the structure that all sub-blocks are defined as circulant permutation matrices or the zero matrix. This matrix can be represented by shift values and can be designed so that the encoder has low complexity. We present a construction algorithm for short block length regular, irregular LDPC codes based on girth condition, Progressive Edge-Growth (PEG) algorithm and variable node connectivity. The code designed by this algorithm has large girth and shows similar performance in low signal to noise ratio(SNR) values and better performance in high SNR values than other codes without structured constraints. Since they have a low error floor, this method is specially effective for irregular design. We construct various codes and show that the proposed algorithm works well in designing block type LDPC codes

Constructions of girth-8 multi-edge QC-LDPC codes and its applications

김인선 Graduate School, Yonsei University 2022 국내박사

본 논문은 최소 사이클의 길이가 8을 만족하는 균일하거나 type-II인 QC-LDPC 부 호의 새로운 다양한 대수적 설계 방식을 제안하였다. 설계된 부호는 다양한 부호율과 길이, 특히 수십에서 수백을 길이로 갖는 부호를 설계하는 방법에 초점을 맞추고 있다. 제안하는 설계 방식은 두 가지 단계로 구성되어 있다. 첫 번째 단계로는, 곱셈 구구표 방식을 기반으로 다양한 길이와 부호율을 갖는 최 소 사이클의 길이가 8인 균일한 QC-LDPC 부호를 설계하는 방법을 제안한다. 특히, 제안하는 QC-LDPC 부호가 짧은 길이를 갖도록 설계하는 방법에 초점을 맞추고 있다. 이 설계는 두 가지 방식을 포함하고 있다. t 2 + 1 형태의 소수를 기반으로 하는 사각 행 렬을 이용하는 간단한 설계 방식과 두 개의 잘 고안된 수열 기반의 설계 방식을 새롭게 제안한다. t 2 + 1 형태의 소수를 기반으로 하는 사각 행렬을 이용하는 간단한 설계는 사각 행렬의 일부를 이용하여 균일한 QC-LDPC 부호를 만들어 내는 방식이다. 두 개 의 잘 고안된 수열은 길이가 4이거나 6인 사이클이 존재하지 않는 조건을 만족하도록 설계를 한다. 두 개의 잘 고안된 수열로 만들어진 기본 행렬은 최소 사이클의 길이가 8 인 QC-LDPC 부호를 발생시킨다. 또한 이러한 두 개의 잘 고안된 수열을 효과적으로 찾는 방법을 제안하고 이를 바탕으로 Golomb 자를 이용하는 설계 방식을 제안한다. 대략 길이 250을 갖는 새롭게 만든 QC-LDPC 부호는 5G NR LDPC 부호에 비해 0.4dB 가량의 추가적인 부호화 이득을 보인다. 두 번째 단계로는, 오류 성능이 좋도록 디자인된 무게 행렬을 이용하여 부호율 0.5 인 type-II QC-LDPC 부호를 설계하는 새로운 방법을 제안한다. 이 설계 방식은 균일 한 QC-LDPC 부호의 성능에 비해 더 좋은 오류 정정 성능을 보인다. QC-LDPC부호의 기본 행렬에서 길이가 4이거나 6인 사이클이 존재하는 다양한 패턴과 조건식을 도출 하였다. 길이가 대략 560 정도인 제안하는 type-II QC-LDPC 부호는 이전에 발표된 부호들에 비해 0.6dB 가량의 추가적인 부호화 이득을 보인다. 마지막 주제로, 제안하는 QC-LDPC 부호의 응용 방안을 고려한다. 저지연 통신을 위한 짧은 길이 데이터 패킷을 고려하는 전지구적 위성항법 시스템에 적용하기 위해 짧은 길이의 type-II QC-LDPC 부호를 설계한다. 제안하는 type-II QC-LDPC 부호와 현재 통신시스템의 표준으로 사용중인 다양한 부호들과 성능 비교를 하고 있다. In this dissertation, we propose some novel algebraic constructions of regular and type-II girth-8 QC-LDPC codes. These codes have various rates and various lengths especially targeted for few hundreds. The proposed constructions combines two steps. First, we propose the some constructions of regular girth-8 QC-LDPC codes of various lengths and rates using multiplication table methods. This includes two methods; Simple constructions based on the square matrices from the primes of the form t2 + 1 and two designed sequences method. Simple constructions of girth-8 QC-LDPC codes based on the square matrix are generalized version of the construction using the multiplication table method in a way that the size of circular permutation matrix can be different from the modulus in the calculation of the exponent matrix. Two designed sequences are made to satisfy the conditions for non-existence of 4- and 6-cycles. The exponent matrix using two designed sequences results the QC-LDPC codes with girth 8.We also propose efficient search for two designed sequences and employ the proposed construction using Golomb ruler. We perform some simulations that the regular QC-LDPC code of length about 250 has an additional coding gain of about 0.4 dB over the 5G NR LDPC codes. The second is to propose new construction of half-rate type-II QC-LDPC codes employing a well-designed weight matrix. From this construction, we improve performance of those from the construction of regular QC-LDPC codes. Various patterns of 4- and 6-cycles and their corresponding conditions are derived for type-II QC-LDPC codes. We performed some simulation that the proposed type-II QC-LDPC code of length about 560 has an additional coding gain about 0.6 dB over the code proposed earlier. For the application of the proposed QC-LDPC codes, we construct some type-II QC-LDPC codes for short lengths in order to adapt for the low-latency communication of short data packets such as future global navigation satellite system. We simulate and compare the performance of the proposed QC-LDPC codes and existing standard error correcting codes.

랜덤 및 버스트 에러 동시 정정을 위한 순환적 부호에 관한 연구

원종호 建國大學校 大學院 1990 국내석사

Cyclic product have following advantages. 1)The code effect a compromise between random and burst error correcting codes and therefore, appear to be well-suited to error-corr ection on channels in which both types of errors occur. 2)As efficient error correction requires the use of long block length codes, the complexity of system is increasing to expontial rate however because product codes are consist of two or more subcodes, the complexity of system is less complex than other coder. In this paper, (105.44)cyclic product code is designed and implemented by two subcodes. The subcodes are (7.4), (15.11) cyclic codes, which is efficient random error correction and burst error correction. This code has efficiency K/N, random error correcting ability is 3 and burst error correcting ability is 8.

Analysis of quasi-cyclic low-density parity-check codes and protograph codes

김성환 서울大學校 大學院 2005 국내박사

The invariants of cyclotomic fields as quadratic spaces

정은경 서울대학교 대학원 1990 국내박사

The Cycle Concentrating Progressive Edge Growth Algorithm and Neural Window Decoder for LDPC Codes

윤대영 서울대학교 대학원 2024 국내박사

이 학위 논문은 프로토그래프 기반 GLDPC 부호를 위한 CC-PEG 알고리즘과 SC-LDPC 부호를 위한 신경망 윈도우 복호기에 대해 다룬다. 첫 번째로, 프로토그래프 GLDPC 부호를 위한 새로운 리프팅 방법인 CC-PEG 알고리즘이 제안되었다. GLDPC 부호에서 GC 노드에 연결되지 않은 도핑되지 않은 변수 노드는 GC 노드의 보호를 받는 도핑된 변수 노드보다 채널 오류에 더 취약하다. 본 논문에서는 동일한 프로토그래프 구조를 갖는 GLDPC 부호들 중, 도핑되지 않은 변수 노드 쪽에 지역 싸이클이 적은 부호들이 더 좋은 디코딩 성능을 갖는다는 것을 확인하였다. 이러한 관찰을 바탕으로, 리프팅 과정에서 취약한 도핑되지 않은 변수 노드 쪽에 지역 싸이클을 피하고 도핑된 변수 노드 쪽에 지역 사이클을 집중시키는 CC-PEG 알고리즘이 제안되었다. 구체적으로, CC-PEG 알고리즘은 먼저 undoped girth (도핑되지 않은 변수 노드를 포함하는 가장 짧은 싸이클의 길이)가 최대가 되는 엣지를 수집한다. 그 다음으로, 가장 낮은 concentrated CM을 갖는 엣지 중 하나를 골라 연결한다. 결과적으로, CC-PEG 알고리즘으로 리프팅된 부호는 견고한 도핑된 변수 노드 쪽에 싸이클이 집중된 비대칭 싸이클 분포를 보인다. 다양한 프로토그래프에서 실험한 결과, CC-PEG 알고리즘으로 리프팅한 GLDPC 부호는 기존 리프팅 알고리즘을 사용한 부호에 비해 최대 20배 낮은 프레임 오류율을 달성하였다. 두 번째로, SC-LDPC 부호를 위한 신경망 윈도우 복호기가 제안되었다. 모든 변수 노드를 복호하는 것을 목표로 하는 기존의 신경망 블록 복호기와 달리, 신경망 윈도우 복호기는 단일 프로토그래프 위치의 변수 노드를 복호하는 것을 목표로 한다. 따라서 신경망 윈도우 복호기는 신경망 블록 복호기보다 출력 노드가 적어 분류해야 하는 레이블의 수를 크게 줄인다. 본 논문은 신경망 윈도우 복호기를 위한 최적의 신경망 신뢰 전파 알고리즘과 손실 함수를 탐색하고, 성능 손실 없이 학습 및 복호 복잡도를 최소화 하기 위해 웨이트 공유 기법을 사용한다. 결과적으로, 신경망 윈도우 복호기는 신경망 블록 복호기에 비해 빠른 훈련 수렴 속도와 향상된 프레임 오류율 성능을 보인다. 추가적으로, 신경망 윈도우 복호기의 학습 결과를 바탕으로 SC-LDPC 부호를 위한 비균일 복호 스케줄을 제안한다. 윈도우 SC-LDPC의 독특한 구조는 훈련된 신경망 윈도우 복호기에 특정한 패턴을 만들어낸다. 학습의 결과로 특정 웨이트는 크게 감소하며, 이에 해당하는 신경망 연결을 끊어도 복호기의 성능에 영향을 크게 미치지 않는 다는것이 확인되었다. 따라서 신경망 윈도우 복호기의 학습 결과를 바탕으로 SC-LDPC 부호에 비균일 스케줄링을 적용함으로써, 총 체크 노드 연산의 40%만으로 균일 범람 복호 스케줄과 동일한 성능을 달성할 수 있음을 보였다. In this dissertation, two main topics are addressed as follows: i) the cycle-concentrating progressive edge growth (CC-PEG) algorithm for protograph generalized low-density parity-check (GLDPC) codes and ii) neural window decoder (NWD) for spatially coupled low-density parity-check (SC-LDPC) codes. First, a new lifting method for protograph GLDPC codes, called CC-PEG, is pro- posed. In GLDPC codes, undoped variable nodes (VNs) that are not connected to generalized constraint (GC) nodes are more vulnerable to channel errors than doped VNs protected by GC nodes. I observe that among GLDPC codes sharing the same protograph structure, codes with fewer local cycles at undoped VNs have better decoding performances. Inspired by this observation, the CC-PEG algorithm is proposed to concentrate local cycles at doped VNs and avoid local cycles at vulnerable undoped VNs during the lifting process. Specifically, the CC-PEG algorithm first collects edges that result in the maximum undoped girth, defined as the length of the shortest cycle containing undoped VNs. Following this, the CC-PEG algorithm selects the edge with the lowest concentrated cycle metric. Consequently, the lifted codes exhibit asymmetric cycle distributions where cycles concentrated around robust doped VNs. Simulation results for various protographs show that the CC-PEG algorithm achieves a performance gain of up to 20 times lower frame error rate compared to conventional lifting algorithms. Second, I introduce an NWD for SC-LDPC codes. In contrast to conventional neural block decoders (NBDs), which aim to decode all VNs, the NWD typically targets a single protograph position of VNs for decoding. Therefore, the NWD has fewer output nodes than the NBD, which drastically reduces the number of labels to be classified. I examine the optimal neural belief propagation (BP) algorithm and loss function for the NWD, and weight sharing techniques to minimize training complexity and memory usage without sacrificing performance. As a result, the NWD exhibited 0.25 dB frame error rate (FER) gain compared to the NBD with lower training and decoding complexity. Additionally, I propose a non-uniform decoding schedule for SC-LDPC codes based on the training results of the NWD. Owing to the unique structure of windowed SC-LDPC, the trained weight of NWD exhibits specific patterns. During the training process, certain weights decrease significantly, and I discover that disconnecting the corresponding neural connections have a negligible impact on the NWD’s decoding performance. By applying non-uniform scheduling to the SC-LDPC code based on the NWD’s training outcomes, the same performance as the uniform flooding schedule is achieved with only 40% of the check node (CN) operations.