[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

KR102058499B1 - 리드-솔로몬 저밀도 패리티 검사 디코더를 포함하는 반도체 메모리 시스템 및 그것의 읽기 방법 - Google Patents

리드-솔로몬 저밀도 패리티 검사 디코더를 포함하는 반도체 메모리 시스템 및 그것의 읽기 방법 Download PDF

Info

Publication number
KR102058499B1
KR102058499B1 KR1020130000283A KR20130000283A KR102058499B1 KR 102058499 B1 KR102058499 B1 KR 102058499B1 KR 1020130000283 A KR1020130000283 A KR 1020130000283A KR 20130000283 A KR20130000283 A KR 20130000283A KR 102058499 B1 KR102058499 B1 KR 102058499B1
Authority
KR
South Korea
Prior art keywords
matrix
sub
row
parity check
data
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.)
Active
Application number
KR1020130000283A
Other languages
English (en)
Other versions
KR20140088423A (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 삼성전자주식회사
Priority to KR1020130000283A priority Critical patent/KR102058499B1/ko
Priority to US13/755,222 priority patent/US9141467B2/en
Publication of KR20140088423A publication Critical patent/KR20140088423A/ko
Application granted granted Critical
Publication of KR102058499B1 publication Critical patent/KR102058499B1/ko
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11C—STATIC STORES
    • G11C29/00—Checking stores for correct operation ; Subsequent repair; Testing stores during standby or offline operation
    • G11C29/04—Detection or location of defective memory elements, e.g. cell constructio details, timing of test signals
    • G11C29/08—Functional testing, e.g. testing during refresh, power-on self testing [POST] or distributed testing
    • G11C29/12—Built-in arrangements for testing, e.g. built-in self testing [BIST] or interconnection details
    • G11C29/38—Response verification devices
    • G11C29/42—Response verification devices using error correcting codes [ECC] or parity check
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR 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/1008—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices
    • G06F11/1048—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices using arrangements adapted for a specific error detection or correction feature
    • 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
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1148—Structural properties of the code parity-check or generator matrix
    • 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

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Quality & Reliability (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Error Detection And Correction (AREA)

Abstract

본 발명에서는 연산량 및 하드웨어 복잡도가 감소된 RS-LDPC 디코더를 포함하는 반도체 메모리 시스템 및 그것의 읽기 방법을 제공한다. 본 발명에 따른 반도체 메모리 시스템은 메모리 장치로부터 읽어낸 데이터를 저장하는 읽기 데이터 관리부, 읽기 데이터 관리부로부터 출력되는 데이터에 우도(Likelihood Ratio)값들을 사상하여 사상 데이터를 출력하는 우도값 사상부 및 사상 데이터에 대해, 패리티 검사 행렬(Parity Check Matrix)를 사용하여 저밀도 패리티 검사(Low Density Parity Check) 디코딩을 수행하는 디코딩 부를 포함하되, 패리티 검사 행렬은 k 개의 N×M 서브 행렬을 포함하는 k＊N×M 행렬이고(단, k, N, M은 2 이상의 정수), k 개의 N×M 서브 행렬은, N×M 크기를 갖는 제 1 서브 행렬 및 N×M 크기를 갖고, 제 1 서브 행렬과 인접하여 위치하며, 제 1 서브 행렬을 순환 주기 M에 따라 행방향으로 N만큼 순환 시프트시킨 행렬과 동일한 원소 배열을 갖는 제 2 서브 행렬을 포함하고, 제 1 서브 행렬은 리드-솔로몬(Reed-Solomon) 부호에 따라 생성된 부호어(code word)를 심볼 위치 벡터로 변환한 이진(binary) 순열인 제 1 행, 제 1 행과 인접하여 위치하고, 제 1 행을 순환 주기 N에 따라 1만큼 순환 시프트시킨 행과 동일한 원소 배열을 갖는 제 2 행 및 제 2 행과 인접하여 위치하고, 제 2 행을 순환 주기 N에 따라 1만큼 순환 시프트시킨 행과 동일한 원소 배열을 갖되, 제 1 행과는 다른 제 3 행을 포함한다.

Description

리드-솔로몬 저밀도 패리티 검사 디코더를 포함하는 반도체 메모리 시스템 및 그것의 읽기 방법{SEMICONDUCTOR MEMORY SYSTEM INCLUDING REED-SOLOMON LOW DENSITY PARITY CHECK DECODER AND READ METHOD THEREOF}
본 발명은 반도체 메모리 시스템에 관한 것으로서, 더욱 상세하게는 저장된 데이터를 읽어낼 때 읽어낸 데이터의 에러를 정정하기 위한 리드-솔로몬 저밀도 패리티 검사 디코더를 포함하는 반도체 메모리 시스템 및 그것의 읽기 방법에 관한 것이다.
반도체 메모리 장치(semiconductor memory device)는 실리콘(Si, silicon), 게르마늄(Ge, Germanium), 비소 갈륨(GaAs, gallium arsenide), 인화인듐(InP, indium phospide) 등과 같은 반도체를 이용하여 구현되는 기억장치이다. 반도체 메모리 장치는 크게 휘발성 메모리 장치(Volatile memory device)와 불휘발성 메모리 장치(Nonvolatile memory device)로 구분된다.
반도체 메모리 장치에 프로그램된 데이터를 읽어낼 때, 읽어낸 데이터에는 다양한 이유로 에러가 포함될 수 있다. 읽어낸 데이터의 에러를 정정하기 위하여, BCH(Bose-Chaudhuri-Hocquenghem) 부호, LDPC(Low Density Parity Check) 부호, 터보(Tutbo) 부호 등과 같은 에러 정정 부호들이 연구되고 있다.
특히 LDPC 부호 중에서 리드-솔로몬(Reed-Solomon, 이하 RS) 부호를 LDPC 부호로 확장시킨 RS-LDPC 부호는 최소 거리와 거스(girth)의 길이가 길기 때문에 상대적으로 에러 정정 능력이 뛰어난 특성을 가진다. 그러나, RS-LDPC 부호는 뛰어는 에러 정정 성능에도 불구하고 패리티 검사 행렬의 구조가 매우 랜덤하다. 이러한, 랜덤 구조의 패리티 검사 행렬은 RS-LDPC 디코더의 연산 처리량 및 하드웨어 복잡도를 증가시키는 단점이 있다.
본 발명의 목적은 RS-LDPC 디코더를 위한 단순 구조의 패리티 검사 행렬을 제안하고, 제안된 패리티 검사 행렬을 이용하여 효율적으로 데이터를 디코딩하는 RS-LDPC 디코더를 포함하는 반도체 메모리 시스템 및 그것의 읽기 방법을 제공하는 데 있다.
본 발명의 다른 목적은 연산 처리량 및 하드웨어 복잡도가 감소된 RS-LDPC 디코더를 포함하는 반도체 메모리 시스템 및 그것의 읽기 방법을 제공하는 데 있다.
본 발명에 따른 반도체 메모리 시스템은 메모리 장치로부터 읽어낸 데이터를 저장하는 읽기 데이터 관리부; 상기 읽기 데이터 관리부로부터 출력되는 상기 데이터에 우도(Likelihood Ratio)값들을 사상하여 사상 데이터를 출력하는 우도값 사상부; 및 상기 사상 데이터에 대해, 패리티 검사 행렬(Parity Check Matrix)를 사용하여 저밀도 패리티 검사(Low Density Parity Check) 디코딩을 수행하는 디코딩 부를 포함하되, 상기 패리티 검사 행렬은 k 개의 N×M 서브 행렬을 포함하는 k＊N×M 행렬이고(단, k, N, M은 2 이상의 정수), 상기 k 개의 N×M 서브 행렬은 N×M 크기를 갖는 제 1 서브 행렬; 및 N×M 크기를 갖고, 상기 제 1 서브 행렬과 인접하여 위치하며, 상기 제 1 서브 행렬을 순환 주기 M에 따라 행방향으로 N만큼 순환 시프트시킨 행렬과 동일한 원소 배열을 갖는 제 2 서브 행렬을 포함하고, 상기 제 1 서브 행렬은 리드-솔로몬(Reed-Solomon) 부호에 따라 생성된 부호어(code word)를 심볼 위치 벡터로 변환한 이진(binary) 순열인 제 1 행; 상기 제 1 행과 인접하여 위치하고, 상기 제 1 행을 순환 주기 N에 따라 1만큼 순환 시프트시킨 행과 동일한 원소 배열을 갖는 제 2 행; 및 상기 제 2 행과 인접하여 위치하고, 상기 제 2 행을 순환 주기 N에 따라 1만큼 순환 시프트시킨 행과 동일한 원소 배열을 갖되, 상기 제 1 행과는 다른 제 3 행을 포함한다.
실시 예로서, 상기 디코딩 부는 우도값 또는 검사 노드 메시지를 참조하여 변수 노드들 및 검사 노드들의 값들을 갱신하고, 상기 갱신된 변수 노드들 및 검사 노드들의 값들에 따라 상기 데이터의 디코딩을 수행하는 변수 노드 연산부; 상기 갱신된 변수 노드들의 값들을 변수 노드 메시지로서 수신하고, 상기 수신된 변수 노드 메시지를 참조하여 상기 검사 노드 메시지를 제공하는 검사 노드 연산부; 상기 변수 노드 블록으로부터 상기 검사 노드 블록으로의 변수 노드 메시지 전송을 중계하는 제 1 네트워크 부; 및 상기 검사 노드 블록으로부터 상기 변수 노드 블록으로의 검사 노드 메시지 전송을 중계하는 제 2 네트워크 부를 포함한다.
실시 예로서, 상기 제 1 네트워크 부 또는 상기 제 2 네트워크 부는 상기 변수 노드 블록으로부터 입력된 변수 노드 메시지의 적어도 일부를 복수의 채널들 중 어느 하나에 할당하는 스위치 제어부; 및 상기 어느 하나의 채널과 연결된 복수의 입력 단자를 복수의 출력 단자에 고정 배선하는 고정 배선 블록을 포함하는 연결부를 포함한다.
실시 예로서, 상기 스위치 제어부는 클럭 신호에 따라 상기 변수 노드 메시지의 적어도 일부를 대신하여, 상기 변수 노드 메시지의 다른 일부를 상기 어느 하나의 채널에 할당한다.
실시 예로서, 상기 제 1 네트워크 부 또는 상기 제 2 네트워크 부는 상기 패리티 검사 행렬에 따라 상기 변수 노드 메시지를 상기 검사 노드들에 나누어 할당하는 병렬 시프터; 및 상기 병렬 시프터의 동작을 제어하는 시프터 제어부를 포함한다.
실시 예로서, 상기 N은 리드-솔로몬(Reed-Solomon) 부호에 따라 상기 부호어(code word)를 생성하기 위해 사용되는 갈루아 필드의 원소의 개수이다.
실시 예로서, 상기 저밀도 패리티 검사 디코딩에 의한 에러 정정 상태를 판정하는 신드롬 검사부를 더 포함한다.
실시 예로서, 상기 에러 정정 상태의 판정 결과에 따라 상기 디코딩 부는 페일 메시지를 출력하고, 상기 읽기 데이터 관리부는 상기 페일 메시지에 응답하여 상기 메모리 장치로부터 읽어낸 추가 데이터를 저장하고, 상기 우도값 사상부는 상기 추가 데이터에 우도값들을 사상하여 추가 사상 데이터를 출력하고, 상기 디코딩부는 상기 추가 사상 데이터에 대해 상기 패리티 검사 행렬을 사용하여 저밀도 패리티 검사를 수행한다.
실시 예로서, 상기 데이터를 읽어내기 위한 읽기 전압과 상기 추가 데이터를 읽어내기 위한 읽기 전압은 서로 다른 전압 레벨을 갖는다.
실시 예로서, 상기 패리티 검사 행렬을 저장하는 저장부를 더 포함한다.
실시 예로서, 상기 메모리 장치는 낸드 플래시 메모리(NAND Flash Memory)를 포함한다.
본 발명에 따른 반도체 메모리 시스템의 데이터 읽기 방법은 제 1 읽기 전압들을 이용하여 상기 반도체 메모리 시스템에 저장된 데이터를 읽는 단계; 상기 읽혀진 데이터에 대해 패리티 검사 행렬(Parity Check Matrix)을 사용하여 저밀도 패리티 검사(Low Density Parity Check) 디코딩을 수행하는 단계; 및 상기 디코딩 결과에 따라, 상기 읽혀진 데이터의 에러를 정정한 결과를 출력하는 단계를 포함하되, 상기 패리티 검사 행렬은 k 개의 N×M 서브 행렬을 포함하는 k＊N×M 행렬이고(단, k는 2 이상의 정수), 상기 k 개의 N×M 서브 행렬은 N×M 크기를 갖는 제 1 서브 행렬; 및 N×M 크기를 갖고, 상기 제 1 서브 행렬과 인접하여 위치하며, 상기 제 1 서브 행렬을 순환 주기 M에 따라 행방향으로 N만큼 순환 시프트시킨 행렬과 동일한 원소 배열을 갖는 제 2 서브 행렬을 포함하고, 상기 제 1 서브 행렬은 리드-솔로몬(Reed-Solomon) 부호에 따라 생성된 코드 워드를 심볼 위치 벡터로 변환한 이진(binary) 순열인 제 1 행; 상기 제 1 행과 인접하여 위치하고, 상기 제 1 행을 순환 주기 N에 따라 1만큼 순환 시프트시킨 행과 동일한 원소 배열을 갖는 제 2 행; 및 상기 제 2 행과 인접하여 위치하고, 상기 제 2 행을 순환 주기 N에 따라 1만큼 순환 시프트시킨 행과 동일한 원소 배열을 갖되, 상기 제 1 행과는 다른 제 3 행을 포함한다.
실시 예로서, 상기 디코딩 결과에 따라, 상기 제 1 읽기 전압과는 다른 제 2 읽기 전압을 이용하여 상기 저장된 데이터를 다시 읽는 단계; 상기 다시 읽혀진 데이터에 대해 상기 패리티 검사 행렬(Parity Check Matrix)을 사용하여 저밀도 패리티 검사 디코딩을 수행하는 단계를 포함한다.
본 발명이 다른 실시 예에 다른 반도체 메모리 시스템의 데이터 읽기 방법은 정상 읽기 전압들을 이용하여 상기 반도체 메모리 시스템에 저장된 데이터를 읽는 단계; 상기 읽혀진 데이터의 에러 정정을 위한 패리티 검사 행렬(Parity Check Matrix)을 복원하는 단계; 상기 복원된 패리티 검사 행렬(Parity Check Matrix)을 사용하여, 상기 읽혀진 데이터에 대한 저밀도 패리티 검사(Low Density Parity Check) 디코딩을 수행하는 단계; 및 상기 디코딩 결과에 따라, 상기 읽혀진 데이터의 에러를 정정한 결과를 출력하는 단계를 포함하되, 상기 저밀도 패리티 검사 행렬을 복원하는 단계는 상기 저밀도 패리티 검사 행렬의 저장된 적어도 하나의 행을 읽는 단계; 및 상기 저밀도 패리티 검사 행렬의 나머지 행들이 각각 상기 읽은 적어도 하나의 행을 행 방향으로 1 이상의 크기만큼 순환 시프트시킨 형태의 원소 배열을 갖도록, 상기 저밀도 패리티 검사 행렬을 복원하는 단계를 포함하되, 상기 적어도 하나의 행은 리드-솔로몬(Reed-Solomon) 부호에 따라 생성된 코드 워드를 심볼 위치 벡터로 변환한 이진(binary) 순열이다.
실시 예로서, 상기 복원된 패리티 검사 행렬은 N×M 크기를 갖고 병렬로 배열된 제 1 및 제 2 서브 행렬을 포함하고(단, N, M은 2 이상의 정수), 상기 제 1 서브 행렬은 상기 적어도 하나의 행; 상기 적어도 하나의 행과 인접하여 위치하고, 상기 적어도 하나의 행을 순환 주기 N에 따라 1만큼 순환 시프트시킨 행과 동일한 원소 배열을 갖는 제 1 시프트 행; 및 상기 제 1 시프트 행과 인접하여 위치하고, 상기 제 1 시프트 행을 순환 주기 N에 따라 1만큼 순환 시프트시킨 행과 동일한 원소 배열을 갖되, 상기 적어도 하나의 행과는 다른 제 2 시프트 행을 포함하고, 상기 제 2 서브 행렬은 상기 제 1 서브 행렬과 인접하여 위치하며, 상기 제 1 서브 행렬을 순환 주기 M에 따라 행방향으로 N만큼 순환 시프트시킨 행렬과 동일한 원소 배열을 갖는다.
본 발명에 따르면, RS-LDPC 디코더를 위한 단순 구조의 패리티 검사 행렬이 제안되고, 제안된 패리티 검사 행렬을 이용하여 반도체 메모리 시스템이 효율적으로 RS-LDPC 디코딩을 수행할 수 있다.
또한, 반도체 메모리 시스템의 RS-LDPC 디코더가 낮은 하드웨어 복잡도로 구현될 수 있다.
또한, 데이터 디코딩시 반도체 메모리 시스템의 RS-LDPC 디코더에 요구되는 연산 처리량이 감소될 수 있다.
도 1은 본 발명의 실시 예에 따른 반도체 메모리 시스템(1000)을 보여주는 블록도이다.
도 2는 본 발명에 따른 반도체 메모리 시스템이 데이터를 디코딩하는 방법을 나타내는 블록도이다.
도 3은 도 1 에 도시된 ECC 디코더(300)를 보여주는 블록도이다.
도 4는 도 1에 도시된 반도체 메모리 장치의 읽기 방법을 나타내는 순서도이다.
도 5는 LDPC 부호의 패리티 검사 행렬 구조를 나타내는 위한 도면이다.
도 6은 도 5에 도시된 패리티 검사 행렬에 따른 변수 노드들과 검사 노드들 간의 연결 관계를 나타내는 태너 그래프이다.
도 7은 RS-LDPC 부호에 따른 일반적인 패리티 검사 행렬을 나타내는 도면이다.
도 8은 도 7에 도시된 패리티 검사 행렬의 복수의 서브 행렬 중 제 1 서브 행렬(410)을 구체적으로 나타내는 도면이다.
도 9 내지 도 11은 본 발명에 따라 제안된 패리티 검사 행렬을 나타내는 도면이다.
도 12는 본 발명에 의해 제안된 패리티 검사 행렬(500)의 생성 방법을 나타내는 순서도이다.
도 13은 본 발명에 따른 패리티 검사 행렬을 예시적으로 나타내는 도면이다.
도 14는 본 발명의 실시 예에 따른 도 3의 디코더를 나타내는 블록도이다.
도 15는 도 14에 도시된 스위치 네트워크를 예시적으로 나타내는 블록도이다.
도 16 및 도 17은 본 발명에 따른 스위치 네트워크의 고정 배선 블록을 예시적으로 나타내는 도면이다.
도 18은 도 1에 도시된 반도체 메모리 시스템(1000)의 응용 예를 보여주는 블록도이다.
도 19는 본 발명의 실시 예에 따른 메모리 카드(3000)를 보여준다.
도 20은 본 발명의 실시 예에 따른 솔리드 스테이트 드라이브(Solid State Drive)를 나타내는 블록도이다.
도 21은 본 발명의 실시 예에 따른 반도체 메모리 시스템 및 그것을 포함하는 컴퓨팅 시스템의 개략적인 구성을 나타내는 도면이다.
앞의 일반적인 설명 및 다음의 상세한 설명들은 모두 청구된 발명의 부가적인 설명을 제공하기 위한 예시적인 것이다. 그러므로 본 발명은 여기서 설명되는 실시 예에 한정되지 않고 다른 형태로 구체화될 수도 있다. 여기서 소개되는 실시 예는 개시된 내용이 철저하고 완전해 질 수 있도록 그리고 당업자에게 본 발명의 사상이 충분히 전달될 수 있도록 하기 위해 제공되는 것이다.
본 명세서에서, 어떤 부분이 어떤 구성요소를 포함한다고 언급되는 경우에, 이는 그 외의 다른 구성요소를 더 포함할 수도 있다는 것을 의미한다. 이하, 본 발명의 실시 예를 첨부된 도면을 참조하여 상세하게 설명한다.
도 1은 본 발명의 실시 예에 따른 반도체 메모리 시스템(1000)을 보여주는 블록도이다. 도 1을 참조하면, 반도체 메모리 시스템(1000)은 저장 장치(100) 및 컨트롤러(200)를 포함한다. 실시 예로서, 저장 장치(100)는 불휘발성 메모리 장치(예를 들어, 플래시 메모리 장치)를 포함할 수 있다. 이러한 경우, 저장 장치(100)는 메모리 셀들의 문턱 전압을 조절함으로써 데이터를 저장한다.
컨트롤러(200)는 호스트(Host) 및 저장 장치(100)에 연결된다. 호스트(Host)로부터의 요청에 응답하여, 컨트롤러(200)는 저장 장치(100)를 액세스하도록 구성된다. 예를 들면, 컨트롤러(200)는 저장 장치(100)의 읽기, 쓰기, 소거, 그리고 배경(background) 동작을 제어하도록 구성된다. 컨트롤러(200)는 저장 장치(100) 및 호스트(Host) 사이에 인터페이스를 제공하도록 구성된다. 컨트롤러(200)는 저장 장치(100)를 제어하기 위한 펌웨어(firmware)를 구동하도록 구성된다.
예시적으로, 컨트롤러(200)는 저장 장치(100)에 제어 신호 및 어드레스를 제공하도록 구성된다. 그리고, 컨트롤러(200)는 저장 장치(100)와 데이터를 교환하도록 구성된다.
컨트롤러(200)는 에러 정정 코드 디코더(Error Correction Code decoder, 이하 ECC 디코더, 300)를 포함한다. ECC 디코더(300)는 저장 장치(100)로부터 읽어낸 데이터에 대해 에러 정정 코드(Error Correcting Code, 이하 ECC)를 이용한 디코딩을 수행한다. ECC 디코더(300)는 디코딩을 수행하여, 읽어낸 데이터의 에러를 정정한다. ECC 디코더(300)는 RS-LDPC (Reed Solomon-Low Density Parity Check) 부호를 이용하여 디코딩을 수행한다.
컨트롤러(200)는 특정한 통신 규격에 따라 호스트(Host)와 통신한다. 예를 들어, 컨트롤러(200)는 USB (Universal Serial Bus), MMC (multimedia card), PCI (peripheral component interconnection), PCI-E (PCI-express), ATA (Advanced Technology Attachment), Serial-ATA, Parallel-ATA, SCSI (small computer small interface), ESDI (enhanced small disk interface), IDE (Integrated Drive Electronics), 그리고 파이어와이어(Firewire) 등과 같은 다양한 통신 규격들 중 적어도 하나를 통해 호스트(Host)와 통신한다.
본 발명에서는 일반적인 패리티 검사 행렬보다 훨씬 단순화된 구조를 갖는 패리티 검사 행렬이 제안된다. 본 발명에서 제안하는 패리티 검사 행렬은 RS-LDPC 부호에 따라 생성되므로, 에러 정정 능력이 뛰어난 RS-LDPC 부호의 특징을 그대로 유지한다. 또한, 본 발명에서는 RS-LDPC 부호의 특징인 랜덤한 패리티 검사 행렬 구조를 개선하여, 제안된 패리티 검사 행렬이 규칙적이고 단순한 구조를 갖도록 한다.
제안된 패리티 검사 행렬은 ECC 디코더(300)에 적용되어, LDPC 디코딩을 수행하기 위해 사용된다. 이때, ECC 디코더(300)는 RS-LDPC 부호의 뛰어난 에러 정정 성능을 유지하면서도, 패리티 검사 행렬의 단순화된 구조 덕분에 디코딩시 필요한 연산량을 최소화할 수 있다. 따라서, 메모리 반도체 시스템(1000)의 디코딩 효율이 향상될 수 있다.
또한, ECC 디코더(300)는 패리티 검사 행렬의 단순화된 구조 덕분에 변수 노드와 검사 노드를 연결하는 스위치 네트워크를 낮은 하드웨어 복잡도로 구현할 수 있다. 따라서, 메모리 반도체 시스템(1000)의 전체적인 하드웨어 복잡도가 감소하고, ECC 디코더(300)를 구현하기 위해 필요한 칩 면적이 감소될 수 있다.
도 2는 본 발명에 따른 반도체 메모리 시스템이 데이터를 디코딩하는 방법을 나타내는 블록도이다. 도 2를 참조하면, 메모리 반도체 시스템은 도 1에 도시된 저장 장치(100), ECC 디코더(300) 외에도 인코더(400)를 더 포함할 수 있다. 실시 예로서, 인코더(400)는 컨트롤러(200, 도 1 참조)에 포함될 수 있다.
먼저 호스트(Host, 도 1 참조)로부터 데이터가 입력되면, 입력된 데이터는 인코더(400)에 의해 인코딩된다. 이때, 인코더(400)는 패리티 검사 행렬을 사용하여, 입력된 데이터에 대해 LDPC 인코딩을 수행한다. 그리고, 부호화된 데이터는 쓰기 데이터(WD)로서 저장 장치(100)에 프로그램된다. 이때, 쓰기 데이터에는 디코딩을 위한 패리티 비트들이 포함될 수 있다.
그리고, 읽기 명령이 수신되면, 반도체 메모리 시스템(1000)은 저장 장치(100)에 저장된 데이터를 읽기 데이터(RD)로서 읽어낸다. 이때, 읽기 데이터(RD)에는 다양한 이유로 발생된 에러(E)가 포함될 수 있다. 예를 들어, 쓰기 데이터(WD)가 프로그램될 때의 오동작 또는 쓰기 데이터(WD)가 저장 장치(100)에 저장되는 동안의 데이터 손실에 의해 에러(E)가 발생할 수 있다. 또는, 읽기 데이터(RD)를 읽어내는 읽기 동작에서의 오동작에 의해 에러(E)가 발생할 수 있다.
디코더(300)는 이러한 에러(E)를 제거하기 위해, 패리티 검사 행렬을 사용하여, 읽기 데이터(RD)에 LDPC 디코딩을 수행한다. 이때, 사용되는 패리티 검사 행렬은 인코딩에서 사용된 것과 동일하다. 디코딩된 결과는 디코딩된 데이터(Data’)로서 출력된다.
이때, 디코터(300)의 디코딩 성능은 패리티 검사 행렬의 구조에 의해 크게 영향을 받는다. 앞서 설명한 바와 같이, RS-LDPC 부호를 사용하여 만들어진 패리티 검사 행렬은 일반적인 LDPC 부호에 의한 패리티 검사 행렬보다 에러 정정 능력이 뛰어나지만, 행렬 구조가 복잡한 단점이 있다. 패리티 검사 행렬의 구조가 복잡하면, 디코더(300)는 읽기 데이터(RD)의 디코딩을 위해 보다 많은 연산을 필요로 한다. 또한, LDPC 디코딩에 있어서, 복잡한 패리티 검사 행렬의 구조는 변수 노드와 검사 노드 사이의 네트워크 연결에 있어서 하드웨어 복잡도를 증가시킨다.
본 발명에서는 RS-LDPC 부호의 특징을 유지하면서도, 서브 행렬 단위로 블록 순환(Block Circulation) 구조를 갖고, 각각의 서브 행렬은 준 순환하는(Quasi-Cyclic) 구조를 갖는 패리티 검사 행렬을 제안한다. 이러한 패리티 검사 행렬은 매우 단순한 행렬 구조를 가진다. 따라서, 본 발명의 디코더(300는 제안된 패리티 검사 행렬을 사용하여 RS-LDPC 디코딩을 수행함으로서, 필요한 연산량 및 하드웨어 복잡도를 크게 감소시킬 수 있다. 본 발명에서 제안하는 패리티 검사 행렬에 대해서는 도 5내지 도 13에서 상세히 후술될 것이다.
도 3은 도 1 에 도시된 ECC 디코더(300)를 보여주는 블록도이다. 도 3을 참조하면, ECC 디코더(300)는 읽기 데이터 관리자(310), 우도값(Log Likelihood Value) 사상기(320), 디코더(330)를 포함한다.
읽기 데이터 관리자(310)는 저장 장치(100)로부터 읽어낸 읽기 데이터(RD, 도 1 참조)를 수신하여 저장한다. 읽기 데이터(RD)는 제 1 읽기 데이터(RD1) 및 제 2 읽기 데이터(RD2)를 포함할 수 있다.
경판정(Hard Decision)이 수행될 때, 읽기 데이터 관리자(310)는 정상 읽기 전압을 사용하여 읽어낸 데이터(RD1)를 저장 장치(100)로부터 수신하여 제 1 읽기 데이터(RD1)로서 저장한다. 저장된 제 1 읽기 데이터(RD1)는 경판정 또는 연판정(Soft Decision) 시에 우도값 사상기(320)에 제공될 수 있다.
또한, 연판정이 수행될 때, 읽기 데이터 관리자(310)는 부분 읽기 전압을 통해 읽어낸 데이터를 저장 장치(100)로부터 수신하여 제 2 읽기 데이터(RD2)로서 저장한다. 여기서, 부분 읽기 전압은 정상 읽기 전압과 인접하되 정상 읽기 전압과는 다른 전압 레벨을 갖는 전압을 의미한다. 연판정이 수행될 때, 읽기 데이터 관리자(310)는 제 2 읽기 데이터(RD2)를 우도값 사상기(320)에 제공한다.
우도값 사상기(320)는 제공된 읽기 데이터(RD1, RD2)에 우도값들을 사상하도록 구성된다. 실시 예로서, 우도값 사상기(320)는 경판정 시에 사상될 우도값들을 저장하는 경판정 우도값 레지스터(미도시) 및 연판정 시에 사상될 우도값들을 저장하는 연판정 우도값 레지스터(미도시)를 포함할 수 있다.
실시 예로서, 경판정 시에, 우도값 사상기(320)는 읽기 데이터 관리자(310)로부터 제 1 읽기 데이터(RD1)를 수신한다. 우도값 사상기(320)는 제 1 읽기 데이터(RD1)의 각 비트의 값에 따라, 제 1 읽기 데이터(RD1)를 대응되는 우도값들로 사상한다.
연판정 시에, 우도값 사상기(320)는 읽기 데이터 관리자(310)로부터 제 2 읽기 데이터(RD2)를 수신한다. 우도값 사상기(320)는 제 2 읽기 데이터(RD2)의 각 비트의 값에 따라, 제 2 읽기 데이터(RD2)를 대응되는 우도값들로 사상한다.
경판정 또는 연판정 시에, 우도값 사상기(320)에 의해 사상된 결과는 디코더(330)에 우도값 데이터(LLR)로서 출력된다.
디코더(330)는 경판정 또는 연판정 시에 우도값 사상기(320)로부터 우도값 데이터(LLR)를 수신한다. 판정부(330)는 수신된 우도값 데이터(LLR)를 LDPC 디코딩한다. 경판정 및 연판정 시에 각각의 우도값 데이터(LLR)는 동일한 방법 및 장치를 이용하여 LDPC 디코딩된다.
판정부(330)는 LDPC 디코딩 시에, 패리티 검사 행렬에 따라 검사 노드들(check nodes) 및 변수 노드들(variable nodes)의 갱신을 수행한다. 판정부(330)는 갱신 결과(예를 들어, 사후 확률(posteriori probability))에 따라, 잠정 디코딩을 수행하고, 잠정 디코딩된 데이터와 패리티 검사 행렬을 연산하여 연산 결과에 따라 디코딩이 올바르게 수행되었는지 판단한다.
실시 예로서, 패리티 검사 행렬과의 연산 결과가 영행렬이면, 디코딩이 올바르게 수행된 것으로 판단한다. 그렇지 않으면, 디코딩이 올바르게 수행되지 않은 것으로 판단한다.
디코딩이 올바르게 수행되면, 디코더(330)는 디코딩된 데이터를 디코딩된 데이터(CD)로서 출력한다. 올바른 디코딩이 수행되지 않았으면(즉, 읽기 데이터(RD)의 에러가 모두 정정되지 않았으면), 디코더(330)는 검사 노드들 및 변수 노드들의 갱신을 다시 수행한다.
위와 같은 검사 노드들 및 변수 노드들의 갱신과 잠정 디코딩은 반복적으로(iteratively) 수행된다. 검사 노드들 및 변수 노드들의 갱신과 잠정 디코딩은 하나의 디코딩 루프를 구성할 수 있다.
디코더(330)에서 경판정이 수행되고, 경판정에 따른 패리티 검사가 실패할 때, 디코더(330)는 페일 메시지(Fail)를 읽기 데이터 관리자(310)에 전송한다. 읽기 데이터 관리자(310)는 페일 메시지(Fail)에 응답하여 컨트롤러(200, 도 1 참조)에 연판정을 위한 읽기 요청을 전송한다. 또는, 디코더(330)에서 경판정이 수행되고, 경판정에 따른 패리티 검사가 실패할 때, 디코더(330)는 페일 메시지(Fail)를 컨트롤러(200)에 직접 전송한다. 컨트롤러(200)는 페일 메시지(Fail) 또는 읽기 요청에 응답하여 연판정을 위한 읽기 동작을 준비할 것이다.
연판정이 수행될 때, 제 2 읽기 데이터(RD2)가 읽기 데이터 관리자(310)에 저장된다. 저장된 제 2 읽기 데이터(RD2)는 우도값 사상기(320)에 제공되어, 대응되는 우도값들을 사상하기 위해 사용된다. 실시 예로서, 연판정이 수행될 때, 제 1 읽기 데이터(RD1)가 제 2 읽기 데이터(RD2)와 함께 제공될 수 있다.
제 2 읽기 데이터(RD2)는 메모리 셀들의 문턱 전압들에 대한 정보를 추가적으로 얻기 위해 부분 읽기 전압을 사용하여 읽어낸 데이터이다. 연판정에서는 제 2 읽기 데이터(RD2)에 따른 추가 정보에 기반하여, 다양한 우도값들이 사상된다. 예를 들어, 하나의 메모리 셀이 정상 읽기 전압에 의해 '1'로 읽어졌지만, 부분 읽기 전압에 의해 '0'에 가까운 문턱 전압을 갖는 '1'인 것으로 읽어지면, 이러한 메모리 셀은 상대적으로 낮은 우도값을 갖도록 사상된다. 반면에, 하나의 메모리 셀이 정상 읽기 전압에 의해 '1'로 읽어지고, 부분 읽기 전압에 의해 '0'과 큰 차이가 있는 문턱 전압을 갖는 것으로 읽어지면, 이러한 메모리 셀은 상대적으로 높은 우도값을 갖도록 사상된다. 메모리 셀들의 문턱 전압들에 대한 추가 정보를 이용하므로, 연판정의 디코딩 정확도는 경판정의 디코딩 정확도보다 높다.
본 발명에서, 디코더(330)은 RS-LDPC 부호에 따르면서도 단순한 행렬 구조를 갖는 패리티 검사 행렬을 이용한다. 따라서, 디코더(330)는 높은 에러 정정 능력을 유지하면서, 필요한 연산량을 감소시킬 수 있다. 후술하겠지만, 특히, 변수 노드들과 검사 노드들 간의 스위칭 네트워크를 매우 단순한 구조로 구현될 수 있으므로, 디코더(330)를 구현하기 위한 하드웨어 구성이 단순해지고, 필요한 하드웨어 면적이 감소될 수 있다.
여기서 설명되지 않은 디코더(330)의 일반적인 구성 및 RS-LDPC 디코딩의 일반적인 방법은 당해 기술 분야에 널리 알려져 있으므로, 그에 대한 설명은 생략한다.
도 4는 도 1에 도시된 반도체 메모리 장치의 읽기 방법을 나타내는 순서도이다. 도 4를 참조하면, 반도체 메모리 장치(1000)의 읽기 방법은 S110 단계 내지 S180 단계를 포함한다.
S110 단계에서, 반도체 메모리 장치(1000)는 제 1 읽기 전압을 사용하여 저장 장치(100, 도 1 참조)에 저장된 데이터를 제 1 읽기 데이터로서 읽어낸다. 여기서 제 1 읽기 전압은 앞에서 설명한 정상 읽기 전압일 수 있다.
S120 단계에서, 반도체 메모리 장치(1000)는 제 1 읽기 데이터에 대해 제안된 패리티 검사 행렬을 이용하여 경판정을 수행한다. 이때, 제안된 패리티 검사 행렬은 단순한 행렬 구조를 가지므로, 경판정에 필요한 연산량이 감소하고 디코더(330, 도 3 참조)의 하드웨어 복잡도가 감소된다. 제안된 패리티 검사 행렬에 대한 구체적인 설명은 후술될 것이다.
S130 단계에서, 반도체 메모리 장치(1000)는 경판정 결과 제 1 읽기 데이터에 대한 디코딩이 오류없이 수행되었는지 판단한다. 디코딩된 데이터에 오류가 없으면 읽기 방법은 S180 단계로 진행한다. 디코딩된 데이터에 오류가 있으면 읽기 방법은 S140 단계로 진행한다.
S140 단계에서, 반도체 메모리 장치(1000)는 제 2 읽기 전압을 사용하여, 저장 장치(100)에 저장된 데이터를 제 2 읽기 데이터로서 읽어낸다. 여기서, 제 2 읽기 전압은 앞에서 설명한 부분 읽기 전압일 수 있다.
S150 단계에서, 반도체 메모리 장치(1000)는 제 2 읽기 데이터에 대해 제안된 패리티 검사 행렬을 이용하여 연판정을 수행한다.
S160 단계에서, 반도체 메모리 장치(1000)는 연판정 결과 제 1 및 제 2 읽기 데이터에 대한 디코딩이 오류없이 수행되었는지 판단한다. 디코딩된 데이터에 오류가 없으면 읽기 방법은 S180 단계로 진행한다. 디코딩된 데이터에 오류가 있으면 읽기 방법은 S170 단계로 진행한다.
S170 단계에서, 반도체 메모리 장치(1000)는 데이터 읽기가 실패한 것으로 판단하고, 읽기 에러 메시지를 출력한다. S170 단계가 종료되면, 읽기 방법은 종료된다.
다시 S140 단계 또는 S160 단계로 돌아가서, 읽기 방법이 S180 단계로 진행하면, 반도체 메모리 장치(1000)는 디코딩된 데이터를 출력하고, 읽기 방법은 종료된다.
상기와 같은 구성에 따르면, 본 발명의 실시 예에 따른 반도체 메모리 장치(1000)의 읽기 방법이 제공된다. 이때, 읽기 방법은 제안된 패리티 검사 행렬을 사용하여, RS-LDPC 디코딩을 수행한다. 그리고, 제안된 패리티 검사 행렬은 단순화된 행렬 구조를 가지므로, 본 발명에 따른 읽기 방법은 RS-LDPC에 필요한 연산량을 감소시키고 디코더(330)의 하드웨어 복잡도도 크게 감소시킬 수 있다.
도 5는 LDPC 부호의 패리티 검사 행렬 구조를 나타내는 위한 도면이다. 도 5를 참조하면, 패리티 검사 행렬(H)과 검사 노드들(C1, C2, C3) 및 변수 노드들(V1, V2, V3, V4, V5)이 도시되어 있다.
패리티 검사 행렬(H)의 원소들 중 제 1 행의 원소들, 제 2 행의 원소들, 그리고 제 3 행의 원소들은 각각 제 1 내지 제 3 검사 노드들(C1, C2, C3)을 형성한다. 패리티 검사 행렬(H)의 원소들 중 제 1 내지 제 5 열의 원소들은 각각 제 1 내지 제 5 변수 노드들(V1, V2, V3, V4, V5)을 형성한다.
도 5에 도시된 바와 같이, 패리티 검사 행렬(H)의 각 원소들은 검사 노드에 속하는 동시에 변수 노드에 속한다. 이때, 패리티 검사 행렬(H)의 어떤 원소가 '1'이면, 해당 원소가 속하는 검사 노드와 변수 노드는 서로 연결되는 것을 의미한다. 예를 들어, 패리티 검사 행렬(H)의 제 1 행 제 1 열의 원소(H11)가 '1'일 때, 원소(H11)가 속하는 제 1 검사 노드(C1) 및 제 1 변수 노드(V1)은 서로 연결된다.
한편, ECC 디코더(300)에서 사용되는 패리티 검사 행렬(H)은 도 5에 도시된 행렬로 한정되지 않는다. 예를 들어, 도 5의 패리티 검사 행렬(H)보다 더 낮은 밀도의 "1"을 갖는 패리티 검사 행렬이 ECC 디코더(300)에서 사용될 수 있다. ECC 디코더(300)에서 사용되는 패리티 검사 행렬의 크기도 도 5에 도시된 바와 같이 3×5 인 것으로 한정되지 않는다.
도 6은 도 5에 도시된 패리티 검사 행렬에 따른 변수 노드들과 검사 노드들 간의 연결 관계를 나타내는 태너 그래프이다. 도 5 및 도 6을 참조하면 도시된 태너 그래프는 제 1 내지 제 3 검사 노드들(C1, C2, C3)과 제 1 내지 제 5 변수 노드들(V1, V2, V3, V4, V5) 사이의 연결 관계를 나타낸다.
패리티 검사 행렬(H)의 어떤 원소(Hij)가 '1'이면, 태너 그래프에서 해당 원소(Hij)가 속하는 검사 노드(Ci)와 변수 노드(Vj)는 선으로 연결된다. LDPC 디코딩(RS-LDPC 디코딩을 포함)에서 변수 노드들은 데이터를 처리하여 연결된 검사 노드들로 처리된 데이터를 전송한다. 마찬가지로, LDPC 디코딩(RS-LDPC 디코딩을 포함)에서 검사 노드들은 검사 노드에서 처리된 데이터를 연결된 변수 노드들로 전송한다. 이처럼, LDPC 디코딩 과정에서, 검사 노드들과 변수 노드들은 연결 관계에 따라 반복적으로 데이터를 교환한다.
다시 도 4 및 5를 참조하면, 제 1 검사 노드(C1)의 원소들 중 제 1 열, 제 3열 및 제 5 열의 원소 '1'이다. 따라서, 제 1 검사 노드(C1)는 제 1 변수 노드(V1), 제 3 변수 노드(V3) 및 제 5 변수 노드(V5)와 각각 연결된다. 마찬가지로, 제 2 검사 노드(C2)의 제 3 열 및 제 4 열의 원소가 '1'이므로, 제 2 검사 노드(C2)는 제 3 변수 노드(V3) 및 제 4 변수 노드(V4)와 각각 연결된다. 그리고, 제 3 검사 노드(C3)의 제 1 열, 제 3 열 및 제 4 열의 원소가 '1'이므로, 제 3 검사 노드(C3)는 제 1 변수 노드(V1), 제 3 변수 노드(V3) 및 제 4 변수 노드(V4)와 연결된다.
실시 예로서, 검사 노드들(C1, C2, C3)와 변수 노드들(V1, V2, V3, V4, V5)의 연결은 별도의 스위치 네트워크를 통해 구현될 수 있다. 이때, 앞서 설명한 바와 같이 노드들 간의 연결 관계는 패리티 검사 행렬(H)의 원소들의 값 및 행렬 구조에 의존한다. 따라서, 패리티 검사 행렬(H)의 구조가 불규칙하고 복잡할수록, 스위치 네트워크의 하드웨어 구성 역시 복잡해지게 된다.
도 7은 RS-LDPC 부호에 따른 일반적인 패리티 검사 행렬을 나타내는 도면이다. 도 7을 참조하면, 패리티 검사 행렬(400)은 복수의 서브 행렬(410, 420, 430)을 포함할 수 있다.
복수의 서브 행렬(410, 420, 430)의 각 행들은 리드-솔로몬(Reed-Solomon) 부호에 따라 생성된 부호어(code word)를 심볼 위치 벡터로 변환한 이진(binary) 순열을 원소로서 갖는다.
또한, 복수의 서브 행렬(410, 420, 430) 각각은 복수의 N×N 정사각 행렬을 포함한다. 여기서 N은 리드-솔로몬(Reed-Solomon, RS) 부호에 따라 부호어를 생성하기 위해 사용되는 갈루아 필드(Galois-field)의 원소의 개수를 의미한다.
다시 도 7을 참조하면, 복수의 N×N 정사각 행렬 중 A 행렬을 구체화한 행렬(411)이 도시된다. 여기서는 예시적으로 N=8로 가정한다. 도 7에서 A 행렬(411)은 8개의 행과 8개의 열을 가진 격자 형태를 구성하는 복수의 사각형에 의해 표현된다. 이때, 검은색 사각형(a)은 대응되는 원소가 '1'인 것을 의미한다. 반대로, 하얀색 사각형(b)은 대응되는 원소가 '0'인 것을 의미한다.
예를 들면, 검은색 사각형(a)이 A 행렬(411)의 4번째 행 및 8번째 열에 위치하면, A 행렬(A)의 제 4 행 제 8 열의 원소는 '1'이다. 반대로, 하얀색 사각형(b)이 A 행렬(411)의 5번째 행 및 8번째 열에 위치하면, A 행렬(A)의 제 5 행 제 8 열의 원소는 '0'이다.
도 7의 A 행렬(411)에서 보듯이, RS-LDPC 부호에 따른 일반적인 패리티 검사 행렬(400)은 랜덤한 행렬 구조를 갖는다. 즉, 패리티 검사 행렬(400)은 원소들의 배열(원소들 각각이 '0'인지 또는 '1'인지)에 있어서 특정한 규칙성을 가지지 않는다. 패리티 검사 행렬(400)의 모든 N×N 정사각 행렬들이 A 행렬(411)과 동일하게 랜덤한 행렬 구조를 가지므로, 패리티 검사 행렬(400)을 사용하는 디코더는 매우 복잡한 하드웨어 구성을 가지며, 그에 따라 요구되는 연산량도 증가한다.
도 8은 도 7에 도시된 패리티 검사 행렬의 복수의 서브 행렬 중 제 1 서브 행렬(410)을 구체적으로 나타내는 도면이다. 도 7을 참조하면, 제 1 서브 행렬(410)은 예시적으로 직렬로 배열된 6개의 N×N 정사각 행렬들을 포함한다.
도 8에 따르면, 제 1 서브 행렬(410)의 제 1 행(411)은 6개의 N×N 정사각 행렬들의 제 1 행들을 직렬로 배열한 것과 동일한 행렬 구조(또는, 원소 배열)를 갖는다. 마찬가지로, 제 1 서브 행렬(410)의 제 2 행(412)은 6개의 N×N 정사각 행렬들의 제 2 행들을 직렬로 배열한 것과 동일한 행렬 구조(또는, 원소 배열)를 갖는다. 즉, 제 1 서브 행렬(410)의 제 p 행은 6개의 N×N 정사각 행렬들의 제 p 행들을 직렬로 배열한 것과 동일한 행렬 구조(또는, 원소 배열)를 갖는다.
도 7에서 설명한 바와 같이, 제 1 서브 행렬(410)의 각 행들은 리드-솔로몬(Reed-Solomon, RS) 부호에 따라 생성된 부호어(code word)를 심볼 위치 벡터로 변환한 이진(binary) 순열을 원소로서 갖는다.
RS 부호에 따라 부호어를 생성하고, 생성된 부호어를 심볼 위치 벡터로 변환하는 방법은 당해 기술 분야에 널리 알려져 있으므로, 여기서는 그러한 과정에 대해 간략하게 설명한다.
먼저, 갈루아 필드(Galois Field)를 이용하여 RS 부호의 생성 다항식을 생성한다. 갈루아 필드는 사칙연산이 정의되는 유한개의 원소를 갖는 필드이다. 리드-솔로몬 부호의 생성 다항식은 수학식 1과 같이 나타낼 수 있다.
Figure 112013000272199-pat00001
여기서, 생성 다항식 g(X)의 각 항들의 계수 gi는 갈루아 필드 내의 원소이다. 그리고, 생성 다항식 g(X)는 최소 무게 부호 다항식이므로, 각 계수 gi는 0이 아니다.
그리고, 생성 다항식 g(X)로부터 부호어 집합(coset)을 생성한다. 이를 위해, 먼저 생성 다항식 g(X)의 계수들로부터 생성 행렬(Gb)을 만든다. 생성 행렬(Gb)을 만드는 구체적인 방법은 당해 기술 분야에 널리 알려져 있으므로, 그에 대한 설명은 생략한다.
생성 행렬의 첫 번째 행을 r1, 두 번째 행을 r2라 하면, 두 행 r1, r2의 선형 조합은 부호어 집합을 형성할 수 있다. 여기서, 두 행 r1, r2의 선형 조합에 의해 생성되는 부호어 집합은 수학식 2와 같이 정의될 수 있다.
Figure 112013000272199-pat00002
여기서, GF(Ps)는 Ps개의 원소를 갖는 갈루아 필드이고, P는 소수, s는 양의 정수를 나타낸다. 그리고, α, β는 각각 갈루아 필드의 원시 원소(primitive element)이다.
수학식 2에 나타난 부호어 집합(Cb (i))를 코셋(coset)이라고 하고, 하나의 코셋을 이루는 모든 부호어(code word)들은 독립적인 관계를 갖는다.
그리고, 부호어 집합의 부호어들을 심볼 위치 벡터로 변환하여 이진 순열을 생성한다. 생성된 이진 순열들 각각은 RS-LDPC 부호에 따른 패리티 검사 행렬의 각 행을 구성한다. RS-LDPC 부호에 따라 패리티 검사 행렬의 각 행을 생성하는 방법은 당해 기술 분야에 널리 알려져 있으므로, 그에 대한 더욱 구체적인 설명은 생략한다.
이렇게 생성된 패리티 검사 행렬(H)의 두 행은 최대 하나의 위치에서만 동시에 1이 되므로, 길이 4의 순환을 가지지 않게 되고, 거스(girth)의 크기는 적어도 6 이상이 된다. 따라서, 일반적인 LDPC 부호에 비해 RS-LDPC 부호는 에러 정정 성능이 뛰어나다. 반면에, RS 부호에 따라 생성되는 패리티 검사 행렬(H)의 각 행은 원소 구조가 서로 독립적이고 임의적이므로, 패리티 검사 행렬(H)의 행렬 구조는 매우 복잡해지게 된다.
도 8을 참조하면, 제 1 서브 행렬(410)의 행렬 구조가 도시되어 있다. 제 1 서브 행렬(410)의 각 행들은 서로 독립적인 원소 구조(예를 들어, 각 행의 '0'원소와 '1'원소의 배열 순서)를 가지므로, 제 1 서브 행렬(410)의 전체적인 행렬 구조도 복잡하고 임의적인 형태를 가진다.
도 9 내지 도 11은 본 발명에 따라 제안된 패리티 검사 행렬을 나타내는 도면이다. 도 9에는 제안된 패리티 검사 행렬(500)의 첫 번째 서브 행렬(510)을 생성하는 방법이 도시된다. 도 10에는 제안된 패리티 검사 행렬(500)의 첫 번째 서브 행렬(510)의 행렬 구조가 예시적으로 도시된다. 도 11에는 첫 번째 서브 행렬(510)을 이용하여, 패리티 검사 행렬(500)의 나머지 서브 행렬들을 생성하는 방법이 도시된다.
도 9를 참조하면, 먼저 첫 번째 서브 행렬(510)의 제 1 행(511)이 RS 부호에 따라 생성된다. 즉, RS 부호에 따라 생성된 부호어(code word)들 중 어느 하나를 심볼 위치 벡터로 변환한 이진(binary) 순열을 첫 번째 서브 행렬(510)의 제 1 행(511)으로서 결정한다. RS 부호에 따라 제 1 행(511)을 생성하는 구체적인 방법은 위에서 설명한 바와 동일하다.
그리고, 제 1 행(511)이 생성되면, 본 발명에서 제안된 패리티 검사 행렬을 생성하기 위해 제 1 행(511)을 순차적으로 순환 시프트(cicular shift)시켜 첫 번째 서브 행렬(510)의 나머지 행들을 생성한다. 이때, 제 1 행(511)은 1씩 순차적으로 N을 주기로 순환 시프트되어 제 2 행(512) 내지 제 N 행(514)을 형성한다. 이때, N은 RS 부호에 따라 부호어를 생성하기 위해 사용된 갈루아 필드의 원소의 개수이다.
구체적으로, 제 1 행(511)을 행방향으로 1만큼 순환 시프트시켜 제 2 행(512)를 생성한다. 그리고, 제 2 행(512)을 행방향으로 1만큼 순환 시프트시켜 제 3 행(513)을 생성한다.
이와 같은 방법으로, 제 k 행을 행방향으로 1만큼 순환 시프트시켜 제 k+1 행을 생성한다(단, k는 1이상 N-1 이하의 정수). 이때, 각각의 행은 N을 주기로 하여 순환 시프트되므로, 제 k 행의 N번째 열, 2N번째 열, … , p·N번째 열의 원소는 각각 제 k+1 행의 1번째 열, N+1번째 열, … , (p-1)·N+1번째 열의 원소가 된다.
한편, 도 9와 같이 제 1 서브 행렬(510)이 직렬로 배열된 6개의 N×N 정사각 행렬들을 포함하고, 제 1 서브 행렬(510)이 6·N개의 열을 갖는다고 가정한다. 단, 제 1 서브 행렬(510)은 RS 부호에 따라 부호어를 변환하여 생성한 행렬이므로, 제 1 서브 행렬(510)의 각각의 N×N 정사각 행렬은 하나의 행에 오직 하나의 원소만이 '1'의 값을 갖는다.
이때, 제 1 서브 행렬(510)의 각 행들은 N을 순환 주기로 서로 순환 시프트되므로, N×N 정사각 행렬들 각각은 하나의 순환 마디를 구성한다. 따라서, N×N 정사각 행렬의 k번째 행의 마지막 원소(또는, N번째 원소)는 N×N 정사각 행렬의 k+1번째 행의 첫 번째 원소가 된다.
즉, 각각의 N×N 정사각 행렬들에 있어서, k번째 행의 첫 번째 내지 N-1번째 원소는 각각 k+1번째 행의 두 번째 내지 N번째 원소로 시프트되고, 순환 마디의 끝인 k 번째 행의 N번째 원소는 순환 시프트되어 다음행(즉, k+1번째 행)의 첫 번째 원소가 된다.
예를 들어, 제 1 서브 행렬(510)의 세 번째 N×N 정사각 행렬(510a)의 첫 번째 행은 N-1번째 원소가 '1'이다. 그리고, 두 번째 행은 첫 번째 행을 순환 시프트한 행이므로, 첫 번째 행의 N-1번째 원소는 두 번째 행에서 N번째 원소가 된다. 따라서, 두 번째 행은 N번째 원소가 '1'이다. 그리고, 세 번째 행은 두 번째 행을 순환 시프트한 행이고 순환 주기는 N이므로, 두 번째 행의 N번째 원소는 세 번째 행에서 1번째 원소가 된다. 따라서, 세 번째 행은 1번째 원소가 '1'이다.
유사하게, 제 1 서브 행렬(510)의 여섯 번째 N×N 정사각 행렬(510b)의 첫 번째 행은 N번째 원소가 '1'이다. 그리고, 두 번째 행은 첫 번째 행을 순환 시프트한 행이므로, 첫 번째 행의 N번째 원소는 두 번째 행에서 1번째 원소가 된다. 따라서, 두 번째 행은 1번째 원소가 '1'이다.
위와 같은 방법으로, 제 1 서브 행렬(510)의 각 행을 순차적으로 1씩 순환 시프트시켜(순환 주기는 N) 제 1 서브 행렬(510) 두 번째 내지 N번째 행을 생성한다. 그리고, 생성된 N개의 행을 병렬로 배열하면 제 1 서브 행렬(510)이 완성된다. 이때, 완성된 제 1 서브 행렬(510)의 N×N 정사각 행렬들은 각각 행단위로 순환하는 순환 구조를 가지고, 제 1 서브 행렬(510)은 순환하는 복수의 N×N 정사각 행렬들을 포함하는 준 순환(Quasi-Cyclic) 행렬 구조를 가진다.
도 10은 도 9에서 설명한 방법에 따라 생성된 제 1 서브 행렬을 나타내는 도면이다. 도 10을 참조하면, 제 1 서브 행렬(510)의 각 행은 인접한 행이 1씩 순환 시프트(순환 주기 N)되어 생성된다. 즉, 제 1 서브 행렬(510)의 제 2 행(512)은 제 1 행(512)이 순환 시프트된 결과이고, 제 3 행(513)은 제 2 행(512)이 순환 시프트된 결과이다. 이와 같은 방법으로, 제 8 행(514)까지 순차적으로 각 행을 순환 시프트하여 제 1 서브 행렬(510)이 완성된다.
도 10을 참조하면, 위와 같은 방법으로 생성된 제 1 서브 행렬(510)은 전체적으로 준 순환(Quasi-Cyclic)의 행렬 구조를 가진다. 따라서, 도 8의 제 1 서브 행렬(410)의 구조와 비교할 때, 본 발명에 따른 제 1 서브 행렬(510)은 상당히 단순화되고 정렬된 행렬 구조를 갖는다.
한편, 여기서는 제 1 서브 행렬(510)을 생성하기 위해 각각의 행을 1만큼 순환 시프트시켜 인접하는 행을 생성하는 예를 설명하였으나, 본 발명은 이에 한정되지 않는다. 예를 들어, 제 1 서브 행렬(510)의 각각의 행을 1보다 큰 소정의 크기만큼 순환 시프트시켜 인접하는 행을 생성할 수 있다. 이 경우, 제 1 서브 행렬(510)의 행렬 구조는 앞서 설명한 실시 예와 달라질 수 있으나, 제 1 서브 행렬(510)의 인접하는 행들 간의 '1'의 위치 변화는 여전히 일정한 규칙성을 가진다. 따라서,패리티 검사 행렬이 단순화된 구조를 가지므로, ECC 디코더(300, 도 1 참조)의 하드웨어 복잡도 및 연산량이 감소될 수 있다..
도 11에는 제 1 서브 행렬(510)을 이용하여, 패리티 검사 행렬(500)을 완성하는 방법이 도시된다. 도 11을 참조하면, 패리티 검사 행렬(500)은 제 1 내지 제 3 서브 행렬(510, 520, 530)을 포함한 복수의 서브 행렬들로 구성된다.
도 11에서는 제 1 서브 행렬(510)은 도 9 내지 도 10에서 설명한 방법으로 생성된다. 즉, 제 1 서브 행렬(510)의 하나의 행을 순환 시프트시켜 다음 행을 생성하는 방법을 순차적으로 수행함으로써, 제 1 서브 행렬(510)은 생성될 수 있다.
그리고, 본 실시 예에서는, 도 11에 도시된 바와 같이, 제 1 서브 행렬(510)을 블록 단위로 순환 시프트시켜 제 1 서브 행렬(510)에 인접한 제 2 서브 행렬(520)을 생성한다. 그리고, 제 2 서브 행렬(520)을 블록 단위로 순환 시프트시켜 제 2 서브 행렬(520)에 인접한 제 3 서브 행렬(530)을 생성한다. 마찬가지로, k 번째 서브 행렬를 블록 단위로 순환 시프트시켜 k+1 번째 서브 행렬을 생성한다(단, k는 1 이상의 정수). 이처럼, 블록 단위의 순환 시프트를 통해 패리티 검사 행렬(500)의 모든 서브 행렬들이 생성되면, 생성된 서브 행렬들을 병렬 결합시켜 패리티 검사 행렬(500)을 완성한다. 이때, 순환 시프트 단위로서의 블록은 도 9 내지 도 10에서 설명한 N×N 정사각 행렬일 수 있다.
예를 들어, 도 11과 같이 패리티 검사 행렬(500)의 제 1 서브 행렬(510)이 6개의 블록(또는, N×N 정사각 행렬)을 포함하는 N×M 행렬이라고 가정한다. 이때, 6개의 블록들(A, B, C, D, E, F)은 순차적으로 직렬 배열되어 제 1 서브 행렬(510)을 구성한다. 제 1 서브 행렬(510)을 생성하는 구체적인 방법은 도 9 내지 도 10에서 설명한 바와 동일하다. 그리고, 제 1 서브 행렬(510)을 블록 단위로 순환 시프트시켜 제 2 서브 행렬(520)이 생성된다. 이때, 제 1 서브 행렬(510)의 순환 주기는 6 블록(또는, M 개의 열)이다.
구체적으로, 블록 단위의 순환 시프트에 의해 제 1 서브 행렬(510)의 첫 번째 블록(A)은 시프트되어 제 2 서브 행렬(520)의 두 번째 블록(A)이 된다. 그리고, 제 1 서브 행렬(510)의 두 번째 블록(B)은 시프트되어 제 2 서브 행렬(520)의 세 번째 블록(B)이 된다. 마찬가지로, 제 1 서브 행렬(510)의 n 번째 블록은 시프트되어 제 2 서브 행렬(520)의 n+1 번째 블록이 된다(단, n은 1 이상 5 이하의 정수). 그리고, 제 1 서브 행렬(510)의 마지막 블록(F)은 시프트되어 제 2 서브 행렬(520)의 첫 번째 블록(F)이 된다. 즉, 순환 주기의 끝에 위치하는 블록(F)은 블록 단위의 순환 시프트에 의해 순환 주기의 처음으로 시프트된다. 위와 같이, 제 1 서브 행렬(510)이 블록 단위로 순환 시프트되어 생성된 제 2 서브 행렬(520)은 제 1 서브 행렬(510)을 순환 주기 M에 따라 행방향으로 N만큼 순환 시프트시킨 행렬과 동일한 원소 배열을 갖게 된다. 즉, 제 1 서브 행렬(510)이 N×M 행렬일 때, 1개의 블록 시프트는 N개의 열 시프트와 실질적으로 동일하다.
동일하게, 제 2 서브 행렬(520)을 블록 단위로 순환 시프트시켜 제 3 서브 행렬(530)이 생성된다. 이처럼, k 번째 서브 행렬을 블록 단위로 순환 시프트시켜 k+1 번째 서브 행렬을 생성하고, 생성된 서브 행렬들을 병렬로 배열하여 패리티 검사 행렬(500)이 완성된다. 실시 예로서, 패리티 검사 행렬(500)은 반도체 메모리 시스템(1000, 도 1 참조)의 저장 장치(100, 도 1 참조)에 저장될 수 있다. 또는, 패리티 검사 행렬(500)은 컨트롤러(200, 도 1 참조)에 포함된 별도의 저장부(미도시)에 저장될 수 있다. 저장된 패리티 검사 행렬(500)은 읽기 데이터(RD, 도 1 참조)의 디코딩을 위해 호출되어 사용될 수 있다.
상기와 같은 구성에 따르면, 패리티 검사 행렬(500)은 서브 행렬 단위로 블록 순환(Block Circulation)하고, 각각의 블록은 준 순환(Quasi-Cyclic)하는 행렬 구조를 갖는다. 따라서, 종래의 랜덤하고 복잡한 패리티 검사 행렬에 비해, 본 발명에서 제안하는 패리티 검사 행렬(500)은 매우 단순화된 행렬 구조를 갖는다. 따라서, RS-LDPC 디코딩에 필요한 연산량이 감소하고, 검사 노드와 변수 노드를 연결하는 네트워크 구성을 비롯한 전체적인 하드웨어 복잡도가 크게 감소할 수 있다.
도 12는 본 발명에 의해 제안된 패리티 검사 행렬(500)의 생성 방법을 나타내는 순서도이다. 도 12를 참조하면, 패리티 검사 행렬(500)의 생성 방법은 S210 단계 내지 S250 단계를 포함한다.
S210 단계에서, RS 부호의 코드어를 심볼 위치 벡터로 변환하여 제 1 서브 행렬(510, 도 9 참조)의 제 1 행(511, 도 9 참조)을 생성한다. RS 부호의 코드어로부터 제 1 행(511)을 생성하는 구체적인 방법은 위에서 설명한 바와 같다.
S220 단계에서, 제 1 행(511)을 1만큼 순환 시프트시켜 제 2 행(512)을 생성한다. 그리고, 제 2 행(512)을 1만큼 순환 시프트시켜 제 3 행(513)을 생성한다. 동일한 방법으로, N개의 행이 생성될 때까지, 생성된 행을 1씩 순환 시프트시켜 다음 행을 생성한다. 각 행을 순환 시프트시키는 구체적인 방법은 도 9 내지 10에서 설명한 바와 동일하다.
S230 단계에서, 생성된 행들을 병렬로 배열하여, 제 1 서브 행렬(510)을 생성한다.
S240 단계에서, 제 1 서브 행렬(510)을 1블록 만큼 블록 단위로 순환 시프트시켜 제 2 서브 행렬(520)을 생성한다. 그리고, 제 2 서브 행렬(520)을 1블록 만큼 블록 단위로 순환 시프트시켜 제 3 서브 행렬(530)을 생성한다. 동일한 방법으로, 패리티 검사 행렬(500)을 완성하기 위해 필요한 서브 행렬들이 모두 생성될 때까지, 생성된 서브 행렬을 1블록 만큼 블록 단위로 순환 시프트시켜 다음 서브 행렬을 생성한다.
S250 단계에서, 생성된 서브 행렬들을 병렬로 배열하여, 패리티 검사 행렬(500)을 완성한다.
한편, 여기서는 RS 부호의 코드어로부터 제 1 행(511)을 생성하는 것을 예시하였으나, 본 발명은 여기에 한정되지 않는다. 예를 들어, RS 부호의 코드어로부터 제 3 행(513)을 생성하고, 제 3 행(513)을 순차적으로 순환 시프트시켜 제 1 서브 행렬(511)의 나머지 행들을 생성할 수 있다. 이러한 경우에도, 제 1 서브 행렬(511)이 준 순환(Quasi-Cyclic)하는 행렬 구조를 갖는 것은 변하지 않는다.
또한, 여기서는 제 1 서브 행렬(511)의 각 행은 인접한 행을 1씩 순환 시프트시켜 생성되는 것으로 예시하였으나, 본 발명에 따른 제 1 서브 행렬(511)의 각 행은 인접한 행을 2 이상의 소정의 크기만큼 순환 시프트시켜 생성될 수 있다. 예를 들어, p 번째 행을 2씩 순환 시프트시켜 p+1 번째 행을 생성하고(단, p는 1 이상 N-1 이하의 정수), 생성된 행들을 병렬로 배열하여 제 1 서브 행렬(511)을 생성할 수 있다.
또한, 여기서는 서브 행렬을 1 블록의 크기만큼 순환 시프트시켜 인접한 서브 행렬을 생성하는 것으로 예시하였으나, 본 발명에 따른 패리티 검사 행렬(500)의 각 서브 행렬은 인접한 서브 행렬을 2 블록 이상의 크기만큼 블록 순환시켜 생성될 수 있다. 예를 들어, q 번째 서브 행렬을 2 블록만큼 블록 순환시켜 q+1 번째 행을 생성하고(단, q는 1 이상의 정수), 생성된 서브 행렬들을 병렬로 배열하여 패리티 검사 행렬(500)을 생성할 수 있다.
상기와 같은 구성에 따르면, 도 9 내지 도 11에서 설명한 패리티 검사 행렬(500)이 생성될 수 있다.
도 13은 본 발명에 따른 패리티 검사 행렬을 예시적으로 나타내는 도면이다. 도 13을 참조하면, 복수의 블록으로 구성된 복수의 서브 행렬을 포함하는 패리티 검사 행렬(600) 및 블록(610)의 행렬 구조가 예시적으로 도시된다.
도 13을 참조하면, 패리티 검사 행렬(600)은 열방향을 따라 병렬로 배열된 6 개의 서브 행렬을 포함한다. 그리고, 각각의 서브 행렬은 행방향을 따라 직렬로 배열된 28 개의 블록을 포함한다. 패리티 검사 행렬(600)의 서브 행렬들은 순차적으로 서로 블록 순환된다. 예를 들어, 패리티 검사 행렬(600)의 p 번째 서브 행렬의 k 번째 블록은 p+1 번째 서브 행렬의 k+1 번째 블록과 동일하다(단, p는 1 이상 6 이하의 정수, k는 1 이상 27이하의 정수). 다만, 패리티 검사 행렬(600)의 서브 행렬들은 하나의 서브 행렬에 포함된 블록 수를 순환 주기로 하여 서로 블록 순환하므로, p 번째 서브 행렬의 28 번째 블록은 p+1 번째 서브 행렬의 첫 번째 행렬과 동일하다. 이처럼, 패리티 검사 행렬(600)은 동일한 블록들이 일정한 규칙성을 갖고 배열되는 단순한 행렬 구조를 갖는다. 따라서, 패리티 검사 행렬(600)은 하나의 서브 행렬의 행렬 구조로부터 전체 패리티 검사 행렬(600)의 행렬 구조가 용이하게 도출될 수 있다.
다시, 도 13을 참조하면, 패리티 검사 행렬(600)에 포함된 블록의 행렬 구조가 예시적으로 도시된다. 패리티 검사 행렬(600)의 각 행들은 RS 부호의 부호어를 기초로 생성되므로, 패리티 검사 행렬(600)의 각 블록들은 하나의 행에 하나의 '1'을 원소로서 가진다. 즉, 블록의 어떤 행의 5 번째 열의 원소가 '1'이면, 그 행의 5 번째 열의 원소를 제외한 나머지 원소들은 모두 '0'이다. 그리고, 도 9 내지 도 10에서 설명한 바와 같이, 패리티 검사 행렬(600)의 각 블록들은 행단위로 순환하는 행렬 구조를 갖는다. 한편, 패리티 검사 행렬(600)의 각 블록들 안에 쓰여진 숫자는 각 블록들의 제 1 행의 몇 번째 원소가 '1'인지를 나타낸다. 예를 들어, 블록안에 쓰여진 숫자가 40이면, 그 블록의 제 1 행은 40 번째 원소가 '1'이고 나머지 원소는 '0'인 것을 의미한다.
구체적으로, 패리티 검사 행렬(600)의 첫 번째 서브 행렬의 9 번째 블록(610)을 예로 들어 설명한다. 도 13의 하단에는 블록(610)의 행렬 구조가 구체적으로 도시된다. 블록(610)에는 11의 숫자가 쓰여져 있다. 따라서, 블록(610)의 제 1 행은 11번째 원소가 '1'이고 나머지 원소는 '0'이다. 그리고, 블록(610)은 행단위로 1씩 순환하는 구조를 갖는다. 즉, 블록(610)의 i 번째 행의 j 번째 원소와 i+1 번째 행의 j+1 번째 원소는 서로 동일하다. 다만, 블록(610)의 i 번째 행의 마지막 원소는 i+1 번째 행의 첫 번째 원소와 서로 동일하게 됨은 앞에서 살펴본 바와 같다.
이와 같은 블록(610)의 구체적인 행렬 구조가 도 13에 도시되어 있다. 도 13을 참조하면, 블록(610)의 제 1 행의 11 번째 원소는 '1'이고 제 1 행의 나머지 원소들은 '0'이다. 그리고, 블록(610)의 제 2 행은 제 1 행이 1씩 행방향으로 순환 시프트된다. 따라서, 제 2 행의 12 번째 원소가 '1'이고 제 2 행의 나머지 원소들은 '0'이다. 이와 동일한 방식으로, 블록(610)의 모든 행들이 구성된다.
도 14는 본 발명의 실시 예에 따른 도 3의 디코더를 나타내는 블록도이다. 도 14를 참조하면, 디코더(330)는 변수 노드 블록(331), 검사 노드 블록(333), 정정 데이터 관리자(335), 신드롬 검사기(336) 및 스위치 네트워크들(332, 334)을 포함한다. 본 실시 예에서, 디코더(330)는 도 9 내지 도 13에서 제안된 패리티 검사 행렬(500, 도 11 참조)을 사용하여 RS-LDPC 디코딩을 수행한다.
RS-LDPC 디코딩에서 패리티 검사 행렬(500)의 0이 아닌(nonzero) 원소는 대응되는 변수 노드와 검사 노드가 서로 연결되는 것을 의미한다. 그리고, 이러한 변수 노드와 검사 노드의 연결에 따라 전달되는 데이터를 통해 디코딩이 수행된다.
먼저, 읽기 데이터 관리자(310)가 수신한 읽기 데이터(RD)를 우도값 사상기(320)에 전송하면, 우도값 사상기(320)는 전송된 읽기 데이터(RD)에 대응되는 우도값을 디코더(330)에 제공한다.
변수 노드 블록(331)은 제공된 우도값을 저장하고, 저장한 우도값을 변수 노드 메시지로서 제 1 스위치 네트워크(332)를 통해 검사 노드 블록(333)에 제공한다.
검사 노드 블록(331)은 제공된 변수 노드 메시지를 참조하여, 각 검사 노드에 대해 변수 노드들의 값을 비교하여, 제 1 및 제 2 최소값을 검사 노드 메시지(CHK)로서 제공한다. 여기서, 제 1 최소값은 비교된 변수 노드 값들 중 가장 작은 값을 의미하고, 제 2 최소값은 비교된 변수 노드 값들 중 두 번째로 작은 값을 의미한다. 검사 노드 메시지(CHK)는 제 2 스위치 네트워크(334)를 통해 변수 노드 블록(331)으로 제공된다.
변수 노드 블록(331)은 수신된 검사 노드 메시지(CHK)를 참조하여, 변수 노드 및 검사 노드 값들을 갱신한다. 그리고, 갱신된 변수 노드 및 검사 노드 값들에 따라 디코딩을 수행한다. 디코딩된 결과는 디코딩 데이터로서 정정 데이터 관리자(335)에 제공된다.
정정 데이터 관리자(335)는 변수 노드 블록(331)에서 수행된 디코딩 결과를 저장하고, 신드롬 검사기(336)의 디코딩 성공 여부 판단에 따라 외부로 디코딩 데이터(CD) 또는 읽기 에러 메시지(Err)를 출력한다.
신드롬 검사기(336)은 정정 데이터 관리자(335)에 저장된 디코딩 데이터에 따라, 디코딩 성공 여부를 판단한다. 예를 들어, 신드롬 검사기(336)은 디코딩 데이터와 패리티 검사 행렬(500)의 전치 행렬을 곱하고, 곱한 결과가 영행렬인지 아닌지에 따라 디코딩 성공 여부(또는, 에러가 모두 정정되었는지 여부)를 판단한다. 그리고, 디코딩 성공 여부의 판단 결과를 정정 데이터 관리(335)에 제공한다.
실시 예로서, 신드롬 검사기(336)은 디코딩이 실패한 경우, 새로운 디코딩 루프의 실행을 위한 제어 메시지를 변수 노드 블록(331) 또는 제 1 스위치 네트워크(332)에 제공할 수 있다. 이때, 새로운 디코딩 루프에서, 변수 노드 블록(331)은 제어 메시지에 응답하여, 갱신된 변수 노드 값들을 변수 노드 메시지로서 검사 노드 블록(331)으로 제공한다. 그리고, 검사 노드 블록(331)은 제공된 변수 노드 메시지를 참조하여, 새로운 검사 노드 메시지를 변수 노드 블록(331)에 제공한다. 그리고, 변수 노드 블록(331)은 새로운 검사 노드 메시지를 참조하여, 변수 노드 및 검사 노드 값들을 갱신하고, 갱신된 변수 노드 및 검사 노드 값들에 따라 디코딩을 수행한다. 그리고, 디코딩 결과에 따라 신드롬 검사기(336)가 디코딩 성공 여부를 판단하고, 신드롬 검사기(336)의 판단 결과에 따라, 디코딩이 종료되거나 새로운 디코딩 루프가 반복적으로 실행된다.
제 1 및 제 2 스위치 네트워크(332, 334)는 변수 노드 블록(331)과 검사 노드 블록(333) 사이의 데이터 교환을 중계한다. 구체적으로 제 1 스위치 네트워크(332)는 변수 노드 블록(331)으로부터 제공되는 변수 노드 메시지를 검사 노드 블록(333)에 전달한다. 제 2 스위치 네트워크(334)는 검사 노드 블록(333)으로부터 제공되는 검사 노드 메시지를 변수 노드 블록(331)에 전달한다.
본 발명에 따른 디코더(330)에서, 패리티 검사 행렬(500)은 매우 규칙적이고 단순한 구조를 갖는다. 따라서, 변수 노드들과 검사 노드들의 연결 관계도 매우 단순하고 규칙적이다. 따라서, 제 1 및 제 2 스위치 네트워크(332, 334)는 복수의 고정 배선 스위치(hard-wired 스위치) 또는 병렬 시프터를 통해 쉽게 구현될 수 있다. 제 1 및 제 2 스위치 네트워크(332, 334)에 대한 구체적인 내용은 도 15 및 도 16과 함께 후술될 것이다.
상기와 같은 구성에 따르면, 단순한 구조의 패리티 검사 행렬(500)을 사용함으로써 변수 노드들 및 검사 노드들 간의 연결 관계가 단순화된다. 따라서, 변수 노드들 및 검사 노드들 사이의 데이터 교환을 위한 연산량 및 필요 메모리가 감소된다. 또한, 변수 노드 블록(331) 및 검사 노드 블록(333)을 중계하는 스위치 네트워크(332, 334)들이 단순한 하드웨어 구조로 구현될 수 있으므로, 디코더(330)의 하드웨어 복잡도 및 하드웨어 면적이 감소될 수 있다.
한편, 여기서 설명되지 않은 디코더(330) 및 RS-LDPC 디코딩의 일반적인 내용은 당해 기술 분야에 널리 알려져 있으므로, 그에 대한 설명은 생략한다.
도 15는 도 14에 도시된 스위치 네트워크를 예시적으로 나타내는 블록도이다. 도 15에서는 제 1 스위치 네트워크(332, 도 14 참조)의 구체적인 블록도가 도시된다. 한편, 제 2 스위치 네트워크(334, 도 14 참조)는 제 1 스위치 네트워크(332)와 실질적으로 동일한 구성을 가지므로, 본 실시 예에서 제 2 스위치 네트워크(334)에 대한 설명은 생략된다.
도 15를 참조하면, 제 1 스위치 네트워크(332)는 스위치 제어부(332a) 및 연결부(332b)를 포함한다.
스위치 제어부(332a)는 변수 노드 블록(331)로부터 변수 노드 메시지를 수신하고, 클럭 신호에 응답하여 변수 노드 메시지를 복수의 채널 중 대응되는 채널에 할당한다. 변수 노드 메시지가 할당되는 채널은 클럭 신호에 따라 달라질 수 있다. 실시 예로서, 스위치 제어부(310)는 클럭 신호를 발생하는 클럭 카운터(332c)를 포함할 수 있다.
연결부(332b)는 복수의 고정 배선 블록들(10, 20, 30, 40, 50)을 포함한다. 그리고, 고정 배선 블록들(10, 20, 30, 40, 50) 각각은 스위치 제어부(332a)와 연결된 채널을 통해 변수 노드 메시지를 수신한다. 그리고, 고정 배선 블록들(10, 20, 30, 40, 50)은 수신된 변수 노드 메시지를 고정 배선을 통해 미리 정해진 출력 경로로 출력한다.
이때, 고정 배선 블록들(10, 20, 30, 40, 50) 각각은 제 1 서브 행렬(510, 도 10 참조)에 포함된 N×N 정사각 행렬들 중 어느 하나에 대응되도록 입력 단자들과 출력 단자들이 연결된다. 예를 들어, 제 1 고정 배선 블록(10)은 N×N 정사각 행렬(A, 도 10 참조)에 대응되도록 입력 단자들과 출력 단자들이 연결될 수 있다. 또는, 제 2 고정 배선 블록(30)은 N×N 정사각 행렬(C, 도 10 참조)에 대응되도록 입력 단자들과 출력 단자들이 연결될 수 있다. 고정 배선 블록들(10, 30)의 구체적인 구성 및 N×N 정사각 행렬들(A, C)과의 대응 관계는 도 16 및 도 17에서 후술될 것이다.
한편, 제 1 스위치 네트워크(332)는 연결부(332b)에 제 1 서브 행렬(510)에 대응되는 고정 배선 블록들만을 구비하고, 패리티 검사 행렬(500) 전체에 대응되는 데이터 전송을 중계할 수 있다.
예를 들어, 클럭 신호가 제 1 서브 행렬(510)를 나타내는 경우, 스위치 제어부(332b)는 제 1 서브 행렬(510)에 대응되는 변수 노드 메시지를 고정 배선 블록들(10, 20, 30, 40, 50)에 차례로 할당한다. 그리고, 클럭 신호가 제 2 서브 행렬(520, 도 10 참조)를 나타내는 경우, 스위치 제어부(332b)는 변수 노드 메시지가 할당되는 채널을 한 블록씩 시프트시켜, 제 2 고정 배선 블록(20)부터 차례로 변수 노드 메시지를 할당한다. 제 1 고정 배선 블록(10)에는 변수 노드 메시지의 마지막 부분이 할당된다. 패리티 검사 행렬(500)의 각각의 서브 행렬은 서로 블록 순환되는 행렬 구조를 가진다. 따라서, 이와 같이 클럭 신호에 따라 변수 노드 메시지를 할당하는 채널을 단순히 시프트시키는 매우 단순한 연산을 통해, 전체 변수 노드들을 검사 노드들에 연결할 수 있다. 따라서, 변수 노드들과 검사 노드들을 연결하는데 필요한 연산량 및 필요 메모리가 감소한다. 그리고, 최소한의 고정 배선 블록들을 이용하여 스위치 네트워크가 구현되므로, 디코더(330, 도 14 참조)의 하드웨어 복잡도 및 하드웨어 면적이 최소화될 수 있다.
도 16 및 도 17은 본 발명에 따른 스위치 네트워크의 고정 배선 블록을 예시적으로 나타내는 도면이다.
도 16은 제 1 고정 배선 블록(10, 도 15 참조)의 입력-출력 연결 관계를 나타낸다. 도 17은 제 3 고정 배선 블록(30, 도 15 참조)의 입력-출력 연결 관계를 나타낸다. 제 1 및 제 3 고정 배선 블록(10, 30)은 각각 N×N 정사각 행렬(A, C, 도 10 참조)에 대응되는 입력-출력 연결 관계를 갖는 것으로 가정한다.
도 16을 참조하면, N×N 정사각 행렬(A) 및 제 1 고정 배선 블록(10)의 연결 관계가 나타난다. N×N 정사각 행렬(A)은 제 1 행 제 1 열의 원소가 '1'이고 제 1 행의 나머지 원소는 '0'이다. 그리고, 본 발명에 따른 패리티 검사 행렬(500, 도 10 참조)에서 N×N 정사각 행렬(A)은 행단위로 순환하는 행렬 구조를 갖는다. 따라서, N×N 정사각 행렬(A)은 제 i 행 제 i 열의 원소가 '1'이고(단, i는 N 이하의 정수), 나머지 원소는 '0'이다.
패리티 검사 행렬(500)에서 원소 '1'은 대응되는 변수 노드 및 검사 노드가 서로 연결되는 것을 의미한다. 반면에, 패리티 검사 행렬(500)에서 원소 '0'은 대응되는 변수 노드 및 검사 노드가 서로 연결되지 않는 것을 의미한다. 따라서, N×N 정사각 행렬(A)에 따라, 제 1 고정 배선 블록(10)의 변수 노드 단자들(A1, A2, A3, A4, A5, A6, A7, A8)은 검사 노드 단자들(B1, B2, B3, B4, B5, B6, B7, B8)에 차례로 고정 배선된다.
이때, 클럭 신호가 제 1 서브 행렬(510, 도 10 참조)을 나타내면, 스위치 제어부(332a)는 입력되는 변수 노드 메시지의 첫 번째 부분을 제 1 고정 배선 블록(10)과 연결될 채널에 할당할 것이다. 여기서, 변수 노드 메시지의 첫 번째 부분은 제 1 서브 행렬(510)의 첫 번째 N×N 정사각 행렬(A)에 대응되는 변수 노드들로부터 발생한 변수 노드 값들을 의미한다.
그리고, 이때, 클럭 신호가 제 2 서브 행렬(520, 도 10 참조)을 나타내면, 스위치 제어부(332a)는 입력되는 변수 노드 메시지의 두 번째 부분을 제 1 고정 배선 블록(10)과 연결될 채널에 할당할 것이다. 여기서, 변수 노드 메시지의 두 번째 부분은 제 2 서브 행렬(520)의 두 번째 N×N 정사각 행렬(A)에 대응되는 변수 노드들로부터 발생한 변수 노드 값들을 의미한다. 제 2 서브 행렬(520)의 두 번째 N×N 정사각 행렬(A)의 변수 노드-검사 노드 연결 관계는 제 1 서브 행렬(510)의 첫 번째 N×N 정사각 행렬(A)의 변수 노드-검사 노드 연결 관계와 동일한 규칙성을 갖는다. 따라서, 위와 같은 채널 시프트를 통해, 입력되는 변수 노드 메시지에 대응되는 서브 행렬이 바뀌어도, 변수 노드 메시지는 대응되는 검사 노드에 올바르게 할당된다.
도 17을 참조하면, N×N 정사각 행렬(C) 및 제 1 고정 배선 블록(30)의 연결 관계가 나타난다. N×N 정사각 행렬(C)은 제 1 행 제 7 열의 원소가 '1'이고 제 1 행의 나머지 원소는 '0'이다. 그리고, 본 발명에 따른 패리티 검사 행렬(500, 도 10 참조)에서 N×N 정사각 행렬(C)은 행단위로 순환하는 행렬 구조를 갖는다. 따라서, N×N 정사각 행렬(C)은 N×N 정사각 행렬(A)와 마찬가지로 행단위로 1씩 순환 시프트된다.
따라서, N×N 정사각 행렬(C)에 따라, 제 3 고정 배선 블록(30)의 변수 노드 단자들(A1, A2, A3, A4, A5, A6, A7, A8)은 검사 노드 단자들(B3, B4, B5, B6, B7, B8, B1, B2)에 차례로 고정 배선된다.
이때, 클럭 신호가 제 1 서브 행렬(510, 도 10 참조)을 나타내면, 스위치 제어부(332a)는 입력되는 변수 노드 메시지의 세 번째 부분을 제 3 고정 배선 블록(30)과 연결될 채널에 할당할 것이다. 여기서, 변수 노드 메시지의 세 번째 부분은 제 1 서브 행렬(510)의 세 번째 N×N 정사각 행렬(C)에 대응되는 변수 노드들로부터 발생한 변수 노드 값들을 의미한다.
그리고, 이때, 클럭 신호가 제 2 서브 행렬(520, 도 10 참조)을 나타내면, 스위치 제어부(332a)는 입력되는 변수 노드 메시지의 네 번째 부분을 제 3 고정 배선 블록(30)과 연결될 채널에 할당할 것이다. 여기서, 변수 노드 메시지의 네 번째 부분은 제 2 서브 행렬(520)의 네 번째 N×N 정사각 행렬(C)에 대응되는 변수 노드들로부터 발생한 변수 노드 값들을 의미한다. 이처럼, 제 1 스위치 네트워크(15)는 고정 배선 블록과 연결되는 채널을 시프트함으로써, 변수 노드 메시지를 대응되는 검사 노드에 올바르게 할당할 수 있다.
패리티 검사 행렬(500)의 인접하는 서브 행렬들은 한 블록만큼 블록 순환하는 관계에 있다. 따라서, 위와 같이 단순한 채널 시프트를 수행함으로써, 동일한 고정 배선 블록들(10, 20, 30, 40, 50, 도 15 참조)을 통해 패리티 검사 행렬(500)의 모든 변수 노드들 및 검사 노드들 사이의 연결을 수행할 수 있다.
한편, 여기서는 제 1 스위치 네트워크(332)의 구성 및 동작에 대해서만 설명하였다. 그러나, 제 2 스위치 네트워크(334)도 실질적으로 제 1 스위치 네트워크(332)와 동일하게 동작한다. 다만, 제 2 스위치 네트워크(334)는 검사 노드 블록(333)으로부터 검사 노드 메시지를 입력받아 변수 노드 블록(331)에 출력하는 것이 다르다.
한편, 여기서는 제 1 및 제 2 스위치 네트워크(332)를 고정 배선 블록들을 사용하여 구현하는 예만 설명되었으나, 앞서 설명한 바와 같이 제 1 및 제 2 스위치 네트워크(332)는 병렬 시프터(미도시)를 사용하여 구현될 수 있다.
본 발명의 패리티 검사 행렬(500)은 서브 행렬마다 블록 순환하는 행렬 구조를 가진다. 따라서, 병렬 시프터는 제 1 서브 블록(510)에 따른 변수 노드-검사 노드 연결 관계를 기초로 입출력 경로를 병렬 시프트시킴으로써, 전체 패리티 검사 행렬(500)에 대한 변수 노드-검사 노드 간 데이터 전송을 중계할 수 있다.
실시 예로서, 제 1 및 제 2 스위치 네트워크는 병렬 시프터 및 병렬 시프터를 제어하는 제어부를 포함할 수 있다. 병렬 시프터를 포함하는 스위치 네트워크의 구체적인 구성 및 동작은 당해 기술 분야에 널리 알려져 있으므로 그에 대한 설명은 생략한다.
도 18은 도 1에 도시된 반도체 메모리 시스템(1000)의 응용 예를 보여주는 블록도이다. 도 18을를 참조하면, 반도체 메모리 시스템(2000)은 저장 장치(2100) 및 컨트롤러(2200)를 포함한다. 저장 장치(2100)는 복수의 저장 칩들을 포함한다. 복수의 저장 칩들은 복수의 그룹들(2100a, 2100b, 2100c)로 분할된다.
복수의 저장 칩들은 각 그룹마다 하나의 공통 채널을 통해 컨트롤러(2200)와 통신하도록 구성된다. 예시적으로, 복수의 저장 칩들은 복수의 그룹에 각각 할당된 복수의 채널들을 통해 컨트롤러(2200)와 통신할 수 있다.
컨트롤러(2200)는 도 3에서 설명된 EEC 디코더(300, 도 3 참조)와 동일한 구성을 갖는 복수의 ECC 디코더들(ECC1, ECC2, ECCn)을 포함한다. ECC 디코더들(ECC1, ECC2, ECCn)은 저장 장치(2100)로부터 읽어지는 데이터의 에러를 정정한다.
ECC 디코더들(ECC1, ECC2, ECCn)은 컨트롤러(2200)와 저장 장치(2100)를 연결하는 채널들의 수에 해당하는 만큼 제공된다. 하나의 ECC 디코더는 하나의 채널에 연결된 저장 칩들의 에러를 정정한다.
본 실시 예에서 ECC 디코더들(ECC1, ECC2, ECCn)은 저장 장치(2100)로부터 읽어낸 데이터에 대해 RS-LDPC 디코딩을 수행한다. 그리고, ECC 디코더들(ECC1, ECC2, ECCn)은 도 9 내지 도 13에서 설명한 패리티 검사 행렬(500, 도 10 참조)을 사용하여, 변수 노드들과 검사 노드들간에 데이터를 전송하고, 읽어낸 데이터를 디코딩한다. 본 발명에 따른 패리티 검사 행렬(500)은 RS-LDPC 부호의 에러 정정 성능을 유지하면서도, 간단한 행렬 구조를 갖는다. 따라서, 본 실시 예에 따른 메모리 시스템(2000)은 높은 에러 정정 성능을 가지면서, 동시에 ECC 디코더(300)의 하드웨어 복잡도를 감소시킬 수 있다. 또한, ECC 디코더(300)의 연산 처리량도 감소될 수 있다.
도 18에서는, 하나의 채널에 복수의 저장 칩들이 연결되는 것으로 설명되었다. 그러나, 하나의 채널에 하나의 저장 칩이 연결되도록 저장 시스템(2000)은 변형될 수 있다.
도 19는 본 발명의 실시 예에 따른 메모리 카드(3000)를 보여준다. 도 19를 참조하면, 메모리 카드(3000)는 저장 장치(3100), 컨트롤러(3200)를 포함한다. 여기서, 저장 장치(3100)는 플래시 메모리를 비롯한 불휘발성 메모리 장치일 수 있다.
컨트롤러(3200)는 도 3에서 설명된 바와 동일한 ECC 디코더(3300)를 포함한다. ECC 디코더(3300)는 저장 장치(3100)로부터 읽어지는 데이터의 에러를 정정한다.
앞서 설명한 바와 같이 ECC 디코더(3300)는 단순화된 구조를 갖는 패리티 검사 행렬(500, 도 10 참조)을 사용하여, 변수 노드들과 검사 노드들간에 데이터를 전송하고, 읽어낸 데이터를 디코딩한다. 본 발명에 따른 패리티 검사 행렬(500)은 RS-LDPC 부호의 에러 정정 성능을 유지하면서도, 간단한 행렬 구조를 갖는다. 따라서, 본 실시 예에 따른 메모리 카드(3000)는 높은 에러 정정 성능을 가지면서, 동시에 ECC 디코더(3300)의 하드웨어 복잡도를 감소시킬 수 있다. 또한, ECC 디코더(3300)의 연산 처리량도 감소될 수 있다.
메모리 카드(3000)는 PC 카드(PCMCIA, personal computer memory card international association), 컴팩트 플래시 카드(CF), 스마트 미디어 카드(SM, SMC), 메모리 스틱, 멀티미디어 카드(MMC, RS-MMC, MMCmicro), SD 카드(SD, miniSD, microSD, SDHC), 유니버설 플래시 기억장치(UFS) 등과 같은 메모리 카드들을 구성한다.
도 20은 본 발명의 실시 예에 따른 솔리드 스테이트 드라이브(Solid State Drive, 이하 SSD)를 나타내는 블록도이다. 도 20을 참조하면, 사용자 장치(4000)는 SSD(4100) 및 호스트(4200)를 포함한다. SSD(4100)는 불휘발성 메모리 장치(4130), SSD 컨트롤러(4110), ECC 디코더(4120) 및 그리고 버퍼 메모리(4140)를 포함한다.
SSD 컨트롤러(4110)는 호스트(4200)와 SSD(4100)와의 물리적 연결을 제공한다. 즉, SSD 컨트롤러(4110)는 호스트(4200)의 버스 포맷(Bus format)에 대응하여 SSD(4100)와의 인터페이싱을 제공한다. 특히, SSD 컨트롤러(4110)는 호스트(4200)로부터 제공되는 명령어를 디코딩한다. 디코딩된 결과에 따라, SSD 컨트롤러(4110)는 불휘발성 메모리 장치(4130)를 액세스한다. 호스트(4200)의 버스 포맷(Bus format)으로 USB(Universal Serial Bus), SCSI(Small Computer System Interface), PCI express, ATA, PATA(Parallel ATA), SATA(Serial ATA), SAS(Serial Attached SCSI) 등이 포함될 수 있다.
버퍼 메모리(4140)에는 호스트(4200)로부터 제공되는 쓰기 데이터 또는 불휘발성 메모리 장치(4130)로부터 읽혀진 데이터가 일시 저장된다. 호스트(4200)의 읽기 요청시에 불휘발성 메모리 장치(4130)에 존재하는 데이터가 캐시되어 있는 경우에는, 버퍼 메모리(4140)는 캐시된 데이터를 직접 호스트(4200)로 제공하는 캐시 기능을 지원한다. 일반적으로, 호스트(4200)의 버스 포맷(예를 들면, SATA 또는 SAS)에 의한 데이터 전송 속도는 SSD(4100)의 메모리 채널의 전송 속도보다 월등히 빠르다. 즉, 호스트(4200)의 인터페이스 속도가 월등히 높은 경우, 대용량의 버퍼 메모리(4140)를 제공함으로써 속도 차이로 발생하는 퍼포먼스 저하를 최소화할 수 있다.
버퍼 메모리(4140)는 대용량의 보조 기억 장치로 사용되는 SSD(4100)에서 충분한 버퍼링을 제공하기 위해 동기식 DRAM(Synchronous DRAM)으로 제공될 수 있다. 하지만, 버퍼 메모리(4140)가 여기의 개시에 국한되지 않음은 이 분야의 통상적인 지식을 습득한 자들에게 자명하다.
불휘발성 메모리 장치(4130)는 SSD(4100)의 저장 매체로서 제공된다. 예를 들면, 불휘발성 메모리 장치(4130)는 대용량의 저장 능력을 가지는 낸드 플래시 메모리 장치로 제공될 수 있다. 불휘발성 메모리 장치(4130)는 복수의 메모리 장치로 구성될 수 있다. 이 경우, 각각의 메모리 장치들은 채널 단위로 SSD 컨트롤러(4110)와 연결된다. 저장 매체로서 불휘발성 메모리 장치(4130)가 낸드 플래시 메모리 장치인 경우를 예로 들어 설명되었으나, 또 다른 불휘발성 메모리 장치들로 구성될 수 있다. 예를 들면, 저장 매체로서 PRAM, ReRAM, FRAM, MRAM, NOR 플래시 메모리 등이 사용될 수 있으며, 이종의 메모리 장치들이 혼용되는 메모리 시스템도 적용될 수 있다.
상술한 SSD(4100)에서, SSD 컨트롤러(4110)는 도 3에서 설명된 ECC 디코더와 동일한 ECC 디코더(4120)를 포함한다. ECC 디코더(4120)는 불휘발성 메모리 장치(4130)로부터 읽어지는 데이터의 에러를 정정한다.
앞서 설명한 바와 같이 ECC 디코더(4120)는 단순화된 구조를 갖는 패리티 검사 행렬(500, 도 10 참조)을 사용하여, 변수 노드들과 검사 노드들간에 데이터를 전송하고, 읽어낸 데이터를 디코딩한다. 본 발명에 따른 패리티 검사 행렬(500)은 RS-LDPC 부호의 에러 정정 성능을 유지하면서도, 간단한 행렬 구조를 갖는다. 따라서, 본 실시 예에 따른 SSD(4100)는 높은 에러 정정 성능을 가지면서, 동시에 ECC 디코더(4120)의 하드웨어 복잡도를 감소시킬 수 있다. 또한, ECC 디코더(4120)의 연산 처리량도 감소될 수 있다.
도 21은 본 발명의 실시 예에 따른 반도체 메모리 시스템 및 그것을 포함하는 컴퓨팅 시스템의 개략적인 구성을 나타내는 도면이다. 도 21을 참조하면, 본 발명에 따른 컴퓨팅 시스템(5000)은 버스(5600)에 전기적으로 연결된 불휘발성 메모리 장치(5510), 메모리 컨트롤러(5520), 마이크로프로세서(5100), 랜덤 액세스 메모리(5200, RAM) 및 사용자 인터페이스(5300)를 포함할 수 있다.
도 21의 컴퓨팅 시스템(5000)에서, 불휘발성 메모리 장치(5510)는 도 20에서 설명한 불휘발성 메모리 장치(4130, 도 20 참조)와 실질적으로 동일한 장치일 수 있다. 불휘발성 메모리 장치(5510)는 낸드 플래시 메모리 장치일 수 있다.
메모리 컨트롤러(5520)는 도 3에서 설명한 ECC 디코더(300, 도 3 참조)와 동일한 ECC 디코더(5530)를 포함할 수 있다. ECC 디코더(5530)는 불휘발성 메모리 장치(5510)로부터 읽어낸 에러를 정정한다. 앞서 설명한 바와 같이 ECC 디코더(5530)는 단순화된 구조를 갖는 패리티 검사 행렬(500, 도 10 참조)을 사용하여, 변수 노드들과 검사 노드들간에 데이터를 전송하고, 읽어낸 데이터를 디코딩한다. 본 발명에 따른 패리티 검사 행렬(500)은 RS-LDPC 부호의 에러 정정 성능을 유지하면서도, 간단한 행렬 구조를 갖는다. 따라서, 본 실시 예에 따른 반도체 메모리 시스템 장치(5500) 및 그것을 포함하는 컴퓨팅 시스템(5000)은 높은 에러 정정 성능을 가지면서, 동시에 ECC 디코더(5530)의 하드웨어 복잡도를 감소시킬 수 있다. 또한, ECC 디코더(5530)의 연산 처리량도 감소될 수 있다.
본 발명에 따른 컴퓨팅 시스템이 모바일 장치인 경우, 컴퓨팅 시스템의 동작 전압을 공급하기 위한 배터리(5400)가 추가적으로 제공될 수 있다. 비록 도면에는 도시되지 않았지만, 본 발명에 따른 컴퓨팅 시스템에는 응용 칩셋(application chipset), 카메라 이미지 프로세서(Camera Image Processor: CIS), 모바일 디램, 등이 더 제공될 수 있다. 메모리 컨트롤러(6200)와 불휘발성 메모리 장치(6100)는, 예를 들면, 데이터를 저장하는 데 불휘발성 메모리를 사용하는 SSD(Solid State Drive/Disk)를 구성할 수 있다.
본 발명에 따른 불휘발성 메모리 장치 그리고/또는 메모리 컨트롤러는 다양한 형태들의 패키지를 이용하여 실장될 수 있다. 예를 들면, 본 발명에 따른 플래시 메모리 장치 그리고/또는 메모리 컨트롤러는 PoP(Package on Package), Ball grid arrays(BGAs), Chip scale packages(CSPs), Plastic Leaded Chip Carrier(PLCC), Plastic Dual In-Line Package(PDIP), Die in Waffle Pack, Die in Wafer Form, Chip On Board(COB), Ceramic Dual In-Line Package(CERDIP), Plastic Metric Quad Flat Pack(MQFP), Thin Quad Flatpack(TQFP), Small Outline(SOIC), Shrink Small Outline Package(SSOP), Thin Small Outline(TSOP), System In Package(SIP), Multi Chip Package(MCP), Wafer-level Fabricated Package(WFP), Wafer-Level Processed Stack Package(WSP), 등과 같은 패키지들을 이용하여 실장 될 수 있다.
본 발명의 상세한 설명에서는 구체적인 실시 예를 들어 설명하였으나, 본 발명의 범위에서 벗어나지 않는 한 각 실시 예는 여러 가지 형태로 변형될 수 있다. 또한, 여기서 특정한 용어들이 사용되었으나, 이는 단지 본 발명을 설명하기 위한 목적에서 사용된 것이지 의미 한정이나 특허청구범위에 기재된 본 발명의 범위를 제한하기 위하여 사용된 것은 아니다. 그러므로 본 발명의 범위는 상술한 실시 예에 국한되어 정해져서는 안되며 후술하는 특허 청구범위뿐만 아니라 이 발명의 특허 청구범위와 균등한 것들에 의해 정해져야 한다.

Claims (15)

  1. 메모리 장치로부터 읽어낸 데이터를 저장하도록 구성된 읽기 데이터 관리부;
    상기 읽기 데이터 관리부로부터 출력되는 상기 데이터에 우도(Likelihood Ratio)값들을 사상하여 사상 데이터를 출력하도록 구성된 우도값 사상부;
    상기 사상 데이터에 대해, 패리티 검사 행렬(Parity Check Matrix)를 사용하여 저밀도 패리티 검사(Low Density Parity Check) 디코딩을 수행하도록 구성되는 디코딩 부를 포함하고,
    상기 패리티 검사 행렬은 k개의 N×M 서브 행렬을 포함하는 (k*N)×M 행렬이고(단, k는 2보다 크거나 같은 정수이고, N 및 M은 각각 3보다 크거나 같은 정수),
    상기 k개의 N×M 서브 행렬 중 하나는 N×M 크기를 갖는 제1 서브 행렬이고, 상기 k개의 N×M 서브 행렬 중 다른 하나는 N×M 크기를 갖는 제2 서브 행렬이고,
    상기 제2 서브 행렬은 상기 제1 서브 행렬과 인접하여 위치하고, 순환 주기 M에 따라 행 방향으로 N만큼 상기 제1 서브 행렬을 순환 시프트시킴으로써 획득된 행렬과 동일한 원소 배열을 포함하고,
    상기 제1 서브 행렬은:
    리드-솔로몬(Reed-Solomon) 부호에 따라 생성된 부호어(code word)를 심볼 위치 벡터로 변환한 이진 순열인 제1 행; 및
    상기 제1 행과 연속으로 인접하여 위치한 제2 내지 제N 행들을 포함하고,
    상기 제2 내지 제N 행들 각각은 순환 주기 N에 따라 1만큼씩 이전 행을 순차적으로 시프팅시킴으로써 획득된 행과 동일한 원소 배열을 포함하는 반도체 메모리 시스템.
  2. 제 1 항에 있어서,
    상기 디코딩 부는
    우도값 또는 검사 노드 메시지를 참조하여 변수 노드들 및 검사 노드들의 값들을 갱신하고, 상기 변수 노드들 및 상기 검사 노드들의 상기 갱신된 값들에 따라 상기 데이터를 디코딩하도록 구성된 변수 노드 연산부;
    상기 변수 노드들의 상기 갱신된 값들을 변수 노드 메시지로서 수신하고, 상기 수신된 변수 노드 메시지를 참조하여 상기 검사 노드 메시지를 제공하는 검사 노드 연산부;
    변수 노드 블록으로부터 검사 노드 블록으로 상기 변수 노드 메시지의 전송을 중계하도록 구성된 제1 네트워크 부;
    상기 검사 노드 블록으로부터 상기 변수 노드 블록으로 상기 검사 노드 메시지의 전송을 중계하도록 구성된 제2 네트워크 부를 포함하는 반도체 메모리 시스템.
  3. 제 2 항에 있어서,
    상기 제1 네트워크 부 또는 상기 제2 네트워크 부는:
    상기 변수 노드 블록으로부터 입력된 상기 변수 노드 메시지의 적어도 일부를 복수의 채널들 중 어느 하나에 할당하도록 구성된 스위치 제어부; 및
    상기 어느 하나의 채널에 연결된 복수의 입력 단자들을 복수의 출력 단자들에 고정하는 고정 배선 블록을 포함하는 연결부를 포함하는 반도체 메모리 시스템.
  4. 제 3 항에 있어서,
    상기 스위치 제어부는 클럭 신호에 따라 상기 변수 노드 메시지의 적어도 일부를 대신하여 상기 변수 노드 메시지의 다른 일부를 상기 어느 하나의 채널에 할당하는 반도체 메모리 시스템.
  5. 제 2 항에 있어서,
    상기 제1 네트워크 부 또는 상기 제2 네트워크 부는
    상기 패리티 검사 행렬에 따라 상기 변수 노드 메시지를 상기 검사 노드들에 나누어 할당하도록 구성된 병렬 시프터; 및
    상기 병렬 시프터의 동작을 제어하도록 구성된 시프터 제어부를 포함하는 반도체 메모리 시스템.
  6. 제 1 항에 있어서,
    상기 N은 리드-솔로몬(Reed-Solomon) 부호에 따라 상기 부호어(code word)를 생성하기 위해 사용되는 갈루아 필드의 원소의 개수인 반도체 메모리 시스템.
  7. 제 1 항에 있어서,
    상기 저밀도 패리티 검사 디코딩을 기반으로 에러 정정 상태를 판별하도록 구성된 신드롬 검사부를 더 포함하는 반도체 메모리 시스템.
  8. 제 7 항에 있어서,
    상기 에러 정정 상태의 판정 결과에 따라,
    상기 디코딩 부는 페일 메시지를 출력하고,
    상기 읽기 데이터 관리부는 상기 페일 메시지에 응답하여 상기 메모리 장치로부터 읽어낸 추가 데이터를 저장하고,
    상기 우도값 사상부는 상기 추가 데이터에 우도값들을 사상하여 추가 사상 데이터를 출력하고,
    상기 디코딩 부는 상기 추가 사상 데이터에 대해 상기 패리티 검사 행렬을 사용하여 저밀도 패리티 검사를 수행하는 반도체 메모리 시스템.
  9. 제 8 항에 있어서,
    상기 데이터를 읽어내기 위한 읽기 전압 및 상기 추가 데이터를 읽어내기 위한 읽기 전압은 서로 다른 반도체 메모리 시스템.
  10. 제 1 항에 있어서,
    상기 패리티 검사 행렬을 저장하도록 구성된 저장부를 더 포함하는 반도체 메모리 시스템.
  11. 제 1 항에 있어서,
    상기 메모리 장치는 낸드 플래시 메모리를 포함하는 반도체 메모리 시스템.
  12. 제 1 항에 있어서,
    상기 메모리 장치는 불휘발성 메모리를 포함하고,
    상기 읽기 데이터 관리부, 상기 우도값 사상부, 및 상기 디코딩 부는 상기 반도체 메모리 시스템의 메모리 컨트롤러의 에러 정정 부호(ECC; Error correction code) 디코더를 구성하는 반도체 메모리 시스템.
  13. 반도체 메모리 시스템의 데이터 읽기 방법에 있어서,
    제1 읽기 전압들을 사용하여 상기 반도체 메모리 시스템에 저장된 데이터를 읽는 단계;
    패리티 검사 행렬을 사용하여 상기 읽은 데이터에 대한 저밀도 패리티 검사 디코딩을 수행하는 단계; 및
    상기 저밀도 패리티 검사 디코딩 의 결과에 따라 상기 읽은 데이터의 에러를 정정한 결과를 출력하는 단계를 포함하고,
    상기 패리티 검사 행렬은 k개의 N×M 서브 행렬을 포함하는 (k*N)×M 행렬이고(단, k는 2보다 크거나 같은 정수이고, N 및 M은 각각 3보다 크거나 같은 정수),
    상기 k개의 N×M 서브 행렬 중 하나는 N×M 크기를 갖는 제1 서브 행렬이고, 상기 k개의 N×M 서브 행렬 중 다른 하나는 N×M 크기를 갖는 제2 서브 행렬이고,
    상기 제2 서브 행렬은 상기 제1 서브 행렬과 인접하여 위치하고, 순환 주기 M에 따라 행 방향으로 N만큼 상기 제1 서브 행렬을 순환 시프트시킴으로써 획득된 행렬과 동일한 원소 배열을 포함하고,
    상기 제1 서브 행렬은:
    리드-솔로몬(Reed-Solomon) 부호에 따라 생성된 부호어(code word)를 심볼 위치 벡터로 변환한 이진 순열인 제1 행; 및
    상기 제1 행과 연속으로 인접하여 위치한 제2 내지 제N 행들을 포함하고,
    상기 제2 내지 제N 행들 각각은 순환 주기 N에 따라 1만큼씩 이전 행을 순차적으로 시프팅시킴으로써 획득된 행과 동일한 원소 배열을 포함하는 읽기 방법.
  14. 제 13 항에 있어서,
    상기 저밀도 패리티 검사 디코딩의 결과에 따라 제1 읽기 전압과 다른 제2 읽기 전압을 사용하여 상기 저장된 데이터를 다시 읽는 단계; 및
    상기 패리티 검사 행렬을 사용하여 상기 다시 읽은 데이터에 대한 저밀도 패리티 검사 디코딩을 수행하는 단계를 더 포함하는 읽기 방법.
  15. 제 13 항에 있어서,
    상기 데이터는 상기 반도체 메모리 시스템의 낸드 플래시 메모리로부터 읽어지는 읽기 방법.

KR1020130000283A 2012-03-23 2013-01-02 리드-솔로몬 저밀도 패리티 검사 디코더를 포함하는 반도체 메모리 시스템 및 그것의 읽기 방법 Active KR102058499B1 (ko)

Priority Applications (2)

Application Number Priority Date Filing Date Title
KR1020130000283A KR102058499B1 (ko) 2013-01-02 2013-01-02 리드-솔로몬 저밀도 패리티 검사 디코더를 포함하는 반도체 메모리 시스템 및 그것의 읽기 방법
US13/755,222 US9141467B2 (en) 2012-03-23 2013-01-31 Semiconductor memory system including Reed-Solomon low density parity check decoder and read method thereof

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020130000283A KR102058499B1 (ko) 2013-01-02 2013-01-02 리드-솔로몬 저밀도 패리티 검사 디코더를 포함하는 반도체 메모리 시스템 및 그것의 읽기 방법

Publications (2)

Publication Number Publication Date
KR20140088423A KR20140088423A (ko) 2014-07-10
KR102058499B1 true KR102058499B1 (ko) 2020-01-22

Family

ID=51736987

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020130000283A Active KR102058499B1 (ko) 2012-03-23 2013-01-02 리드-솔로몬 저밀도 패리티 검사 디코더를 포함하는 반도체 메모리 시스템 및 그것의 읽기 방법

Country Status (1)

Country Link
KR (1) KR102058499B1 (ko)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR102656075B1 (ko) 2023-06-20 2024-04-08 성균관대학교산학협력단 단일 심볼 오류 정정 및 이중 비트 오류 정정을 위한 부호 생성 방법, 이를 위한 오류 정정 부호 생성 장치

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR102556479B1 (ko) * 2015-03-20 2023-07-17 에스케이하이닉스 주식회사 Ldpc 디코더, 반도체 메모리 시스템 및 그것의 동작 방법
KR102466325B1 (ko) * 2015-12-14 2022-11-15 삼성전자주식회사 저밀도 패리티 검사 코드 생성 방법 및 저밀도 패리티 검사 코드를 생성하는 코드 생성 회로
KR102706994B1 (ko) * 2016-09-07 2024-09-19 에스케이하이닉스 주식회사 메모리 컨트롤러, 반도체 메모리 시스템 및 그것의 동작 방법
CN109298968B (zh) * 2018-10-31 2024-12-27 卓荣集成电路科技有限公司 Qc-ldpc解码器、循环移位矩阵分割方法及存储设备
KR20220057087A (ko) 2020-10-29 2022-05-09 에스케이하이닉스 주식회사 리드-솔로몬 코드의 소프트-디시젼 디코딩 방법 및 장치

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2005302079A (ja) 2004-04-06 2005-10-27 Samsung Electronics Co Ltd ホログラム媒体記録再生装置およびホログラム媒体再生装置

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2009120952A2 (en) * 2008-03-27 2009-10-01 Thomson Licensing Apparatus and method for decoding signals

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2005302079A (ja) 2004-04-06 2005-10-27 Samsung Electronics Co Ltd ホログラム媒体記録再生装置およびホログラム媒体再生装置

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR102656075B1 (ko) 2023-06-20 2024-04-08 성균관대학교산학협력단 단일 심볼 오류 정정 및 이중 비트 오류 정정을 위한 부호 생성 방법, 이를 위한 오류 정정 부호 생성 장치

Also Published As

Publication number Publication date
KR20140088423A (ko) 2014-07-10

Similar Documents

Publication Publication Date Title
US9141467B2 (en) Semiconductor memory system including Reed-Solomon low density parity check decoder and read method thereof
US9996420B2 (en) Error-correction encoding and decoding
US9792176B2 (en) Method and apparatus for encoding and decoding data in memory system
KR102058499B1 (ko) 리드-솔로몬 저밀도 패리티 검사 디코더를 포함하는 반도체 메모리 시스템 및 그것의 읽기 방법
KR101753498B1 (ko) 신뢰도 데이터 업데이트
JP5913560B2 (ja) 低密度パリティチェック符号を使用する符号化および復号技法
US10707902B2 (en) Permutation network designing method, and permutation circuit of QC-LDPC decoder
KR102275717B1 (ko) 플래시 메모리 시스템 및 그의 동작 방법
KR20100081551A (ko) 디코딩 방법 및 그 방법을 이용하는 메모리 시스템 장치
US10606697B2 (en) Method and apparatus for improved data recovery in data storage systems
US9116825B2 (en) Memory controller
US20170134049A1 (en) Decoding method, memory storage device and memory control circuit unit
KR102528972B1 (ko) 연판정 디코딩 방법 및 시스템
US9858994B2 (en) Memory system with MLC memory cells and partial page compression or reduction
KR20230132697A (ko) 일반 연결 코드 코드워드를 디코딩하는 장치, 저장 시스템 및 그 제어 방법
JP5488472B2 (ja) 復号装置、この復号装置を有するデータ通信装置およびデータ記憶装置
US10700708B2 (en) Permutation network designing method, and permutation circuit of QC-LDPC decoder
CN114731166A (zh) 空间耦合fec编码方法和使用gel码的分量码的设备
KR102797517B1 (ko) 국부성을 사용한 일반화된 연접 에러 정정 코딩 방법
KR102719067B1 (ko) 메모리 시스템에서 데이터를 인코딩하고 디코딩하기 위한 방법 및 장치
WO2017132487A1 (en) Apparatus and method for multi-code distributed storage
CN110971240A (zh) 解码器设计方法与存储控制器
KR101722798B1 (ko) 천공 코드의 콤팩트 디코딩
CN113904690A (zh) 解码装置、设备、方法和计算机程序
RU2743784C1 (ru) Способ кодирования данных на основе LDPC кода

Legal Events

Date Code Title Description
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 20130102

PG1501 Laying open of application
PA0201 Request for examination

Patent event code: PA02012R01D

Patent event date: 20171128

Comment text: Request for Examination of Application

Patent event code: PA02011R01I

Patent event date: 20130102

Comment text: Patent Application

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20190304

Patent event code: PE09021S01D

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: 20190917

GRNT Written decision to grant
PR0701 Registration of establishment

Comment text: Registration of Establishment

Patent event date: 20191217

Patent event code: PR07011E01D

PR1002 Payment of registration fee

Payment date: 20191218

End annual number: 3

Start annual number: 1

PG1601 Publication of registration
PR1001 Payment of annual fee

Payment date: 20221123

Start annual number: 4

End annual number: 4

PR1001 Payment of annual fee

Payment date: 20241126

Start annual number: 6

End annual number: 6