KR20170097580A - 폴라 코딩 장치 - Google Patents

폴라 코딩 장치 Download PDF

Info

Publication number
KR20170097580A
KR20170097580A KR1020170021711A KR20170021711A KR20170097580A KR 20170097580 A KR20170097580 A KR 20170097580A KR 1020170021711 A KR1020170021711 A KR 1020170021711A KR 20170021711 A KR20170021711 A KR 20170021711A KR 20170097580 A KR20170097580 A KR 20170097580A
Authority
KR
South Korea
Prior art keywords
rti
code
matrix
length
graph
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.)
Granted
Application number
KR1020170021711A
Other languages
English (en)
Other versions
KR102601215B1 (ko
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 삼성전자주식회사
Publication of KR20170097580A publication Critical patent/KR20170097580A/ko
Application granted granted Critical
Publication of KR102601215B1 publication Critical patent/KR102601215B1/ko
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

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/2921—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 wherein error correction coding involves a diagonal direction
    • H03M13/2924—Cross interleaved Reed-Solomon codes [CIRC]
    • 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/1575—Direct decoding, e.g. by a direct determination of the error locator polynomial from syndromes and subsequent analysis or by matrix operations involving syndromes, e.g. for codes with a small minimum Hamming distance
    • 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
    • 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/134—Non-binary linear block codes not provided for otherwise
    • 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/25—Error detection or forward error correction by signal space coding, i.e. adding redundancy in the signal constellation, e.g. Trellis Coded Modulation [TCM]
    • H03M13/256—Error detection or forward error correction by signal space coding, i.e. adding redundancy in the signal constellation, e.g. Trellis Coded Modulation [TCM] with trellis coding, e.g. with convolutional codes and TCM
    • 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/61—Aspects and characteristics of methods and arrangements for error correction or error detection, not provided for otherwise
    • H03M13/615—Use of computational or mathematical techniques
    • H03M13/616—Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations
    • 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/61—Aspects and characteristics of methods and arrangements for error correction or error detection, not provided for otherwise
    • H03M13/618—Shortening and extension of 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/63—Joint error correction and other techniques
    • H03M13/635—Error control coding in combination with rate matching
    • H03M13/6362—Error control coding in combination with rate matching by puncturing
    • 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/6502—Reduction of hardware complexity or efficient processing
    • 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/6508—Flexibility, adaptability, parametrability and configurability of the implementation
    • H03M13/6516—Support of multiple code parameters, e.g. generalized Reed-Solomon decoder for a variety of generator polynomials or Galois fields

Landscapes

  • Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • Probability & Statistics with Applications (AREA)
  • Theoretical Computer Science (AREA)
  • Mathematical Physics (AREA)
  • General Physics & Mathematics (AREA)
  • Pure & Applied Mathematics (AREA)
  • Algebra (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Computing Systems (AREA)
  • Error Detection And Correction (AREA)

Abstract

Figure pat00131
변환을 구현하는 인코더 회로와 코드 워드 C를 전송 채널을 통해 전송하는 전송기 회로를 포함하는 폴라 코딩 장치가 개시된다. 여기서,
Figure pat00132
, BN -s,
Figure pat00133
및 C는 갈로아 필드(Galois field)(GF(2k), k>1)에 대해 정의되고, N=2n, s<N,
Figure pat00134
= (u1, ..., uN-s)는 갈로아 필드(GF(2k))에 대한 N-s 개의 입력 벡터이고, BN -s 는 순열 행렬(permutation matrix),
Figure pat00135
이고, 행렬 M1 은 크기 q × q, 2 <q 및 N = qn 의 미리 정의된 행렬이고, C는 N-s 개의 심볼들의 코드 워드 벡터이며, C의 디코딩 복잡도는 C에서의 심볼 수에 비례한다.

Description

폴라 코딩 장치{APPARATUS FOR POLAR CODING}
본 발명의 실시 예들은 에러 정정 코드(ECC: error correcting code)에 관한 것으로, 더 상세하게는, 채널 편파 코드(channel polarization code)의 변형에 관한 것이다.
블록 코드(block code)는 에러 정정 코드(ECC)의 중요한 패밀리이다. 이러한 코드는 정보 비트들의 고정된 블록에 대해 동작한다. 각각의 인코딩 동작에서, k 개의 정보 비트들의 벡터는 N 심볼들-이진 코드들의 경우에는 N 비트들-의 (리던던트) 벡터로 인코딩된다. 부호화된 비트 수 N은 코드의 블록 길이라고 불린다.
폴라 코드(polar code)는 어달 알칸(Erdal Arkan)에 의해 개발된 선형 블록 에러 정정 코드로, 대칭의 이진(binary) 입력, 이산(discrete), 무 메모리(memoryless) 채널(B-DMC)에 대한 채널 용량을 실질적인 복잡성(practical complexity)으로 달성하는 명시적인 구조의 첫 번째 코드이다. 폴라 코드는 길이 N = 2n(n은 양의 정수)의 코드로 정의되며, 디코딩 복잡도가 O(N log N)인 알고리즘이 존재한다. 예를 들어, n = 10의 경우 길이 1024의 폴라 코드가 있다.
폴라 코드는 용량 달성 특성 때문에 NAND 플래시 장치에 적합한 코드 일 수 있다. NAND 플래시 장치에 대한 폴라 ECC 방식을 설계하기 위해 해결해야 하는 첫 번째 문제 중 하나는 길이 호환성(length compatibility)이다. 일반적으로 ECC의 다양한 응용에서, 코드의 길이는 주어진 길이에 맞게 조정할 필요가 있다. 그러나, 많은 패밀리의 코드들에서, 채널 편파 코드들의 경우에서와 같이, 블록 길이는 임의로 선택될 수 없고, 이러한 상황을 다루기 위해 문헌에 공지된 많은 기성(off-the-shelf)의 방법들이 있다.
솔리드 스테이트 드라이브 및 다른 NAND 플래시 메모리 장치와 같은 많은 통신 및 저장 시스템에서, 정보 비트의 수 k는 2의 정수 승(integral power of two)(즉, 2n, n은 양의 정수)이다. 이는 블록의 길이를 2의 정수 승이 되지 않게 한다. 지난 수년간 여러 저자에 의해 제안된 바와 같이, 단축(shortening)와 펑처링(puncturing)의 알려진 방법이 이 코드에도 적용될 수 있다.
ECC 기법의 디코딩 복잡도는 ECC 시스템의 또 다른 중요한 성능 특성이다. 코드의 블록 길이를 조정하기 위한 기성의 방법은 조정 이전에 코드의 원래 블록 길이와 관련된 디코딩 복잡성으로 끝난다. 대부분의 경우에, 채널 편파 코드들에서와 같이, 원래 블록 길이는 목표 블록 길이보다 크다(때로는 훨씬 더 크고, 예를 들어 대략 2 배가된다). 이는 실제 전송/저장된 블록으로 인해 예상되는 것보다 디코딩 복잡성이 상당히 클 수 있다.
예를 들어, 펑처링(puncturing)이라고 하는 기술은 특정 비트를 전송하지 않고 펑처링된 비트에 대해 비유용한 정보 (LLR = 0)를 고정시키면서 전체 길이 폴라 코드(full length polar code)에 대해 풀 디코더(full decoder)를 동작시키는 것을 포함한다. 이러한 동작들은 전체 코드 그래프(code graph)에서 수행되므로 복잡도는 전체 길이의 폴라 코드와 일치하며 펑처링된 길이의 폴라 코드와 일치하지 않는다. 종래의 다른 방법은 단축(쇼트닝, shortening)이라고 하며, 무한(최대 레벨) LLR(log-likelihood ratio) 값을 갖는 풀 디코더를 동작시키는 것을 포함한다. 이 방법은 코딩된 비트들 중 일부가 선험적(예를 들어, 0 비트)으로 알려져 있는 방식으로 정보 비트를 인코딩하는 것을 허용한다. 이것이 통신 시나리오에서 이러한 비트를 저장하거나 전송할 필요가 없는 이유이다. 그러나, 디코더에서, 풀(FULL) 디코더는 단축된 비트에 대한 완전한 정보를 갖는 동안 동작한다.
본 발명이 이루고자 하는 기술적인 과제는 목표 길이(target length)와 관련된 디코딩 복잡도로 동작하면서 임의의 블록 길이(arbitrary block length)의 채널 편파 코드(channel polarization codes)를 제공하는 장치 및 방법을 제공하는 것이다.
본 발명의 일 실시예에 따르면,
Figure pat00001
변환을 구현하는 인코더 회로; 및 코드 워드 C를 전송 채널을 통해 전송하는 전송기 회로를 포함하는 폴라 코딩 장치가 제공된다.
Figure pat00002
, BN -s,
Figure pat00003
및 C는 갈로아 필드(Galois field)(GF(2k), k>1)에 대해 정의되고, N=2n, s<N,
Figure pat00004
= (u1, ..., uN-s)는 갈로아 필드(GF(2k))에 대한 N-s 개의 입력 벡터이고, BN -s는 순열 행렬(permutation matrix),
Figure pat00005
이고, 행렬 M1 은 크기 q × q, 2 <q 및 N = qn 의 미리 정의된 행렬이고, C는 N-s 개의 심볼들의 코드 워드 벡터이며, C의 디코딩 복잡도는 C에서의 심볼 수에 비례한다.
실시예에 따라, 집합
Figure pat00006
에 대하여, ui = 0
Figure pat00007
이다.
실시예에 따라,
Figure pat00008
이다.
실시예에 따라,
Figure pat00009
, BN -s, M1 및 대응하는 산술 연산은 갈루아 필드 GF (2)에 대해 정의된다.
실시예에 따라, 상기 순열 행렬 BN -s 는 비트 역전 행렬(bit reversal matrix)이다.
실시예에 따라, 상기 장치는 전송 채널로부터 출력 워드(
Figure pat00010
)를 수신하는 수신기 회로; 및 상기 출력 워드(
Figure pat00011
)로부터 정보 비트(
Figure pat00012
)의 추정치(
Figure pat00013
)를 생성하는 디코더 회로를 더 포함하며, 상기
Figure pat00014
는 미리 결정된 유한 알파벳에 대해 정의된 크기 N-s의 벡터이다.
실시예에 따라,상기 M1 은
Figure pat00015
이다.
본 발명의 다른 실시예에 따르면, 전송 채널로부터 출력 워드(
Figure pat00016
)를 수신하는 수신기 회로; 및 상기 출력 워드(
Figure pat00017
)로부터 정보 비트(
Figure pat00018
)의 추정치(
Figure pat00019
)를 생성하는 디코더 회로를 포함하는 폴라 코딩 장치가 제공된다.
상기
Figure pat00020
는 미리 결정된 유한 알파벳에 대해 정의된 크기 N-s의 벡터이고, 상기 출력 워드(
Figure pat00021
)는
Figure pat00022
에 의해, 입력 워드(
Figure pat00023
)와 연관되고,
Figure pat00024
, BN -s,
Figure pat00025
및
Figure pat00026
는 갈로아 필드(Galois field)(GF(2k), k>1)에 대해 정의되며, N=2n, s<N,
Figure pat00027
= (u1,..., uN-s)는 N-s 비트의 입력 벡터이고, BN-s 는 순열 행렬(permutation matrix),
Figure pat00028
이고, 행렬 M1은 크기 q × q, 2 <q 및 N = qn 의 미리 정의된 행렬이고, f는 확률적 함수이고,
Figure pat00029
의 디코딩 복잡도는
Figure pat00030
에서의 심볼 수에 비례한다.
실시예에 따라, 집합
Figure pat00031
에 대하여, ui = 0
Figure pat00032
이다.
실시예에 따라,
Figure pat00033
이다.
실시예에 따라,
Figure pat00034
, BN -s, M1 및 대응하는 산술 연산은 갈루아 필드 GF (2)에 대해 정의된다.
실시예에 따라, 상기 순열 행렬 BN -s 는 비트 역전 행렬(bit reversal matrix)이다.
실시예에 따라, 상기 장치는 변환(
Figure pat00035
)을 구현하는 인코더 회로; 및 전송 채널/저장 매체를 통해 코드워드(
Figure pat00036
)를 전송/저장하는 전송기/저장 회로를 더 포함한다.
실시예에 따라,상기 M1 은
Figure pat00037
이다.
본 발명의 실시예에 따르면, 목표 길이와 관련된 디코딩 복잡도로 동작하면서 임의의 블록 길이의 채널 편파 코드, 즉 폴라 코드를 제공할 수 있다.
즉, 본 발명의 실시예에 따르면, 임의의 블록 길이(arbitrary block length)을 갖는 폴라 코드를 제공하면서, 디코딩 복잡도를 줄임으로써, 하드웨어 비용 및 전력 소모 측면에서 상당한 효과를 얻을 수 있다.
본 발명의 상세한 설명에서 인용되는 도면을 보다 충분히 이해하기 위하여 각 도면의 간단한 설명이 제공된다.
도 1a 및 도 1b는 본 발명의 일 실시예에 따른 폴라 코드의 부호화 그래프 및 복호화 그래프의 예를 나타내는 도면이다.
도 2는 본 발명의 일 실시예에 따른 인코더 그래프의 슬라이싱(slicing)을 도시한다.
도 3은 본 발명의 일 실시예에 따른, 디코더 그래프의 슬라이싱을 도시한다.
도 4는 동등하고 거의 동일한 슬라이싱 위치가 있는 슬라이싱을 위한 다른 방법을 도시한다.
도 5는 본 발명의 일 실시예에 따른 결과 그래프를 도시한다.
도 6은 본 발명의 일 실시예에 따른 다른 슬라이싱의 디코더 그래프를 도시한다.
도 7은 본 발명의 일 실시 예에 따른 슬라이스 인코딩/디코딩을 수행하기 위한 장치의 블록도이다.
본 명세서에 개시되어 있는 본 발명의 개념에 따른 실시 예들에 대해서 특정한 구조적 또는 기능적 설명은 단지 본 발명의 개념에 따른 실시 예들을 설명하기 위한 목적으로 예시된 것으로서, 본 발명의 개념에 따른 실시 예들은 다양한 형태들로 실시될 수 있으며 본 명세서에 설명된 실시 예들에 한정되지 않는다.
본 발명의 개념에 따른 실시 예들은 다양한 변경들을 가할 수 있고 여러 가지 형태들을 가질 수 있으므로 실시 예들을 도면에 예시하고 본 명세서에서 상세하게 설명하고자 한다. 그러나, 이는 본 발명의 개념에 따른 실시 예들을 특정한 개시 형태들에 대해 한정하려는 것이 아니며, 본 발명의 사상 및 기술 범위에 포함되는 모든 변경, 균등물, 또는 대체물을 포함한다.
제1 또는 제2 등의 용어는 다양한 구성 요소들을 설명하는데 사용될 수 있지만, 상기 구성 요소들은 상기 용어들에 의해 한정되어서는 안 된다. 상기 용어들은 하나의 구성 요소를 다른 구성 요소로부터 구별하는 목적으로만, 예컨대 본 발명의 개념에 따른 권리 범위로부터 벗어나지 않은 채, 제1구성 요소는 제2구성 요소로 명명될 수 있고 유사하게 제2구성 요소는 제1구성 요소로도 명명될 수 있다.
어떤 구성 요소가 다른 구성 요소에 "연결되어" 있다거나 "접속되어" 있다고 언급된 때에는, 그 다른 구성 요소에 직접적으로 연결되어 있거나 또는 접속되어 있을 수도 있지만, 중간에 다른 구성 요소가 존재할 수도 있다고 이해되어야 할 것이다. 반면에, 어떤 구성 요소가 다른 구성 요소에 "직접 연결되어" 있다거나 "직접 접속되어" 있다고 언급된 때에는 중간에 다른 구성 요소가 존재하지 않는 것으로 이해되어야 할 것이다. 구성 요소들 간의 관계를 설명하는 다른 표현들, 즉 "~사이에"와 "바로 ~사이에" 또는 "~에 이웃하는"과 "~에 직접 이웃하는" 등도 마찬가지로 해석되어야 한다.
본 명세서에서 사용한 용어는 단지 특정한 실시 예를 설명하기 위해 사용된 것으로서, 본 발명을 한정하려는 의도가 아니다. 단수의 표현은 문맥상 명백하게 다르게 뜻하지 않는 한, 복수의 표현을 포함한다. 본 명세서에서, "포함하다" 또는 "가지다" 등의 용어는 본 명세서에 기재된 특징, 숫자, 단계, 동작, 구성 요소, 부분품 또는 이들을 조합한 것이 존재함을 지정하려는 것이지, 하나 또는 그 이상의 다른 특징들이나 숫자, 단계, 동작, 구성 요소, 부분품 또는 이들을 조합한 것들의 존재 또는 부가 가능성을 미리 배제하지 않는 것으로 이해되어야 한다.
다르게 정의되지 않는 한, 기술적이거나 과학적인 용어를 포함해서 여기서 사용되는 모든 용어들은 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자에 의해 일반적으로 이해되는 것과 동일한 의미를 나타낸다. 일반적으로 사용되는 사전에 정의되어 있는 것과 같은 용어들은 관련 기술의 문맥상 가지는 의미와 일치하는 의미를 갖는 것으로 해석되어야 하며, 본 명세서에서 명백하게 정의하지 않는 한, 이상적이거나 과도하게 형식적인 의미로 해석되지 않는다.
이하, 본 명세서에 첨부된 도면들을 참조하여 본 발명의 실시 예들을 상세히 설명한다.
여기에 기술된 바와 같은 본 발명의 예시적인 실시 예들은 일반적으로 목표 길이(target length)와 관련된 디코딩 복잡도로 동작하면서 임의의 블록 길이의 채널 편파 코드(channel polarization code)를 제공하는 시스템 및 방법을 제공한다. 실시 예들은 다양한 수정들 및 대안적인 형태들에 영향을 받기 쉽지만, 그것들의 특정 실시예들은 도면들에서 예로서 도시되고 여기에 상세히 설명될 것이다.
채널 편파(Channel polarization)는 B-DMC W의 N 개의 독립적인 사본의 제1 세트로부터 N 개의 2 진 입력 채널
Figure pat00038
의 제2 세트를 구성하는 동작으로서, N이 커질수록 대칭 채널 용량
Figure pat00039
이 1에 가까운 지표 i의 비율(fraction)은 I(W)로 표시되는 채널 용량에 가까워지고,
Figure pat00040
가 0에 가까운 비율은 1- I(W)에 접근한다.
채널 편파 동작은 채널 결합 단계(channel combining phase) 및 채널 분할 단계(channel splitting phase)를 포함한다. 이러한 원칙을 기반으로 구성된 코드를 폴라 코드(또는 극 부호)(polar code)라고 한다. 다음 설명에서, 모든 스칼라, 벡터, 행렬 및 이들에 대한 연산은 이진 필드(binary field) GF(2) 상의 벡터 공간에서 수행된다. 그러나, 실시예들은 이진 필드(GF(2)) 상의 벡터 공간에 한정되지 않으며, 본 발명의 실시예들은 N이 양의 정수인 임의의 이산 필드(discrete field) GF(N) 상의 벡터 공간에 적용 가능하다. 커널(kernel)이 더 이상 2x2 행렬이 아닌 아리칸(Arikan)의 오리지널 코드에 대한 일반화가 있으며, 코드가 비-이진 알파벳(non-binary alphabets) 상에 구성되는 다른 일반화가 있다. 본 발명의 실시 예에 따른 슬라이싱은 그래프와 관련하여 이들 방법 모두에 대해 수행될 수 있다.
표기
Figure pat00041
는 행(row) 벡터 (a1, ..., aN)를 나타낸다. 폴라 코딩(Polar coding)은 각 좌표 채널
Figure pat00042
에 개별적으로 액세스할 수 있고 최대 우도 결정 오류 확률(probability of maximum-likelihood decision error)이 0에 가까운 부호를 통해 데이터를 전송하는 코딩 시스템을 생성한다. 폴라 코딩에서는
Figure pat00043
은 채널(WN)을 통해 전송되는 코드 워드(
Figure pat00044
)로 인코딩되고, 채널 출력은
Figure pat00045
이다.
채널 결합은 주어진 B-DMC W의 복사본을 재귀적으로 결합하여 벡터 채널 WN: XN -> YN 을 생성한다. 여기서 N = 2n, n은 양의 정수이다. 합성 채널 WN 의 입력(
Figure pat00046
)을 기본 원시 채널 WN 의 입력(
Figure pat00047
)으로의 인코딩은
Figure pat00048
으로 표현될 수 있다. 여기서 GN 은 다음의 수학식 1에 의해 정의되는 생성 행렬(generator matrix)이다.
Figure pat00049
임의의 N = 2n, n> = 2 일 때, BN은 비트 반전 행렬(bit-reversal matrix)이고
Figure pat00050
는
Figure pat00051
의 n 번째 크로네커 승(Kronecker power)이다. 여기서,
Figure pat00052
는 행렬의 크로네커(Kronecker) 곱셈을 나타낸다.
두 채널(WN 및 WN)의 전이 확률(transition probabilities)은 다음 수학식 2와 같은 관계를 갖는다.
Figure pat00053
크기 K의 {1, ..., N}의 임의의 부분 집합 A에 대하여, 수학식1은 로 표현될 수 있다.
여기서, GN(A)는 A에서 인덱스를 가지는 행(rows)에 의해 형성된 GN의 서브행렬을 나타낸다. uA 를 고정시키지 않고, A와
Figure pat00055
가 고정되면 소스 블록 uA 에서 코드 워드
Figure pat00056
으로의 매핑이 얻어진다. A는 정보 집합으로 불리며,
Figure pat00057
는 고정된 비트 또는 벡터로 불린다.
채널 분할은 WN 을 다음 수학식의 전이 확률(transition probabilities)로 정의되는 N 개의 이진 입력 좌표 채널들(binary-input coordinate channels)의 집합
Figure pat00058
으로 되돌린다.
Figure pat00059
여기서,
Figure pat00060
은
Figure pat00061
의 출력 및 ui 의 입력을 나타낸다.
도 1a는 N = 8에 대한 인코더를 나타낸다. 회로에 대한 입력은
Figure pat00062
의 비트 반전된 버전(bit-reversed version), 즉
Figure pat00063
이다. 신호는 왼쪽에서 오른쪽으로 전달된다. 각 에지(edge)는 신호 0 또는 1을 전달한다. 각 노드는 왼쪽에서 들어오는 모든 에지의 신호를 더하고(mod-2), 오른쪽의 모든 에지로 결과를 보낸다.
출력은
Figure pat00064
에 의해 주어진다. 일반적으로, 이 구현의 복잡성은 BN에 대해서는 O(N),
Figure pat00065
에 대해서는 O (N log N)을 가지는 O(N log N) 이다.
도 1b는 N = 8에 대한 디코더를 도시한다. 채널 출력이
Figure pat00066
이면, 디코더의 작업은 A,
Figure pat00067
, and
Figure pat00068
이 주어질 때,
Figure pat00069
의 추정치
Figure pat00070
를 생성하는 것이다. 디코더는
Figure pat00071
를 설정함으로써 고정된 부분을 고정하고, 이는 uA 의 추정치(
Figure pat00072
)를 생성하는 디코딩 태스크를 줄인다. 디코더는 소스 벡터(
Figure pat00073
)의 각 요소(ui )에 대해 하나씩의 결정 요소(DEs)를 포함하며 일반적으로 그래프에 대한 노드 처리 일정(schedule)이 있다. 이는 특정 스케줄링에만 국한되지는 않으며, 모든 디코딩 알고리즘은, 하드웨어/소프트웨어 리소스에 따라 달라질 수 있는 가능한 자체 작업 스케줄 세트를 가지고 있다.
이제 일정에 따라 데이터 처리가 그래프 내로 쇄도하고, 처리는 노드들에서 수행되고, 데이터는 에지를 기반으로 전송된다. 노드(ui)에 대해, 입력은 관심 비율(ratio of interest)을 생성하는 데 사용할 수 있는 임시 메시지일 수 있다.
도 1b에 도시된 바와 같이, 본 발명의 비제한적인 실시 예에서, DE는 1에서 N까지의 순서로 활성화될 수 있다.
Figure pat00074
이고, 원소가 알려져 있으면, i 번째 DE는 차례가 되면,
Figure pat00075
로 단순히 설정하여, 이 결과를 모든 후속 DE에 보낸다.
모든 중간 노드는 두 개의 왼쪽 인접 노드가 처리를 끝내자마자, 특정 이전 결정(previous decisions)(
Figure pat00076
)을 사용할 수 있게 되는 즉시 활성화될 수 있다.
Figure pat00077
이면, i 번째 DE는 이전 결정(
Figure pat00078
)을 수신할 때까지 기다리고, 두 개의 왼쪽 노드가 자신의 처리를 끝내고, 이를 수신하자마자 이전의 결정과 임시 중간 노드 메시지에 기초하여, 우도 비(LR: likelihood ratio)
Figure pat00079
를 산출하고, 그 결정을
Figure pat00080
로 생성할 수 있으며, 그 결정은 모든 성공 DE들로 전송된다.
이 알고리즘의 복잡성은 기본적으로 LR을 계산하는 복잡성에 의해 결정된다.
그래프의 각 노드는 알고리즘 과정에서 발생하는 LR 요청을 계산한다. 왼쪽에서 시작하여 노드의 첫 번째 열(column)은 길이 8(결정 레벨)의 LR 요청, 노드의 두 번째 열은 길이 4의 요청, 세 번째는 길이 2, 및 네 번째는 길이 1(채널 수준)에 해당한다. 그래프의 각 노드는 두 개의 라벨(label)을 가진다. 제1 라벨은 계산할 LR 값을 나타내며 제2 라벨은 이 노드가 활성화될 시기를 나타낸다. 도 1b와 관련하여 도시된 노드 프로세싱의 스케줄은, 예시적이고 비 제한적임을 이해해야 하며, 본 발명의 다른 실시 예에서는, 계산의 방향이 완전히 다른, 다른 스케줄이 있다.
본 발명의 실시 예들은 가변 길이의 폴라 코드들의 구성에 관한 것이다. 폴라 코드의 원래 구성은
Figure pat00081
에 대하여 길이(
Figure pat00082
)의 코드를 생성하지만 실용적인 고려 사항은 분명히 다른 유형의 길이를 요구할 수 있다. 예를 들어, NAND 플래시 메모리에서, 코드 길이는 정보 길이, 일반적으로 2의 거듭 제곱 및 허용된 작은 오버 헤드(예를 들어 10 %)에 의해 결정되며, 전형적으로 2의 거듭 제곱보다 약간 높다.
일반적으로 선형 코드에 대해, 길이 N 인 코드로부터 길이 N'(N' < N)의 코드를 만드는 일반적인 방법은 단축(shortening) 및 펑처링(puncturing)이다. 폴라 코드(polar code)에 대해서 단축 및 펑처링이 고려되었지만, 실용적인 문제는 문헌에서 빠져있다.
상세하게는, 현재의 이 분야 논문은 마치 펑처링/단축이 없는 것처럼, 풀 팩터(full factor) 그래프를 사용하는 반면, 펑처링/단축은 펑처링/단축된 비트에 대한 입력 로그 - 우도 비율 (LLR: log-likelihood ratios)을 각각
Figure pat00083
로 설정함으로써 고려된다. 결과로 생성되는 복잡성은 저장되는 블록 길이가 아닌 긴 블록 길이와 일치한다. 이는 나쁜 성능 특성을 초래한다.
그러나 특정 좌표에 대해 펑처링/단축을 수행하는 경우, 가변 노드들의 개수가 펑처링/단축된 길이와 원래 길이(N=2n) 간의 비율과 동일한 비율만큼 감소하도록 팩터 그래프가 "슬라이스드(sliced)"될 수 있다.
상술한 바와 같이, NAND 플래시 메모리에 대해, 이 팩터는 2에 가깝기 때문에, 본 명세서의 실시 예는 가변 노드의 수를 약 2 배 감소시킬 수 있다. 이는 이 분야의 선행 기술과 비교하여 엣지 카운트 및 전반적인 복잡성을 훨씬 더 감소시키는 것을 의미한다. 결론적으로, 본 발명의 실시 예는 통상적으로 당업계의 현존 기술과 비교하여 약 2 배만큼 복잡성을 감소시킬 것이다. 또한 하드웨어 구현 면적에 있어서 상당한 이득이 있다. 이로 인해 하드웨어 비용 및 전력 소모 측면에서 상당한 효과를 얻을 수 있고, 소프트웨어 구현을 위한 메모리 크기가 더 이상 중요한 문제는 아니지만 소프트웨어 구현을 위한 메모리 크기 측면에서도 상당한 효과를 얻을 수 있다.
보다 공식적으로, 본 발명의 일 실시 예에 따르면, n≥1에 대해
Figure pat00084
을 정의한다. 여기서,
Figure pat00085
이다. N=2n 을 갖는 폴라 코드
Figure pat00086
은 다음의 수학식과 같은 형태를 가진다.
Figure pat00087
여기서,
Figure pat00088
는 고정 좌표의 일부 집합이다.
상세하게, 본 발명의 일 실시 예에 따르면,
Figure pat00089
을 기록하고,
Figure pat00090
에 대해, 다음의 수학식이 성립한다.
Figure pat00091
여기서, A'는 A의 전치 행렬(transpose)을 나타낸다.
Figure pat00092
은 위 삼각형(upper triangular)이므로
Figure pat00093
의 마지막 s 행들은 0이다. 즉, z가
Figure pat00094
에 있는 모든 가능한 벡터에 대해 작동할 때,
Figure pat00095
의 첫 번째 N-s 좌표는
Figure pat00096
에 있는 모든 가능한 벡터에 대해 작동하고 마지막 s 좌표는 0이어야 한다.
그러므로, 다음의 수학식이 성립한다.
Figure pat00097
다시 말하면, 코드의 마지막 s 좌표를 줄이는 것은 u'의 마지막 s 좌표(중 아직 고정되지 않은 비트들)를 줄이는 것과 같은 것이다.
그러나 팩터 그래프의 모든 로컬 코드(local codes)는 길이가 2 인 반복 코드(repetition codes) 또는 단일 패리티 코드(single-parity codes)이므로, 변수를 0으로 설정하면 해당 노드와 이 노드에 연결된 모든 에지들을 삭제하는 것과 완전히 동일하다는 것을 알 수 있다. 따라서 팩터 그래프는 출력과 입력 모두에서 "슬라이스" 될 수 있다. 또한, 슬라이싱은 u'의 마지막 s 좌표에서 발생할 필요는 없지만, 반드시 서로 인접할 필요는 없는 임의의 s 행(row) 세트가 폴라 코드 내의 임의의 위치에서 슬라이스될 수 있음을 알 수 있다. 상술한 설명은 슬라이싱의 특정 예이며, 본 발명의 다른 실시 예에 따라 팩터 그래프의 임의의 행에 의해 구현될 수 있는 일반적인 슬라이싱은 아니다.
슬라이스된 행(row)의 적절한 선택을 위해, 본 발명의 실시예에 따른 슬라이스된 폴라 코드의 디코딩 성능은 종래의 단축 및 펑처링 패턴과 수학적으로 등가임을 보여줄 수 있다. 마지막 행이 슬라이스된 경우 성능은 슬라이스된 디코더로 마지막 행을 단축하는 것과 동일한 것으로 입증될 수 있다. 비트-반전된 순서의 로우들이 슬라이스된 경우, 성능은 슬라이스된 디코더로, 비트 반전된 펑 처링 패턴과 동일한 것으로 입증될 수 있다. 따라서, 슬라이스된 에지 및 노드의 적절한 선택에 의해, 결과적인 코딩 방식은 특정 단축 및 펑처링 기술과 동일한 성능으로 동작할 수 있다. 그러나, 본원의 실시 예에 따른 슬라이스된 코드의 복잡성은 원래의 블록 길이 2n이 아닌 슬라이싱된 길이 k(1 + OH)의 그것과 정합할 수 있고, 저장 애플리케이션의 경우 상당한 기여가 될 수 있으며, 이러한 시스템은 일반적으로 고속 코드로 작동할 수 있다.
폴라 코드는 2n에서 k (1 + OH)로 슬라이스된다. 여기서'OH'는 오버헤드(overhead)를 나타낸다. 숫자로 된 실시예가 이슈(issue)를 더 잘 설명할 것이다. 표준 폴라 코딩에서, 코드의 모든 블록 길이(block length)는 2의 정수 승 (integral power of two), 즉 n = 11에 대해 블록 길이가 2048 인 코드가 있다. 이것은 정보와 오버헤드(overhead)를 함께 포함한다. 좋은 지표 집합이 크기 1536이고, 3/4 레이트(rate)로 통신한다고 가정한다. 이것은 유용하지만 일부 애플리케이션, 주로 스토리지 애플리케이션 및 주로 NAND 플래시 저장 장치에서, 정보와 패리티 비트(parity bits)를 함께 포함하는 전체 블록 길이가 아닌, 정보 비트의 수가 2의 정수 승(integral power of two)이 되어야 한다. 저장 응용 프로그램이 정보의 맨 위에 33%의 오버 헤드가 있는 3/4 레이트로 통신하기를 원한다고 가정하면, 현재의 예는 메모리 장치 및 다른 응용 프로그램에서도 어려움이 있으며, 1536의 정보 길이(information length)로 동작하지 않을 것이며, 1024 비트의 정보 또는 2048 비트의 정보 중 하나로 동작할 것이다. k = 1024 비트의 정보가 있다고 가정하면, 전체 블록 길이 k (1 + OH)는 약 1365 비트이다. 그러나 길이 1365의 폴라 코드는 없다. 전체 블록, 즉, 정보 및 패리티에 대해 1024 또는 2048이다. 또 다른 수치 예에서, 채널이 10 %의 오버 헤드로 동작하고 k = 8192 비트라고 가정하자. 그러면, k (1 + OH)(이 때, k는 8192, OH는 0.1)는 9011 비트이다. 다시 말하자면, 길이가 2n = 8192 또는 16384 인 폴라 코드가 있으므로 슬라이스가 필요하다.
이제는 이러한 상황에 대한 연장 솔루션(lengthening solution)을 제공하는 선행 기술이 있다. 그러나 '슬라이싱'이 없는 이러한 선행 솔루션의 디코더 복잡도는 길이가 9011 인 '슬라이스 된'코드가 아닌 16384 코드의 디코더와 일치한다. 이는 성능 및 구현 문제에 엄청난 영향을 미친다. 하드웨어 및 소프트웨어 디코더 모두 복잡성 감소의 이점을 얻을 수 있지만 하드웨어에서는 디코더 구현이 16384 길이 코드가 아닌 9011 길이 코드인 경우, 디코더 구현의 면적 및 성능에 상당한 영향을 미친다.
본 발명의 일 실시 예에 따르면, 그래프는 슬라이싱 됨으로써 수정된다. 즉, 폴라 코드 그래프가 주어지면, 노드와 해당 에지가 그래프에서 제거되어 관심있는 목표 블록 길이(target block length)에 대한 슬라이스된 폴라 코드를 제공한다. 노드와 에지를 제거하는 많은 옵션이 있다. 본 발명의 일 실시 예에 따르면, 이들 옵션 중 적어도 2 개는 반드시 최적의 옵션일 필요는 없지만, 알려진 단축 및 펑처링 기술의 에러 성능과 매치한다. 그러나, 본 발명의 일 실시 예에 따른 디코더는 슬라이스된 그래프상에서 동작하고, 따라서 그의 디코딩 복잡도는 원래의 블록 길이가 아닌 목표 길이의 디코딩 복잡도와 일치한다. 그래프 자체의 입력이나 출력이 아니라, 인코더와 디코더의 그래프 모두가 슬라이스된다. 인코더와 디코더는 모두 코드 그래프에 따라 작동 / 정의되며 일반적으로 동일한 그래프를 참조해야 한다.
단축과 펑처링은 그래프를 전혀 참조하지 않는다. 왜냐하면 이러한 동작들은 제로 전송/저장을 부과하므로, 연역적으로(a-priori)를 전송/저장할 필요가 유사한 정보 비트를 삽입하거나, 또는, 펑쳐링의 경우, 단순히 특정 비트를 전송하지 않는 것을 포함한다. 반면에 슬라이싱은 코드 자체를 변경하므로 인코딩 및 디코딩을 변경하는 반면, 단축/펑처링은 특정 비트를 전송에서 간단히 삽입하거나 삭제(제거)한다. 결과적으로 단축 및 펑처링에 기반한 기술에서는, 디코더 및 인코더는 더 긴 '마더(mother)' 코드 전체에서 작동해야 하므로 성능 및 구현 비용 측면에서 비용이 많이 든다. 슬라이싱에서는 코드 자체가 변경되므로 시간 복잡성, 칩 면적 및 전력 비용면에서 더 간단한 장치로 동작할 수 있다.
본 발명의 실시 예에 따른 폴라 코드 그래프는 인코더 및 디코더 모두에서 슬라이싱된다. 디코더와 인코더 모두 동일한 그래프에서 작동해야 하므로 코드가 슬라이스되면 인코더와 디코더 모두에 대해 수행해야 한다. 인코더와 디코더는 모두 원래의 길이 N = 2n 폴라 코드의 그래프를 오프라인으로 슬라이싱하면 더 짧은 슬라이스 코드에서 작동한다. 따라서, 결과적인 인코더 및 디코더는 길이 2N = 2 × 2n의 거의 2 배 길이가 아닌 실제 저장/송신된 데이터와 동일한 크기의 블록을 처리한다.
이 속성은 대부분의 스토리지 시스템, 특히 솔리드 스테이트 스토리지 및 특히 일반적인 오버 헤드가 8-11 %이고 정보 블록 길이가 2의 정수 승수(integral powers of 2)인 NAND 플래시 스토리지 시스템에서 유용하다. 10.94 %의 오버 헤드, 1KB 코드의 종래의 디코더는 16384 비트 크기의 블록을 동작시켜야 할 것이다. 본 발명의 일 실시 예에 따른 슬라이스된 폴라 코드들에 대한 디코더는 9088 비트들의 블록을 처리 할 것이다. 이러한 차이는 채널 편파 코딩 기술의 레이턴시(latency), 전력(power) 및 면적(area)의 개선에 기여할 것이다.
폴라 코드의 슬라이싱은 폴라 코드 그래프의 용어로 정의된다. 폴라 코드 그래프는 인코딩(또는 디코딩) 그래프로 정의된다. 또한, 도 1a 내지 도 1b는 각각 폴라 코드에 대한 인코딩 및 디코딩 그래프를 도시한다.
도 2는 인코더 그래프의 슬라이싱을 도시한다. 이 그래프에서 파선된 수평 경계선(dashed horizontal border) 아래의 그래프 행(row)은 이 행들의 노드들을 그래프의 나머지 노드에 연결하는 모든 에지와 함께 제거된다. 왼쪽에는 길이 8 폴라 코드의 인코더 그래프가 표시된다. 파선 아래의 두 개의 하단 정보 노드들이 슬라이스된다. 노드들과 모든 해당 에지들이 그래프에서 잘려 나간다. 길이 6의 결과 그래프가 오른쪽에 표시된다. 이것은 슬라이스된 폴라 코드의 인코더 그래프이다. 정보 노드 8 및 4를 슬라이싱하는 것은 비 제한적인 예이다. 임의의 방식으로 노드들을 슬라이스하여 제거할 수 있다. 물론 모든 슬라이싱 패턴은 결과 코드의 오류 성능에 영향을 미치며 실제 패턴은 코드의 실제 응용에 따라 만들어야 한다. 인코딩 동작이 슬라이스된 그래프에만 관련이 있으며 따라서 복잡성이 원래 코드가 아닌 슬라이스된 코드와 일치한다.
본 발명의 일 실시 예에 따르면, 슬라이스된 폴라 코드의 하나의 애플리케이션(응용)은 ECC 스킴이다. 여기서 코드는 슬라이스된 폴라 코드이며 ECC 스킴에 사용된다.
도 3은 슬라이싱의 미러 이미지, 즉 인코더 대신 디코더 그래프를 도시한다. 왼쪽에 있는 파선(dashed line) 아래의 행은 슬라이스된 행과 나머지 행 내의 노드를 연결하는 모든 에지들과 함께 슬라이스된다. 변경되지 않은 노드에서의 노드 처리는 동일하게 유지된다. 단일 입력을 갖는 변경된 노드의 경우, LLR 처리가 수행되지 않는다. 채널 편파 코드(channel polarization code)의 디코딩은 연속적인 제거(successive cancellation) 또는 명시적인 BP 디코딩 및 MS 디코딩 및 SC 리스트 디코딩과 같은 관련된 단순화와 같은 많은 다른 제거 또는 디코딩 기술들 중 하나를 사용할 수 있음을 유의해야 한다. 이들 모든 디코딩 기술은 폴라 코드의 그래프 정의에 의존하며, 본 발명의 실시 예에 따라 그래프가 슬라이스 될 때 적용될 수 있다.
슬라이싱 자체는 표준 폴라 코딩에서 길이 문제를 해결할 수 있고, 전체 폴라 길이 N = 2n이 아니라, 목표 길이 k (1 + OH)에 의해 제어되는 복잡도로 인코딩 및 디코딩을 제공할 수 있는 단순하지만 새로운 동작이다. 여기서 k는 정보 길이이고 OH는 오버 헤드이다. 실제 노드 처리는 변경되지 않은 나머지 노드에 대해 동일하다. 본 발명의 실시 예에 따르면, 최첨단 펑처링 및 단축 방식에 대비하여 성능의 손실은 없다.
본 발명의 실시 예에 따르면, 본 발명의 일 실시예에 따른 슬라이스된 폴라 코드는 폴라 코드 그래프를 적절하게 슬라이싱하면서 최첨단 단축 및 펑처링 기술과 동일한 에러 성능을 달성할 수 있음이 증명될 수 있다.
슬라이싱 명제에 대한 증명은 유도(induction)에 의해 뒤따를 수 있다: N = 4 길이의 폴라 코드에 대해, 결과적인 디코딩 방정식이 모든 가능한 슬라이싱 동작에 대해 계산될 수 있다. N '= 2 (n-1)에 대한 요구가 있다고 가정하면, N = 2n 길이 코드에 대한 경우를 만족시키는 것이 검증될 수 있다.
슬라이스된 행을 적절하게 선택하면, 디코딩은 종래의 단축 및 펑처링 패턴과 동일하다는 것을 알 수 있다. 마지막 행이 슬라이스된 경우, 성능은 마지막 행을 단축하는 것과 동일하다고 입증될 수 있다. 다만, 슬라이스된 디코더가 필요하다. 반면에, 비트 역순의 로우들(bit reversed order of rows)이 슬라이스되는 경우, 즉 1 ... #punctured 비트의 비트 역순이 슬라이스되는 경우, 성능은 슬라이스된 (sliced) 디코더의 경우, 비트 역순된 펑처링 패턴과 동일한 것으로 입증될 수 있다.
도 4는 동등하고 거의 동일한 슬라이싱 위치가 있는 다른 슬라이싱 방법을 도시한다. 그래프에 대한 일부 동작이 다른 것보다 덜 복잡한 특정의 단순화된 디코딩 기법에 관심이 있을 수 있다. 왼쪽에 표시된 바와 같이, N = 8 폴라 코드의 파선(dashed line) 아래의 하단 두 행을 슬라이스하는 대신에, 도 5의 우측 및 좌측에 있는 파선 원(dashed circle)에 표시된 바와 같이, 성분(components) N' = 4 폴라 코드 중 하나의 두 행을 슬라이스할 수고, 다음 단계를 위한 제한된 폴라리제이션(polarization)을 진행할 수 있다. N '= 4 폴라 코드에서 이 슬라이싱은 이전의 슬라이싱과 같지만, 올바른 폴라 단계는 연결될 노드를 가지는 에지만 남기고 수행되어야 한다. 결과적인 6 노드 그래프는 도 5 우측에 도시된다. 입력 인덱스 3과 7은 24코드에서 마지막 폴라리제이션(polarization) 단계만 다르고 동일하므로 거의 4와 8로 작동한다. 도 6은 좌측의 파선 원으로 표시된 바와 같이, 8 노드 그래프의 N '= 4 및 N'= 8 코드가 슬라이스되어, 우측의 6 노드 그래프를 생성하는 다른 슬라이싱의 디코더 그래프를 도시한다.
도 7은 슬라이스된 폴라 디코더에 대한 본 발명의 실시 예에 따른 예시적인 장치의 블록도이다. 본 발명의 일 실시예에 따른 예시적인 장치는 하드웨어 또는 소프트웨어, 또는 이 둘의 임의의 조합으로 구현될 수 있다. 도면을 참조하면, 예시적인 장치는 입력 관측 큐(input observations queue, 71), 입력 관측 큐 (71)로부터 메시지를 수신하도록 접속된 메인 제어부(main control unit, 73), 메인 제어부(73)에 접속된 그래프 정의 메모리 유닛(72) 및 임시 메시지 메모리 유닛 (74), 메인 제어부(73)와 신호를 송수신하기 위해 접속된 노드 프로세서 (75,76,77,78)의 프로세서 유닛(70), 메인 제어부(73)로부터의 복호 메시지를 수신하기 위해 접속된 복호 메시지큐(79)를 포함한다. 프로세서 유닛(70)의 노드 프로세서의 수는 예시적인 것이며, 본 발명의 다른 실시 예에서, 프로세서 유닛(70)은 임의의 수의 노드 프로세서를 포함할 수 있다.
이러한 예시적인 장치가 하드웨어로서 구현되는 경우, 컨트롤러 및 프로세서는 응용 주문형 집적 회로(ASICs: application specific integrated circuits), FPGAs(field programmable gate arrays) 또는 범용 중앙 처리 장치(CPU)일 수 있다. 그래프 정의 메모리 유닛(73)은 처리될 슬라이스된 그래프의 정의를 저장할 수 있고, 임시 메시지 메모리 유닛(74)은 그래프상의 메시지가 처리되는 동안 LLR과 같은 임시 결과를 저장할 수 있다. 유닛들(72, 74) 모두는 예를 들어, 레지스터들의 뱅크 또는 회로 내에서 합성인 메모리 유닛일 수 있다. 그래프 정의에 기초하여, 메인 제어부(73)는 사용중인 특정 노드 유형에 따라 선택될 수 있는 프로세서 유닛(70)에 대한 입력 관측 큐(71)로부터 적절한 입력 메시지를 선택할 수 있고, 메인 제어부(73)는 임시 메시지 유닛(74)에 저장될 프로세서 출력을 수신한다. 노드 프로세서는 예를 들어 선택된 실제의 폴라 코드 디코딩 알고리즘에 따라 동작(예컨대, 합산 등 연산)을 수행할 수 있다.
ui 값에 대응하는 노드가 사용될 때, 메인 제어부(73)는 디코딩된 출력을 대해 ui 노드의 실제 비트 메시지를 결정할 수 있다. 본 발명의 실시 예에 따른 슬라이싱은 구현의 복잡성에서 최소의 오버 헤드로 임의의 폴라 디코더에 적용될 수 있음을 이해해야 한다.
본 발명은 도면에 도시된 실시 예를 참고로 설명되었으나 이는 예시적인 것에 불과하며, 본 기술 분야의 통상의 지식을 가진 자라면 이로부터 다양한 변형 및 균등한 타 실시 예가 가능하다는 점을 이해할 것이다. 따라서, 본 발명의 진정한 기술적 보호 범위는 첨부된 등록청구범위의 기술적 사상에 의해 정해져야 할 것이다.
71: 입력 관측 큐(input observations queue)
73, 74: 메모리 유닛
73: 메인 제어부(main control unit)
75,76,77,78: 노드 프로세서
79: 복호 메시지큐

Claims (10)

  1. 폴라 코딩 장치에 있어서,
    변환
    Figure pat00098
    을 구현하는 인코더 회로; 및
    코드 워드 C를 전송 채널을 통해 전송하는 전송기 회로를 포함하고,
    Figure pat00099
    , BN -s,
    Figure pat00100
    및 C는 갈로아 필드(Galois field)(GF(2k), k>1)에 대해 정의되고,
    N=2n, s<N,
    Figure pat00101
    = (u1, ..., uN-s)는 갈로아 필드(GF(2k))에 대한 N-s 개의 입력 벡터이고, BN -s 는 순열 행렬(permutation matrix),
    Figure pat00102
    이고, 행렬 M1 은 크기 q × q, 2 <q 및 N = qn 의 미리 정의된 행렬이고, C는 N-s 개의 심볼들의 코드 워드 벡터이며,
    C의 디코딩 복잡도는 C에서의 심볼 수에 비례하는 폴라 코딩 장치.
  2. 제1항에 있어서, 집합
    Figure pat00103
    에 대하여,
    ui = 0
    Figure pat00104
    인 폴라 코딩 장치.
  3. 제1항에 있어서,
    Figure pat00105
    인 폴라 코딩 장치.
  4. 제1항에 있어서,
    Figure pat00106
    , BN -s, M1 및 대응하는 산술 연산은 갈루아 필드 GF (2)에 대해 정의되는 폴라 코딩 장치.
  5. 제1항에 있어서, 상기 순열 행렬 BN -s 는 비트 역전 행렬(bit reversal matrix)인 폴라 코딩 장치.
  6. 제1항에 있어서, 상기 장치는
    전송 채널로부터 출력 워드(
    Figure pat00107
    )를 수신하는 수신기 회로; 및
    상기 출력 워드()로부터 정보 비트(
    Figure pat00109
    )의 추정치(
    Figure pat00110
    )를 생성하는 디코더 회로를 더 포함하며,
    상기
    Figure pat00111
    는 미리 결정된 유한 알파벳에 대해 정의된 크기 N-s의 벡터인 폴라 코딩 장치.
  7. 제1항에 있어서, 상기 M1 은
    Figure pat00112
    인 폴라 코딩 장치.
  8. 폴라 코딩 장치에 있어서,
    전송 채널로부터 출력 워드(
    Figure pat00113
    )를 수신하는 수신기 회로; 및
    상기 출력 워드(
    Figure pat00114
    )로부터 정보 비트(
    Figure pat00115
    )의 추정치(
    Figure pat00116
    )를 생성하는 디코더 회로를 포함하며,
    상기
    Figure pat00117
    는 미리 결정된 유한 알파벳에 대해 정의된 크기 N-s의 벡터이고,
    상기 출력 워드(
    Figure pat00118
    )는
    Figure pat00119
    에 의해, 입력 워드(
    Figure pat00120
    )와 연관되고,
    Figure pat00121
    , BN -s,
    Figure pat00122
    및
    Figure pat00123
    는 갈로아 필드(Galois field)(GF(2k), k>1)에 대해 정의되며,
    N=2n, s<N,
    Figure pat00124
    = (u1,..., uN-s)는 N-s 비트의 입력 벡터이고, BN -s 는 순열 행렬(permutation matrix),
    Figure pat00125
    이고, 행렬 M1은 크기 q × q, 2 <q 및 N = qn 의 미리 정의된 행렬이고, f는 확률적 함수이고,
    Figure pat00126
    의 디코딩 복잡도는
    Figure pat00127
    에서의 심볼 수에 비례하는 폴라 코딩 장치.
  9. 제8항에 있어서, 집합
    Figure pat00128
    에 대하여,
    ui = 0
    Figure pat00129
    인 폴라 코딩 장치.
  10. 제8항에 있어서,
    Figure pat00130
    인 폴라 코딩 장치.
KR1020170021711A 2016-02-18 2017-02-17 폴라 코딩 장치 Active KR102601215B1 (ko)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US15/047,196 2016-02-18
US15/047,196 US9941906B2 (en) 2016-02-18 2016-02-18 Sliced polar codes

Publications (2)

Publication Number Publication Date
KR20170097580A true KR20170097580A (ko) 2017-08-28
KR102601215B1 KR102601215B1 (ko) 2023-11-10

Family

ID=59631493

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020170021711A Active KR102601215B1 (ko) 2016-02-18 2017-02-17 폴라 코딩 장치

Country Status (2)

Country Link
US (1) US9941906B2 (ko)
KR (1) KR102601215B1 (ko)

Families Citing this family (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10291264B2 (en) * 2016-06-17 2019-05-14 Huawei Technologies Co., Ltd. Systems and methods for rate matching when using general polar codes
US10579452B2 (en) * 2016-06-17 2020-03-03 Huawei Technologies Co., Ltd. Systems and methods for rate matching via a heterogeneous kernel when using general polar codes
US10425186B2 (en) * 2016-09-12 2019-09-24 Mediatek Inc. Combined coding design for efficient codeblock extension
EP3520223B1 (en) * 2016-09-30 2023-06-14 Telefonaktiebolaget LM Ericsson (PUBL) Spatially coupled polar codes
CN108649965B (zh) * 2016-10-25 2019-07-09 华为技术有限公司 编码、译码方法及设备
CN108347301B (zh) * 2017-01-25 2020-06-02 华为技术有限公司 数据的传输方法和装置
US10075197B1 (en) * 2017-03-07 2018-09-11 Lg Electronics Inc. Method and apparatus for transmitting hamming weight and codeword
WO2018174615A1 (en) * 2017-03-23 2018-09-27 Samsung Electronics Co., Ltd. Method and apparatus for rate-matching of polar codes
CN108063649B (zh) * 2017-12-14 2020-10-02 东南大学 一种低时延低复杂度的极化码译码方法
CN110034843B (zh) * 2018-01-12 2022-06-14 华为技术有限公司 信道编码方法和编码装置
CN110557221A (zh) 2018-05-31 2019-12-10 索尼公司 电子设备、通信方法、解码方法及介质
KR102632560B1 (ko) 2018-10-19 2024-02-02 삼성전자주식회사 경로 메트릭을 이용하여 입력 데이터를 디코딩하는 장치 및 이를 이용하는 디코딩 방법
CN109768846B (zh) * 2019-01-09 2021-05-14 山东科技大学 基于二核三核混合极化码的凿孔方法、系统、装置及介质
CN112929035B (zh) * 2021-01-17 2024-07-26 中国传媒大学 一种非二进制极化码的编码与译码方法
US11791844B2 (en) * 2021-12-22 2023-10-17 Huawei Technologies Co., Ltd. Systems and methods for using special nodes for polar encoding in polar codes

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8347186B1 (en) * 2012-04-19 2013-01-01 Polaran Yazilim Bilisim Danismanlik Ithalat Ihracat Sanayi Ticaret Limited Sirketi Method and system for error correction in transmitting data using low complexity systematic encoder
US20140331083A1 (en) * 2012-12-29 2014-11-06 Emc Corporation Polar codes for efficient encoding and decoding in redundant disk arrays
US20150295593A1 (en) * 2014-04-10 2015-10-15 Samsung Electronics Co., Ltd Apparatus and method for encoding and decoding data in twisted polar code

Family Cites Families (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3813614B2 (ja) 2004-01-29 2006-08-23 川崎マイクロエレクトロニクス株式会社 エラー補正回路およびａ／ｄコンバータ
KR101271473B1 (ko) 2011-06-27 2013-06-05 전북대학교산학협력단 폴라 코드 시퀀스를 이용한 디코딩 방법
KR20120054571A (ko) 2012-04-09 2012-05-30 전북대학교산학협력단 래딕스 4 기반의 폴라코드를 이용한 부호화방법
KR101919934B1 (ko) 2012-04-19 2018-11-20 삼성전자주식회사 불휘발성 메모리 장치를 제어하는 컨트롤러의 동작 방법 및 극 부호화된 부호어를 불휘발성 메모리 장치의 멀티 비트 데이터에 매핑하는 매핑 패턴을 선택하는 매핑 패턴 선택 방법
US9503126B2 (en) 2012-07-11 2016-11-22 The Regents Of The University Of California ECC polar coding and list decoding methods and codecs
US9454552B2 (en) 2012-07-31 2016-09-27 Empire Technology Development Llc Entropy coding and decoding using polar codes
KR102015121B1 (ko) 2012-10-17 2019-08-28 삼성전자주식회사 불휘발성 메모리 장치를 제어하도록 구성되는 컨트롤러 및 컨트롤러의 동작 방법
US10193578B2 (en) * 2014-07-10 2019-01-29 The Royal Institution For The Advancement Of Learning / Mcgill University Flexible polar encoders and decoders
US9742440B2 (en) * 2015-03-25 2017-08-22 Samsung Electronics Co., Ltd HARQ rate-compatible polar codes for wireless channels

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8347186B1 (en) * 2012-04-19 2013-01-01 Polaran Yazilim Bilisim Danismanlik Ithalat Ihracat Sanayi Ticaret Limited Sirketi Method and system for error correction in transmitting data using low complexity systematic encoder
US20140331083A1 (en) * 2012-12-29 2014-11-06 Emc Corporation Polar codes for efficient encoding and decoding in redundant disk arrays
US20150295593A1 (en) * 2014-04-10 2015-10-15 Samsung Electronics Co., Ltd Apparatus and method for encoding and decoding data in twisted polar code

Also Published As

Publication number Publication date
US20170244429A1 (en) 2017-08-24
US9941906B2 (en) 2018-04-10
KR102601215B1 (ko) 2023-11-10

Similar Documents

Publication Publication Date Title
KR102601215B1 (ko) 폴라 코딩 장치
KR102223968B1 (ko) 극 부호의 병렬화된 연속 제거 디코딩 및 연속 제거 리스트 디코딩을 위한 장치 및 방법
US10326478B2 (en) Apparatus and method for encoding and decoding data in twisted polar code
JP5705106B2 (ja) ユークリッド空間リード−マラー符号の軟判定復号を実行する方法
CN109155634B (zh) 实施极化码的设备和方法
US20150333775A1 (en) Frozen-Bit Selection for a Polar Code Decoder
CN116783848B (zh) 使用并行极化码中的非理想极化比特信道的系统和方法
CN107370488A (zh) 纠错编码方法及装置
CN115398809A (zh) 极化调整卷积码的列表解码
WO2014122772A1 (ja) 誤り訂正符号の検査行列のデータ構造、並びに誤り訂正符号の符号化率可変装置および可変方法
WO2019130475A1 (ja) 通信路分極を用いた誤り訂正符号化方法および装置、復号方法および装置
EP3713096B1 (en) Method and device for decoding staircase code, and storage medium
US20160049962A1 (en) Method and apparatus of ldpc encoder in 10gbase-t system
US20030188248A1 (en) Apparatus for iterative hard-decision forward error correction decoding
EP3652863A1 (en) Generalized low-density parity check codes (gldpc)
US20170134048A1 (en) Message-passing based decoding using syndrome information, and related methods
JP2019525638A (ja) ２のべき乗でない長さに拡張されたポーラ符号の符号化および復号化
CN107733441B (zh) 编码方法及装置、译码方法及装置
CN112534724B (zh) 用于解码极化码和乘积码的解码器和方法
CN118251844A (zh) 在极化码中使用特殊节点进行极化编码的系统和方法
EP3408956B1 (en) Apparatus and method for multi-code distributed storage
JP5523064B2 (ja) 復号装置及び方法
CN116491083B (zh) 具有共享数据和协作解码的并行极化码
EP3771105A1 (en) Transmitter, receiver, communication system, and coding rate revision method
CN112640314B (zh) 用于在乘积码和分量极化码之间映射冻结集的装置和方法

Legal Events

Date Code Title Description
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 20170217

PG1501 Laying open of application
A201 Request for examination
PA0201 Request for examination

Patent event code: PA02012R01D

Patent event date: 20220215

Comment text: Request for Examination of Application

Patent event code: PA02011R01I

Patent event date: 20170217

Comment text: Patent Application

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

Patent event code: PE07011S01D

Comment text: Decision to Grant Registration

Patent event date: 20230807

GRNT Written decision to grant
PR0701 Registration of establishment

Comment text: Registration of Establishment

Patent event date: 20231107

Patent event code: PR07011E01D

PR1002 Payment of registration fee

Payment date: 20231108

End annual number: 3

Start annual number: 1

PG1601 Publication of registration