KR20160017820A - 코딩 방법 및 코딩 장치 - Google Patents
코딩 방법 및 코딩 장치 Download PDFInfo
- Publication number
- KR20160017820A KR20160017820A KR1020140100995A KR20140100995A KR20160017820A KR 20160017820 A KR20160017820 A KR 20160017820A KR 1020140100995 A KR1020140100995 A KR 1020140100995A KR 20140100995 A KR20140100995 A KR 20140100995A KR 20160017820 A KR20160017820 A KR 20160017820A
- Authority
- KR
- South Korea
- Prior art keywords
- message
- parity
- code
- decoding
- error
- 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
Links
- 238000000034 method Methods 0.000 title claims abstract description 43
- 238000012937 correction Methods 0.000 claims description 7
- 238000010586 diagram Methods 0.000 description 8
- 238000004364 calculation method Methods 0.000 description 4
- 238000013461 design Methods 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 238000004088 simulation Methods 0.000 description 2
- HCUOEKSZWPGJIM-YBRHCDHNSA-N (e,2e)-2-hydroxyimino-6-methoxy-4-methyl-5-nitrohex-3-enamide Chemical compound COCC([N+]([O-])=O)\C(C)=C\C(=N/O)\C(N)=O HCUOEKSZWPGJIM-YBRHCDHNSA-N 0.000 description 1
- 238000007796 conventional method Methods 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 238000012804 iterative process Methods 0.000 description 1
- 238000012545 processing Methods 0.000 description 1
- 238000011084 recovery Methods 0.000 description 1
Images
Classifications
-
- 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/29—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 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
- H03M13/2906—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 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes using block codes
- H03M13/2927—Decoding strategies
- H03M13/293—Decoding strategies with erasure setting
-
- 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/29—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 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
- H03M13/2906—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 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes using block codes
- H03M13/2909—Product codes
-
- 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/29—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 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
- H03M13/2906—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 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes using block codes
- H03M13/2918—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 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes using block codes with error correction codes in three or more dimensions, e.g. 3-dimensional product code where the bits are arranged in a cube
-
- 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/29—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 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
- H03M13/2906—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 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes using block codes
- H03M13/2927—Decoding strategies
-
- 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/29—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 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
- H03M13/2948—Iterative decoding
-
- 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/65—Purpose and implementation aspects
- H03M13/6561—Parallelized implementations
-
- 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/13—Linear codes
- H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
- H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
- H03M13/1515—Reed-Solomon codes
-
- 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/13—Linear codes
- H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
- H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
- H03M13/152—Bose-Chaudhuri-Hocquenghem [BCH] codes
Landscapes
- Physics & Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Mathematical Physics (AREA)
- Error Detection And Correction (AREA)
- Algebra (AREA)
- General Physics & Mathematics (AREA)
- Pure & Applied Mathematics (AREA)
Abstract
본 발명의 일 실시예에 의한 인코딩 방법은 다수 개의 메시지를 외부 코드로 인코딩하여 다수 개의 패리티 블록을 생성하는 제 1 단계; 다수 개의 메시지와 다수 개의 패리티 블록을 조합하여 다수 개의 메시지 데이터를 생성하는 제 2 단계; 및 다수 개의 메시지 데이터 각각을 내부 코드로 인코딩하여 다수 개의 심볼을 생성하는 제 3 단계를 포함한다.
Description
본 발명은 코딩 방법 및 코딩 장치에 관한 것으로서 보다 구체적으로는 액세스 단위로 메시지를 보호하는 동시에 다수의 액세스 단위로 추가적인 보호를 제공함으로써 메시지 보호 수준을 향상시키는 코딩 방법 및 코딩 장치에 관한 것이다.
종래에는 하나의 액세스 단위로 메시지를 보호하였다.
예를 들어 액세스 단위가 페이지라고 가정하면 종래에는 한 페이지 메시지를 다수의 블록으로 분할한 후 이들에 대하여 BC-BCH 코드를 적용하였다.
이러한 종래의 기술에서는 메시지 보호 단위가 하나의 액세스 단위로 한정되어 메시지 보호 수준이 제한되는 문제가 있다.
본 발명은 액세스 단위로 메시지를 보호하는 동시에 다수의 액세스 단위로 추가적인 보호를 제공함으로써 메시지 보호 수준을 향상시키는 코딩 방법 및 코딩 장치를 제공한다.
본 발명의 일 실시예에 의한 인코딩 방법은 다수 개의 메시지를 외부 코드로 인코딩하여 다수 개의 패리티 블록을 생성하는 제 1 단계; 다수 개의 메시지와 다수 개의 패리티 블록을 조합하여 다수 개의 메시지 데이터를 생성하는 제 2 단계; 및 다수 개의 메시지 데이터 각각을 내부 코드로 인코딩하여 다수 개의 심볼을 생성하는 제 3 단계를 포함한다.
본 발명의 일 실시예에 의한 디코딩 방법은 외부 코드와 내부 코드에 따라 인코딩되어 메시지, 외부 패리티 및 내부 패리티를 포함하는 제 1 심볼을 디코딩하는 방법으로서 제 1 심볼을 내부 코드에 의해 디코딩하는 제 1 단계; 제 1 단계에서 오류가 발생하는 경우 외부 패리티를 통해 제 1 심볼과 연관된 제 2 심볼을 내부 코드에 의해 디코딩하는 제 2 단계; 및 제 1 및 제 2 단계에서 발생한 오류를 외부 코드에 의해 정정하는 제 3 단계를 포함한다.
본 발명의 일 실시예에 의한 인코딩 장치는 다수 개의 메시지를 외부 코드로 인코딩하여 다수 개의 패리티 블록을 생성하는 패리티 생성부; 및 다수 개의 메시지와 다수 개의 패리티 블록을 조합하여 다수 개의 메시지 데이터를 생성하고, 다수 개의 메시지 데이터 각각을 내부 코드로 인코딩하여 다수 개의 심볼을 생성하는 내부 인코더 블록을 포함한다.
본 발명의 일 실시예에 의한 디코딩 장치는 외부 코드와 내부 코드에 따라 인코딩되어 메시지, 외부 패리티 및 내부 패리티를 포함하는 제 1 심볼을 디코딩하는 디코딩 장치로서 외부 패리티에 의해 제 1 심볼과 연관된 제 2 심볼과 제 1 심볼을 내부 코드에 의해 디코딩하는 내부 디코더 블록; 제 1 심볼로부터 디코딩된 제 1 메시지와 제 2 심볼로부터 디코딩된 제 2 메시지를 연산하여 연산 메시지를 생성하는 메시지 연산부 및 외부 코드를 이용하여 제 1 메시지 및 제 2 메시지를 정정하는 외부 디코더 블록을 포함한다.
본 기술을 통해 액세스 단위로 메시지를 보호하는 동시에 다수의 액세스 단위로 추가적인 보호를 제공함으로써 메시지 보호 수준을 향상시킬 수 있다.
도 1은 본 발명의 일 실시예에 의한 인코딩 방법을 나타낸 순서도.
도 2 내지 도 6은 본 발명의 일 실시예에 의한 인코딩 방법을 설명하는 설명도.
도 7 및 도 8은 본 발명의 일 실시예에 의한 디코딩 방법을 나타낸 순서도.
도 9는 연산 메시지의 생성 방법을 설명하는 설명도.
도 10은 본 발명의 일 실시예에 의한 인코딩 장치의 블록도.
도 11은 본 발명의 다른 실시예에 의한 인코딩 장치의 블록도.
도 12는 본 발명의 일 실시예에 의한 디코딩 장치의 블록도.
도 13은 본 발명의 효과를 설명하는 그래프.
도 2 내지 도 6은 본 발명의 일 실시예에 의한 인코딩 방법을 설명하는 설명도.
도 7 및 도 8은 본 발명의 일 실시예에 의한 디코딩 방법을 나타낸 순서도.
도 9는 연산 메시지의 생성 방법을 설명하는 설명도.
도 10은 본 발명의 일 실시예에 의한 인코딩 장치의 블록도.
도 11은 본 발명의 다른 실시예에 의한 인코딩 장치의 블록도.
도 12는 본 발명의 일 실시예에 의한 디코딩 장치의 블록도.
도 13은 본 발명의 효과를 설명하는 그래프.
이하에서는 첨부한 도면을 참조하여 본 발명의 실시예에 대해서 상세히 설명한다. 이하의 설명에서 동일한 참조 부호는 실질적으로 동일한 대상을 지시한다.
이하의 개시에서 하나의 액세스 단위는 페이지인 것으로 가정한다. 또한 하나의 페이지 내에서 메시지를 보호하기 위하여 사용되는 코드를 내부 코드, 다수의 페이지들 사이에서 메시지를 보호하기 위하여 사용되는 코드를 외부 코드라 지칭하며, 외부 코드는 4개의 페이지를 사이에서 적용되는 것으로 가정한다.
또한 이하의 개시에서는 내부 코드로서 BC-BCH 코드를 사용하고 외부 코드로서 RS 코드를 사용하는 것으로 가정한다. BC-BCH 코드와 RS 코드 각각에 의한 코딩 방법 및 장치는 공지된 것이므로 이에 대해서는 구체적인 설명을 생략한다.
실시예에 따라 내부 코드와 외부 코드의 종류 및 외부 코드가 적용되는 페이지의 개수는 달라질 수 있다.
도 1은 본 발명의 일 실시예에 의한 인코딩 방법을 나타내는 순서도이다.
먼저 4개의 페이지 메시지 각각을 메시지 블록으로 분할한다(S110).
도 2는 하나의 페이지 메시지(100)를 다수의 메시지 블록(110)들로 분할한 예를 나타낸다.
도면에서 Nr과 Nc는 BC-BCH 코드를 적용하기 위하여 메시지 블록들을 행과 열 단위로 배치하였을 때 행의 개수와 열의 개수를 나타낸다.
각 메시지 블록(110)에 포함되는 비트 수, 즉 메시지 블록의 크기는 BC-BCH 코드의 설계 방식에 따라 달라질 수 있다. 예를 들어 메시지 블록의 크기는 모두 동일할 수도 있고 그렇지 않을 수도 있다. 후자의 경우 메시지 블록의 크기는 최대값과 최소값의 차이가 1이 되도록 할 수도 있다. 이하에서는 메시지 블록(110)의 크기의 최대값을 L로 정의한다.
RS 코드에 따라 인코딩을 수행하는 경우에도 각 메시지 블록(110)의 최대 크기가 제한될 수 있다. 이 경우 메시지 블록(110)을 다수의 서브 메시지 블록(111)으로 분할한 후 RS 코드에 의해 인코딩을 수행할 수 있다.
도 3은 하나의 메시지 블록(110)을 다수의 서브 메시지 블록(111)으로 분할한 예를 나타낸다.
도 3에서 각 메시지 블록(110)은 m 개의 서브 메시지 블록(111)으로 분할된다. 하나의 서브 메시지 블록(111)의 크기를 μ라고 하면 도 3에서 m은 다음 수학식 1과 같이 정의될 수 있다.
도 1로 돌아가서 페이지를 메시지 블록(110) 또는 서브 메시지 블록(111)들로 분할한 이후 페이지별로 RS 코드에 따라 제 1 패리티를 생성한다.
도 4는 도 3과 같이 서브 메시지 블록(111)들로 분할된 페이지(100)에 대해서 RS 코드를 적용하여 제 1 패리티(200)를 생성한 예를 나타낸다.
RS 코드에 따른 인코딩은 서브 메시지 블록(111)들의 행 단위로 수행된다. 인코딩 결과 행 단위로 각각 네 개씩의 패리티 P1 i ~ P4 i (1 ≤i ≤m)가 생성된다. 패리티의 개수는 함께 외부 코드가 적용되는 페이지의 개수와 연관된다. 도 4와 같은 형태의 제 1 패리티(200)가 페이지마다 생성된다.
도 1로 돌아가서, 다음 단계(S130)에서는 먼저 각 페이지별로 생성된 제 1 패리티(200)들에 대해서 XOR 연산을 수행하여 제 2 패리티(300)를 생성한다. 제 2 패리티와 제 1 패리티의 관계는 다음 수학식 2와 같이 정의될 수 있다.
제 2 패리티(300)는 도 5와 같이 4 개의 패리티 집합(310)으로 분할될 수 있고 각각의 패리티 집합(310)은 하나의 패리티 블록(320)으로 병합될 수 있다.
본 실시예에서는 패리티 블록을 생성함에 있어서 4개의 메시지를 각각 외부 코드로 인코딩하여 총 4 개의 제 1 패리티를 얻고 이들을 XOR 연산하여 제 2 패리티를 얻은 후 이를 4 개로 분할하여 4개의 패리티 블록을 얻었다.
다른 실시예에서는 순서를 바꾸어 먼저 4개의 메시지들을 같은 위치의 블록들끼리 XOR 연산하여 하나의 연산 메시지를 생성하고, 이를 외부 코드로 인코딩하여 생성된 패리티를 4 개로 분할하여 4 개의 패리티 블록을 생성할 수도 있다.
도 1로 돌아가서, 위와 같이 생성된 4 개의 패리티 블록(320)들 중 하나와 도 1의 메시지 블록(110)들을 합하여 하나의 페이지 데이터가 형성된다. 이에 따라 패리티 블록(320)의 크기는 메시지 블록(110)들이 가질 수 있는 크기로 설계되는 것이 바람직하다.
이후 4 개의 페이지 데이터에 대해서 각각 내부 코드인 BC-BCH 코드를 이용하여 인코딩을 수행한다(S140)
본 실시예에서는 외부 코드인 RS 코드의 오류 정정 능력을 2로 설계함으로써 필요한 패리티 블록의 개수는 4가 된 것이다. 만일 오류 정정 능력을 바꾸면 필요한 패리티 블록의 개수는 변경될 수 있고 외부 코드에 의해 보호되는 페이지의 개수 역시 4가 아닌 다른 개수로 변경될 수 있다.
도 6은 페이지 데이터(400)에 대해서 BC-BCH 코드를 적용한 예를 나타낸 도면이다.
도면에서 각 페이지 데이터(400)는 Nr x Nc - 1개의 메시지 블록(110)과 1 개의 패리티 블록(320)을 포함하여 총 Nr x Nc 개의 블록을 포함하게 된다.
이들을 행과 열로 배치하고 Nr개의 행 및 Nc개의 열에 대해서 각각 행 코드(510)와 열 코드(620)를 생성한다.
페이지 데이터(400), 행 코드 블록(500) 및 열 코드 블록(600)이 합쳐져 하나의 심볼(S)이 형성된다.
이상과 같이 하나의 심볼은 페이지 메시지와 외부 코드에 의해 형성된 외부 패리티(패리티 블록) 및 내부 코드에 의해서 형성된 내부 패리티(행 패리티 및 열 패리티)를 포함하며 페이지 메시지는 외부 패리티와 내부 패리티에 의해서 이중으로 보호될 수 있다.
이하에서는 본 발명의 일 실시예에 의한 디코딩 방법을 개시한다. 이하의 개시는 전술한 인코딩 방법에 의해 생성된 제 1 심볼을 읽는 경우에 있어서 발생하는 오류를 정정하는 방법을 개시한다.
이하에서는 읽는 대상이 되는 제 1 심볼에 대응하는 페이지를 제 1 페이지, 제 1 심볼과 외부 코드를 통해 연관되는 제 2 내지 제 4 심볼에 대응하는 페이지를 제 2 내지 제 4 페이지로 지칭한다.
도 7 및 8은 본 발명의 일 실시예에 의한 디코딩 방법을 나타내는 순서도이다.
먼저 제 1 심볼을 읽고 이를 BC-BCH 코드를 이용하여 디코딩한다(S210).
디코딩시 오류가 발생했는지 판단하고(S220), 오류가 발생하지 않았으면 성공을 표시하고(S221) 종료한다. 이때 오류는 BC-BCH 코드에 의하여 정정이 불가능한 오류를 의미한다.
디코딩시 오류가 발생했으면 오류 블록의 위치를 저장한다(S230). BC-BCH 코드에 의해 디코딩을 수행하는 경우 도 6과 같이 행 코드(500) 및 열 코드(600)에서 동시에 오류가 발생한 행과 열을 특정함으로써 오류 블록의 위치를 알 수 있다.
이후 오류가 발생한 블록의 개수가 허용치를 초과하는지 판단한다(S240).
허용치는 RS 코드를 이용하여 정정할 수 있는 오류 블록의 최대 개수를 의미하며, 허용치는 RS 코드의 설계에 따라 달라질 수 있다.
오류 블록의 개수가 허용치를 초과하는 경우 실패를 표시하고(S241) 종료한다.
오류 블록의 개수가 허용치를 초과하지 않는 경우에는 제 1 심볼과 연관된 제 2 내지 제 4 심볼 각각을 BC-BCH 코드에 따라 디코딩한다(S250).
오류가 발생하지 않았으면 곧바로 오류를 정정하는 단계(S300)로 이동하고 오류가 발생했으면 오류가 발생한 블록들의 위치를 저장한다(S270).
오류 정정 단계(S300)에 대해서는 도 8을 참조하여 이하에서 구체적으로 개시한다. 이때 오류는 BC-BCH 코드에 의하여 정정이 불가능한 오류를 의미한다.
이후 제 1 심볼 내지 제 4 심볼을 디코딩하는 과정에서 오류가 발행한 총 블록의 개수가 허용치를 초과하는지 판단한다(S280). 이때 허용치는 단계(S240)에서의 허용치와 동일하다.
총 오류 블록의 개수가 허용치를 초과하는 경우에는 오류를 정정할 수 없으므로 실패를 표시하고(S241) 종료한다.
총 오류 블록의 개수가 허용치를 초과하지 않는 경우에는 단계(S281)로 이동한다.
단계(S281)에서는 오류 블록들의 위치 정보를 이용하여 동일한 위치의 블록들에서 오류가 발생했는지 판단한다. 예를 들어 제 1 페이지 데이터의 첫 번째 블록에서 오류가 발생하고 제 2 페이지 데이터의 첫 번째 블록에서 오류가 발생했다면 동일한 위치의 블록에서 오류가 발생한 것으로 판단한다.
다만 패리티 블록의 경우에는 여러 페이지에서 오류가 발생하더라도 동일한 위치에서 오류가 발생한 것으로 판단하지 않고 서로 다른 위치에서 오류가 발생한 것처럼 판단한다.
다음으로 오류가 발생한 위치의 개수와 오류가 중복 발생한 위치의 개수가 동일한지 여부를 판단한다(S282).
만일 오류가 발생한 위치의 개수와 오류가 중복 발생한 위치의 개수가 동일한 경우에는 오류 정정 단계(S300)에서 오류를 정정하는 것이 불가능하게 되므로 실패를 표시하고(S241) 종료한다.
만일 오류가 발생한 위치의 개수와 오류가 중복 발생한 위치의 개수가 동일하지 않다면 오류를 정정하는 단계(S300)로 진행한다.
이하에서 다시 개시하겠으나 오류를 정정하는 단계(S300)에서는 모든 오류 블록이 정정되는 경우에는 오류 존재 플래그를 비활성화하고 오류 블록이 남아 있는 경우에는 오류 존재 플래그를 활성화한다.
오류를 정정하는 단계(S300) 이후에 오류 존재 플래그가 활성화되어 있는지 판단하여(S290), 오류 존재 플래그가 활성화되어 있지 않으면 모든 오류 블록이 정정된 것이므로 성공을 표시하고(S291) 종료한다.
오류 존재 플래그가 활성화되어 있으면 단계(S210)로 돌아가 제 1 심볼에 대한 BC-BCH 코드를 이용한 디코딩 단계를 다시 수행한다. 다만 이 경우에는 전체 디코딩을 다시 할 필요는 없고 기존의 디코딩 결과에 단계(S300)에서의 오류 정정 결과를 반영하여 제 1 페이지 데이터(400)를 갱신하고 갱신된 제 1 페이지 데이터(400)에 대해서 내부 코드를 이용하여 오류를 정정한 후 오류 정보를 갱신하면 충분하다.
따라서 오류 정정(S300)을 수행한 이후 여전히 오류 블록이 남아 있더라도 단계(S210)를 수행함으로써 제 1 페이지 데이터(400)에 존재하는 오류가 모두 정정될 수 있다. 이 경우 성공을 표시하고(S210) 종료할 수 있다.
도 8은 도 7의 오류 정정 단계(S300)를 나타낸 순서도이다.
전술한 바와 같이 제 1 내지 제 4 페이지 데이터(400)에 포함된 패리티 블록(320)들은 각 페이지 데이터(400)에 포함된 메시지 블록(110)들을 RS 코드로 인코딩하여 생성된 제 1 패리티들을 페이지 단위로 XOR 연산하여 생성된 제 2 패리티를 분할한 것이다.
수학적으로 RS 코드에 의한 인코딩 연산과 페이지 단위의 XOR 연산은 교환 가능하다. 이는 메시지 블록들을 페이지 단위로 XOR 연산하여 얻어진 연산 메시지 블록들을 RS 코드로 인코딩하여 생성한 패리티는 메시지 블록들을 RS 코드로 인코딩하여 생성한 제 1 패리티들을 XOR 연산하여 얻은 제 2 패리티와 동일함을 의미한다.
도 8로 돌아가 먼저 제 1 심볼 내지 제 4 심볼을 BC-BCH 코드를 통해 디코딩한 결과 얻어진 메시지 블록들을 페이지 단위로 XOR 연산하여 연산 메시지를 생성한다(S310).
도 9는 제 1 심볼 내지 제 4 심볼을 디코딩하여 얻어진 제 1 내지 제 4 페이지 데이터에 포함된 메시지(m1, m2, m3, m4)를 대응하는 블록끼리 페이지 단위로 XOR 연산하여 연산 메시지(m')를 생성하는 방법을 설명한다.
도 8로 돌아가 다음으로 연산 메시지(m')의 블록들 중 오류가 발생한 위치에 대응하는 블록들을 모두 미지수 블록(Erasure)으로 처리한다(S320). 미지수 블록은 블록에 포함된 비트가 0도 아니고 1도 아닌 미지의 값을 가지는 블록을 의미한다.
다음으로 미지수 블록을 포함하는 연산 메시지(m')와 제 1 내지 제 4 심볼을 BC-BCH 코드에 의해 디코딩하여 얻은 4 개의 패리티 블록을 이용하여 미지수 블록들을 복원한다(S330).
전술한 바와 같이 RS 코드에 의한 인코딩 연산과 페이지 단위의 XOR 연산은 서로 교환 가능하므로 연산 메시지(m')를 RS 코드로 인코딩한 결과는 4 개의 패리티 블록과 동일해야 한다. 이에 따라 각각의 미지수 블록들은 연산 메시지(m')와 4 개의 패리티 블록들을 RS 코드로 디코딩함으로써 그 값을 복원할 수 있다.
이에 따라 연산 메시지(m')에서 미지수 블록들의 값이 복원되므로 이하에서는 연산 메시지(m')를 이용하여 각 메시지(m1, m2, m3, m4)에 존재하는 오류 블록을 복원하게 된다.
전술한 바와 같이 본 실시예에서는 오류가 발생한 블록의 위치에 관한 정보를 먼저 제공하여 해당 위치의 블록(미지수 블록)에 대해서만 외부 코드에 의한 디코딩을 수행한다.
다른 실시예에서는 오류가 발생한 위치에 관한 정보를 활용하지 않고 미지수 블록 처리를 수행하지 않은 상태에서 연산 메시지(m')와 패리티 블록들을 외부 코드에 의해 디코딩함으로써 연산 메시지(m')를 복원할 수도 있다.
이를 위하여 먼저 변수 N을 1로 설정한다(S340). N은 각각의 오류 블록을 지시하는 인덱스이다.
다음으로 N 번째 오류 블록의 위치가 두 페이지 이상에서 오류가 중복적으로 발생한 위치인지 확인한다(S350).
만일 N 번째 오류 블록의 위치가 오류가 중복 발생한 위치라면 오류를 정정하지 못하므로 오류 존재 플래그를 활성화하고(S360), 다음 단계(S370)로 진행한다.
만일 N 번째 오류 블록의 위치가 오류가 중복 발생한 위치가 아니라면 해당 오류 블록을 정정한다(S351). 예를 들어서 N 번째 오류 블록이 제 1 페이지에 존재한다고 가정하고, 연산 메시지(m')에서 대응하는 위치의 블록을 S, 메시지에서 대응하는 위치의 블록을 B라고 하면 N 번째 메시지 블록은 다음 수학식 3에 의해서 정정된다.
이후 전체 오류 블록에 대하여 전술한 단계들을 반복하여 수행하고 종료한다(S350, S351, S360).
이 과정에서 적어도 한 번 단계(S360)가 실행되었다면 특정 위치에서 중복된 오류가 발생하여 정정되지 않은 블록이 존재함을 나타낸다.
이러한 경우에는 도 7에서 단계(S210) 및 그 이후의 단계들이 반복 수행된다.
반복 수행 과정에서는 도 8의 단계(S351)에서 정정된 결과가 반영된다. 이에 따라 도 7의 단계(S210)를 수행하면서 페이지 내의 오류 블록이 내부 코드에 의해 정정 가능하게 되어 디코딩이 성공적으로 종료될 수 있다.
도 10은 본 발명의 일 실시예에 의한 인코딩 장치를 나타낸 블록도이다.
본 발명의 일 실시예에 의한 인코딩 장치는 외부 인코딩 블록(110), 패리티 연산부(20) 및 내부 인코딩 블록(30)을 포함한다.
외부 인코딩 블록(110)은 네 개의 페이지에 존재하는 메시지(M1, M2, M3, M4)를 외부 코드, 예를 들어 RS 코드,를 이용하여 인코딩함으로써 각 페이지에 대응하는 제 1 패리티(P1, P2, P3, P4)를 생성한다.
도 4를 참조하여 설명한 바와 같이 본 실시예에서 제 1 패리티 각각은 4개의 하위 패리티로 구분될 수 있다.
본 실시예에서 외부 인코더 블록(110)은 4 개의 외부 인코더(11)를 포함할 수 있다. 4 개의 외부 인코더(11) 각각은 대응하는 페이지의 메시지를 외부 코드에 의해 인코딩하여 대응하는 제 1 패리티를 생성할 수 있다.
다른 실시예에서 외부 인코더 블록(110)은 1 개의 외부 인코더(11)를 포함할 수도 있다. 이때 1 개의 외부 인코더(11)는 4개의 메시지를 순차적으로 인코딩하여 4개의 제 1 패리티를 순차적으로 출력할 수도 있다.
패리티 연산부(20)는 수학식 2와 같이 제 1 패리티(P1, P2, P3, P4)를 페이지 단위로 XOR 연산하여 4개의 패리티 블록(P'1, P'2, P'3, P'4)을 생성한다.
내부 인코더 블록(30)은 4개의 패리티 블록(P'1, P'2, P'3, P'4) 중 어느 하나와 4 개의 페이지 메시지(M1, M2, M3, M4) 중 어느 하나를 합하여 총 4개의 페이지 데이터를 생성하고 각 페이지 데이터에 대하여 내부 코드, 예를 들어 BC-BCH 코드,를 적용하여 인코딩함으로써 4 개의 심볼(S1, S2, S3, S4)을 생성한다.
본 실시예에서 내부 인코더 블록(30)은 4 개의 내부 인코더(31)를 포함할 수 있다. 4 개의 내부 인코더(31) 각각은 대응하는 하나의 페이지 메시지와 하나의 패리티 블록을 하나의 페이지 데이터로 합하고 이를 내부 코드에 의해 인코딩하여 대응하는 심볼을 출력할 수 있다. 이에 대해서는 도 6을 참조하여 개시한 바 있다.
다른 실시예에서 내부 인코더 블록(30)은 1 개의 내부 인코더(31)를 포함할 수도 있다. 이때 1 개의 내부 인코더(31)는 4번의 인코딩 동작을 순차적으로 수행하여 4 개의 심볼(S1, S2, S3, S4)을 순차적으로 출력할 수 있다.
도 11은 본 발명의 다른 실시예에 의한 인코딩 장치를 나타낸 블록도이다.
도 11의 인코딩 장치는 메시지 연산부(60), 외부 인코더(11) 및 내부 인코더 블록(30)을 포함한다.
메시지 연산부(60)는 먼저 4 개의 페이지 메시지(M1, M2, M3, M4)를 동일한 위치의 블록들끼리 XOR 연산하여 연산 메시지(M')를 생성한다. 연산 메시지(M')의 생성 방법은 도 9에 개시된 것과 실질적으로 동일하다.
외부 인코더(11)는 연산 메시지(M')를 외부 코드로 인코딩하여 패리티를 생성하고 이를 4개의 패리티 블록(P'1, P'2, P'3, P'4)으로 분할한다.
내부 인코더 블록(30)은 4개의 패리티 블록(P'1, P'2, P'3, P'4) 중 어느 하나와 4 개의 페이지 메시지(M1, M2, M3, M4) 중 어느 하나를 합하여 총 4개의 페이지 데이터를 생성하고 각 페이지 데이터에 대하여 내부 코드, 예를 들어 BC-BCH 코드,를 적용하여 인코딩함으로써 4 개의 심볼(S1, S2, S3, S4)을 생성한다.
도 12는 본 발명의 일 실시예에 의한 디코딩 장치를 나타내는 블록도이다.
이하에서는 현재 읽고자 하는 심볼을 제 1 심볼(S1)로 하고 제 1 심볼과 외부 코드에 의해 연관된 심볼을 제 2 내지 제 4 심볼로 한다.
본 발명의 일 실시예에 의한 디코딩 장치는 디코딩 제어부(40), 내부 디코더 블록(50), 메시지 연산부(60), 외부 디코더 블록(780) 및 메시지 선택부(80)를 포함한다.
디코딩 제어부(70)는 도 7 및 도 8을 참조하여 개시한 전반적인 디코딩 동작을 수행하며 이를 위하여 내부 디코더 블록(40), 외부 디코더 블록(70), 메시지 선택부(80)를 제어한다.
디코딩 제어부(40)는 디코딩 동작이 완료되는 경우 완료 플래그(C)를 활성화하여 출력하고, 디코딩 동작이 성공하는 경우 성공 플래그(S)를 활성화하여 출력할 수 있다.
내부 디코더 블록(50)은 4개의 내부 디코더(51)를 포함한다. 각 내부 디코더(41)는 대응하는 심볼을 읽어 이를 내부 코드, 예를 들어 BC-BCH 코드,를 이용하여 디코딩한다. 이때 각각의 내부 디코더(51)는 디코딩 과정에서 정정할 수 없는 오류가 발생하는 경우 오류 발생 여부 및 오류 발생 위치를 표시하는 오류 정보(e1, e2, e3, e4)를 디코딩 제어부(40)에 제공한다.
다른 실시예에서 내부 디코더(50) 블록은 하나의 내부 디코더(51)를 포함하여 4 개의 페이지들을 순차적으로 디코딩할 수도 있다.
제 1 심볼(S1)을 내부 코드로 디코딩한 결과 오류가 발생하지 않으면 오류 정보(e1)를 참조하여 디코딩 제어부(70)는 메시지 선택 신호(msel)를 비활성화하여 메시지 선택부(80)에서 내부 디코더(41)에서 디코딩된 메시지(m1)가 출력 메시지(M1)로서 선택되어 출력되도록 제어하고 디코딩 동작을 종료한다.
제 1 심볼(S1)을 내부 코드로 디코딩한 결과 오류가 발생하면 디코딩 제어부(40)는 오류 정보(e1)를 참조하여 오류 발생 블록의 위치 및 오류 발생 블록의 개수 등을 파악한다.
오류 발생 블록의 개수가 허용치를 초과하면 디코딩 제어부(40)는 성공 플래그(S)를 비활성화하고 종료 플래그(C)를 활성화한 후 디코딩 동작을 종료한다.
오류 발생 블록의 개수가 허용치 이내이면 디코딩 제어부(40)는 내부 디코더 제어 신호(idcon)에 따라 제 1 심볼(S1)과 연관된 제 2 내지 제 4 심볼(S2, S3, S4)을 디코딩하도록 내부 디코더 블록(50)을 제어한다.
제 2 내지 제 4 심볼(S2, S3, S4)들을 디코딩한 결과 오류가 발생하면 디코딩 제어부(40)는 오류 정보(e2, e3, e4)에 따라 오류 발생 블록의 위치 및 오류 발생 블록의 개수 등을 파악한다.
제 1 심볼(S1)의 디코딩 과정에서 발생한 오류를 포함하여 총 오류 발생 블록의 개수가 허용치를 초과하면 디코딩 제어부(40)는 성공 플래그(S)를 비활성화하고 종료 플래그(C)를 활성화한 후 디코딩 동작을 종료한다.
내부 디코더 블록(50)은 디코딩 결과 메시지(m1, m2, m3, m4)와 패리티 블록(p'1, p'2, p'3, p'4)을 출력한다.
메시지 연산부(60)는 각 메시지들을 같은 위치의 블록끼리 페이지 단위로 XOR 연산하여 연산 메시지(m')를 출력한다. 메시지 연산부(60)의 연산 동작은 도 9를 참조하여 개시한 바 있다.
외부 디코더 블록(70)은 제 1 외부 디코더(71)와 제 2 외부 디코더(72)를 포함한다.
제 1 외부 디코더(71)는 연산 메시지(m')를 복구하고, 제 2 외부 디코더(72)는 복구된 연산 메시지(m')와 메시지(m1, m2, m3, m4)를 이용하여 각 오류 블록들을 정정한다.
디코딩 제어부(40)는 오류 정보들로부터 오류가 발생한 블록의 위치 정보(el)를 외부 디코더 블록(70)에 제공한다.
제 1 외부 디코더(70)는 연산 메시지(m')에서 오류가 발생한 블록의 위치에 해당하는 블록을 미지수 블록으로 처리한다. 이후 제 1 외부 디코더(70)는 연산 메시지(m')와 패리티 블록(p'1, p'2, p'3, p'4)에 외부 코드를 적용하여 미지수 블록을 복구한다.
다른 실시예에서 제 1 외부 디코더(70)는 오류가 발생한 위치의 정보를 사용하지 않고 연산 메시지(m')를 복구할 수 있다. 이 경우 제 1 외부 디코더(70)는 오류가 발생한 위치를 찾는 구성까지 더 포함하게 되므로 본 실시예에 의한 제 1 외부 디코더(70)에 비추어 구성이 더 복잡해진다.
제 2 외부 디코더(72)는 복구된 연산 메시지(m')와 와 메시지(m1, m2, m3, m4)를 이용하여 오류가 발생한 메시지 블록들을 복구한다. 메시지 블록의 복구는 수학식 3의 연산을 통해 순차적으로 수행될 수 있다.
이때 오류가 발생한 메시지 블록의 위치가 중복된 경우 해당 블록에 대해서는 오류를 복구하지 않고 플래그(F)를 활성화한 후 다음 블록을 복구한다.
제 2 외부 디코더(72)는 플래그(F) 신호와 오류가 복구된 메시지(m1, m2, m3, m4)를 디코딩 제어부(40)에 제공한다.
플래그(F)가 비활성화된 경우 디코딩 제어부(40)는 성공 플래그(S)를 활성화하고 완료 플래그(C)를 활성화한 후 디코딩 동작을 종료한다. 이때 디코딩 제어부(40)는 메시지 선택 신호(msel)를 활성화하여 디코딩된 메시지(m1)가 출력 메시지(M1)로서 출력되도록 제어한다.
플래그(F)가 활성화된 경우 디코딩 제어부(40)는 전술한 동작을 반복 제어한다. 이때 디코딩 제어부(40)는 제 2 외부 디코더(72)에서 출력된 메시지(m1, m2, m3, m4)를 내부 디코더 블록(50)에 제공한다. 이를 이용하여 각 내부 디코더(51)는 기존에 디코딩을 통해 얻은 메시지(m1, m2, m3, m4)를 갱신하고, 갱신된 메시지에 대해서 정정 가능한 오류가 있는 경우 이를 정정하고 오류 정보(e1, e2, e3, e4)를 갱신한다.
이후의 동작은 전술한 바와 같이 반복된다. 디코딩 제어부(40)는 이러한 루프 반복 회수를 일정한 임계치 이내로 제한할 수 있다. 루프 반복 회수가 임계점을 초과하면 디코딩 제어부(40)는 성공 플래그(S)를 비활성화하고 완료 플래그(C)를 활성화한 후 종료한다.
도 13은 본 발명의 효과를 설명하는 그래프로서 4kB 크기의 페이지를 액세스 단위로 하는 메모리 셀 어레이에서의 에러 발생율을 나타낸다.
그래프에서 종래기술은 4kB 크기의 페이지를 BCH 코드로만 보호하는 경우를 나타내고 본 발명은 페이지의 크기가 4kB이고 전술한 실시예와 같이 각 페이지를 내부 코드인 BC-BCH 코드와 외부 코드인 RS 코드로 보호하는 경우를 나타낸다.
그래프의 가로축은 원 비트 에러율(Raw BER)로서 메모리 셀이 기본적으로 가지고 있는 에러율을 나타내고, 세로축은 코드워드 에러율(CER)로서 하나의 페이지를 읽는 경우의 에러율을 나타낸다. 그래프에서 실선은 시뮬레이션을 통해 도출된 결과이고 점선은 시뮬레이션 결과를 외삽하여 도출된 결과이다.
그래프를 통해 원 비트 에러율이 동일한 경우 본 발명이 종래 기술에 비하여 우수한 성능을 보여주는 것을 알 수 있다. 예를 들어 원 비트 에러율이 6.5 x 10-3인 경우를 기준으로 하면 코드워드 에러율(CER)은 종래에 비하여 약 천 분의 일로 줄어들고, 원 비트 에러율이 5 x 10-3인 경우를 기준으로 하면 코드워드 에러율(CER)은 종래에 비하여 약 백만 분의 일로 줄어들 것으로 예상된다.
이상에서 도면을 참조하여 본 발명의 실시예를 개시하였다. 이상의 개시는 설명을 위한 것으로서 본 발명의 권리범위를 한정하는 것은 아니며, 본 발명의 권리범위는 이하의 특허청구범위에 문언적으로 기재된 범위와 그 균등범위에 의해 정해진다.
100: 페이지 메시지
110: 메시지 블록
111: 하위 메시지 블록
200: 제 1 패리티
300: 제 2 패리티
310: 패리티 집합
320: 패리티 블록
400: 페이지 데이터
500: 행 패리티
510: 행 패리티 블록
600: 열 패리티
610: 열 패리티 블록
10: 외부 인코더 블록
11: 외부 인코더
20: 패리티 연산부
30: 내부 인코더 블록
31: 내부 인코더
40: 디코딩 제어부
50: 내부 디코더 블록
51: 내부 디코더
60: 메시지 연산부
70: 외부 디코더 블록
71: 제 1 외부 디코더
72; 제 2 외부 디코더
80: 메시지 선택부
110: 메시지 블록
111: 하위 메시지 블록
200: 제 1 패리티
300: 제 2 패리티
310: 패리티 집합
320: 패리티 블록
400: 페이지 데이터
500: 행 패리티
510: 행 패리티 블록
600: 열 패리티
610: 열 패리티 블록
10: 외부 인코더 블록
11: 외부 인코더
20: 패리티 연산부
30: 내부 인코더 블록
31: 내부 인코더
40: 디코딩 제어부
50: 내부 디코더 블록
51: 내부 디코더
60: 메시지 연산부
70: 외부 디코더 블록
71: 제 1 외부 디코더
72; 제 2 외부 디코더
80: 메시지 선택부
Claims (20)
- 다수 개의 메시지를 외부 코드로 인코딩하여 다수 개의 패리티 블록을 생성하는 제 1 단계;
상기 다수 개의 메시지와 상기 다수 개의 패리티 블록을 조합하여 다수 개의 메시지 데이터를 생성하는 제 2 단계; 및
상기 다수 개의 메시지 데이터 각각을 내부 코드로 인코딩하여 다수 개의 심볼을 생성하는 제 3 단계
를 포함하는 인코딩 방법. - 청구항 1에 있어서, 상기 제 1 단계는
상기 다수 개의 메시지 각각에 상기 외부 코드를 적용하여 다수의 제 1 패리티를 생성하는 단계;
상기 다수의 제 1 패리티를 연산하여 제 2 패리티를 생성하는 단계; 및
상기 제 2 패리티를 분할하여 상기 다수 개의 패리티 블록을 생성하는 단계
를 포함하는 인코딩 방법. - 청구항 1에 있어서, 상기 제 1 단계는
상기 다수 개의 메시지를 연산하여 연산 메시지를 생성하는 단계;
상기 연산 메시지를 상기 외부 코드로 인코딩하여 패리티를 생성하는 단계 및
상기 패리티를 분할하여 상기 다수 개의 패리티 블록을 생성하는 단계
를 포함하는 인코딩 방법. - 청구항 2에 있어서, 상기 제 2 단계에서 상기 다수 개의 메시지 데이터 각각은 상기 다수 개의 메시지 중 어느 하나와 상기 다수 개의 패리티 블록 중 어느 하나를 포함하는 인코딩 방법.
- 청구항 1에 있어서, 상기 제 1 단계는 상기 다수 개의 메시지 각각을 다수의 메시지 블록으로 분할하는 단계를 더 포함하는 인코딩 방법.
- 청구항 4에 있어서, 상기 제 3 단계는 상기 다수 개의 메시지 데이터에 포함되는 다수의 메시지 블록과 패리티 블록을 격자형으로 배치한 메시지 격자를 생성하는 단계;
상기 메시지 격자의 각 행에 대하여 행 코드를 생성하는 단계; 및
상기 메시지 격자의 각 열에 대하여 열 코드를 생성하는 단계
를 포함하는 인코딩 방법. - 외부 코드와 내부 코드에 따라 인코딩되어 메시지, 외부 패리티 및 내부 패리티를 포함하는 제 1 심볼을 디코딩하는 방법으로서
상기 제 1 심볼을 상기 내부 코드에 의해 디코딩하는 제 1 단계;
상기 제 1 단계에서 오류가 발생하는 경우 상기 외부 패리티를 통해 상기 제 1 심볼과 연관된 제 2 심볼을 상기 내부 코드에 의해 디코딩하는 제 2 단계; 및
상기 제 1 및 상기 제 2 단계에서 발생한 오류를 상기 외부 코드에 의해 정정하는 제 3 단계
를 포함하는 디코딩 방법. - 청구항 7에 있어서, 상기 3 단계는
상기 제 1 심볼을 디코딩하여 생성된 제 1 메시지와 상기 제 2 심볼을 디코딩하여 생성된 제 2 메시지를 연산하여 연산 메시지를 생성하는 단계;
상기 외부 패리티를 이용하여 상기 연산 메시지를 복원하는 단계; 및
상기 복원된 연산 메시지, 상기 제 1 메시지 및 상기 제 2 메시지를 이용하여 상기 제 1 메시지 및 상기 제 2 메시지의 오류를 정정하는 단계
를 포함하는 디코딩 방법. - 청구항 8에 있어서, 상기 제 3 단계는
제 1 메시지와 제 2 메시지에서 오류가 발생한 위치에 대응하는 상기 연산 메시지의 위치를 미지수 처리하는 단계를 더 포함하고, 상기 연산 메시지를 복원하는 단계는 상기 미지수 처리된 상기 연산 메시지의 위치를 복원하는 단계인 디코딩 방법. - 청구항 8에 있어서, 상기 제 3 단계를 수행한 결과 정정되지 않은 오류가 남아 있는 경우
상기 제 1 단계 및 상기 제 2 단계의 디코딩 결과 출력된 제 1 메시지, 제 2 메시지 및 외부 패리티를 상기 제 3 단계의 정정 결과를 이용하여 갱신하는 단계 및
상기 갱신 결과를 이용하여 상기 제 2 단계 및 제 3 단계를 반복하는 단계
를 더 포함하는 디코딩 방법. - 다수 개의 메시지를 외부 코드로 인코딩하여 다수 개의 패리티 블록을 생성하는 패리티 생성부; 및
상기 다수 개의 메시지와 상기 다수 개의 패리티 블록을 조합하여 다수 개의 메시지 데이터를 생성하고, 상기 다수 개의 메시지 데이터 각각을 내부 코드로 인코딩하여 다수 개의 심볼을 생성하는 내부 인코더 블록
을 포함하는 인코딩 장치. - 청구항 11에 있어서, 상기 패리티 생성부는
상기 다수 개의 메시지를 각각 상기 외부 코드로 인코딩하여 다수 개의 제 1 패리티를 생성하는 외부 인코더 블록; 및
상기 다수 개의 제 1 패리티를 연산하여 제 2 패리티를 생성하고 상기 제 2 패리티를 상기 다수 개의 패리티 블록으로 분할하는 패리티 연산부
를 포함하는 인코딩 장치. - 청구항 11에 있어서, 상기 패리티 생성부는
상기 다수 개의 메시지를 연산하여 연산 메시지를 생성하는 메시지 연산부 및;
상기 연산 메시지를 상기 외부 코드로 인코딩하여 패리티를 생성하고 상기 패리티를 상기 다수 개의 패리티 블록으로 분할하는 외부 인코더 블록
을 포함하는 인코딩 장치. - 외부 코드와 내부 코드에 따라 인코딩되어 메시지, 외부 패리티 및 내부 패리티를 포함하는 제 1 심볼을 디코딩하는 디코딩 장치로서
상기 외부 패리티에 의해 상기 제 1 심볼과 연관된 제 2 심볼과 상기 제 1 심볼을 상기 내부 코드에 의해 디코딩하는 내부 디코더 블록;
상기 제 1 심볼로부터 디코딩된 제 1 메시지와 상기 제 2 심볼로부터 디코딩된 제 2 메시지를 연산하여 연산 메시지를 생성하는 메시지 연산부 및
상기 외부 코드를 이용하여 상기 제 1 메시지 및 상기 제 2 메시지를 정정하는 외부 디코더 블록
을 포함하는 디코딩 장치. - 청구항 14에 있어서, 상기 외부 디코더 블록은
상기 외부 코드에 의해 상기 연산 메시지를 정정하는 제 1 외부 디코더; 및
상기 정정된 연산 메시지와 상기 제 1 메시지 및 상기 제 2 메시지를 연산하여 상기 제 1 메시지 및 상기 제 2 메시지를 정정하는 제 2 외부 디코더
를 포함하는 디코딩 장치. - 청구항 15에 있어서, 상기 제 1 외부 디코더는 상기 제 1 메시지 및 상기 제 2 메시지의 오류 위치에 대응하는 위치에서 상기 연산 메시지를 정정하는 디코딩 장치.
- 청구항 14에 있어서, 상기 내부 디코더 블록 및 상기 외부 디코더 블록을 제어하는 디코딩 제어부를 더 포함하는 디코딩 장치.
- 청구항 17에 있어서, 상기 외부 디코더 블록은 정정되지 않은 오류가 존재하는 경우 에러 플래그를 활성화하고, 상기 디코딩 제어부는 상기 에러 플래그가 활성화된 경우 상기 외부 디코더 블록에서 정정된 제 1 메시지 및 제 2 메시지를 상기 내부 디코더 블록에 제공하고, 상기 내부 디코더 블록은 내부 코드에 따라 상기 디코딩 제어부에서 제공된 제 1 메시지 및 제 2 메시지를 정정하는 디코딩 장치.
- 청구항 18에 있어서, 상기 외부 디코더 블록은 상기 제 1 메시지 및 상기 제 2 메시지의 동일한 위치에 오류가 있는 경우 상기 에러 플래그를 활성화하는 디코딩 장치.
- 청구항 18에 있어서, 상기 디코딩 제어부의 제어에 따라 상기 내부 디코더 블록에서 디코딩된 상기 제 1 메시지 또는 상기 외부 디코더 블록에서 정정된 제 1 메시지를 선택하여 출력하는 메시지 선택부를 더 포함하는 디코딩 장치.
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020140100995A KR20160017820A (ko) | 2014-08-06 | 2014-08-06 | 코딩 방법 및 코딩 장치 |
| US14/546,685 US20160043741A1 (en) | 2014-08-06 | 2014-11-18 | Coding method and device |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020140100995A KR20160017820A (ko) | 2014-08-06 | 2014-08-06 | 코딩 방법 및 코딩 장치 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| KR20160017820A true KR20160017820A (ko) | 2016-02-17 |
Family
ID=55268215
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| KR1020140100995A Withdrawn KR20160017820A (ko) | 2014-08-06 | 2014-08-06 | 코딩 방법 및 코딩 장치 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US20160043741A1 (ko) |
| KR (1) | KR20160017820A (ko) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2022092353A1 (ko) * | 2020-10-29 | 2022-05-05 | 엘지전자 주식회사 | 무선 통신 시스템에서 채널 인코딩 및 디코딩을 수행하기 위한 방법 및 장치 |
Family Cites Families (22)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0619913B2 (ja) * | 1984-03-30 | 1994-03-16 | パイオニア株式会社 | ビデオフオ−マツト信号に担持されるデ−タのエラ−訂正方式 |
| US5172381A (en) * | 1989-04-27 | 1992-12-15 | International Business Machines Corporation | Enhanced data formats and machine operations for enabling error correction |
| EP0523969B1 (en) * | 1991-07-18 | 1997-12-29 | Canon Kabushiki Kaisha | Error correction encoding and decoding system |
| US5309451A (en) * | 1992-08-12 | 1994-05-03 | Digital Equipment Corporation | Data and parity prefetching for redundant arrays of disk drives |
| JP3328093B2 (ja) * | 1994-07-12 | 2002-09-24 | 三菱電機株式会社 | エラー訂正装置 |
| US6023783A (en) * | 1996-05-15 | 2000-02-08 | California Institute Of Technology | Hybrid concatenated codes and iterative decoding |
| US6351832B1 (en) * | 1999-05-28 | 2002-02-26 | Lucent Technologies Inc. | Turbo code symbol interleaver |
| US6266795B1 (en) * | 1999-05-28 | 2001-07-24 | Lucent Technologies Inc. | Turbo code termination |
| US6473878B1 (en) * | 1999-05-28 | 2002-10-29 | Lucent Technologies Inc. | Serial-concatenated turbo codes |
| US7356752B2 (en) * | 2000-03-14 | 2008-04-08 | Comtech Telecommunications Corp. | Enhanced turbo product codes |
| US6807238B1 (en) * | 2001-02-01 | 2004-10-19 | Lsi Logic Corporation | Method and apparatus for decoding M-PSK turbo code using new approximation technique |
| US7107505B2 (en) * | 2001-03-27 | 2006-09-12 | Comtech Aha Corporation | Concatenated turbo product codes for high performance satellite and terrestrial communications |
| US8656246B2 (en) * | 2001-04-16 | 2014-02-18 | Qualcomm Incorporated | Method and an apparatus for use of codes in multicast transmission |
| US6697996B2 (en) * | 2001-05-18 | 2004-02-24 | Lockheed Martin Corp. | Multi-dimensional packet recovery system and method |
| US20030093740A1 (en) * | 2001-10-19 | 2003-05-15 | Nebojsa Stojanovic | Iterative hard decoding method for multidimensional SPC |
| EP1359672A1 (en) * | 2002-05-03 | 2003-11-05 | Siemens Aktiengesellschaft | Method for improving the performance of concatenated codes |
| US7206987B2 (en) * | 2003-04-30 | 2007-04-17 | Hewlett-Packard Development Company, L.P. | Error detection and correction in a layered, 3-dimensional storage architecture |
| US7895498B2 (en) * | 2004-09-09 | 2011-02-22 | Mitsubishi Electric Corporation | Apparatuses and method for error correction coding and error correction decoding |
| US8132073B1 (en) * | 2009-06-30 | 2012-03-06 | Emc Corporation | Distributed storage system with enhanced security |
| US8438344B2 (en) * | 2010-03-12 | 2013-05-07 | Texas Instruments Incorporated | Low overhead and timing improved architecture for performing error checking and correction for memories and buses in system-on-chips, and other circuits, systems and processes |
| US9166626B2 (en) * | 2011-11-18 | 2015-10-20 | Korea Advanced Institute Of Science And Technology | Encoding, decoding, and multi-stage decoding circuits for concatenated BCH, and error correction circuit of flash memory device using the same |
| US9666225B2 (en) * | 2015-10-26 | 2017-05-30 | International Business Machines Corporation | Efficient recovery of the codeword interleave address |
-
2014
- 2014-08-06 KR KR1020140100995A patent/KR20160017820A/ko not_active Withdrawn
- 2014-11-18 US US14/546,685 patent/US20160043741A1/en not_active Abandoned
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2022092353A1 (ko) * | 2020-10-29 | 2022-05-05 | 엘지전자 주식회사 | 무선 통신 시스템에서 채널 인코딩 및 디코딩을 수행하기 위한 방법 및 장치 |
Also Published As
| Publication number | Publication date |
|---|---|
| US20160043741A1 (en) | 2016-02-11 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US20200401475A1 (en) | Detection and correction of data bit errors using error correction codes | |
| US9654147B2 (en) | Concatenated error correction device | |
| US10333558B2 (en) | Decoding device and decoding method | |
| WO2017194013A1 (zh) | 纠错编码方法及装置 | |
| US20210218419A1 (en) | Method, device and apparatus for storing data, computer readable storage medium | |
| US10291258B2 (en) | Error correcting code for correcting single symbol errors and detecting double bit errors | |
| US9960788B2 (en) | Memory controller, semiconductor memory device, and control method for semiconductor memory device | |
| JP2019057752A (ja) | メモリシステム | |
| JP2014022848A (ja) | 誤り訂正符号の符号化方法及び復号方法 | |
| JP7429223B2 (ja) | ターボ積符号の復号方法、装置、デコーダー及びコンピュータ記憶媒体 | |
| JP2013029882A (ja) | メモリコントローラ、半導体記憶装置および復号方法 | |
| JP2020042512A (ja) | メモリシステム | |
| US20150200686A1 (en) | Encoding device, decoding device, and operating method thereof | |
| CN108270518A (zh) | 用以解码接收息的解码方法与相关解码装置 | |
| JP2012050008A (ja) | 誤り検出訂正方法および半導体メモリ装置 | |
| US20200089417A1 (en) | Memory system | |
| CN113489995B (zh) | 用以解码接收信息的解码方法与相关解码装置 | |
| US12119841B2 (en) | G-LDPC decoder and G-LDPC decoding method | |
| US10970166B2 (en) | Memory system and method of controlling non-volatile memory | |
| KR20160017820A (ko) | 코딩 방법 및 코딩 장치 | |
| CN107659319A (zh) | 一种对Turbo乘积码编码的方法和装置 | |
| JP2021044750A (ja) | メモリシステム | |
| US10951238B1 (en) | Memory system and method for controlling non-volatile memory | |
| CN110289863B (zh) | 译码设备、方法及信号传输系统 | |
| KR101496052B1 (ko) | 블록 단위 연접 bch 부호 성능 개선 및 오류마루 경감을 위해 순환 자리 이동을 활용하는 복호 기법 및 회로 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PA0109 | Patent application |
Patent event code: PA01091R01D Comment text: Patent Application Patent event date: 20140806 |
|
| 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 |