[go: up one dir, main page]

KR20040033554A - 에러 정정 부호화 장치 및 그 방법 - Google Patents

에러 정정 부호화 장치 및 그 방법 Download PDF

Info

Publication number
KR20040033554A
KR20040033554A KR1020020062692A KR20020062692A KR20040033554A KR 20040033554 A KR20040033554 A KR 20040033554A KR 1020020062692 A KR1020020062692 A KR 1020020062692A KR 20020062692 A KR20020062692 A KR 20020062692A KR 20040033554 A KR20040033554 A KR 20040033554A
Authority
KR
South Korea
Prior art keywords
cycle
component
parity check
check matrix
forming group
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Withdrawn
Application number
KR1020020062692A
Other languages
English (en)
Inventor
김기현
박인식
심재성
한성휴
Original Assignee
삼성전자주식회사
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 삼성전자주식회사 filed Critical 삼성전자주식회사
Priority to KR1020020062692A priority Critical patent/KR20040033554A/ko
Priority to US10/680,419 priority patent/US7188281B2/en
Priority to JP2003352528A priority patent/JP3772168B2/ja
Priority to DE60317446T priority patent/DE60317446D1/de
Priority to EP03256432A priority patent/EP1422829B1/en
Priority to TW092128256A priority patent/TWI227394B/zh
Priority to CNB2003101209393A priority patent/CN1307804C/zh
Publication of KR20040033554A publication Critical patent/KR20040033554A/ko
Withdrawn legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1004—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's to protect a block of data words, e.g. CRC or checksum
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • General Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Quality & Reliability (AREA)
  • General Physics & Mathematics (AREA)
  • Error Detection And Correction (AREA)
  • Detection And Correction Of Errors (AREA)

Abstract

본 발명은 에러 정정 부호화 장치 및 그 방법에 관한 것으로, 그 장치는 각 행에 성분값 1을 가지는 소정개수의 성분을 포함하고 각 열에 성분값 1을 가지는 소정개수의 성분을 포함하고 그 외 성분들은 성분값 0을 가지는 패리티 검사 행렬C을 생성하는 패리티검사행렬 생성부; 상기 패리티검사행렬 생성부로부터 상기 패리티 검사 행렬C을 입력받아, 상기 패리티 검사 행렬C의 성분 중에 사각형의 각 꼭지점의 위치에 있고 각 성분값이 1을 만족하는 4개의 성분으로 구성된 사이클형성 그룹을 탐색하여, 상기 사이클형성 그룹이 적어도 하나 이상 존재하면 상기 사이클형성 그룹의 적어도 하나의 성분의 성분값 1과 다른 성분의 성분값 0을 교환하여 사이클형성 그룹이 제거된 패리티 검사 행렬H을 출력하는 패리티검사행렬 조정부; 및 상기 패리티검사행렬 조정부로부터 상기 사이클형성 그룹이 제거된 패리티 검사 행렬H을 입력받고 m개의 비트로 이루어진 메시지 워드를 입력받아 LDPC 코딩을 수행하는 LDPC 코딩부;를 포함한다. 이러한 에러 정정 부호화 장치를 이용함으로써 패리티 검사 행렬에 존재하는 사이클 형성 그룹을 제거하여 LDPC 복호화 성능을 향상시킨다.

Description

