[go: up one dir, main page]

KR20080100627A - 오류 제어 코드의 펑쳐링 장치 및 방법 - Google Patents

오류 제어 코드의 펑쳐링 장치 및 방법 Download PDF

Info

Publication number
KR20080100627A
KR20080100627A KR1020070046566A KR20070046566A KR20080100627A KR 20080100627 A KR20080100627 A KR 20080100627A KR 1020070046566 A KR1020070046566 A KR 1020070046566A KR 20070046566 A KR20070046566 A KR 20070046566A KR 20080100627 A KR20080100627 A KR 20080100627A
Authority
KR
South Korea
Prior art keywords
code
bits
codewords
puncturing
codeword
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
KR1020070046566A
Other languages
English (en)
Other versions
KR101134064B1 (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 KR1020070046566A priority Critical patent/KR101134064B1/ko
Priority to US11/889,410 priority patent/US20080288853A1/en
Publication of KR20080100627A publication Critical patent/KR20080100627A/ko
Application granted granted Critical
Publication of KR101134064B1 publication Critical patent/KR101134064B1/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/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/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

Landscapes

  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Error Detection And Correction (AREA)

Abstract

코드 펑쳐링 장치 및 방법이 제공된다. 본 발명의 코드 펑쳐링 장치는 k비트의 유효 정보와 하나의 잉여 비트로부터 생성된 모체 코드워드 가운데 연속된 (n-1)개의 모체 코드워드들을 선택하는 코드워드 선택부, 및 상기 (n-1)개의 모체 코드워드들에 포함된 잉여 비트들 가운데 k개를 선택하고 나머지 잉여 비트들을 삭제하고, 상기 (n-1)개의 모체 코드워드들을 nㆍk 비트의 목표 코드워드로 재배열하는 펑쳐링부를 포함하는 것을 특징으로 하며, 이로 인해 오류 제어 코드의 부호율을 높일 수 있다.
코드 펑쳐링, 오류 제어 코드, 부호율, 저장 매체

Description

오류 제어 코드의 펑쳐링 장치 및 방법 {APARATUS OF PUCTURING OF ERROR CONTROL CODES AND METHOD USING THE APARATUS}
도 1은 본 발명의 일 실시예에 따른 코드 펑쳐링 과정을 나타낸 도면이다.
도 2는 본 발명의 일 실시예에 따른 코드 펑쳐링 장치를 나타낸 블록도이다.
도 3은 본 발명의 일 실시예에 따른 코드 펑쳐링 방법을 나타낸 순서도이다.
도 4는 도 3에 도시된 단계의 일 예를 상세히 나타낸 순서도이다.
<도면의 주요 부분에 대한 부호의 설명>
210: 코드워드 선택부 220: 펑쳐링부
본 발명은 오류 제어 코드(error control codes)에 관한 것으로서, 특히 오류 제어 코드의 부호율(code rate)을 높이기 위한 오류 제어 코드의 펑쳐링(puncturing)에 관한 것이다.
오류 제어 코드는 유효한 정보에 적절한 잉여 정보(redundant information) 를 부가하여 정보의 전달 과정에서 발생할 수 있는 오류를 검출 및 정정할 수 있도록 하는 정보의 처리 방법에 관한 기술이다.
일반적으로 정보를 전달하는 경로를 채널(channel)이라 부를 수 있다. 정보의 전달 과정이 유선 통신이면, 채널은 정보가 전달되는 통신선(communication line)이고, 정보의 전달 과정이 무선 통신이면, 채널은 정보를 포함한 전자기파가 통과하는 대기(air)이다.
반도체 메모리 장치에서는 정보를 포함한 데이터가 반도체 메모리 장치에 저장되었다가 저장된 데이터를 읽어 내는 과정에서 정보의 오류가 생길 수 있으므로, 데이터를 저장하고, 저장된 데이터를 읽어 내는 경로가 채널이 된다.
반도체 메모리 장치에서는 데이터가 저장되는 시점과 저장된 데이터가 출력되는 시점이 다른 것이 일반적이며, 양 시점 사이의 차이가 클수록 데이터의 오류가 생길 가능성이 커지게 된다.
이러한 이유에서, 반도체 메모리 장치에서 오류 제어 코드의 사용의 필요성은 점차 높아지고 있으며, 이러한 경향은 반도체 메모리 장치의 집적도가 높아짐에 따라 더욱 강하게 나타나고 있다.
오류 제어 코드는 유효 정보에 잉여 정보를 부가하는 것이므로 오류 제어 코드의 사용은 반도체 메모리 장치에서 보다 큰 저장 공간을 필요로 하게 된다. 일반적으로, 부가되는 잉여 정보의 유효 정보에 대한 비율이 커질수록 오류 제어 코드의 오류 제어 성능은 향상되지만, 데이터를 저장하는 데 필요한 부가적인 저장 공간의 부담 또한 커지므로, 오류 제어 성능과 부가적인 저장 공간의 부담 사이에 서 트레이드-오프(trade-off)를 통해 최적의 해답을 찾아야 한다.
따라서, 큰 부가적인 저장 공간을 필요로 하지 않으면서도 오류 제어 성능을 향상시킬 수 있는 코드 펑쳐링 방법의 개발은 매우 중요한 문제이다.
본 발명은 상술한 바와 같은 종래 기술의 문제점을 해결하기 위해 안출된 것으로서, 오류 제어 성능의 저하를 가져오지 않으면서도 코드 데이터 저장 공간을 줄일 수 있는 코드 펑쳐링 장치 및 방법을 제안하는 것을 목적으로 한다.
또한, 본 발명은 반도체 메모리 장치에 적용되기에 적합한 오류 제어 코드를 생성할 수 있는 코드 펑쳐링 장치 및 방법을 제안하는 것을 목적으로 한다.
또한, 본 발명은 오류 제어 코드의 부호율을 높일 수 있는 코드 펑쳐링 장치 및 방법을 제안하는 것을 목적으로 한다.
또한, 본 발명은 반도체 메모리 제어 회로의 복잡도를 줄일 수 있는 코드 펑쳐링 장치 및 방법을 제안하는 것을 목적으로 한다.
상기의 목적을 달성하고 종래 기술의 문제점을 해결하기 위하여, 본 발명의 코드 펑쳐링(code puncturing) 장치는 k비트(k는 자연수)의 유효 정보(effective information)와 하나의 잉여 비트(redundancy bit)로부터 생성된 모체 코드워드(mother codeword) 가운데 연속된 (n-1)개의 모체 코드워드들을 선택하는 코드워드 선택부, 및 상기 (n-1)개의 모체 코드워드들에 포함된 잉여 비트들 가운데 k개를 선택하고 나머지 잉여 비트들을 삭제하고, 상기 (n-1)개의 모체 코드워드 들을 nㆍk 비트의 목표 코드워드(target codeword)로 재배열하는 펑쳐링부를 포함하는 것을 특징으로 한다.
또한, 본 발명의 일 실시예에 따른 코드 펑쳐링 방법은 k비트(k는 자연수)의 유효 정보와 하나의 잉여 비트로부터 생성된 모체 코드워드 가운데 연속된 (n-1)개의 모체 코드워드들을 선택하는 단계, 및 상기 (n-1)개의 모체 코드워드들에 포함된 잉여 비트들 가운데 k개를 선택하고 나머지 잉여 비트들을 삭제하고, 상기 (n-1)개의 모체 코드워드들을 nㆍk 비트의 목표 코드워드로 재배열하는 단계를 포함하는 것을 특징으로 한다.
이하, 본 발명에 따른 바람직한 실시예를 첨부된 도면을 참조하여 상세하게 설명한다.
도 1은 본 발명의 일 실시예에 따른 코드 펑쳐링 과정을 도시하는 도면이다.
도 1을 참조하면, 본 발명의 일 실시예에 따른 코드 펑쳐링 과정은 2비트의 유효 정보와 1비트의 잉여 비트로 이루어진 모체 코드워드들(110, 120, 130, 140, 150, 160, 170)로 이루어진 모체 코드에 대해 적용된다.
상기 모체 코드는 2/3의 부호율(code rate)을 가지게 된다. 코드 펑쳐링 과정은 2/3의 부호율을 가지는 상기 모체 코드를 7/8의 부호율을 가지는 목표 코드로 변환한다.
이 때, 상기 7/8의 부호율은 코드 펑쳐링 과정이 메모리 어레이에 적용되는 경우, 상기 메모리 어레이의 구조에 의해 정해지는 것일 수 있다. 따라서, 본 발명의 코드 평쳐링 과정은 메모리 어레이에 적용되기에 적합한 것일 수 있다.
모체 코드워드(110)를 예로 들면, i0 1, i0 2는 각각 유효 정보에 대응하는 비트이고, r0는 잉여 비트이다. 이처럼 유효 정보와 잉여 비트가 명확히 구별되는 코드를 체계적 코드(systematic codes)라 하고, 반대로 유효 정보와 잉여 비트를 별도의 디코딩 과정 없이는 명확히 구별할 수 없는 코드를 비체계적 코드(non-systematic codes)라 한다.
비체계적 코드는 회귀적 과정(recursive process)에 의해 체계적 코드로 변환될 수 있다. 예를 들어, 부호율 1/2인 비체계적 코드의 생성자(generator) g를 g = (g0, g1)이라 하면, 회귀적 과정에 의해 변환된 체계적 코드에 대응하는 새로운 생성자 g'는 g' = (1, g1/g0)로 나타내어질 수 있다.
상기 모체 코드가 체계적 코드이면, 코드 펑쳐링 과정이 반도체 회로에 의해 구현될 경우에 구현된 회로가 간단해지는 장점이 있다. 코드 펑쳐링 과정이 반도체 메모리 회로에 적용되는 대부분의 경우에, 코드 펑쳐링 과정이 반도체 메모리 회로를 제어하는 콘트롤러 또는 페리페럴 회로(peripheral circuit)에 의해 구현된다. 구현된 회로를 간단하게 함으로써 반도체 메모리 회로의 면적이 크게 줄어들 수 있는 장점이 있다.
따라서, 최초에 유효 정보에 기초하여 생성된 코드가 비체계적 코드이면, 코드 펑쳐링 과정은 상기 최초에 생성된 코드를 회귀적 과정에 의해 체계적 코드로 변환하는 과정을 포함할 수 있다.
부호율(code rate)은 코드의 유효 정보의 크기와 코드의 코드워드의 크기의 비율로 나타내어진다. 예를 들어, 부호율이 7/8이 되기 위해서는 8비트 코드가 7비트 유효 정보를 포함하거나 16비트 코드가 14비트 유효 정보를 포함하는 경우가 있을 수 있다.
부호율 2/3을 가지는 상기 모체 코드를 부호율 7/8을 가지는 상기 목표 코드로 변환하는 과정은 다음과 같다.
7개의 상기 모체 코드워드들(110, 120, 130, 140, 150, 160, 170)을 선택하여 하나의 그룹으로 그룹핑한다.
그룹 내에서 상기 모체 코드의 부호율 2/3의 분자인 2에 대응하는 2개의 상기 모체 코드워드들을 선택한다. 이 때, 상기 모체 코드가 컨벌루셔널 코드(convolutional codes)이면, 순서상 앞서는 2개의 상기 모체 코드워드들(110, 120)을 선택한다.
일반적으로 유효 정보에 대한 컨벌루션 연산(convolution operation)을 통해 생성된 컨벌루셔널 코드는 비체계적 코드일 가능성이 높다. 위에서 설명한 바와 같이, 비체계적 코드인 컨벌루셔널 코드는 회귀적 과정에 의하여 체계적 코드로 변환될 수 있으므로, 코드 펑쳐링 과정은 체계적 코드로 변환된 컨벌루셔널 코드를 상기 모체 코드로 선택하여 사용한다.
일반적으로, 컨벌루셔널 코드의 성능은 컨벌루셔널 코드의 앞부분이 오류를 포함하고 있을수록 악화된다. 컨벌루셔널 코드에 대한 펑쳐링 과정은 일부의 잉여 비트를 삭제함으로써 일종의 오류를 발생시키는 것과 유사한 작용을 하게 되 므로 컨벌루셔널 코드에서 앞부분의 모체 코드워드들의 잉여 비트를 제외한 나머지 모체 코드워드들의 잉여 비트를 삭제하는 방법이 우수한 성능을 가지게 된다.
따라서, 순서상 앞선 2개의 모체 코드워드들(110, 120)을 제외한 나머지 모체 코드워드들(130, 140, 150, 160, 170)의 잉여 비트 r2, r3, r4, r5, r6, r7을 삭제하고, 상기 7개의 모체 코드워드들(110, 120, 130, 140, 150, 160, 170)의 유효 정보와 모체 코드워들(110, 120)의 잉여 비트 r0, r1을 포함하는 16비트의 데이터를 재배열하여 목표 코드워드를 생성한다.
목표 코드워드는 16비트의 데이터에 14비트의 유효 정보와 2비트의 잉여 비트를 포함하므로 7/8의 부호율을 가진다.
본 발명의 다른 실시예에 따른 코드 펑쳐링 과정에 의하면, 부호율 k/(k+1)을 가지는 모체 코드로부터 부호율 (n-1)/n을 가지는 목표 코드를 생성할 수 있다.
모체 코드는 k비트의 유효 정보와 하나의 잉여 비트로 이루어진 모체 코드워드들로 이루어진다.
(n-1)개의 모체 코드워드들을 하나의 그룹으로 선택하고, 그룹 내에서 순서상 앞선 k개의 모체 코드워드를 제외한 나머지 모체 코드워드들의 잉여 비트를 삭제한다.
(n-1)ㆍk 비트의 유효 정보와 k 비트의 잉여 비트를 재배열하여 목표 코드워드를 생성한다.
상기 목표 코드워드는 [(n-1)ㆍk + k] = nㆍk 비트의 데이터 가운데 (n-1)ㆍk 비트의 유효 정보를 포함하므로, (n-1)/n 의 부호율을 가진다.
따라서, n > k 인 관계를 만족하면, 목표 코드는 모체 코드보다 높은 부호율을 가지게 된다.
반도체 메모리 장치에서는 데이터의 저장이 가능한 물리적 공간이 한정되어 있으므로, 오류 제어 코드(error control codes, ECC)의 부호율이 높을수록 한정된 물리적 공간에 많은 데이터를 저장할 수 있다. 일반적으로 오류 제어 코드의 부호율이 높으면, 오류 제어 성능은 저하될 수 있으나, 오류 제어 성능을 일정 수준 이상 높이기 위해서 추가로 필요한 데이터 저장 공간이 지나치게 커지면, 반도체 메모리 장치의 가격 상승으로 연결되므로 오류 제어 성능과 반도체 메모리 장치의 경제성 사이에서 트레이드-오프(trade-off)를 통해 최적의 해답을 찾아야 한다.
본 발명의 코드 펑쳐링 과정은 오류 제어 성능을 크게 저하시키지 않으면서도 반도체 메모리 장치에 적용되기에 적합한 오류 제어 코드를 제공한다.
코드 펑쳐링 과정은 체계적 코드를 모체 코드로 선택함으로써, 체계적 코드인 목표 코드를 생성한다.
목표 코드가 체계적 코드이면 유효 정보와 잉여 비트를 별도의 디코딩 과정 없이 분리할 수 있으므로, 코드 펑쳐링 과정은 목표 코드를 저장하거나 저장된 목표 코드를 읽어 내는 과정에서 유효 정보와 잉여 비트를 구분하는 데에 별도의 부가적인 회로 또는 연산 장치를 필요로 하지 않는다.
만일 코드 펑쳐링 과정이 반도체 메모리 장치에 적용된다면, 코드 펑쳐링 과정은 반도체 메모리 장치의 주변 회로(peripheral circuit) 또는 컨트롤러 등에 포함되는 반도체 회로를 통해 구현된다. 이 때, 코드 펑쳐링 과정은 주변 회로 등에 포함되는 반도체 회로의 복잡도를 크게 떨어뜨린 효과가 있다.
반도체 회로의 복잡도 감소는 반도체 메모리 장치의 전체 면적의 감소로 이어지게 되므로, 코드 펑쳐링 과정은 반도체 메모리 장치의 경제성을 크게 증가시키는데 기여할 수 있다.
도 2는 본 발명의 일 실시예에 따른 코드 펑쳐링 장치를 나타내는 블록도이다.
도 2를 참조하면, 본 발명의 일 실시예에 따른 코드 펑쳐링 장치는 코드워드 선택부(210), 펑쳐링부(220)를 포함한다.
코드워드 선택부(210)는 k비트(k는 자연수)의 유효 정보와 하나의 잉여 비트로부터 생성된 모체 코드워드 가운데 연속된 (n-1)개의 모체 코드워드들을 선택한다.
상기 모체 코드는 k/(k+1)의 부호율을 가진다.
이 때, 상기 모체 코드는 상기 유효 정보와 상기 잉여 비트가 구분되는 체계적 코드일 수 있다.
이 때, 상기 모체 코드는 상기 유효 정보에 대한 컨벌루션 연산을 통해 생성된 컨벌루셔널 코드일 수 있다.
이 때, 상기 유효 정보에 대한 컨벌루션 연산을 통해 생성된 컨벌루셔널 코드가 상기 유효 정보와 상기 잉여 비트가 직접적으로 구분되지 않는 비체계적 코 드이면, 코드워드 선택부(210)는 상기 비체계적 코드를 회귀적 과정에 의하여 체계적 코드로 변환하고, 상기 변환된 체계적 코드를 상기 모체 코드로 선택할 수 있다.
이 때, 상기 기설정된 자연수 n은 상기 코드 펑쳐링 장치와 연결되는 메모리의 어레이 구조에 의하여 정해지는 것일 수 있다.
상기 메모리의 어레이가 16개의 메모리 셀들을 하나의 단위로 하여 상기 단위가 반복되는 구조를 가지면, 상기 자연수 n은 16으로 정해질 수 있다.
일반적으로, 상기 메모리의 어레이는 2M (M은 자연수) 개의 메모리 셀들을 하나의 단위로 하여 상기 단위가 반복되는 구조를 가지므로, 상기 자연수 n = 2M 일 수 있다.
펑쳐링부(220)는 상기 (n-1)개의 모체 코드워드들에 포함된 잉여 비트들 가운데 k개를 선택하고 나머지 잉여 비트들을 삭제하고, 상기 (n-1)개의 모체 코드워드들을 nㆍk 비트의 목표 코드워드로 재배열한다.
상기 목표 코드워드로 이루어진 목표 코드는 (n-1)/n의 부호율을 가진다.
이 때, 상기 펑쳐링부(220)는 상기 (n-1)개의 모체 코드워드들에 포함된 잉여 비트들 가운데 순서상 앞서는 상기 모체 코드워드에 포함된 상기 k개 만큼의 잉여 비트를 제외한 나머지 잉여 비트들을 삭제할 수 있다.
본 발명의 다른 실시예에 따른 코드 펑쳐링 장치의 코드워드 선택부는 상기 유효 정보에 대한 컨벌루션 연산을 통해 생성된 컨벌루셔널 코드로부터, 회귀적 코드를 생성하는 방법을 이용하여 상기 하나의 잉여 비트를 포함하는 체계적 코드를 생성하고, 상기 체계적 코드를 상기 모체 코드로 선택할 수 있다.
이 때, 상기 펑쳐링부는 상기 하나의 그룹에 포함된 잉여 비트들 가운데 순서상 앞서는 상기 모체 코드워드에 포함된 상기 k개 만큼의 잉여 비트를 제외한 나머지 잉여 비트들을 삭제할 수 있다.
도 3은 본 발명의 일 실시예에 따른 코드 펑쳐링 방법을 나타내는 동작 흐름도이다.
도 3을 참조하면, 본 발명의 일 실시예에 따른 코드 펑쳐링 방법은 k비트(k는 자연수)의 유효 정보와 하나의 잉여 비트로부터 생성된 모체 코드워드 가운데 연속된 (n-1)개의 모체 코드워드들을 선택한다(S310).
이 때, 상기 모체 코드는 상기 유효 정보와 상기 잉여 비트가 구분되는 체계적 코드일 수 있다.
이 때, 상기 모체 코드는 상기 유효 정보에 대한 컨벌루션 연산을 통해 생성된 컨벌루셔널 코드일 수 있다.
이 때, 상기 유효 정보에 대한 컨벌루션 연산을 통해 생성된 컨벌루셔널 코드가 상기 유효 정보와 상기 잉여 비트가 직접적으로 구분되지 않는 비체계적 코드이면, 코드 펑쳐링 방법은 상기 비체계적 코드를 회귀적 과정에 의하여 체계적 코드로 변환하고, 상기 변환된 체계적 코드를 상기 모체 코드로 선택할 수 있다.
이 때, 상기 기설정된 자연수 n은 상기 코드 펑쳐링 방법이 적용되는 메모리의 어레이 구조에 의하여 정해지는 것일 수 있다.
상기 메모리의 어레이가 16개의 메모리 셀들을 하나의 단위로 하여 상기 단위가 반복되는 구조를 가지면, 상기 자연수 n은 16으로 정해질 수 있다.
일반적으로, 상기 메모리의 어레이는 2M (M은 자연수) 개의 메모리 셀들을 하나의 단위로 하여 상기 단위가 반복되는 구조를 가지므로, 상기 자연수 n = 2M 일 수 있다.
코드 펑쳐링 방법은 상기 (n-1)개의 모체 코드워드들에 포함된 잉여 비트들 가운데 k개를 선택하고 나머지 잉여 비트들을 삭제하고, 상기 (n-1)개의 모체 코드워드들을 nㆍk 비트의 목표 코드워드로 재배열한다(S320).
상기 목표 코드워드로 이루어진 목표 코드는 (n-1)/n의 부호율을 가진다.
이 때, 코드 펑쳐링 방법은 상기 (n-1)개의 모체 코드워드들에 포함된 잉여 비트들 가운데 순서상 앞서는 상기 모체 코드워드에 포함된 상기 k개 만큼의 잉여 비트를 제외한 나머지 잉여 비트들을 삭제할 수 있다.
도 4는 본 발명의 일 실시예에 따른 코드 펑쳐링 방법의 한 단계를 더욱 상세히 나타내는 동작 흐름도이다.
도 4를 참조하면, 본 발명의 일 실시예에 따른 코드 펑쳐링 방법은 상기 유효 정보에 대한 컨벌루션 연산을 통해 컨벌루셔널 코드를 생성한다(S410).
코드 펑쳐링 방법은 상기 생성된 컨벌루셔널 코드로부터, 회귀적 코드를 생성하는 방법을 이용하여 상기 하나의 잉여 비트를 포함하는 체계적 코드를 생성한다(S420).
코드 펑쳐링 방법은 상기 생성된 체계적 코드를 상기 모체 코드로 선택한다(S430).
이 때, 코드 펑쳐링 방법은 상기 하나의 그룹에 포함된 잉여 비트들 가운데 순서상 앞서는 상기 모체 코드워드에 포함된 상기 k개 만큼의 잉여 비트를 제외한 나머지 잉여 비트들을 삭제할 수 있다.
본 발명에 따른 코드 펑쳐링 방법은 다양한 컴퓨터 수단을 통하여 수행될 수 있는 프로그램 명령 형태로 구현되어 컴퓨터 판독 가능 매체에 기록될 수 있다. 상기 컴퓨터 판독 가능 매체는 프로그램 명령, 데이터 파일, 데이터 구조 등을 단독으로 또는 조합하여 포함할 수 있다. 상기 매체에 기록되는 프로그램 명령은 본 발명을 위하여 특별히 설계되고 구성된 것들이거나 컴퓨터 소프트웨어 당업자에게 공지되어 사용 가능한 것일 수도 있다. 컴퓨터 판독 가능 기록 매체의 예에는 하드 디스크, 플로피 디스크 및 자기 테이프와 같은 자기 매체(magnetic media), CD-ROM, DVD와 같은 광기록 매체(optical media), 플롭티컬 디스크(floptical disk)와 같은 자기-광 매체(magneto-optical media), 및 롬(ROM), 램(RAM), 플래시 메모리 등과 같은 프로그램 명령을 저장하고 수행하도록 특별히 구성된 하드웨어 장치가 포함된다. 상기 매체는 프로그램 명령, 데이터 구조 등을 지정하는 신호를 전송하는 반송파를 포함하는 광 또는 금속선, 도파관 등의 전송 매체일 수도 있다. 프로그램 명령의 예에는 컴파일러에 의해 만들어지는 것과 같은 기계어 코드뿐만 아니라 인터프리터 등을 사용해서 컴퓨터에 의해서 실행될 수 있는 고급 언어 코드를 포함한다. 상기된 하드웨어 장치는 본 발명의 동작을 수행하기 위해 하나 이상의 소프트웨어 모듈로서 작동하도록 구성될 수 있으며, 그 역도 마찬가지이다.
이상과 같이 본 발명은 비록 한정된 실시예와 도면에 의해 설명되었으나, 본 발명은 상기의 실시예에 한정되는 것은 아니며, 본 발명이 속하는 분야에서 통상의 지식을 가진 자라면 이러한 기재로부터 다양한 수정 및 변형이 가능하다.
그러므로, 본 발명의 범위는 설명된 실시예에 국한되어 정해져서는 아니 되며, 후술하는 특허청구범위뿐 아니라 이 특허청구범위와 균등한 것들에 의해 정해져야 한다.
본 발명에 따르면 오류 제어 성능의 저하를 가져오지 않으면서도 코드 데이터 저장 공간을 줄일 수 있는 코드 펑쳐링 장치 및 방법의 구현이 가능하다.
또한, 본 발명에 따르면 반도체 메모리 장치에 적용되기에 적합한 오류 제어 코드를 생성할 수 있는 코드 펑쳐링 장치 및 방법의 구현이 가능하다.
또한, 본 발명에 따르면 오류 제어 코드의 부호율을 높일 수 있는 코드 펑쳐링 장치 및 방법의 구현이 가능하다.
또한, 본 발명에 따르면 반도체 메모리 제어 회로의 복잡도를 줄일 수 있는 코드 펑쳐링 장치 및 방법의 구현이 가능하다.

Claims (15)

  1. k비트(k는 자연수)의 유효 정보와 하나의 잉여 비트로부터 생성된 모체 코드워드 가운데 연속된 (n-1)개의 모체 코드워드들을 선택하는 코드워드 선택부; 및
    상기 (n-1)개의 모체 코드워드들에 포함된 잉여 비트들 가운데 k개를 선택하고 나머지 잉여 비트들을 삭제하고, 상기 (n-1)개의 모체 코드워드들을 nㆍk 비트의 목표 코드워드로 재배열하는 펑쳐링부
    를 포함하는 코드 펑쳐링 장치.
  2. 제1항에 있어서,
    상기 기설정된 자연수 n은 상기 코드 펑쳐링 장치와 연결되는 메모리의 어레이 구조에 의하여 정해지는 것을 특징으로 하는 코드 펑쳐링 장치.
  3. 제1항에 있어서,
    상기 모체 코드워드는
    상기 유효 정보와 상기 잉여 비트가 구분되는 체계적 코드인 것을 특징으로 하는 코드 펑쳐링 장치.
  4. 제3항에 있어서,
    상기 모체 코드워드는
    상기 유효 정보에 대한 컨벌루션 연산을 통해 생성된 컨벌루셔널 코드인 것을 특징으로 하는 코드 펑쳐링 장치.
  5. 제4항에 있어서,
    상기 펑쳐링부는
    상기 (n-1)개의 모체 코드워드들에 포함된 잉여 비트들 가운데 순서상 앞서는 k개 만큼의 잉여 비트를 제외한 나머지 잉여 비트들을 삭제하는 것을 특징으로 하는 코드 펑쳐링 장치.
  6. 제1항에 있어서,
    상기 코드워드 선택부는
    상기 유효 정보에 대한 컨벌루션 연산을 통해 생성된 컨벌루셔널 코드로부터, 회귀적 코드를 생성하는 방법을 이용하여 상기 하나의 잉여 비트를 포함하는 체계적 코드를 생성하고, 상기 체계적 코드 가운데 연속된 (n-1)개의 모체 코드워드들을 선택하는 것을 특징으로 하는 코드 펑쳐링 장치.
  7. 제6항에 있어서,
    상기 펑쳐링부는
    상기 (n-1)개의 모체 코드워드들에 포함된 잉여 비트들 가운데 순서상 앞서는 k개 만큼의 잉여 비트를 제외한 나머지 잉여 비트들을 삭제하는 것을 특징으 로 하는 코드 펑쳐링 장치.
  8. k비트(k는 자연수)의 유효 정보와 하나의 잉여 비트로부터 생성된 모체 코드워드 가운데 연속된 (n-1)개의 모체 코드워드들을 선택하는 단계; 및
    상기 (n-1)개의 모체 코드워드들에 포함된 잉여 비트들 가운데 k개를 선택하고 나머지 잉여 비트들을 삭제하고, 상기 (n-1)개의 모체 코드워드들을 nㆍk 비트의 목표 코드워드로 재배열하는 단계
    를 포함하는 코드 펑쳐링 방법.
  9. 제8항에 있어서,
    상기 기설정된 자연수 n은 상기 코드 펑쳐링 방법이 적용되는 메모리의 어레이 구조에 의하여 정해지는 것을 특징으로 하는 코드 펑쳐링 방법.
  10. 제8항에 있어서,
    상기 모체 코드워드는
    상기 유효 정보와 상기 잉여 비트가 구분되는 체계적 코드인 것을 특징으로 하는 코드 펑쳐링 방법.
  11. 제10항에 있어서,
    상기 모체 코드워드는
    상기 유효 정보에 대한 컨벌루션 연산을 통해 생성된 컨벌루셔널 코드인 것을 특징으로 하는 코드 펑쳐링 방법.
  12. 제11항에 있어서,
    상기 (n-1)개의 모체 코드워드들을 목표 코드워드로 재배열하는 단계는
    상기 하나의 그룹에 포함된 잉여 비트들 가운데 순서상 앞서는 k개 만큼의 잉여 비트를 제외한 나머지 잉여 비트들을 삭제하는 것을 특징으로 하는 코드 펑쳐링 방법.
  13. 제8항에 있어서,
    상기 (n-1)개의 모체 코드워드들을 선택하는 단계는
    상기 유효 정보에 대한 컨벌루션 연산을 통해 생성된 컨벌루셔널 코드로부터, 회귀적 코드를 생성하는 방법을 이용하여 상기 하나의 잉여 비트를 포함하는 체계적 코드를 생성하고, 상기 체계적 코드 가운데 (n-1)개의 모체 코드워드들을 선택하는 것을 특징으로 하는 코드 펑쳐링 방법.
  14. 제13항에 있어서,
    상기 (n-1)개의 모체 코드워드들을 목표 코드워드로 재배열하는 단계는
    상기 하나의 그룹에 포함된 잉여 비트들 가운데 순서상 앞서는 k개 만큼의 잉여 비트를 제외한 나머지 잉여 비트들을 삭제하는 것을 특징으로 하는 코드 펑쳐 링 방법.
  15. 제8항 내지 제14항 중 어느 한 항의 방법을 실행하기 위한 프로그램이 기록되어 있는 것을 특징으로 하는 컴퓨터에서 판독 가능한 기록 매체.
KR1020070046566A 2007-05-14 2007-05-14 오류 제어 코드의 펑쳐링 장치 및 방법 Active KR101134064B1 (ko)

Priority Applications (2)

Application Number Priority Date Filing Date Title
KR1020070046566A KR101134064B1 (ko) 2007-05-14 2007-05-14 오류 제어 코드의 펑쳐링 장치 및 방법
US11/889,410 US20080288853A1 (en) 2007-05-14 2007-08-13 Apparatus and method of puncturing of error control codes

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020070046566A KR101134064B1 (ko) 2007-05-14 2007-05-14 오류 제어 코드의 펑쳐링 장치 및 방법

Publications (2)

Publication Number Publication Date
KR20080100627A true KR20080100627A (ko) 2008-11-19
KR101134064B1 KR101134064B1 (ko) 2012-04-13

Family

ID=40028763

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020070046566A Active KR101134064B1 (ko) 2007-05-14 2007-05-14 오류 제어 코드의 펑쳐링 장치 및 방법

Country Status (2)

Country Link
US (1) US20080288853A1 (ko)
KR (1) KR101134064B1 (ko)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR102296738B1 (ko) 2015-06-01 2021-09-01 삼성전자 주식회사 반도체 메모리 장치, 이를 포함하는 메모리 시스템 및 반도체 메모리 장치의 에러 정정 방법

Family Cites Families (17)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE3724729A1 (de) * 1987-07-25 1989-02-02 Ant Nachrichtentech Verfahren zur aufbereitung eines faltungscodes zur uebertragung sowie dessen empfangsseitige rueckwandlung sowie anordnung hierzu
JP2531533B2 (ja) * 1988-08-25 1996-09-04 富士通株式会社 逐次復号器
US5844922A (en) * 1993-02-22 1998-12-01 Qualcomm Incorporated High rate trellis coding and decoding method and apparatus
US5438590A (en) * 1993-05-24 1995-08-01 Comstream Corporation Transmitting and receiving apparatus and method including punctured convolutional encoding and decoding
US5511082A (en) * 1994-05-10 1996-04-23 General Instrument Corporation Of Delaware Punctured convolutional encoder
GB9622540D0 (en) * 1996-10-30 1997-01-08 Discovision Ass Trackback for viterbi decoder
EP0848524A1 (fr) * 1996-12-10 1998-06-17 Koninklijke Philips Electronics N.V. MAQ à codage perforé en trellis, avec décodage itératif
KR19990003242A (ko) * 1997-06-25 1999-01-15 윤종용 구조적 펀처드 길쌈부호 부호와 및 복호기
CA2474859C (en) * 1998-04-06 2007-06-19 Nortel Networks Limited Encoding and decoding methods and apparatus
US6738949B2 (en) * 1998-05-13 2004-05-18 Matsushita Electric Industrial Co., Ltd. Error correction circuit and error correction method
KR100315708B1 (ko) * 1998-12-31 2002-02-28 윤종용 이동통신시스템에서터보인코더의펑처링장치및방법
KR100451716B1 (ko) * 1999-08-24 2004-10-08 엘지전자 주식회사 이동 통신 시스템의 레이트 매칭 방법
JP2003518800A (ja) * 1999-12-20 2003-06-10 コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ 改善されたデコーダーを備えた受信機
US6807238B1 (en) * 2001-02-01 2004-10-19 Lsi Logic Corporation Method and apparatus for decoding M-PSK turbo code using new approximation technique
US6903665B2 (en) * 2002-10-30 2005-06-07 Spacebridge Semiconductor Corporation Method and apparatus for error control coding in communication systems using an outer interleaver
US7489621B2 (en) * 2003-12-30 2009-02-10 Alexander A Maltsev Adaptive puncturing technique for multicarrier systems
US7685505B2 (en) * 2004-01-20 2010-03-23 Qualcomm Incorporated Coding apparatus, and associated method, for forming a punctured binary convolutional code for use in a radio communication system

Also Published As

Publication number Publication date
KR101134064B1 (ko) 2012-04-13
US20080288853A1 (en) 2008-11-20

Similar Documents

Publication Publication Date Title
US9141467B2 (en) Semiconductor memory system including Reed-Solomon low density parity check decoder and read method thereof
US8321746B2 (en) Systems and methods for quasi-cyclic LDPC code production and decoding
KR102851230B1 (ko) 메모리 컨트롤러
KR102275717B1 (ko) 플래시 메모리 시스템 및 그의 동작 방법
TW200417156A (en) Rate-compatible LDPC codes
JP2007087529A (ja) 信号復号装置、信号復号方法、および記憶システム
US11888500B2 (en) Encoding circuit, decoding circuit, and decoding method
US10379756B2 (en) Logical format utilizing lateral encoding of data for storage on magnetic tape
US8832525B2 (en) Memory controller with low density parity check code decoding capability and relevant memory controlling method
KR20190072972A (ko) 컨볼루션 타입의 저밀도 패리티 체크 코드를 이용하여 인코딩 및 디코딩을 수행하는 메모리 컨트롤러, 이를 포함하는 메모리 시스템 및 이의 동작 방법
KR20230132697A (ko) 일반 연결 코드 코드워드를 디코딩하는 장치, 저장 시스템 및 그 제어 방법
KR102058499B1 (ko) 리드-솔로몬 저밀도 패리티 검사 디코더를 포함하는 반도체 메모리 시스템 및 그것의 읽기 방법
CN113131947B (zh) 译码方法、译码器和译码装置
US8566665B2 (en) Systems and methods for error correction using low density parity check codes using multiple layer check equations
US9639421B2 (en) Operating method of flash memory system
KR20190019798A (ko) 채널 편파 코드의 연속 제거 리스트 디코딩을 위한 효율적인 생존 메모리 아키텍처
JP5488472B2 (ja) 復号装置、この復号装置を有するデータ通信装置およびデータ記憶装置
KR102797517B1 (ko) 국부성을 사용한 일반화된 연접 에러 정정 코딩 방법
JP7429223B2 (ja) ターボ積符号の復号方法、装置、デコーダー及びコンピュータ記憶媒体
KR20060056933A (ko) 데이터를 엔코딩 및 디코딩하는 방법 및 장치
CN110795271B (zh) 对用户数据执行纠错的纠错电路和使用其的纠错方法
KR101134064B1 (ko) 오류 제어 코드의 펑쳐링 장치 및 방법
KR101355988B1 (ko) 연접 비씨에이치 부호, 복호 및 다계층 복호 회로 및 방법, 이를 이용한 플래쉬 메모리 장치의 오류 정정 회로 및 플래쉬 메모리 장치
US20120089883A1 (en) Systems and Methods for Error Correction Using Irregular Low Density Parity Check Codes
KR101496052B1 (ko) 블록 단위 연접 bch 부호 성능 개선 및 오류마루 경감을 위해 순환 자리 이동을 활용하는 복호 기법 및 회로

Legal Events

Date Code Title Description
A201 Request for examination
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 20070514

PA0201 Request for examination
E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20080527

Patent event code: PE09021S01D

AMND Amendment
PG1501 Laying open of application
E601 Decision to refuse application
PE0601 Decision on rejection of patent

Patent event date: 20081125

Comment text: Decision to Refuse Application

Patent event code: PE06012S01D

Patent event date: 20080527

Comment text: Notification of reason for refusal

Patent event code: PE06011S01I

J201 Request for trial against refusal decision
PJ0201 Trial against decision of rejection

Patent event date: 20081224

Comment text: Request for Trial against Decision on Refusal

Patent event code: PJ02012R01D

Patent event date: 20081125

Comment text: Decision to Refuse Application

Patent event code: PJ02011S01I

Appeal kind category: Appeal against decision to decline refusal

Decision date: 20101019

Appeal identifier: 2008101013675

Request date: 20081224

AMND Amendment
PB0901 Examination by re-examination before a trial

Comment text: Amendment to Specification, etc.

Patent event date: 20090123

Patent event code: PB09011R02I

Comment text: Request for Trial against Decision on Refusal

Patent event date: 20081224

Patent event code: PB09011R01I

Comment text: Amendment to Specification, etc.

Patent event date: 20080711

Patent event code: PB09011R02I

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

Comment text: Notification of reason for refusal

Patent event date: 20090211

Patent event code: PE09021S01D

B601 Maintenance of original decision after re-examination before a trial
PB0601 Maintenance of original decision after re-examination before a trial

Comment text: Report of Result of Re-examination before a Trial

Patent event code: PB06011S01D

Patent event date: 20090922

J301 Trial decision

Free format text: TRIAL DECISION FOR APPEAL AGAINST DECISION TO DECLINE REFUSAL REQUESTED 20081224

Effective date: 20101019

PJ1301 Trial decision

Patent event code: PJ13011S01D

Patent event date: 20101019

Comment text: Trial Decision on Objection to Decision on Refusal

Appeal kind category: Appeal against decision to decline refusal

Request date: 20081224

Decision date: 20101019

Appeal identifier: 2008101013675

PS0901 Examination by remand of revocation
S901 Examination by remand of revocation
E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20101122

Patent event code: PE09021S01D

PE0902 Notice of grounds for rejection

Comment text: Final Notice of Reason for Refusal

Patent event date: 20110804

Patent event code: PE09021S02D

PS0701 Decision of registration after remand of revocation

Patent event date: 20120321

Patent event code: PS07012S01D

Comment text: Decision to Grant Registration

Patent event date: 20101020

Patent event code: PS07011S01I

Comment text: Notice of Trial Decision (Remand of Revocation)

GRNT Written decision to grant
PR0701 Registration of establishment

Comment text: Registration of Establishment

Patent event date: 20120330

Patent event code: PR07011E01D

PR1002 Payment of registration fee

Payment date: 20120402

End annual number: 3

Start annual number: 1

PG1601 Publication of registration
FPAY Annual fee payment

Payment date: 20150302

Year of fee payment: 4

PR1001 Payment of annual fee

Payment date: 20150302

Start annual number: 4

End annual number: 4

PR1001 Payment of annual fee

Payment date: 20160229

Start annual number: 5

End annual number: 5

FPAY Annual fee payment

Payment date: 20170228

Year of fee payment: 6

PR1001 Payment of annual fee

Payment date: 20170228

Start annual number: 6

End annual number: 6

FPAY Annual fee payment

Payment date: 20180228

Year of fee payment: 7

PR1001 Payment of annual fee

Payment date: 20180228

Start annual number: 7

End annual number: 7

FPAY Annual fee payment

Payment date: 20190228

Year of fee payment: 8

PR1001 Payment of annual fee

Payment date: 20190228

Start annual number: 8

End annual number: 8

PR1001 Payment of annual fee

Payment date: 20200228

Start annual number: 9

End annual number: 9

PR1001 Payment of annual fee

Payment date: 20210225

Start annual number: 10

End annual number: 10

PR1001 Payment of annual fee

Payment date: 20220223

Start annual number: 11

End annual number: 11

PR1001 Payment of annual fee

Payment date: 20240227

Start annual number: 13

End annual number: 13

PR1001 Payment of annual fee

Payment date: 20250225

Start annual number: 14

End annual number: 14