에러 정정 부호화 장치 및 그 방법{Apparatus and method for error correction coding}
본 발명은 에러 정정 부호화 장치 및 그 방법에 관한 것으로서, 특히 Low Density Parity Code(이하, LDPC라 한다) 부호화에 있어서 패리티 검사 행렬의 성분을 조정하여 부호화 성능을 향상시키는 에러 정정 부호화 장치 및 방법에 관한것이다.
무선통신분야 또는 광 기록재생 분야 등에서 사용되는 에러 정정 부호화 기술의 한 가지로서 LDPC 부호화 방법이 있다. LDPC 부호화는 성분값 1을 가지는 성분이 각 행(row)과 각 열(column)에 일정 개수씩 포함되고 그 외 성분들은 성분값 0을 가지는 패리티 검사 행렬을 이용하여 패리티 정보(부가 정보)를 생성한다. LDPC 부호화에 대한 보다 상세한 설명은 "Good error correction codes based on very sparse matrices"(D.J.MacKay, IEEE Trans. on Information Theory, vol. 45, no.2, pp.399-431, 1999)에 기술되어 있다.
패리티 검사 행렬의 구성 성분중 동일한 행에 위치한 두 개의 성분의 성분값이 1이고, 그 두 개의 성분이 위치하는 각 열에 존재하는 성분값 1인 성분들 중에 동일한 행에 위치하는 두 개의 성분이 존재하는 경우를 사이클-4(Cycle-4)인 상황이라고 한다. 도 2a 및 도 3a에 사이클-4인 상황이 두 개 발생한 패리티 검사 행렬의 예가 도시되어 있다. 각각의 도면에서 성분값에 O 표시와 □표시가 된 각 네 개의 성분들이 하나의 사이클-4인 상황을 발생시킨다. 즉, 사이클-4인 상황은 성분값이 1인 네 개의 성분이 직사각형의 네 꼭지점을 형성하는 경우라고 말할 수 있다.
사이클이 존재하는 패리티 검사 행렬을 이용하여 패리티 정보를 생성하면 복호시에 복호에 실패하거나 복호 성능이 저하되는 문제점이 있다.
또한 패리티 검사 행렬은 선형 독립적(linearly independent)이어야 하고 전술한 바와 같이 각 행(row)과 각 열(column)에 성분값 1을 가지는 성분이 일정 개수씩 포함되고 그 외 성분들은 성분값 0을 가져야 하는 두 가지 성질을 만족해야한다. 새로운 패리티 검사 행렬을 생성하거나 패리티 검사 행렬의 구성 성분의 위치를 이동시킴으로써 전술한 두 가지 성질을 만족함과 동시에 사이클을 제거한다는 것은 어려운 문제점이 있다.
따라서, 본 발명이 이루고자 하는 기술적 과제는 생성된 패리티 검사 행렬의 구성성분들중에 사이클을 발생시키는 구성성분들의 위치를 이동시킴으로써 패리티 검사 행렬에 요구되는 성질을 만족함과 동시에 사이클이 제거된 패리티 검사 행렬을 생성하여 LDPC 복호화 성능을 향상시키는 LDPC 부호화 장치 및 방법을 제공하는데 있다.
도 1은 본 발명에 따른 에러정정 부호화 장치의 일 실시예를 설명하기 위한 블록도,
도 2a 내지 도 2d는 도 1에 도시된 패리티 검사 행렬 조정부에 의해 성분값이 조정된 패리티 검사 행렬의 일 실시예를 나타내는 도면,
도 3a 내지 도 3d는 사이클 형성 그룹의 구성성분의 성분값을 이동시킬 수 없는 경우를 나타내는 도면,
도 4는 도 1에 도시된 본 발명에 따른 에러 정정 부호화 장치에서 실시되는 에러 정정 부호화 방법을 설명하기 위한 흐름도,
도 5는 도 4에 도시된 제230 단계의 상세 구성을 나타내는 흐름도이다.
상기 과제를 이루기 위해, 본 발명에 의한 에러 정정 부호화 장치는,
각 행에 성분값 1을 가지는 소정개수의 성분을 포함하고 각 열에 성분값 1을 가지는 소정개수의 성분을 포함하고 그 외 성분들은 성분값 0을 가지는 패리티 검사 행렬C을 생성하는 패리티검사행렬 생성부; 상기 패리티검사행렬 생성부로부터 상기 패리티 검사 행렬C을 입력받아, 상기 패리티 검사 행렬C의 성분 중에 사각형의 각 꼭지점의 위치에 있고 각 성분값이 1을 만족하는 4개의 성분으로 구성된 사이클형성 그룹을 탐색하여, 상기 사이클형성 그룹이 적어도 하나 이상 존재하면 상기 사이클형성 그룹의 적어도 하나의 성분의 성분값 1과 다른 성분의 성분값 0을 교환하여 사이클형성 그룹이 제거된 패리티 검사 행렬H을 출력하는 패리티검사행렬 조정부; 및 상기 패리티검사행렬 조정부로부터 상기 사이클형성 그룹이 제거된패리티 검사 행렬H을 입력받고 m개의 비트로 이루어진 메시지 워드를 입력받아 LDPC 코딩을 수행하는 LDPC 코딩부;를 포함하는 것이 바람직하다.
상기 과제를 이루기 위해, 본 발명에 의한 에러 정정 부호화 방법은,
(a) 각 행에 성분값 1을 가지는 소정개수의 성분을 포함하고 각 열에 성분값 1을 가지는 소정개수의 성분을 포함하고 그 외 성분들은 성분값 0을 가지는 패리티 검사 행렬C을 생성하는 패리티 검사 행렬 생성 단계; (b) 상기 패리티 검사 행렬C의 성분 중에 사각형의 각 꼭지점의 위치에 있고 각 성분값이 1을 만족하는 4개의 성분으로 구성된 사이클형성그룹을 탐색하여, 상기 사이클형성그룹이 적어도 하나 이상 존재하면 상기 사이클형성그룹의 적어도 하나의 성분의 성분값 1과 다른 성분의 성분값 0을 교환하여 사이클형성그룹이 제거된 패리티 검사 행렬H을 생성하는 패리티 검사 행렬 조정 단계; 및 (c) 상기 패리티 검사 행렬H을 입력받고 m개의 비트로 이루어진 메시지 워드를 입력받아 LDPC 코딩을 수행하는 LDPC 코딩 단계;를 포함하는 것이 바람직하다.
이하, 첨부된 도면들을 참조하여 본 발명에 따른 바람직한 실시예를 상세히 설명한다.
도 1 내지 도 3d를 참조하여 본 발명에 따른 에러정정 부호화 장치의 일 실시예를 설명한다.
도 1은 본 발명에 따른 에러정정 부호화 장치의 블록도이다. 도 1을 참조하면, 에러 정정 부호화 장치는 패리티 검사 행렬 생성부(110), 패리티 검사 행렬 조정부(130) 및 LDPC 코딩부(150)를 포함한다. 패리티 검사 행렬 조정부(130)는 행렬성분검사부(131) 및 행렬성분교환부(133)를 포함한다.
패리티 검사 행렬 생성부(110)는 각 행에 성분값 1을 가지는 소정개수의 성분과 각 열에 성분값 1을 가지는 소정개수의 성분을 포함하고 그 외 성분들은 성분값 0을 가지는 패리티 검사 행렬C을 생성한다. 패리티 검사 행렬C는 p×c 크기를 가진다. p는 패리티 정보의 비트 수에 해당하는 값이고, c는 코드 워드의 비트 수에 해당하는 값으로서 p에 메시지 워드의 비트 수에 해당하는 값 m을 더한 값이다.
패리티 검사 행렬C는 전술한 바와 같이 두 가지 성질을 만족해야 한다. 즉, 컬럼 웨이트(colummn weight)와 로우 웨이트(row weight)는 각 행과 각 열에서 항상 일정해야 한다. 컬럼 웨이트는 각 열에 포함된 성분값이 1인 성분의 개수를 말하고, 로우 웨이트는 각 행에 포함된 성분값이 1인 성분의 개수를 말한다.
그리고 패리티 검사 행렬C는 선형 독립적(linearly independent)이어야 한다. 선형 독립성을 만족하지 않으면 복호시에 패리티 검사 행렬C를 사용하여 행렬 연산을 수행할 수 없기 때문이다.
예를 들면, 패리티 검사 행렬C는 p가 100이고 m이 900이 되어 c가 1000인 경우, 각 열에 3개의 성분값 1을 포함하고 각 행에 30개의 성분값 1을 포함하고 그 외 성분들은 성분값 0을 가지도록 하여 생성할 수 있다. 이러한 경우, 패리티 검사 행렬C는 컬럼 웨이트가 3이고 로우 웨이트는 30이다. 컬럼 웨이트와 로우 웨이트간의 비율은 상기 예에서는 1:10이다. 그러나 이에 한정될 필요는 없다.
패리티 검사 행렬 조정부(130)는 패리티 검사 행렬 생성부(110)로부터 패리티 검사 행렬C을 입력받아 패리티 검사 행렬C의 성분 중에 (w,x), (w,y), (z,x)및 (z,y)인 위치에 있고 각 성분값이 1인 4개의 성분으로 구성된 사이클형성그룹을 탐색한다. 탐색 결과, 사이클형성그룹이 적어도 하나 이상 존재하면 사이클형성그룹의 적어도 하나의 성분의 성분값 1과 다른 성분의 성분값 0을 교환하여 사이클형성그룹이 제거된 패리티 검사 행렬H을 출력한다.
본 실시예에서 사이클형성 그룹이란 패리티 검사 행렬C의 성분들 중에서 성분값이 1인 네 개의 성분이 직사각형의 네 꼭지점을 형성하는 경우, 그 구성성분들의 집합을 말한다.
도 2a 내지 도 2d는 패리티 검사 행렬 조정부(130)에 의해 성분값이 조정된 패리티 검사 행렬C의 일 실시예를 나타내는 도면이다.
행렬성분 검사부(131)는 패리티 검사 행렬C에 존재하는 다수의 사이클 형성 그룹을 탐색하여 행렬성분 교환부(133)로 두 개의 사이클 형성 그룹 각각을 구성하는 성분들의 위치 정보를 출력한다.
도 2a를 참조하면 성분값에 O 표시와 □표시가 된 각 네 개의 성분들이 하나의 사이클-4인 상황을 발생함을 알 수 있다. □표시가 된 4개의 성분들을 제1 사이클형성그룹이라고 정의하고 O 표시가 된 4개의 다른 성분들을 제2 사이클형성그룹이라 정의한다.
행렬성분 검사부(131)는 제1 사이클형성 그룹을 구성하는 각 성분들의 위치정보인 (w1,x1), (w1,y1), (z1,x1) 및 (z1,y1)와 제2 사이클형성 그룹을 구성하는 각 성분들의 위치 정보인 (w2,x2), (w2,y2), (z2,x2) 및 (z2,y2)을 행렬성분 교환부(133)로 출력한다.
행렬성분 교환부(133)는 두 개의 사이클 형성 그룹의 각 구성 성분들의 위치정보를 입력받아 적어도 하나의 성분값을 이동시킴으로써 사이클형성그룹을 제거한다.
도 2b는 행렬성분 교환부(133)에서의 동작을 이해하기 쉽게 설명하기 위해 도 2a에 도시된 패리티 검사 행렬C에서 제1 사이클형성 그룹, 제2 사이클형성 그룹 및 주변 성분값을 포함하고 그 외 성분들은 생략된 단순화된 패리티 검사 행렬을 나타낸다.
행렬성분 교환부(133)는 도 2b에 나타난 바와 같은 두 개의 사이클형성 그룹에 대해 제1 사이클 형성 그룹의 하나의 구성성분의 성분값 1을 동일한 열(column)상에서 제2 사이클형성 그룹의 구성성분들이 존재하는 행으로 이동시킨다. 제1 사이클형성 그룹의 구성 성분이 이동된 행에 존재하는 두 개의 제2 사이클형성 그룹의 구성 성분 중 하나를 동일한 열 상에서 제1 사이클형성 그룹 중 이동된 구성성분이 원래 존재하던 행으로 이동시킨다.
도 2c 및 도 2d에 단순화된 패리티 검사 행렬에서 사이클형성 그룹의 구성성분들을 이동시키는 일 예들이 도시되어 있다.
도 2c는 (3,1)의 위치에 있던 제1 사이클형성 그룹의 성분값 1이 (1,1)의 위치로 이동하고, 제1 사이클형성 그룹의 성분이 이동한 제1 행에 존재하는 두 개의 제2 사이클형성 그룹의 성분 중 (1,3)의 위치에 있던 성분값 1이 열의 값 3은 유지하면서 제1 사이클형성 그룹이 존재하던 제3 행으로 이동하여 (3,3)의 위치로 이동한 경우를 나타낸다.
도 2d는 (3,1)의 위치에 있던 제1 사이클형성 그룹의 성분값 1이 (2,1)의 위치로 이동되고, 제1 사이클형성 그룹의 성분이 이동된 제2 행에 존재하는 두 개의 제2 사이클형성 그룹의 성분중 (2,3)의 위치에 있던 성분값 1이 (3,3)의 위치로 이동된 경우를 나타낸다.
도 2c 및 도 2d에 도시된 바와 같은 방식으로 각 사이클 형성 그룹의 구성성분의 성분값 1을 이동시킴으로써 두 개의 사이클 형성 그룹이 제거되고 패리티 검사 행렬에 관한 전술한 두 가지 규칙도 여전히 만족하는 새로운 패리티 검사 행렬H가 결정된다.
본 실시예에서는 각 사이클 형성 그룹의 구성성분의 성분값 1을 열의 값은 유지하고 행의 값만 변화시켜 수직방향으로 이동하였으나 반대로 행의 값은 유지하고 열의 값만 변화시켜 수평방향으로 이동시켜도 동일한 효과를 달성할 수 있다.
그러나 성분값을 이동시키는 경우에 문제가 생기는 경우가 있다.
도 3a 내지 도 3d는 사이클형성 그룹의 구성성분의 성분값을 이동시킬 수 없는 경우를 설명하기 위한 도면이다.
도 3a에는 성분값에 O 표시와 □표시가 된 각 네 개의 성분들이 하나의 사이클-4인 상황을 발생시키는 패리티 검사 행렬C가 도시되어 있다. 한표시가 된 4개의 성분들을 제1 사이클형성그룹이라고 하고 O 표시가 된 4개의 다른 성분들을 제2 사이클형성그룹이라 한다. 제1 사이클형성 그룹 및 제2 사이클형성 그룹의 구성성분이 아닌 성분으로서 성분값이 1인 성분에는 △ 표시가 되어 있다.
도 3b는 설명의 편의를 위해 도 3a에 도시된 패리티 검사 행렬C에서 제1 사이클형성그룹, 제2 사이클형성그룹 및 주변 성분값을 포함하고 그 외 성분들은 제외된 단순화된 패리티 검사 행렬을 나타낸다.
전술한 바와 같이 행렬성분 교환부(133)는 도 3b에 도시된 두 개의 사이클형성 그룹에 대해 제1 사이클 형성 그룹의 하나의 구성성분의 성분값 1을 동일한 열(column)상에서 행(row)의 값을 변경하되 제2 사이클형성 그룹의 구성성분들이 존재하는 행으로 이동시킨다. 제1 사이클형성 그룹의 구성성분이 이동된 행에 존재하는 두 개의 제2 사이클형성그룹의 구성 성분 중 하나를 그 열의 값은 유지한 채로 이동된 제1 사이클형성 그룹의 구성성분이 원래 존재하던 행으로 이동시킨다.
도 3b를 참고하면, (3,1)의 위치에 있던 제1 사이클형성 그룹의 성분값 1을 (1,1)의 위치로 이동시킬 수 없다. 이미 성분값 1이 존재하기 때문이다. 행렬성분 교환부(133)는 사이클 형성 그룹의 구성성분을 이동시키고자 하는 위치에 이미 성분값이 1인 다른 성분이 존재하는 경우에는 성분값 1이 존재하지 않는 다른 위치로 이동시킨다. 행렬성분 교환부(133)는 특정 사이클형성그룹의 구성성분이 이동할 수 있는 성분값 1이 존재하지 않는 위치가 없다면 다른 구성성분을 이동시킨다.
도 3c는 (3,1)의 위치에 있던 제1 사이클형성그룹의 성분값 1이 (2,1)의 위치로 이동되고, 제1 사이클형성그룹의 성분이 이동된 제2행에 존재하는 두 개의 제2사이클형성그룹의 성분중 (2,3)의 위치에 있던 성분값 1이 (3,3)의 위치로 이동된 경우를 나타낸다. 이러한 경우, 점선으로 표시된 바와 같이 (1,1),(1,4),(2,1) 및 (2,4)의 위치에 성분값 1을 가지는 네 개의 구성성분이 존재하게 되어 새로운 사이클형성 그룹이 발생된다. 사이클형성 그룹의 구성 성분을 이동함으로써 새로운사이클형성그룹이 발생하게 되면 그 구성 성분을 그 위치로 이동시킬 수 없다. 따라서 (3,1)의 위치에 있는 제1 사이클형성 그룹의 구성성분은 수직방향으로 이동할 수 없다.
도 3d는 (3,2)의 위치에 있던 제1 사이클형성 그룹의 성분값 1이 (2,2)의 위치로 이동되고, 제1 사이클형성 그룹의 성분이 이동된 제2행에 존재하는 두 개의 제2 사이클형성 그룹의 성분중 (2,5)의 위치에 있던 성분값 1이 (3,5)의 위치로 이동된 경우를 나타낸다. 이 경우에도 점선으로 표시된 바와 같이 (1,1),(1,5),(3,1) 및 (3,5)의 위치에 성분값 1을 가지는 네 개의 구성성분이 존재하게 되어 새로운 사이클형성 그룹이 발생된다. 따라서 (3,2)의 위치에 있는 제1 사이클형성 그룹의 구성성분을 (2,2)의 위치로 이동시킬 수 없다.
도 3b에 도시된 사이클이 발생한 패리티 검사 행렬은 사이클형성 그룹의 어떤 구성성분을 이동시키더라도 항상 새로운 사이클이 발생하거나 이동시키고자 하는 위치에 이미 성분값 1이 존재한다. 이러한 경우에는 행렬성분 교환부(133)는 행렬성분 검사부(131)에 새로운 한 쌍의 사이클 형성 그룹의 위치정보를 요청한다. 입력된 새로운 한 쌍의 사이클형성 그룹에 대해 전술한 바와 같은 동작을 수행하여 두 개의 사이클형성 그룹을 제거한다.
행렬성분 교환부(133)는 모든 사이클 형성 그룹이 제거될 때까지 상기 동작을 반복수행한다.
만약 사이클형성 그룹이 제거되지 않는 경우 또는 하나의 사이클 형성 그룹이 남는 경우에는 행렬성분 교환부(133)는 패리티검사행렬 생성부(110)로 새로운패리티 검사 행렬을 생성할 것을 요청하는 신호를 전송한다.
LDPC 코딩부(150)는 패리티검사행렬 교환부(133)로부터 사이클형성 그룹이 제거된 패리티 검사 행렬H을 입력받고, m개의 비트로 이루어진 메시지 워드 ki(i=1,2...m)를 입력받아 LDPC 코딩을 수행한다.
LDPC 코딩부(150)는 다음의 수학식을 만족하는 행렬X를 결정한다.
행렬X의 구성성분중 k1,k2,...,km는 m비트로 이루어진 메시지 워드이고 x1,x2,...,xp는 p 비트로 이루어진 패리티 정보이다. 행렬H와 행렬X의 구성성분중 ki(i=1,2...m)는 값을 알고 있기 있으므로 상기 수학식에서 패리티 정보xi(i=1,2...p)를 정할 수 있다.
LDPC 코딩부(150)는 메시지 워드에 패리티 정보가 부가된 코드 워드를 출력하여 LDPC 코딩을 수행한다.
이하에서는 도 1, 도 4 및 도 5를 참조하여 본 발명에 따른 에러 정정 부호화 방법의 일 실시예를 설명한다.
도 4는 도 1에 도시된 본 발명에 따른 에러 정정 부호화 장치에서 실시되는 에러 정정 부호화 방법을 설명하기 위한 흐름도이다.
패리티 검사 행렬 생성부(110)는 각 행에 성분값 1을 가지는 소정개수의 성분과 각 열에 성분값 1을 가지는 소정개수의 성분을 포함하고 그 외 성분들은 성분값 0을 가지는 패리티 검사 행렬C을 생성한다(제210 단계).
패리티 검사 행렬 조정부(130)는 패리티 검사 행렬 생성부(110)로부터 패리티 검사 행렬C을 입력받아 패리티 검사 행렬C의 성분 중에 (w,x), (w,y), (z,x) 및 (z,y)인 위치에 있고 각 성분값이 1인 4개의 성분으로 구성된 사이클형성그룹을 탐색한다. 탐색 결과, 사이클형성그룹이 적어도 하나 이상 존재하면 사이클형성그룹의 적어도 하나의 성분의 성분값 1과 다른 성분의 성분값 0을 교환하여 사이클형성그룹이 제거된 패리티 검사 행렬H을 출력한다(제230 단계).
LDPC 코딩부(150)는 패리티 검사 행렬 교환부(133)로부터 사이클형성그룹이 제거된 패리티 검사 행렬H을 입력받고, m개의 비트로 이루어진 메시지 워드 ki(i=1,2...m)를 입력받아 LDPC 코딩을 수행한다(제250 단계).
도 5는 도 4에 도시된 제230 단계의 상세 구성을 나타내는 흐름도이다.
행렬 성분 검사부(131)는 패리티 검사 행렬 생성부(110)로부터 패리티 검사 행렬C을 입력받아, 패리티 검사 행렬C에 존재하는 다수의 사이클형성그룹을 탐색하여 제1 사이클형성그룹의 각 구성성분들의 위치정보인 (w1,x1), (w1,y1), (z1,x1) 및 (z1,y1)와 제2 사이클형성그룹의 각 구성성분들의 위치정보인 (w2,x2), (w2,y2), (z2,x2) 및 (z2,y2)을 행렬 성분 교환부(133)로 출력한다(제231 단계).
행렬 성분 교환부(133)는 제1 사이클형성그룹의 하나의 구성성분 Sij(i=w1 또는 z1이고 j=x1 또는 y1)의 성분값 1을 (i,x2) 또는 (i,y2)중 하나의 위치로 수평방향으로 이동시키고, Sij의 성분값 1이 이동된 열에 존재하는 두 개의 상기 제2 사이클형성그룹의 구성성분 Qkl(k=w2 또는 z2 이고 l=x2 또는 y2)중 하나의 성분값 1을 (k,j) 위치로 이동시켜 제1 사이클형성그룹과 제2 사이클형성그룹을 제거한다(제233 단계). 행렬 성분 교환부(133)는 사이클 형성 그룹의 구성성분을 수평방향뿐 아니라 수직방향으로 이동시킴으로써 동일한 효과를 거둘 수 있다. 즉, 제1 사이클형성그룹의 하나의 구성성분 Sij(i=w1 또는 z1이고 j=x1 또는 y1)의 성분값 1을 (w2,j) 또는 (z2,j)중 하나의 위치로 수직방향으로 이동시키고, Sij의 성분값이 이동된 행에 존재하는 두 개의 제2 사이클형성그룹의 구성성분 Qkl(k=w2 또는 z2 이고 l=x2 또는 y2)중 하나의 성분값 1을 (i,l) 위치로 수직방향으로 이동시켜 제1 사이클형성그룹과 제2 사이클형성그룹을 제거한다.
행렬 성분 교환부(133)는 모든 사이클형성그룹이 제거될 때까지 제231 단계 및 제233 단계를 반복수행한다(제235 단계).
본 발명은 또한 컴퓨터로 읽을 수 있는 기록매체에 컴퓨터가 읽을 수 있는 코드로서 구현하는 것이 가능하다. 컴퓨터가 읽을 수 있는 기록매체는 컴퓨터 시스템에 의하여 읽혀질 수 있는 데이터가 저장되는 모든 종류의 기록장치를 포함한다. 컴퓨터가 읽을 수 있는 기록매체의 예로는, ROM, RAM, CD-ROM, 자기 테이프, 플로피디스크, 광데이터 저장 장치 등이 있으며, 또한 캐리어 웨이브(예를 들어, 인터넷을 통한 전송)의 형태로 구현되는 것도 포함한다. 또한 컴퓨터가 읽을 수 있는 기록매체는 네트워크로 연결된 컴퓨터 시스템에 분산되어, 분산방식으로 컴퓨터가 읽을 수 있는 코드로 저장되고 실행될 수 있다.
이상에서 설명한 바와 같이, 본 발명에 따른 에러 정정 부호화 장치 및 방법은, 패리티 검사 행렬에 존재하는 사이클 형성 그룹을 구성하는 성분들을 적절하게 이동시킴으로써 패리티 검사 행렬의 컬럼 웨이트와 로우 웨이트를 일정하게 유지하고 선형 독립성을 만족시킴과 동시에 복호 성능을 저하시키는 사이클 형성 그룹을 제거하여 LDPC 복호화 성능을 향상시키는 효과를 가진다.

Claims (21)

  1. 각 행에 성분값 1을 가지는 소정개수의 성분을 포함하고 각 열에 성분값 1을 가지는 소정개수의 성분을 포함하고 그 외 성분들은 성분값 0을 가지는 패리티 검사 행렬C을 생성하는 패리티검사행렬 생성부;
    상기 패리티검사행렬 생성부로부터 상기 패리티 검사 행렬C을 입력받아, 상기 패리티 검사 행렬C의 성분 중에 사각형의 각 꼭지점의 위치에 있고 각 성분값이 1을 만족하는 4개의 성분으로 구성된 사이클형성 그룹을 탐색하여, 상기 사이클형성 그룹이 적어도 하나 이상 존재하면 상기 사이클형성 그룹의 적어도 하나의 성분의 성분값 1과 다른 성분의 성분값 0을 교환하여 사이클형성 그룹이 제거된 패리티 검사 행렬H을 출력하는 패리티검사행렬 조정부; 및
    상기 패리티검사행렬 조정부로부터 상기 사이클형성 그룹이 제거된 패리티 검사 행렬H을 입력받고 m개의 비트로 이루어진 메시지 워드를 입력받아 LDPC 코딩을 수행하는 LDPC 코딩부;를 포함하는 것을 특징으로 하는 에러 정정 부호화 장치.
  2. 제1 항에 있어서, 상기 패리티 검사 행렬 조정부는
    상기 패리티 검사 행렬 생성부로부터 상기 패리티 검사 행렬C을 입력받아, 다수의 상기 사이클형성그룹을 탐색하여 제1 사이클형성그룹의 각 구성성분들의 위치정보인 (w1,x1), (w1,y1), (z1,x1) 및 (z1,y1)와 제2 사이클형성그룹의 각 구성성분들의 위치정보인 (w2,x2), (w2,y2), (z2,x2) 및 (z2,y2)을 출력하는 행렬 성분 검사부; 및
    상기 행렬 성분 검사부로부터 상기 제1 사이클형성그룹의 각 구성성분들의 상기 위치정보와 상기 제2 사이클형성그룹의 각 구성성분들의 상기 위치정보를 입력받아, 상기 제1 사이클형성그룹의 하나의 구성성분 Sij(i=w1 또는 z1이고 j=x1 또는 y1)의 성분값 1을 (i,x2) 또는 (i,y2)중 하나의 위치로 이동시키고, 상기 Sij의 성분값 1이 이동된 열 에 존재하는 두 개의 상기 제2 사이클형성그룹의 구성성분 Qkl(k=w2 또는 z2 이고 l=x2 또는 y2)중 하나의 성분값 1을 (k,j) 위치로 이동시켜 상기 제1 사이클형성그룹과 상기 제2 사이클형성그룹이 제거하고, 두 개의 사이클형성그룹에 대해 상기 사이클형성그룹 제거 동작을 반복하여 상기 패리티 검사 행렬H을 생성하는 행렬 성분 교환부;를 포함하는 것을 특징으로 하는 에러 정정 부호화 장치.
  3. 제1 항에 있어서, 상기 패리티 검사 행렬 조정부는
    상기 패리티 검사 행렬 생성부로부터 상기 패리티 검사 행렬C을 입력받아, 다수의 상기 사이클형성그룹을 탐색하여 제1 사이클형성그룹의 각 구성성분들의 위치정보인 (w1,x1), (w1,y1), (z1,x1) 및 (z1,y1)와 제2 사이클형성그룹의 각 구성성분들의 위치정보인 (w2,x2), (w2,y2), (z2,x2) 및 (z2,y2)을 출력하는 행렬 성분 검사부; 및
    상기 행렬 성분 검사부로부터 상기 제1 사이클형성그룹의 각 구성성분들의 상기 위치정보와 상기 제2 사이클형성그룹의 각 구성성분들의 상기 위치정보를 입력받아, 상기 제1 사이클형성그룹의 하나의 구성성분 Sij(i=w1 또는 z1이고 j=x1 또는 y1)의 성분값 1을 (w2,j) 또는 (z2,j)중 하나의 위치로 이동시키고, 상기 Sij의 성분값이 이동된 행 에 존재하는 두 개의 상기 제2 사이클형성그룹의 구성성분 Qkl(k=w2 또는 z2 이고 l=x2 또는 y2)중 하나의 성분값 1을 (i,l) 위치로 이동시켜 상기 제1 사이클형성그룹과 상기 제2 사이클형성그룹이 제거하고, 두 개의 사이클형성그룹에 대해 상기 사이클형성그룹 제거 동작을 반복하여 상기 패리티 검사 행렬H을 생성하는 행렬 성분 교환부;를 포함하는 것을 특징으로 하는 에러 정정 부호화 장치.
  4. 제1 항에 있어서, 상기 LDPC 코딩부는 다음의 행렬식
    을 만족하는 상기 행렬X의 구성성분인 상기 패리티 정보 xi(i=1,2...p)를 결정하여 상기 메시지 워드 ki(i=1,2...m)에 상기 패리티 정보 xi(i=1,2...p)가 부가된 코드 워드를 출력하는것을 특징으로 하는 에러 정정 부호화 장치.
  5. 제2 항 또는 제3 항에 있어서,
    상기 행렬 성분 교환부는 상기 패리티 검사 행렬 생성부로부터 상기 패리티 검사 행렬C을 입력받아, 상기 제1 사이클형성그룹의 하나의 구성성분 Sij(i=w1 또는 z1이고 j=x1 또는 y1)의 성분값 1을 이동시킨 경우에 상기 이동시킨 위치에 성분값 1이 이미 존재하면 상기 Sij의 성분값 1을 다른 위치로 이동시키는 것을 특징으로 하는 에러 정정 부호화 장치.
  6. 제2 항 또는 제3 항에 있어서,
    상기 행렬 성분 교환부는 상기 패리티 검사 행렬 생성부로부터 상기 패리티 검사 행렬C을 입력받아, 상기 제1 사이클형성그룹의 하나의 구성성분 Sij(i=w1 또는 z1이고 j=x1 또는 y1)의 성분값 1을 이동시킨 경우에 상기 이동시킨 위치에 성분값 1이 이미 존재하면 상기 제1 사이클형성그룹의 다른 구성성분의 성분값 1을 이동시키는 것을 특징으로 하는 에러 정정 부호화 장치.
  7. 제2 항 또는 제3 항에 있어서,
    상기 행렬 성분 교환부는 상기 패리티 검사 행렬 생성부로부터 상기 패리티 검사 행렬C을 입력받아, 상기 제1 사이클형성그룹의 하나의 구성성분 Sij(i=w1 또는 z1이고 j=x1 또는 y1)의 성분값 1을 이동시킨 경우에 새로운 제3 사이클형성그룹이 발생하면 상기 Sij의 성분값 1을 다른 위치로 이동시키는 것을 특징으로 하는 에러 정정 부호화 장치.
  8. 제2 항 또는 제3 항에 있어서,
    상기 행렬 성분 교환부는 상기 패리티 검사 행렬 생성부로부터 상기 패리티 검사 행렬C을 입력받아, 상기 제1 사이클형성그룹의 하나의 구성성분 Sij(i=w1 또는 z1이고 j=x1 또는 y1)의 성분값 1을 이동시킨 경우에 새로운 제3 사이클형성그룹이 발생하면 상기 제1 사이클형성그룹의 다른 구성성분의 성분값 1을 이동시키는 것을 특징으로 하는 에러 정정 부호화 장치.
  9. 제2 항 또는 제3 항에 있어서,
    상기 행렬 성분 교환부는 상기 패리티 검사 행렬 생성부로부터 상기 패리티 검사 행렬C을 입력받아, 상기 제1 사이클형성그룹의 하나의 구성성분 Sij(i=w1 또는 z1이고 j=x1 또는 y1)의 성분값 1을 이동시켜 상기 제1 사이클형성그룹과 상기 제2 사이클형성그룹을 제거할 수 없으면 상기 행렬 성분 검사부에 다른 한 쌍의 사이클형성그룹을 요청하여 상기 다른 한 쌍의 사이클형성그룹에 대해 상기 사이클형성그룹 제거 동작을 수행하는 것을 특징으로 하는 에러 정정 부호화 장치.
  10. 제2 항 또는 제3 항에 있어서,
    상기 패리티 검사 행렬 교환부는 상기 패리티 검사 행렬C에 존재하는 사이클형성그룹이 모두 제거되지 않으면 상기 패리티 검사 행렬 생성부로 새로운 패리티 검사 행렬C를 생성할 것을 요청하는 신호를 전송하는 것을 특징으로 하는 에러 정정 부호화 장치.
  11. (a) 각 행에 성분값 1을 가지는 소정개수의 성분을 포함하고 각 열에 성분값 1을 가지는 소정개수의 성분을 포함하고 그 외 성분들은 성분값 0을 가지는 패리티 검사 행렬C을 생성하는 패리티 검사 행렬 생성 단계;
    (b) 상기 패리티 검사 행렬C의 성분 중에 사각형의 각 꼭지점의 위치에 있고 각 성분값이 1을 만족하는 4개의 성분으로 구성된 사이클형성 그룹을 탐색하여,상기 사이클형성 그룹이 적어도 하나 이상 존재하면 상기 사이클형성 그룹의 적어도 하나의 성분의 성분값 1과 다른 성분의 성분값 0을 교환하여 사이클형성 그룹이 제거된 패리티 검사 행렬H을 생성하는 패리티 검사 행렬 조정 단계; 및
    (c) 상기 패리티 검사 행렬H을 입력받고 m개의 비트로 이루어진 메시지 워드를 입력받아 LDPC 코딩을 수행하는 LDPC 코딩 단계;를 포함하는 것을 특징으로 하는 에러 정정 부호화 방법.
  12. 제11 항에 있어서, 상기 (b)단계는
    (b1) 상기 패리티 검사 행렬C을 입력받아, 다수의 상기 사이클형성그룹을 탐색하여 제1 사이클형성그룹의 각 구성성분들의 위치정보인 (w1,x1), (w1,y1), (z1,x1) 및 (z1,y1)와 제2 사이클형성그룹의 각 구성성분들의 위치정보인 (w2,x2), (w2,y2), (z2,x2) 및 (z2,y2)을 출력하는 행렬 성분 검사 단계;
    (b2) 상기 제1 사이클형성그룹의 하나의 구성성분 Sij(i=w1 또는 z1이고 j=x1 또는 y1)의 성분값 1을 (i,x2) 또는 (i,y2)중 하나의 위치로 이동시키고, 상기 Sij의 성분값 1이 이동된 열 에 존재하는 두 개의 상기 제2 사이클형성그룹의 구성성분 Qkl(k=w2 또는 z2 이고 l=x2 또는 y2)중 하나의 성분값 1을 (k,j) 위치로 이동시켜 상기 제1 사이클형성그룹과 상기 제2 사이클형성그룹을 제거하는 단계; 및
    (b3) 상기 (b2)단계를 반복 수행하여 상기 패리티 검사 행렬H을 생성하는 단계;를 포함하는 것을 특징으로 하는 에러 정정 부호화 방법.
  13. 제11 항에 있어서, 상기 (b)단계는
    (b1) 상기 패리티 검사 행렬C을 입력받아, 다수의 상기 사이클형성그룹을 탐색하여 제1 사이클형성그룹의 각 구성성분들의 위치정보인 (w1,x1), (w1,y1), (z1,x1) 및 (z1,y1)와 제2 사이클형성그룹의 각 구성성분들의 위치정보인 (w2,x2), (w2,y2), (z2,x2) 및 (z2,y2)을 출력하는 행렬 성분 검사 단계;
    (b2) 상기 제1 사이클형성그룹의 하나의 구성성분 Sij(i=w1 또는 z1이고 j=x1 또는 y1)의 성분값 1을 (w2,j) 또는 (z2,j)중 하나의 위치로 이동시키고, 상기 Sij의 성분값이 이동된 행 에 존재하는 두 개의 상기 제2 사이클형성그룹의 구성성분 Qkl(k=w2 또는 z2 이고 l=x2 또는 y2)중 하나의 성분값 1을 (i,l) 위치로 이동시켜 상기 제1 사이클형성그룹과 상기 제2 사이클형성그룹이 제거하는 단계; 및
    (b3) 상기 (b2)단계를 반복 수행하여 상기 패리티 검사 행렬H을 생성하는 단계;를 포함하는 것을 특징으로 하는 에러 정정 부호화 방법.
  14. 제11 항에 있어서, 상기 (c)단계는 다음의 행렬식
    을 만족하는 상기 행렬X의 구성성분인 상기 패리티 정보 xi(i=1,2...p)를 결정하여 상기 메시지 워드 ki(i=1,2...m)에 상기 패리티 정보 xi(i=1,2...p)가 부가된 코드워드를 생성하는 단계인 것을 특징으로 하는 에러 정정 부호화 방법.
  15. 제12 항 또는 제13 항에 있어서,
    상기 (b2)단계는 상기 패리티 검사 행렬C을 입력받아, 상기 제1 사이클형성그룹의 하나의 구성성분 Sij(i=w1 또는 z1이고 j=x1 또는 y1)의 성분값 1을 이동시킨 경우에 상기 이동시킨 위치에 성분값 1이 이미 존재하면 상기 Sij의 성분값 1을 다른 위치로 이동시키는 단계인 것을 특징으로 하는 에러 정정 부호화 방법.
  16. 제12 항 또는 제13 항에 있어서,
    상기 (b2)단계는 상기 패리티 검사 행렬C을 입력받아, 상기 제1 사이클형성그룹의 하나의 구성성분 Sij(i=w1 또는 z1이고 j=x1 또는 y1)의 성분값 1을 이동시킨 경우에 상기 이동시킨 위치에 성분값 1이 이미 존재하면 상기 제1 사이클형성그룹의 다른 구성성분의 성분값 1을 이동시키는 단계인 것을 특징으로 하는 에러 정정 부호화 방법.
  17. 제12 항 또는 제13 항에 있어서,
    상기 (b2)단계는 상기 패리티 검사 행렬C을 입력받아, 상기 제1 사이클형성그룹의 하나의 구성성분 Sij(i=w1 또는 z1이고 j=x1 또는 y1)의 성분값 1을 이동시킨 경우에 새로운 제3 사이클형성그룹이 발생하면 상기 Sij의 성분값 1을 다른 위치로 이동시키는 단계인 것을 특징으로 하는 에러 정정 부호화 방법.
  18. 제12 항 또는 제13 항에 있어서,
    상기 (b2)단계는 상기 패리티 검사 행렬C을 입력받아, 상기 제1 사이클형성그룹의 하나의 구성성분 Sij(i=w1 또는 z1이고 j=x1 또는 y1)의 성분값 1을 이동시킨 경우에 새로운 제3 사이클형성그룹이 발생하면 상기 제1 사이클형성그룹의 다른 구성성분의 성분값 1을 이동시키는 단계인 것을 특징으로 하는 에러 정정 부호화 방법.
  19. 제12 항 또는 제13 항에 있어서,
    상기 (b2)단계에서 상기 패리티 검사 행렬C을 입력받아, 상기 제1 사이클형성그룹의 하나의 구성성분 Sij(i=w1 또는 z1이고 j=x1 또는 y1)의 성분값 1을 이동시켜 상기 제1 사이클형성그룹과 상기 제2 사이클형성그룹을 제거할 수 없으면
    (b2') 다른 한 쌍의 사이클형성그룹을 입력받아 상기 (b2)단계를 수행하는 단계를 더 포함하는 것을 특징으로 하는 에러 정정 부호화 방법.
  20. 제12 항 또는 제13 항에 있어서,
    (b4) 상기 패리티 검사 행렬C에 존재하는 사이클형성그룹이 모두 제거되지 않으면 새로운 패리티 검사 행렬C를 생성하는 단계;를 더 포함하고,
    상기 (b1) 내지 상기 (b3)단계를 수행하는 것을 특징으로 하는 에러 정정 부호화 방법.
  21. 제11 항 내지 제14 항중 어느 한 항에 기재된 방법을 실현하기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체.
KR1020020062692A 2002-10-15 2002-10-15 에러 정정 부호화 장치 및 그 방법 Withdrawn KR20040033554A (ko)

Priority Applications (7)

Application Number Priority Date Filing Date Title
KR1020020062692A KR20040033554A (ko) 2002-10-15 2002-10-15 에러 정정 부호화 장치 및 그 방법
US10/680,419 US7188281B2 (en) 2002-10-15 2003-10-08 Error correction coding apparatus and method
JP2003352528A JP3772168B2 (ja) 2002-10-15 2003-10-10 エラー訂正符号化装置、エラー訂正符号化方法、及びその方法を実現するためのプログラムを記録したコンピュータで読み取られる記録媒体
DE60317446T DE60317446D1 (de) 2002-10-15 2003-10-11 Verfahren und Vorrichtung zur Encodierung von Low Density Parity Check (LDPC) Codes
EP03256432A EP1422829B1 (en) 2002-10-15 2003-10-11 Method and apparatus for encoding of low density parity check (LDPC) codes
TW092128256A TWI227394B (en) 2002-10-15 2003-10-13 Error correction coding apparatus and method
CNB2003101209393A CN1307804C (zh) 2002-10-15 2003-10-15 纠错编码设备及方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020020062692A KR20040033554A (ko) 2002-10-15 2002-10-15 에러 정정 부호화 장치 및 그 방법

Publications (1)

Publication Number Publication Date
KR20040033554A true KR20040033554A (ko) 2004-04-28

Family

ID=32226183

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020020062692A Withdrawn KR20040033554A (ko) 2002-10-15 2002-10-15 에러 정정 부호화 장치 및 그 방법

Country Status (7)

Country Link
US (1) US7188281B2 (ko)
EP (1) EP1422829B1 (ko)
JP (1) JP3772168B2 (ko)
KR (1) KR20040033554A (ko)
CN (1) CN1307804C (ko)
DE (1) DE60317446D1 (ko)
TW (1) TWI227394B (ko)

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100724922B1 (ko) * 2004-05-12 2007-06-04 포항공과대학교 산학협력단 가변 부호화율을 가지는 블록 저밀도 패리티 검사 부호부호화/복호 장치 및 방법
US7447972B2 (en) 2004-08-05 2008-11-04 Samsung Electronics Co., Ltd. Methods and apparatus for constructing low-density parity check (LDPC) matrix
US7882418B2 (en) 2004-12-08 2011-02-01 Electronics And Telecommunications Research Institute LDPC encoder and decoder and LDPC encoding and decoding methods
KR101147768B1 (ko) * 2005-12-27 2012-05-25 엘지전자 주식회사 채널 코드를 이용한 복호화 방법 및 장치
KR20230151814A (ko) * 2022-04-26 2023-11-02 성균관대학교산학협력단 정렬된 오류를 정정하는 반도체 칩, 정렬된 오류를 정정하는 반도체 시스템

Families Citing this family (20)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP1524771B1 (en) * 2003-05-30 2011-01-05 Sony Corporation Decoding method, decoding device, program, recording/reproduction device and method, and reproduction device and method
KR20050044963A (ko) * 2003-11-08 2005-05-16 삼성전자주식회사 ｑ차 제곱 잉여류를 이용한 준순환 저밀도 패러티 검사부호 생성 방법
US7581157B2 (en) 2004-06-24 2009-08-25 Lg Electronics Inc. Method and apparatus of encoding and decoding data using low density parity check code in a wireless communication system
KR100918741B1 (ko) 2004-07-27 2009-09-24 삼성전자주식회사 이동 통신 시스템에서 채널 부호화 장치 및 방법
US7143333B2 (en) * 2004-08-09 2006-11-28 Motorola, Inc. Method and apparatus for encoding and decoding data
US7689892B2 (en) 2004-09-08 2010-03-30 Nokia Corporation System and method for adaptive low-density parity-check (LDPC) coding
US8438459B2 (en) * 2004-12-22 2013-05-07 Lg Electronics Inc. Apparatus and method for decoding using channel code
CN100414841C (zh) * 2005-05-11 2008-08-27 电子科技大学 一种ldpc编码的实现方法
CN101064840B (zh) * 2006-04-26 2010-11-03 日电（中国）有限公司 蛇形矩阵编码/解码器以及可视标志编码和呈现系统
KR100975558B1 (ko) 2006-05-03 2010-08-13 삼성전자주식회사 통신 시스템에서 신호 송수신 장치 및 방법
JP4788680B2 (ja) * 2007-07-27 2011-10-05 住友電気工業株式会社 復号器
KR101366284B1 (ko) 2007-11-13 2014-02-20 엘지전자 주식회사 골레이 부호를 이용한 블록 부호 생성 방법, 데이터 부호화방법 및 데이터 부호화 장치
WO2009084891A2 (en) * 2007-12-27 2009-07-09 Lg Electronics Inc. Generation of golay-based systematic block code supporting various sizes
US8392787B2 (en) * 2008-10-31 2013-03-05 Broadcom Corporation Selective merge and partial reuse LDPC (Low Density Parity Check) code construction for limited number of layers Belief Propagation (BP) decoding
GB2489526A (en) * 2011-04-01 2012-10-03 Schlumberger Holdings Representing and calculating with sparse matrixes in simulating incompressible fluid flows.
CN104981979B (zh) * 2013-02-08 2019-03-22 三菱电机株式会社 发送机、接收机以及编码率变更方法
US10284230B2 (en) * 2016-11-15 2019-05-07 Western Digital Technologies, Inc. Linked storage system and host system error correcting code
US10949298B2 (en) * 2018-09-21 2021-03-16 Taiwan Semiconductor Manufacturing Company, Limited System and method of reducing logic for multi-bit error correcting codes
TWI712268B (zh) * 2018-11-14 2020-12-01 慧榮科技股份有限公司 快閃記憶體控制器及其中的編碼電路與解碼電路
CN112880556B (zh) * 2021-01-06 2022-04-22 南京林业大学 一种地基三维激光扫描的林分标准地样木位置的确定方法

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20020042899A1 (en) * 2000-06-16 2002-04-11 Tzannes Marcos C. Systems and methods for LDPC coded modulation
US6944803B2 (en) * 2000-07-06 2005-09-13 Her Majesty The Queen In Right Of Canada, As Represented By The Minister Of Industry Through The Communications Research Centre Canada Code structure, encoder, encoding method, and associated decoder and decoding method and iteratively decodable code structure, encoder, encoding method, and associated iterative decoder and iterative decoding method
US6895547B2 (en) 2001-07-11 2005-05-17 International Business Machines Corporation Method and apparatus for low density parity check encoding of data

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100724922B1 (ko) * 2004-05-12 2007-06-04 포항공과대학교 산학협력단 가변 부호화율을 가지는 블록 저밀도 패리티 검사 부호부호화/복호 장치 및 방법
US7502987B2 (en) 2004-05-12 2009-03-10 Samsung Electronics Co., Ltd Apparatus and method for encoding and decoding block low density parity check codes with a variable coding rate
US8656247B2 (en) 2004-05-12 2014-02-18 Samsung Electronics Co., Ltd Apparatus and method for encoding and decoding block low density parity check codes with a variable coding rate
US7447972B2 (en) 2004-08-05 2008-11-04 Samsung Electronics Co., Ltd. Methods and apparatus for constructing low-density parity check (LDPC) matrix
US7882418B2 (en) 2004-12-08 2011-02-01 Electronics And Telecommunications Research Institute LDPC encoder and decoder and LDPC encoding and decoding methods
KR101147768B1 (ko) * 2005-12-27 2012-05-25 엘지전자 주식회사 채널 코드를 이용한 복호화 방법 및 장치
KR20230151814A (ko) * 2022-04-26 2023-11-02 성균관대학교산학협력단 정렬된 오류를 정정하는 반도체 칩, 정렬된 오류를 정정하는 반도체 시스템

Also Published As

Publication number Publication date
EP1422829A2 (en) 2004-05-26
JP3772168B2 (ja) 2006-05-10
TW200406666A (en) 2004-05-01
EP1422829B1 (en) 2007-11-14
DE60317446D1 (de) 2007-12-27
CN1514548A (zh) 2004-07-21
US7188281B2 (en) 2007-03-06
JP2004140828A (ja) 2004-05-13
US20040168112A1 (en) 2004-08-26
EP1422829A3 (en) 2004-11-17
CN1307804C (zh) 2007-03-28
TWI227394B (en) 2005-02-01

Similar Documents

Publication Publication Date Title
KR20040033554A (ko) 에러 정정 부호화 장치 및 그 방법
US10972216B2 (en) Polar code encoding method and device
KR101270815B1 (ko) 다양한 클래스의 코드들을 인코딩 및 디코딩하는 애플리케이션을 갖는 인-플레이스 변환
US7633413B2 (en) Systems and processes for decoding a chain reaction code through inactivation
JP3565798B2 (ja) バースト誤りパターン生成方法及びバーストおよびバイト誤り検出・訂正装置
US20160294419A1 (en) Coding and decoding methods and apparatus
KR101922990B1 (ko) 멀티미디어 통신 시스템에서 준순환 저밀도 패리티 검사 부호 송/수신 장치 및 방법
KR20080048988A (ko) 무-충돌 불규칙-반복-누산 코드
US7451374B2 (en) Apparatus and method for channel coding in mobile communication system
WO2018219001A1 (zh) Ldpc码校验矩阵的构造方法和设备
TWI311869B (en) 3-stripes gilbert low density parity-check codes
Langberg et al. Coding for the $\boldsymbol\ell _\infty $-Limited Permutation Channel
WO2006109951A1 (en) Method and apparatus for generating block-based low-density parity check matrix and recording medium having recorded thereon code for implementing the method
JP2019525638A (ja) ２のべき乗でない長さに拡張されたポーラ符号の符号化および復号化
TW201907668A (zh) 分散式ｃｒｃ極性碼
US12218682B2 (en) Encoding method, decoding method, electronic device and storage medium
US20070277075A1 (en) Method of Generating Parity Information Using Low Density Parity Check
US7363570B2 (en) Method of converting parity check matrix for low density parity check coding
US20060107180A1 (en) Apparatus and method for constructing low-density parity check matrix
CN114826283A (zh) 译码方法、装置、设备以及计算机可读存储介质
Farkaš et al. On run-length limited error control codes constructed from binary product codes
KR101120593B1 (ko) 데이터 보정 장치, 데이터 보정 방법 및 이의 기록 매체
CN120639102A (zh) 一种数据编码方法以及相关装置
JP4308226B2 (ja) 誤り訂正符号化装置
CN120377934A (zh) 码的构造方法、编码方法、节点修复方法及数据处理装置

Legal Events

Date Code Title Description
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 20021015

PG1501 Laying open of application
PC1203 Withdrawal of no request for examination
WITN Application deemed withdrawn, e.g. because no request for examination was filed or no examination fee was paid