KR102783025B1

KR102783025B1 - ECC decoder, memory controller including the ECC decoder, and ECC decoding method

Info

Publication number: KR102783025B1
Application number: KR1020160158368A
Authority: KR
Inventors: 김수진
Original assignee: 에스케이하이닉스 주식회사
Priority date: 2016-11-25
Filing date: 2016-11-25
Publication date: 2025-03-18
Anticipated expiration: 2036-11-25
Also published as: KR20180059149A

Abstract

에러 정정 코드 디코더는, 입력되는 코드워드에서 제로-패딩 비트들을 제거하여 필터링된 코드워드를 발생시키는 제로-패딩 비트 제거부와, 필터링된 코드워드에 대한 신드롬들을 출력하는 신드롬 연산부와, 신드롬들을 이용하여 에러 위치 다항식의 계수들을 출력하는 에러 위치 다항식 연산부와, 계수들을 이용하여 에러 위치를 연산하여 출력하는 에러 위치 연산부, 및 에러 위치에 대응하는 비트의 에러를 정정하는 에러 정정부를 포함한다.An error correction code decoder includes a zero-padding bit removal unit that removes zero-padding bits from an input codeword to generate a filtered codeword, a syndrome operation unit that outputs syndromes for the filtered codeword, an error location polynomial operation unit that outputs coefficients of an error location polynomial using the syndromes, an error location operation unit that calculates and outputs an error location using the coefficients, and an error correction unit that corrects an error of a bit corresponding to the error location.

Description

Error correction code decoder, memory controller including the ECC decoder, and ECC decoding method

본 개시의 여러 실시예들은, 에러 정정 코드 디코더, 이를 포함하는 메모리 컨트롤러, 및 에러 정정 코드 디코딩 방법에 관한 것이다.Several embodiments of the present disclosure relate to an error correction code decoder, a memory controller including the same, and an error correction code decoding method.

불휘발성(non-volatile) 메모리는 전원이 공급되지 않아도 저장된 데이터가 유지되는 메모리로서, 이를 기반으로 하는 데이터 저장장치는 스마트폰, 디지털 카메라 등 포터블 기기 및 컴퓨터 등에 널리 사용되고 있다. 불휘발성 메모리, 특히 낸드(NAND) 메모리의 집적도는, 미세 공정을 사용하여 셀의 크기와 회로 선폭을 줄이는 기술 및 셀 당 저장할 수 있는 비트 수를 늘려주는 멀티-레벨 셀(multi-level cell; 이하 MLC) 기술에 의해 향상되었다. 최근에는 기존의 2차원 형태인 플래너(planar) 구조가 갖는 미세 공정화의 한계를 극복하고 메모리의 집적도를 지속적으로 높이기 위한 새로운 기술로 셀을 3차원 배열 형태로 구성하는 수직형(vertical) 구조가 개발되었다.Nonvolatile memory is a memory that maintains stored data even when power is not supplied, and data storage devices based on it are widely used in portable devices such as smartphones, digital cameras, and computers. The integration of nonvolatile memory, especially NAND memory, has been improved by technology that reduces the size of cells and circuit line widths using fine processes and multi-level cell (MLC) technology that increases the number of bits that can be stored per cell. Recently, a vertical structure that configures cells in a three-dimensional array form has been developed as a new technology to overcome the limitations of fine processes of the existing two-dimensional planar structure and to continuously increase the integration of memory.

메모리의 집적도를 높이기 위한 미세 공정화 및 MLC화는 메모리 자체의 신뢰성을 하락시키는 원인이 되고 있다. 공정 미세화로 인한 회로 선폭 감소에 의한 셀 간 간섭(cell-to-cell interference)에 취약해지고, MLC화로 각 레벨 간의 간격이 줄어들어 인접 레벨 간 겹치는 영역이 증가하기 때문이다. 이와 같이 메모리 자체의 오류가 증가하는 상황에서, 데이터 저장 장치의 신뢰성을 높은 수준으로 보장하기 위해서는 에러 정정 코드(Error Correction Code; 이하 ECC) 기술을 사용할 필요가 있다.The miniaturization and MLC for increasing the memory integration are causing the reliability of the memory itself to decrease. This is because the circuit line width is reduced due to the miniaturization of the process, making it vulnerable to cell-to-cell interference, and the gap between each level is reduced due to the MLC, increasing the overlapping area between adjacent levels. In this situation where errors in the memory itself are increasing, it is necessary to use Error Correction Code (ECC) technology to ensure a high level of reliability of the data storage device.

한편 상변화 램(PCRAM; Phase Change RAM), 자기메모리(MRAM; Magnetoresistive RAM), 나노 플로팅 게이트 메모리(NFGM; Nano Floating Gate Memory), 저항성 램(RRAM; Resistive RAM), 또는 폴리머 램(Polymer RAM)과 같이 최근 활발하게 연구가 이루어지고 있는 불휘발성 메모리의 경우, 셀 특성으로 인하여 데이터 "0"과 데이터 "1"을 구분하는 리드 마진(read margin)이 상대적으로 작다. 따라서 이와 같은 불휘발성 메모리의 경우, 싱글 레벨 셀(single-level cell)의 구조를 갖더라도 낸드 메모리에 비하여 상대적으로 높은 에러율(error rate)을 나타내며, 그 결과 이 경우 ECC 기술의 적용에 대한 요구가 더욱 더 크다. ECC 기술을 적용하는데 있어서, 상대적으로 에러율이 낮은 경우에는 단순한 해밍 코드(Hamming Code)를 이용하여 에러 탐색 및 정정을 수행할 수 있다. 반면 상대적으로 많은 에러율을 나타내는 경우에는, BCH(Bose-Chaudhuri-Hochquenghem) 코드 또는 RS(Reed-Solomon) 코드를 사용한다. 이진 BCH 코드는 심볼 단위를 사용하는 RS 코드에 비하여, 코드율이 높은 코드를 설계할 수 있고, 보다 간단한 회로를 구현할 수 있다는 장점을 갖는다.On the other hand, in the case of nonvolatile memories that have been actively studied recently, such as Phase Change RAM (PCRAM), Magnetoresistive RAM (MRAM), Nano Floating Gate Memory (NFGM), Resistive RAM (RRAM), or Polymer RAM, the read margin that distinguishes data "0" and data "1" is relatively small due to the cell characteristics. Therefore, in the case of such nonvolatile memories, even if they have a single-level cell structure, they exhibit a relatively high error rate compared to NAND memory, and as a result, the demand for the application of ECC technology is even greater in this case. In applying ECC technology, when the error rate is relatively low, error detection and correction can be performed using a simple Hamming code. On the other hand, when the error rate is relatively high, the Bose-Chaudhuri-Hochquenghem (BCH) code or the Reed-Solomon (RS) code is used. The binary BCH code has the advantage of being able to design codes with a high code rate and implement simpler circuits compared to RS codes that use symbol units.

본 출원이 해결하고자 하는 과제는, ECC 디코딩을 수행하는데 있어서 소요되는 클럭수를 줄이거나, 로직이 차지하는 면적을 줄일 수 있도록 하는 ECC 디코더를 제공하는 것이다.The problem that this application seeks to solve is to provide an ECC decoder that can reduce the number of clocks required to perform ECC decoding or reduce the area occupied by logic.

본 출원이 해결하고자 하는 다른 과제는, 위와 같은 ECC 디코더를 갖는 메모리 컨트롤러를 제공하는 것이다.Another problem that the present application seeks to solve is to provide a memory controller having an ECC decoder as described above.

본 출원이 해결하고자 하는 또 다른 과제는, ECC 디코딩을 수행하는데 있어서 소요되는 클럭수를 줄이거나, 로직이 차지하는 면적을 줄일 수 있도록 하는 ECC 디코딩 방법을 제공하는 것이다.Another problem that the present application seeks to solve is to provide an ECC decoding method that can reduce the number of clocks required to perform ECC decoding or reduce the area occupied by logic.

본 개시의 일 예에 따른 ECC 디코더는, 입력되는 코드워드에서 제로-패딩 비트들을 제거하여 필터링된 코드워드를 발생시키는 제로-패딩 비트 제거부와, 필터링된 코드워드에 대한 신드롬들을 출력하는 신드롬 연산부와, 신드롬들을 이용하여 에러 위치 다항식의 계수들을 출력하는 에러 위치 다항식 연산부와, 계수들을 이용하여 에러 위치를 연산하여 출력하는 에러 위치 연산부, 및 에러 위치에 대응하는 비트의 에러를 정정하는 에러 정정부를 포함한다.An ECC decoder according to an example of the present disclosure includes a zero-padding bit removal unit that removes zero-padding bits from an input codeword to generate a filtered codeword, a syndrome operation unit that outputs syndromes for the filtered codeword, an error location polynomial operation unit that outputs coefficients of an error location polynomial using the syndromes, an error location operation unit that calculates and outputs an error location using the coefficients, and an error correction unit that corrects an error of a bit corresponding to the error location.

본 개시의 일 예에 따른 메모리 컨트롤러는, 호스트와 메모리 장치 사이에서 호스트의 명령에 의해 상기 메모리 장치를 제어하는 메모리 컨트롤러로서, 메모리 장치에 쓰여질 데이터에 대한 에러 정정 인코딩을 수행하여 패리티 비트가 추가된 코드 워드를 생성하는 ECC 인코더와, 그리고 메모리 장치에서 읽은 데이터에 대한 에러 정정 디코딩을 수행하는 ECC 디코더를 포함한다. ECC 디코더는, 입력되는 코드워드에서 제로-패딩 비트들을 제거하여 필터링된 코드워드를 발생시키는 제로-패딩 비트 제거부와, 필터링된 코드워드에 대한 신드롬들을 출력하는 신드롬 연산부와, 신드롬들을 이용하여 에러 위치 다항식의 계수들을 출력하는 에러 위치 다항식 연산부와, 계수들을 이용하여 에러 위치를 연산하여 출력하는 에러 위치 연산부, 및 에러 위치에 대응하는 비트의 에러를 정정하는 에러 정정부를 포함한다.A memory controller according to an example of the present disclosure controls the memory device by a command of the host between the host and the memory device, the memory controller including an ECC encoder which performs error correction encoding on data to be written to the memory device to generate a codeword with added parity bits, and an ECC decoder which performs error correction decoding on data read from the memory device. The ECC decoder includes a zero-padding bit removal unit which removes zero-padding bits from an input codeword to generate a filtered codeword, a syndrome operation unit which outputs syndromes for the filtered codeword, an error location polynomial operation unit which outputs coefficients of an error location polynomial using the syndromes, an error location operation unit which operates and outputs an error location using the coefficients, and an error correction unit which corrects an error of a bit corresponding to the error location.

본 개시의 일 예에 따른 ECC 디코딩 방법은, 입력되는 코드워드에서 제로-패딩 비트들을 제거하여 필터링된 코드워드를 발생시키는 단계와, 필터링된 코드워드에 대한 신드롬들을 출력하는 단계와, 신드롬들을 이용하여 에러 위치 다항식의 계수들을 출력하는 단계와, 계수들을 이용하여 에러 위치를 연산하여 출력하는 단계와, 그리고 에러 위치에 대응하는 비트의 에러를 정정하는 단계를 포함한다.An ECC decoding method according to an example of the present disclosure includes a step of generating a filtered codeword by removing zero-padding bits from an input codeword, a step of outputting syndromes for the filtered codeword, a step of outputting coefficients of an error location polynomial using the syndromes, a step of calculating and outputting an error location using the coefficients, and a step of correcting an error of a bit corresponding to the error location.

여러 실시예들에 따르면, ECC 디코딩을 수행하는데 있어서 소요되는 클럭수를 줄이거나, 로직이 차지하는 면적을 줄일 수 있는 이점이 제공된다.According to various embodiments, the advantage of reducing the number of clocks required to perform ECC decoding or reducing the area occupied by the logic is provided.

도 1은 본 개시의 일 예에 따른 메모리 컨트롤러를 나타내 보인 블록도이다.
도 2는 도 1의 에러 정정 코드(ECC) 인코더의 입력 데이터 및 출력 데이터를 나타내 보인 도면이다.
도 3은 도 1의 에러 정정 코드(ECC) 디코더의 입력 데이터 및 출력 데이터를 나타내 보인 도면이다.
도 4는 도 1의 에러 정정 코드(ECC) 디코더를 나타내 보인 블록도이다.
도 5는 도 1의 에러 정정 코드(ECC) 인코더에 입력되는 오리지널 데이터가 16비트인 경우 에러 정정 코드(ECC) 인코더로부터 출력되는 코드워드를 설명하기 위해 나타내 보인 도면이다.
도 6은 도 1의 에러 정정 코드(ECC) 인코더에 입력되는 오리지널 데이터가 16비트인 경우 도 4의 에러 정정 코드(ECC) 디코더의 리던던시 체커 및 리던던시 필터의 동작을 설명하기 위해 나타내 보인 도면이다.
도 7은 도 1의 에러 정정 코드(ECC) 인코더에 입력되는 오리지널 데이터가 7비트인 경우 에러 정정 코드(ECC) 인코더로부터 출력되는 코드워드를 설명하기 위해 나타내 보인 도면이다.
도 8은 도 1의 에러 정정 코드(ECC) 인코더에 입력되는 오리지널 데이터가 7비트인 경우 도 4의 에러 정정 코드(ECC) 디코더의 리던던시 체커 및 리던던시 필터의 동작을 설명하기 위해 나타내 보인 도면이다.
도 9는 도 1의 에러 정정 코드(ECC) 인코더에 입력되는 오리지널 데이터가 128비트인 경우 에러 정정 코드(ECC) 인코더로부터 출력되는 코드워드를 설명하기 위해 나타내 보인 도면이다.
도 10은 도 1의 에러 정정 코드(ECC) 인코더에 입력되는 오리지널 데이터가 128비트인 경우 도 4의 에러 정정 코드(ECC) 디코더의 리던던시 체커 및 리던던시 필터의 동작을 설명하기 위해 나타내 보인 도면이다.
도 11은 도 4의 에러 정정 코드(ECC) 디코더의 신드롬 연산부의 일 예를 나타내 보인 회로도이다.
도 12는 도 4의 에러 정정 코드(ECC) 디코더의 신드롬 연산부의 다른 예를 나타내 보인 회로도이다.
도 13은 도 4의 에러 정정 코드(ECC) 디코더의 신드롬 연산부의 또 다른 예를 나타내 보인 회로도이다.
도 14는 도 4의 에러 정정 코드(ECC) 디코더의 에러 정정부의 일 예를 나타내 보인 회로도이다.
도 15는 도 4의 에러 정정 코드(ECC) 디코더의 에러 정정부의 다른 예를 나타내 보인 회로도이다.FIG. 1 is a block diagram illustrating a memory controller according to an example of the present disclosure.
FIG. 2 is a diagram showing input data and output data of the error correction code (ECC) encoder of FIG. 1.
FIG. 3 is a diagram showing input data and output data of the error correction code (ECC) decoder of FIG. 1.
FIG. 4 is a block diagram showing the error correction code (ECC) decoder of FIG. 1.
FIG. 5 is a diagram illustrating a codeword output from an error correction code (ECC) encoder when the original data input to the error correction code (ECC) encoder of FIG. 1 is 16 bits.
FIG. 6 is a diagram illustrating the operation of the redundancy checker and redundancy filter of the error correction code (ECC) decoder of FIG. 4 when the original data input to the error correction code (ECC) encoder of FIG. 1 is 16 bits.
FIG. 7 is a diagram illustrating a codeword output from an error correction code (ECC) encoder when original data input to the error correction code (ECC) encoder of FIG. 1 is 7 bits.
FIG. 8 is a diagram illustrating the operation of the redundancy checker and redundancy filter of the error correction code (ECC) decoder of FIG. 4 when the original data input to the error correction code (ECC) encoder of FIG. 1 is 7 bits.
FIG. 9 is a diagram illustrating a codeword output from an error correction code (ECC) encoder when original data input to the error correction code (ECC) encoder of FIG. 1 is 128 bits.
FIG. 10 is a diagram illustrating the operation of the redundancy checker and redundancy filter of the error correction code (ECC) decoder of FIG. 4 when the original data input to the error correction code (ECC) encoder of FIG. 1 is 128 bits.
Fig. 11 is a circuit diagram showing an example of a syndrome operation unit of the error correction code (ECC) decoder of Fig. 4.
Fig. 12 is a circuit diagram showing another example of the syndrome operation unit of the error correction code (ECC) decoder of Fig. 4.
FIG. 13 is a circuit diagram showing another example of the syndrome operation unit of the error correction code (ECC) decoder of FIG. 4.
Fig. 14 is a circuit diagram showing an example of an error correction unit of the error correction code (ECC) decoder of Fig. 4.
Fig. 15 is a circuit diagram showing another example of an error correction unit of the error correction code (ECC) decoder of Fig. 4.

본 출원의 예의 기재에서 "제1" 및 "제2"와 같은 기재는 부재를 구분하기 위한 것이며, 부재 자체를 한정하거나 특정한 순서를 의미하는 것으로 사용된 것은 아니다. 또한, 어느 부재의 "상"에 위치하거나 "상부", "하부", 또는 "측면"에 위치한다는 기재는 상대적인 위치 관계를 의미하는 것이지 그 부재에 직접 접촉하거나 또는 사이 계면에 다른 부재가 더 도입되는 특정한 경우를 한정하는 것은 아니다. 또한, 어느 한 구성 요소가 다른 구성 요소에 "연결되어 있다"거나 "접속되어 있다"의 기재는, 다른 구성 요소에 전기적 또는 기계적으로 직접 연결되어 있거나 또는 접속되어 있을 수 있으며, 또는, 중간에 다른 별도의 구성 요소들이 개재되어 연결 관계 또는 접속 관계를 구성할 수도 있다.In the description of the examples of the present application, descriptions such as "first" and "second" are used to distinguish members, and are not used to limit the members themselves or to mean a specific order. In addition, descriptions such as being located "on" a certain member or located "upper", "lower", or "side" a certain member mean a relative positional relationship, and do not limit a specific case in which another member is directly contacted with the member or further introduced at the interface therebetween. In addition, descriptions that a certain component is "connected" or "connected" to another component may mean that the other component may be directly electrically or mechanically connected or connected, or other separate components may be interposed in the middle to form a connection or connection relationship.

도 1은 본 개시의 일 예에 따른 메모리 컨트롤러를 나타내 보인 블록도이다. 도 1을 참조하면, 메모리 컨트롤러(Memory Controller)(100)는 호스트(Host)와의 인터페이스를 수행하고, 또한 메모리 장치(Memory Device)의 제어 및 억세스(access)를 제공한다. 일반적으로 "호스트"는 메모리 컨트롤러(100)에 데이터를 보내고 받는 시스템의 업스트림 파트(upstream part)를 의미할 수 있다. 메모리 장치는, 낸드 플래시 메모리와 같은 일반적인 메모리이거나, 또는 상변화 램(PCRAM), 자기메모리(MRAM), 나노 플로팅 게이트 메모리(NFGM), 저항성 램(RRAM), 또는 폴리머 램(Polymer RAM)과 같은 뉴 메모리(new memory)일 수 있다. 메모리 컨트롤러(100)는 에러 정정 코드(ECC; Error Correction Code) 인코더(110) 및 에러 정정 코드 디코더(120)를 포함할 수 있다. ECC 인코더(110)는 메모리 장치에 쓰여질 데이터에 대한 에러 정정 인코딩을 수행하여 패리티(parity) 비트가 추가된 코드워드(codeword)를 생성할 수 있다. ECC 디코더(120)는 메모리 장치에서 읽은 데이터에 대한 에러 정정 디코딩을 수행한다.FIG. 1 is a block diagram showing a memory controller according to an example of the present disclosure. Referring to FIG. 1, a memory controller (100) performs an interface with a host, and also provides control and access to a memory device. In general, a "host" may mean an upstream part of a system that sends and receives data to and from the memory controller (100). The memory device may be a general memory such as a NAND flash memory, or a new memory such as a phase change RAM (PCRAM), a magnetic memory (MRAM), a nano floating gate memory (NFGM), a resistive RAM (RRAM), or a polymer RAM. The memory controller (100) may include an error correction code (ECC) encoder (110) and an error correction code decoder (120). An ECC encoder (110) can perform error correction encoding on data to be written to a memory device to generate a codeword with an added parity bit. An ECC decoder (120) performs error correction decoding on data read from a memory device.

도 2는 도 1의 ECC 인코더(110)의 입력 데이터 및 출력 데이터를 나타내 보인 도면이다. 도 2를 참조하면, ECC 인코더(110)에는 k비트의 오리지널 데이터(210)가 입력된다. 일 예에서 k비트의 오리지널 데이터(210)는 한 비트 단위로 직렬 입력된다. 다른 예에서, k비트의 오리지널 데이터(210)는, 호스트와의 인터페이스 및 ECC 인코더(110) 내부의 로직 구성에 따라 병렬로 입력되도록 할 수도 있다. ECC 인코더(110)는, k비트의 오리지널 데이터(210)에 대한 BCH 인코딩을 수행하여 n비트의 코드워드(220)를 출력시킨다. n비트의 코드워드(220)는, k비트의 오리지널 데이터와 (n-k)비트의 패리티 비트들을 포함한다. n비트의 코드워드(220) 또한, 메모리 장치와의 인터페이스 및 ECC 인코더(110) 내부의 로직 구성에 따라 직렬로 출력되거나, 또는 병렬로 출력되도록 할 수 있다.FIG. 2 is a diagram showing input data and output data of the ECC encoder (110) of FIG. 1. Referring to FIG. 2, k-bit original data (210) is input to the ECC encoder (110). In one example, the k-bit original data (210) is input serially in units of one bit. In another example, the k-bit original data (210) may be input in parallel depending on the interface with the host and the logic configuration within the ECC encoder (110). The ECC encoder (110) performs BCH encoding on the k-bit original data (210) and outputs an n-bit codeword (220). The n-bit codeword (220) includes k-bit original data and (n-k)-bit parity bits. The n-bit codeword (220) can also be output serially or in parallel depending on the interface with the memory device and the logic configuration within the ECC encoder (110).

도 3은 도 1의 ECC 디코더(120)의 입력 데이터 및 출력 데이터를 나타내 보인 도면이다. 도 3을 참조하면, ECC 디코더(120)에는 메모리 장치로부터 읽은 n비트의 코드워드(220)가 입력된다. 일 예에서 n비트의 코드워드(220)는 한 비트 단위로 직렬 입력되지만, 메모리 장치와의 인터페이스 및 ECC 디코더(120) 내부의 로직 구성에 따라 병렬로 입력되도록 할 수도 있다. ECC 디코더(120)는, n비트의 코드워드(220)에 대한 BCH 디코딩을 수행하여 에러가 정정된 n비트의 코드워드(240)를 출력시킨다. 에러가 정정된 n비트의 코드워드(240)는, 에러가 정정되기 이전의 n비트의 코드워드(220)와 같이, k비트의 오리지널 데이터와 (n-k)비트의 패리티 비트들을 포함한다. 에러가 정정된 후에는 n비트의 코드워드(240)에서 패리티 비트들이 제거된 k비트의 오리지널 데이터가 호스트로 전달된다.FIG. 3 is a diagram showing input data and output data of the ECC decoder (120) of FIG. 1. Referring to FIG. 3, an n-bit codeword (220) read from a memory device is input to the ECC decoder (120). In one example, the n-bit codeword (220) is input serially in units of one bit, but may be input in parallel depending on the interface with the memory device and the logic configuration within the ECC decoder (120). The ECC decoder (120) performs BCH decoding on the n-bit codeword (220) and outputs an n-bit codeword (240) with an error corrected. The n-bit codeword (240) with an error corrected includes k-bits of original data and (n-k)-bits of parity bits, like the n-bit codeword (220) before the error is corrected. After the error is corrected, the k-bit original data with the parity bits removed from the n-bit codeword (240) is transmitted to the host.

도 4는 도 1의 ECC 디코더(120)를 나타내 보인 블록도이다. 도 4를 참조하면, ECC 디코더(120)는 제로-패딩 비트(zero-padding bit) 제거부(300)와, 신드롬 연산부(410)와, 에러 위치 다항식 연산부(420)와, 에러 위치 연산부(430)와, 그리고 에러 정정부(440)를 포함하여 구성된다. 제로-패딩 비트 제거부(300)는, 리던던시 체커(Redundancy Checker)(310)와, 리던던시 필터(Redundancy Filter)(320)로 구성될 수 있다. 리던던시 체커(310)는, ECC 디코더(120)에 입력되는 n비트의 코드워드의 오리지널 데이터 비트수(k)와, 에러 정정에 필요한 패리티 비트수(n-k)를 입력받아 제로-패딩 비트수(Z)를 출력시킨다. 리던던시 필터(320)는, 메모리 장치로부터 읽은 n비트 코드워드와, 리던던시 체커(310)로부터의 제로-패딩 비트수(Z)를 입력받아, n비트의 코드워드에서 제로-패딩 비트들을 제거한 (n-Z)비트의 필터링된 코드워드((n-Z)-bit filterd codeword))를 출력시킨다. (n-Z)비트의 필터링된 코드워드는 신드롬 연산부(410)에 입력된다.FIG. 4 is a block diagram showing an ECC decoder (120) of FIG. 1. Referring to FIG. 4, the ECC decoder (120) is configured to include a zero-padding bit removal unit (300), a syndrome operation unit (410), an error location polynomial operation unit (420), an error location operation unit (430), and an error correction unit (440). The zero-padding bit removal unit (300) may be configured to include a redundancy checker (310) and a redundancy filter (320). The redundancy checker (310) receives the original data bit number (k) of the n-bit codeword input to the ECC decoder (120) and the number of parity bits (n-k) required for error correction, and outputs the number of zero-padding bits (Z). The redundancy filter (320) receives the n-bit codeword read from the memory device and the number of zero-padding bits (Z) from the redundancy checker (310), and outputs an (n-Z)-bit filtered codeword ((n-Z)-bit filtered codeword)) in which the zero-padding bits are removed from the n-bit codeword. The (n-Z)-bit filtered codeword is input to the syndrome operation unit (410).

신드롬 연산부(410)는, (n-Z)비트의 필터링된 코드워드를 기반으로 에러 위치 다항식 연산에 필요한 신드롬들을 연산하여 출력한다. 에러 위치 다항식 연산부(420)는, 연산된 신드롬들을 이용하여 BM 알고리즘이 적용된 에러 위치 다항식의 계수(coefficient)들을 연산하여 출력한다. 에러 위치 연산부(430)는, 에러 위치 다항식의 계수들을 이용하여 에러 위치를 연산하여 출력한다. 에러 정정부(440)는, 계산된 에러 위치에 해당하는 비트를 반전시킴으로써 에러가 정정된 (n-Z)비트의 에러 정정된 코드워드를 출력한다.The syndrome operation unit (410) calculates and outputs syndromes required for error location polynomial calculation based on the filtered codeword of (n-Z) bits. The error location polynomial operation unit (420) calculates and outputs coefficients of an error location polynomial to which a BM algorithm is applied using the calculated syndromes. The error location operation unit (430) calculates and outputs an error location using the coefficients of the error location polynomial. The error correction unit (440) outputs an error-corrected codeword of (n-Z) bits in which an error is corrected by inverting a bit corresponding to the calculated error location.

도 5는 도 1의 ECC 인코더(110)에 입력되는 오리지널 데이터가 16비트인 경우 ECC 인코더(110)로부터 출력되는 코드워드를 설명하기 위해 나타내 보인 도면이다. 도 5를 참조하면, k비트의 오리지널 데이터가 ECC 인코더(110)에 입력되면, ECC 인코더(110)는, 도 2를 참조하여 설명한 바와 같이, k비트의 오리지널 데이터에 대한 BCH 인코딩을 수행하여 k비트의 오리지널 데이터에 에러 정정에 필요한 (n-k)비트의 패리티 비트들이 추가된 n비트의 코드워드를 출력시킨다. 이때 코드워드의 길이, 즉 코드워드의 비트수(n)와, 에러 정정에 필요한 패리티 비트수(n-k)는 아래의 수학식 1 및 수학식 2와 같이 정의할 수 있다.FIG. 5 is a diagram illustrating a codeword output from an ECC encoder (110) when original data input to the ECC encoder (110) of FIG. 1 is 16 bits. Referring to FIG. 5, when k-bit original data is input to the ECC encoder (110), the ECC encoder (110) performs BCH encoding on the k-bit original data as described with reference to FIG. 2 to output an n-bit codeword in which (n-k) bits of parity bits necessary for error correction are added to the k-bit original data. At this time, the length of the codeword, i.e., the number of bits (n) of the codeword, and the number of parity bits (n-k) necessary for error correction can be defined as in the following Mathematical Expressions 1 and 2.

수학식 1 및 수학식 2에서 m은 3 이상의 정수이며, t는 에러를 정정할 수 있는 최대 비트수(이하 최대 에러 정정 능력)를 나타낸다.In mathematical expressions 1 and 2, m is an integer greater than or equal to 3, and t represents the maximum number of bits capable of correcting an error (hereinafter referred to as maximum error correction capability).

본 예에서 오리지널 데이터(210-1)의 비트수(k)가 16이고, 코드워드(220-1)의 비트수(n)는 오리지널 데이터(210-1)의 비트수(k)인 16보다는 커야 하므로, 식 수학식 1에 의해 m의 최소값은 5가 되고, 이 경우 코드워드(220-1)의 비트수(n)는 31이 된다. 즉 16비트의 오리지널 데이터(210-1)가 ECC 인코더(110)에 입력되면, 31비트의 코드워드(220-1)가 ECC 인코더(110)로부터 출력된다.In this example, since the number of bits (k) of the original data (210-1) is 16 and the number of bits (n) of the codeword (220-1) must be greater than the number of bits (k) of the original data (210-1), which is 16, the minimum value of m is 5 according to mathematical expression 1, and in this case, the number of bits (n) of the codeword (220-1) is 31. That is, when 16-bit original data (210-1) is input to the ECC encoder (110), a 31-bit codeword (220-1) is output from the ECC encoder (110).

31비트의 코드워드(220-1)를 구성하는 데이터 중에서 에러 정정에 필요한 패리티 비트의 수(n-k)는, 위 식 수학식 2에 의해 결정된다. 일 예로, 최대 에러 정정 능력(t)이 2인 경우, 에러 정정에 필요한 패리티 비트의 수(n-k)의 최소값은 10이 된다. 따라서 31비트의 코드워드(220-1) 중 16비트의 오리지널 데이터와 10비트의 패리티 비트들을 제외한 나머지 5비트들은 제로-패딩(zero-padding) 비트들, 즉 에러 정정을 수행하는데 요구되지 않는 비트들을 구성한다. 일 예에서 5비트의 제로-패딩 비트들은, 모두 "0"의 값을 갖는다. 즉 오리지널 데이터(210-1)의 비트수(k)가 16이고, 최대 에러 정정 능력(t)이 2인 경우, 31비트의 코드워드(220-1)가 ECC 인코더(110)로부터 출력되는데, 이 31비트의 코드워드(220-1)는, 5비트의 제로-패딩 비트들과, 16비트의 오리지널 데이터와, 그리고 10비트의 패리티 비트들로 구성된다.The number of parity bits (n-k) required for error correction among the data constituting the 31-bit codeword (220-1) is determined by the mathematical expression 2 above. For example, when the maximum error correction capability (t) is 2, the minimum value of the number of parity bits (n-k) required for error correction is 10. Therefore, among the 31-bit codeword (220-1), the remaining 5 bits, excluding the 16-bit original data and the 10-bit parity bits, constitute zero-padding bits, i.e., bits not required to perform error correction. In one example, all 5 zero-padding bits have the value "0". That is, when the number of bits (k) of the original data (210-1) is 16 and the maximum error correction capability (t) is 2, a 31-bit codeword (220-1) is output from the ECC encoder (110). This 31-bit codeword (220-1) is composed of 5-bit zero-padding bits, 16-bit original data, and 10-bit parity bits.

도 6은 도 1의 ECC 인코더(110)에 입력되는 오리지널 데이터가 16비트인 경우 도 4의 ECC 디코더(120)의 리던던시 체커(310) 및 리던던시 필터(320)의 동작을 설명하기 위해 나타내 보인 도면이다. 도 6을 참조하면, 코드워드(220-1)를 구성하는 오리지널 데이터의 비트수(k)인 16과, 코드워드(220-1)를 구성하는 패리티 비트의 비트수(n-k)인 10이 리던던시 체커(310)에 입력된다. 리던던시 체커(310)는, 이 입력값들에 대해 위 수학식 1 및 수학식 2를 이용한 연산을 수행하여 제로-패딩 비트수(Z)가 5가 된다는 정보 데이터(Z=5)를 연산하여 출력시킨다. 이 정보 데이터(Z=5)는 리던던시 필터(320)에 입력된다. 리던던시 필터(320)는 리던던시 체커(310)로부터의 정보 데이터(Z=5)에 응답하여 리던던시 필터(320)로 입력되는 31비트의 코드워드(220-1) 중에서 5비트의 제로-패딩 비트들이 제거된 26비트의 필터링된 코드워드(230-1)를 출력시킨다. 26비트의 필터링된 코드워드(230-1)는, 16비트의 오리지널 데이터와 10비트의 패리티 비트들만으로 구성된다. 이에 따라 신드롬 연산부(410), 에러 위치 다항식 연산부(420), 에러 위치 연산부(430), 및 에러 정정부(440)에 의한 ECC 디코딩은, 31비트의 코드워드(220-1)에 대해 이루어지는 대신 26비트의 필터링된 코드워드(230-1)에 대해 이루어진다.FIG. 6 is a diagram illustrating the operation of the redundancy checker (310) and the redundancy filter (320) of the ECC decoder (120) of FIG. 4 when the original data input to the ECC encoder (110) of FIG. 1 is 16 bits. Referring to FIG. 6, 16, which is the number of bits (k) of the original data constituting the codeword (220-1), and 10, which is the number of bits (n-k) of the parity bits constituting the codeword (220-1), are input to the redundancy checker (310). The redundancy checker (310) performs an operation using the above mathematical expressions 1 and 2 on these input values to calculate and output information data (Z=5) indicating that the number of zero-padding bits (Z) is 5. This information data (Z=5) is input to the redundancy filter (320). The redundancy filter (320) outputs a 26-bit filtered codeword (230-1) in which 5-bit zero-padding bits are removed from a 31-bit codeword (220-1) input to the redundancy filter (320) in response to information data (Z=5) from the redundancy checker (310). The 26-bit filtered codeword (230-1) is composed of only 16-bit original data and 10-bit parity bits. Accordingly, ECC decoding by the syndrome operation unit (410), the error location polynomial operation unit (420), the error location operation unit (430), and the error correction unit (440) is performed on the 26-bit filtered codeword (230-1) instead of the 31-bit codeword (220-1).

도 7은 도 1의 ECC 인코더(110)에 입력되는 오리지널 데이터가 7비트인 경우 ECC 인코더(110)로부터 출력되는 코드워드를 설명하기 위해 나타내 보인 도면이다. 도 7을 참조하면, 본 예에서 오리지널 데이터(210-2)의 비트수(k)가 7이고, 코드워드(220-2)의 비트수(n)는 오리지널 데이터(210-2)의 비트수(k)인 7보다는 커야 하므로, 식 수학식 1에 의해 m의 최소값은 4가 되고, 이 경우 코드워드(220-2)의 비트수(n)는 15가 된다. 즉 7비트의 오리지널 데이터(210-2)가 ECC 인코더(110)에 입력되면, 15비트의 코드워드(220-2)가 ECC 인코더(110)로부터 출력된다. 15비트의 코드워드(220-2)를 구성하는 데이터 중에서 에러 정정에 필요한 패리티 비트의 수(n-k)는, 위 수학식 2에 의해 결정된다. 일 예로, 최대 에러 정정 능력(t)이 2인 경우, 에러 정정에 필요한 패리티 비트의 수(n-k)의 최소값은 8이 된다. 따라서 15비트의 코드워드(220-2)는 7비트의 오리지널 데이터와 8비트의 패리티 비트들로 구성되며, 제로-패딩 비트들은 존재하지 않는다.FIG. 7 is a diagram illustrating a codeword output from an ECC encoder (110) when original data input to the ECC encoder (110) of FIG. 1 is 7 bits. Referring to FIG. 7, in this example, the number of bits (k) of the original data (210-2) is 7, and the number of bits (n) of the codeword (220-2) must be greater than 7, which is the number of bits (k) of the original data (210-2), so the minimum value of m is 4 by Equation 1, and in this case, the number of bits (n) of the codeword (220-2) is 15. That is, when 7-bit original data (210-2) is input to the ECC encoder (110), a 15-bit codeword (220-2) is output from the ECC encoder (110). The number of parity bits (n-k) required for error correction among the data constituting the 15-bit codeword (220-2) is determined by the mathematical expression 2 above. For example, when the maximum error correction capability (t) is 2, the minimum value of the number of parity bits (n-k) required for error correction is 8. Therefore, the 15-bit codeword (220-2) is composed of 7 bits of original data and 8 bits of parity bits, and there are no zero-padding bits.

도 8은 도 1의 ECC 인코더(110)에 입력되는 오리지널 데이터가 7비트인 경우 도 4의 ECC 디코더(120)의 리던던시 체커(310) 및 리던던시 필더(320)의 동작을 설명하기 위해 나타내 보인 도면이다. 도 8을 참조하면, 코드워드(220-2)를 구성하는 오리지널 데이터의 비트수(k)인 7과, 코드워드(220-2)를 구성하는 패리티 비트의 비트수(n-k)인 8이 리던던시 체커(310)에 입력된다. 리던던시 체커(310)는, 이 입력값들에 대해 위 식 수학식 1 및 수학식 2를 이용한 연산을 수행하여 제로-패딩 비트수(Z)가 0이라는 정보 데이터(Z=0)를 연산하여 출력시킨다. 이 정보 데이터(Z=0)는 리던던시 필터(320)에 입력된다. 리던던시 필터(320)는 리던던시 체커(310)로부터의 정보 데이터(Z=0)에 응답하여 리던던시 필터(320)로 입력되는 15비트의 코드워드(220-1) 중에서 제로-패딩 비트들이 제거된 필터링된 코드워드(230-2)를 출력시킨다. 본 예의 경우 제로-패딩 비트들(Z)이 존재하지 않으므로, 리던던시 필터(320)는 입력되는 15비트의 코드워드(220-2)를 그대로 통과시켜 필터링된 코드워드(230-2)로 출력시킨다. 이에 따라 리던던시 필터(320)로부터 출력되는 15비트의 필터링된 코드워드(230-2)는, 7비트의 오리지널 데이터와 8비트의 패리티 비트들만으로 구성된다.FIG. 8 is a diagram illustrating the operation of the redundancy checker (310) and the redundancy filter (320) of the ECC decoder (120) of FIG. 4 when the original data input to the ECC encoder (110) of FIG. 1 is 7 bits. Referring to FIG. 8, 7, which is the number of bits (k) of the original data constituting the codeword (220-2), and 8, which is the number of bits (n-k) of the parity bits constituting the codeword (220-2), are input to the redundancy checker (310). The redundancy checker (310) performs an operation using the above mathematical expressions 1 and 2 on these input values to calculate and output information data (Z=0) that the number of zero-padding bits (Z) is 0. This information data (Z=0) is input to the redundancy filter (320). The redundancy filter (320) outputs a filtered codeword (230-2) from which zero-padding bits are removed from a 15-bit codeword (220-1) input to the redundancy filter (320) in response to information data (Z=0) from the redundancy checker (310). In the present example, since zero-padding bits (Z) do not exist, the redundancy filter (320) passes the input 15-bit codeword (220-2) as is and outputs the filtered codeword (230-2). Accordingly, the 15-bit filtered codeword (230-2) output from the redundancy filter (320) is composed of only 7 bits of original data and 8 bits of parity bits.

도 9는 도 1의 ECC 인코더(110)에 입력되는 오리지널 데이터가 128비트인 경우 ECC 인코더(110)로부터 출력되는 코드워드를 설명하기 위해 나타내 보인 도면이다. 도 9를 참조하면, 오리지널 데이터(210-3)의 비트수(k)가 128이고, 코드워드(220-3)의 비트수(n)는 오리지널 데이터(210-3)의 비트수(k)인 128보다는 커야 하므로, 식 수학식 1에 의해 m의 최소값은 8이 되고, 이 경우 코드워드(220-1)의 비트수(n)는 255이 된다. 즉 128비트의 오리지널 데이터(210-3)가 ECC 인코더(110)에 입력되면, 255비트의 코드워드(220-3)가 ECC 인코더(110)로부터 출력된다.FIG. 9 is a diagram illustrating a codeword output from an ECC encoder (110) when original data input to the ECC encoder (110) of FIG. 1 is 128 bits. Referring to FIG. 9, since the number of bits (k) of the original data (210-3) is 128 and the number of bits (n) of the codeword (220-3) must be greater than the number of bits (k) of the original data (210-3), which is 128, the minimum value of m is 8 by Equation 1, and in this case, the number of bits (n) of the codeword (220-1) is 255. That is, when 128-bit original data (210-3) is input to the ECC encoder (110), a 255-bit codeword (220-3) is output from the ECC encoder (110).

255비트의 코드워드(220-3)를 구성하는 데이터 중에서 에러 정정에 필요한 패리티 비트의 수(n-k)는, 위 수학식 2에 의해 결정된다. 일 예로, 최대 에러 정정 능력(t)이 2인 경우, 에러 정정에 필요한 패리티 비트의 수(n-k)의 최소값은 16이 된다. 따라서 255비트의 코드워드(220-3) 중 128비트의 오리지널 데이터와 16비트의 패리티 비트들을 제외한 나머지 111비트들은 제로-패딩 비트들을 구성한다. 111비트의 제로-패딩 비트들은, 모두 "0"의 값을 갖는다. 즉 오리지널 데이터(210-3)의 비트수(k)가 128이고, 최대 에러 정정 능력(t)이 2인 경우, 255비트의 코드워드(220-3)가 ECC 인코더(110)로부터 출력되는데, 이 255비트의 코드워드(220-3)는, 111비트의 제로-패딩 비트들과, 128비트의 오리지널 데이터와, 그리고 16비트의 패리티 비트들로 구성된다.The number of parity bits (n-k) required for error correction among the data constituting the 255-bit codeword (220-3) is determined by the mathematical expression 2 above. For example, when the maximum error correction capability (t) is 2, the minimum value of the number of parity bits (n-k) required for error correction is 16. Therefore, among the 255-bit codeword (220-3), the remaining 111 bits, excluding the 128 bits of original data and the 16 bits of parity bits, constitute zero-padding bits. The 111 zero-padding bits all have the value of "0". That is, when the number of bits (k) of the original data (210-3) is 128 and the maximum error correction capability (t) is 2, a 255-bit codeword (220-3) is output from the ECC encoder (110). This 255-bit codeword (220-3) is composed of 111 bits of zero-padding bits, 128 bits of original data, and 16 bits of parity bits.

도 10은 도 1의 ECC 인코더(110)에 입력되는 오리지널 데이터가 128비트인 경우 도 4의 ECC 디코더(120)의 리던던시 체커(310) 및 리던던시 필더(320)의 동작을 설명하기 위해 나타내 보인 도면이다. 도 10을 참조하면, 코드워드(220-1)를 구성하는 오리지널 데이터의 비트수(k)인 128과, 코드워드(220-1)를 구성하는 패리티 비트의 비트수(n-k)인 16이 리던던시 체커(310)에 입력된다. 리던던시 체커(310)는, 이 입력값들에 대해 위 수학식 1 및 수학식 2를 이용한 연산을 수행하여 제로-패딩 비트수(Z)가 111이 된다는 정보 데이터(Z=111)를 연산하여 출력시킨다. 이 정보 데이터(Z=111)는 리던던시 필터(320)에 입력된다. 리던던시 필터(320)는 리던던시 체커(310)로부터의 정보 데이터(Z=111)에 응답하여 리던던시 필터(320)로 입력되는 255비트의 코드워드(220-3) 중에서 111비트의 제로-패딩 비트들이 제거된 144비트의 필터링된 코드워드(230-3)를 출력시킨다. 144비트의 필터링된 코드워드(230-3)는, 128비트의 오리지널 데이터와 16비트의 패리티 비트들만으로 구성된다. 이에 따라 신드롬 연산부(410), 에러 위치 다항식 연산부(420), 에러 위치 연산부(430), 및 에러 정정부(440)에 의한 ECC 디코딩은, 255비트의 코드워드(220-3)에 대해 이루어지는 대신 144비트의 필터링된 코드워드(230-3)에 대해 이루어진다.FIG. 10 is a diagram illustrating the operation of the redundancy checker (310) and the redundancy fielder (320) of the ECC decoder (120) of FIG. 4 when the original data input to the ECC encoder (110) of FIG. 1 is 128 bits. Referring to FIG. 10, the number of bits (k) of the original data constituting the codeword (220-1), which is 128, and the number of bits (n-k) of the parity bits constituting the codeword (220-1), which is 16, are input to the redundancy checker (310). The redundancy checker (310) performs an operation using the above mathematical expressions 1 and 2 on these input values to calculate and output information data (Z=111) indicating that the number of zero-padding bits (Z) is 111. This information data (Z=111) is input to a redundancy filter (320). In response to the information data (Z=111) from the redundancy checker (310), the redundancy filter (320) outputs a 144-bit filtered codeword (230-3) in which 111 bits of zero-padding bits are removed from a 255-bit codeword (220-3) input to the redundancy filter (320). The 144-bit filtered codeword (230-3) consists of only 128 bits of original data and 16 bits of parity bits. Accordingly, ECC decoding by the syndrome operation unit (410), error location polynomial operation unit (420), error location operation unit (430), and error correction unit (440) is performed on a 144-bit filtered codeword (230-3) instead of a 255-bit codeword (220-3).

도 11은 도 4의 ECC 디코더(120)의 신드롬 연산부(410)의 일 예를 나타내 보인 회로도이다. 도 11을 참조하면, 본 예에 따른 신드롬 연산부(410-1)는, 갈로아 필드 곱셈기(521)와, XOR 연산기(522)와, 그리고 레지스터(Reg)(523)를 포함하여 구성된다. 갈로아 필드 곱셈기(521)는, 리던던시 필터(320)로부터의 필터링된 코드워드(230-3)와, 갈로아 필드의 원시근들(primitive elements)((αⁱ)^r, i=1, ..., n-1, r=1, ..., 2t)을 입력받아 갈로아 필드 곱셈 연산을 수행하여 출력한다. 필터링된 코드워드(230-3)의 첫번째 비트값은 갈로아 필드 곱셈 연산 없이 XOR 연산기(522)에 직접 입력된다. 이 값은 레지스터(523)를 통해 XOR 연산기(522)에 입력되어 다음에 갈로아 필드 곱셈기(521)로부터 출력되는 값과 XOR 연산된다. 다음에 필터링된 코드워드(230-3)의 두번째 비트값이 갈로아 필드 곱셈기(521)로 입력되어 갈로아 필드의 원시근들(αⁱ, i=1, ..., n-1) 각각과 순차적으로 갈로아 필드 곱셈 연산된다. 필터링된 코드워드(230-3)의 첫번째 비트값과 마찬가지로, 갈로아 필드 곱셈 연산되어 출력되는 값은 XOR 연산기(522)에 의해 XOR 연산된 결과값과 XOR 연산된다. 이 과정은 필터링된 코드워드(230-3)의 모든 비트값들에 대해 동일하게 수행된다. 필터링된 코드워드(230-3)의 n번째 비트값에 대한 갈로아 필드 곱셈 연산 및 XOR 연산이 종료된 후에 XOR 연산기(522)로부터 출력되는 값은 첫번째 신드롬(S₀)을 구성한다. 이와 같이 첫번째 신드롬(S₀)이 출력되기까지 모두 n 클럭이 소요된다.FIG. 11 is a circuit diagram showing an example of a syndrome operation unit (410) of an ECC decoder (120) of FIG. 4. Referring to FIG. 11, a syndrome operation unit (410-1) according to the present example is configured to include a Galois field multiplier (521), an XOR operation unit (522), and a register (Reg) (523). The Galois field multiplier (521) receives a filtered codeword (230-3) from a redundancy filter (320) and primitive elements ((α ⁱ ) ^r , i=1, ..., n-1, r=1, ..., 2t) of a Galois field, performs a Galois field multiplication operation, and outputs the result. The first bit value of the filtered codeword (230-3) is directly input to the XOR operation unit (522) without a Galois field multiplication operation. This value is input to the XOR operator (522) through the register (523) and is XOR-operated with the value output from the Galois field multiplier (521). Next, the second bit value of the filtered codeword (230-3) is input to the Galois field multiplier (521) and is sequentially subjected to Galois field multiplication with each of the primitive roots (α ⁱ , i=1, ..., n-1) of the Galois field. Similarly to the first bit value of the filtered codeword (230-3), the value output by the Galois field multiplication is XOR-operated with the result value XOR-operated by the XOR operator (522). This process is performed equally for all bit values of the filtered codeword (230-3). After the Galois field multiplication operation and XOR operation for the nth bit value of the filtered codeword (230-3) are completed, the value output from the XOR operator (522) constitutes the first syndrome (S ₀ ). In this way, it takes a total of n clocks until the first syndrome (S ₀ ) is output.

나머지 신드롬들을 연산하기 위해 위와 같은 과정이 반복적으로 이루어진다. 즉 두번째 신드롬(S₁)을 연산하기 위해, 필터링된 코드워드(230-3)의 첫번째 비트값은 갈로아 필드 곱셈 연산 없이 XOR 연산기(522)에 직접 입력된다. 이 값은 레지스터(523)를 통해 XOR 연산기(522)에 입력되어 다음에 갈로아 필드 곱셈기(521)로부터 출력되는 값과 XOR 연산된다. 다음에 필터링된 코드워드(230-3)의 두번째 비트값이 갈로아 필드 곱셈기(521)로 입력되어 갈로아 필드의 원시근들((αⁱ)², i=1, ..., n-1) 각각과 순차적으로 갈로아 필드 곱셈 연산된다. 필터링된 코드워드(230-3)의 첫번째 비트값과 마찬가지로, 갈로아 필드 곱셈 연산되어 출력되는 값은 XOR 연산기(522)에 의해 XOR 연산된 결과값과 XOR 연산된다. 이 과정은 필터링된 코드워드(230-3)의 모든 비트값들에 대해 동일하게 수행된다. 필터링된 코드워드(230-3)의 n번째 비트값에 대한 갈로아 필드 곱셈 연산 및 XOR 연산이 종료된 후에 XOR 연산기(522)로부터 출력되는 값은 두번째 신드롬(S₁)을 구성한다. 첫번째 신드롬(S₀)과 마찬가지로 두번째 신드롬(S₁)이 출력되기까지 소요되는 클럭은 n 클럭이다.The above process is repeated to compute the remaining syndromes. That is, to compute the second syndrome (S ₁ ), the first bit value of the filtered codeword (230-3) is directly input to the XOR operator (522) without a Galois field multiplication operation. This value is input to the XOR operator (522) through the register (523) and XOR-operated with the value output from the Galois field multiplier (521). Next, the second bit value of the filtered codeword (230-3) is input to the Galois field multiplier (521) and sequentially subjected to a Galois field multiplication operation with each of the primitive roots ((α ⁱ ) ² , i = 1, ..., n-1) of the Galois field. Like the first bit value of the filtered codeword (230-3), the value output by the Galois field multiplication operation is XOR-operated with the result value XOR-operated by the XOR operator (522). This process is performed identically for all bit values of the filtered codeword (230-3). After the Galois field multiplication operation and XOR operation for the nth bit value of the filtered codeword (230-3) are completed, the value output from the XOR operator (522) constitutes the second syndrome (S ₁ ). As with the first syndrome (S ₀ ), the number of clocks required until the second syndrome (S ₁ ) is output is n clocks.

마찬가지로 2t번째 신드롬(S_2t-1)을 연산하기 위해, 필터링된 코드워드(230-3)의 첫번째 비트값은 갈로아 필드 곱셈 연산 없이 XOR 연산기(522)에 직접 입력된다. 이 값은 레지스터(523)를 통해 XOR 연산기(522)에 입력되어 다음에 갈로아 필드 곱셈기(521)로부터 출력되는 값과 XOR 연산된다. 다음에 필터링된 코드워드(230-3)의 두번째 비트값이 갈로아 필드 곱셈기(521)로 입력되어 갈로아 필드의 원시근들((αⁱ)^2t, i=1, ..., n-1) 각각과 순차적으로 갈로아 필드 곱셈 연산된다. 필터링된 코드워드(230-3)의 첫번째 비트값과 마찬가지로, 갈로아 필드 곱셈 연산되어 출력되는 값은 XOR 연산기(522)에 의해 XOR 연산된 결과값과 XOR 연산된다. 이 과정은 필터링된 코드워드(230-3)의 모든 비트값들에 대해 동일하게 수행된다. 필터링된 코드워드(230-3)의 n번째 비트값에 대한 갈로아 필드 곱셈 연산 및 XOR 연산이 종료된 후에 XOR 연산기(522)로부터 출력되는 값은 2t번째 신드롬(S_2t-1)을 구성한다. 2t번째 신드롬(S_2t-1) 연산 또한 n 클럭이 소요된다.Likewise, in order to compute the 2t-th syndrome (S _2t-1 ), the first bit value of the filtered codeword (230-3) is directly input to the XOR operator (522) without a Galois field multiplication operation. This value is input to the XOR operator (522) through the register (523) and XOR-operated with the value output from the Galois field multiplier (521). Next, the second bit value of the filtered codeword (230-3) is input to the Galois field multiplier (521) and sequentially subjected to a Galois field multiplication operation with each of the primitive roots ((α ⁱ ) ^2t , i = 1, ..., n-1) of the Galois field. Similarly to the first bit value of the filtered codeword (230-3), the value output by the Galois field multiplication operation is XOR-operated with the result value XOR-operated by the XOR operator (522). This process is performed identically for all bit values of the filtered codeword (230-3). After the Galois field multiplication operation and XOR operation for the nth bit value of the filtered codeword (230-3) are completed, the value output from the XOR operator (522) constitutes the 2tth syndrome (S _2t-1 ). The 2tth syndrome (S _2t-1 ) operation also takes n clocks.

결과적으로, 2t개의 신드롬들(Sr, r=0, ..., 2t-1)을 연산하기 위한 신드롬 연산과정에는 모두 (2×t×n) 클럭이 소요된다. 도 10을 참조하여 설명한 바와 같이, 2비트의 최대 에러 정정 능력을 갖는 경우, 111비트의 제로-패딩 비트들이 제거되어 128비트의 오리지널 데이터와 16비트의 패리티 비트들만으로 구성되는 144비트의 필터링된 코드워드(230-3)에 대한 신드롬 연산부(410-1)의 신드롬 연산 과정에는 144×4=576 클럭들이 소요된다. 이에 반하여 2비트의 최대 에러 정정 능력 조건 및 111비트의 제로-패딩 비트들이 제거되지 않은 상태, 즉 255비트의 코드워드(220-3)의 경우, 신드롬 연산부(410-1)에 의한 신드롬 연산 과정에는 255×4=1020 클럭들이 소요된다. 따라서 본 예에 따른 신드롬 연산부(410-2)는, 제로-패딩 비트들이 제거되지 않은 경우에 비하여, 신드롬 연산 동작을 수행하는데 있어서 상대적으로 적은 클럭이 소요되며, 그 결과 신드롬 연산 동작의 속도를 향상시킬 수 있다.As a result, the syndrome operation process for calculating 2t syndromes (Sr, r=0, ..., 2t-1) requires (2×t×n) clocks. As described with reference to Fig. 10, in the case of a maximum error correction capability of 2 bits, the syndrome operation process of the syndrome operation unit (410-1) for a 144-bit filtered codeword (230-3) composed of only 128-bit original data and 16-bit parity bits by removing 111 bits of zero-padding bits requires 144×4=576 clocks. In contrast, in the case of a 255-bit codeword (220-3) under the condition of a maximum error correction capability of 2 bits and in which 111-bit zero-padding bits are not removed, 255×4=1020 clocks are required for the syndrome operation process by the syndrome operation unit (410-1). Therefore, the syndrome operation unit (410-2) according to the present example requires relatively fewer clocks to perform the syndrome operation compared to the case in which the zero-padding bits are not removed, and as a result, the speed of the syndrome operation can be improved.

도 12는 도 4의 ECC 디코더(120)의 신드롬 연산부의 다른 예를 나타내 보인 회로도이다. 도 12를 참조하면, 본 예에 따른 신드롬 연산부(410-2)는, 2t(t는 최대 에러 정정 능력)개의 신드롬 연산 블록들(510-1, ..., 510-2t)을 포함한다. 신드롬 연산 블록들(510-1, ..., 510-2t) 각각은 동일한 로직 구성을 갖는다. 즉 신드롬 연산 블록들(510-1, ..., 510-2t) 각각은, 갈로아 필드 곱셈기(521)와, XOR 연산기(522)와, 레지스터(Reg)(523)를 포함하여 구성된다. 갈로아 필드 곱셈기(521)는, 리던던시 필터(320)로부터의 필터링된 코드워드(230-3)와 갈로아 필드의 원시근들((αⁱ)^r, i=1, ..., n-1, r=1, ..., 2t)을 입력받아 갈로아 필드 곱셈 연산을 수행하여 출력한다. 갈로아 필드 곱셈기(521)의 출력은 XOR 연산기(522)에 입력된다. XOR 연산기(522)는 갈로아 필드 곱셈기(521)의 출력과 레지스터(523)로부터의 출력에 대한 XOR 연산을 수행하여 출력한다. XOR 연산기(522)의 출력신호는 신드롬(Sr, r=0, ..., 2t-1)을 구성하며, 레지스터(523)를 통해 XOR 연산기(522)에 피드백된다.FIG. 12 is a circuit diagram showing another example of a syndrome operation unit of the ECC decoder (120) of FIG. 4. Referring to FIG. 12, the syndrome operation unit (410-2) according to the present example includes 2t (t is the maximum error correction capability) syndrome operation blocks (510-1, ..., 510-2t). Each of the syndrome operation blocks (510-1, ..., 510-2t) has the same logic configuration. That is, each of the syndrome operation blocks (510-1, ..., 510-2t) is configured to include a Galois field multiplier (521), an XOR operator (522), and a register (Reg) (523). The Galois field multiplier (521) receives the filtered codeword (230-3) from the redundancy filter (320) and the primitive roots of the Galois field ((α ⁱ ) ^r , i=1, ..., n-1, r=1, ..., 2t), performs a Galois field multiplication operation, and outputs the result. The output of the Galois field multiplier (521) is input to an XOR operator (522). The XOR operator (522) performs an XOR operation on the output of the Galois field multiplier (521) and the output from the register (523), and outputs the result. The output signal of the XOR operator (522) constitutes a syndrome (Sr, r=0, ..., 2t-1), and is fed back to the XOR operator (522) through the register (523).

리던던시 필터(320)로부터의 필터링된 코드워드(230-3)의 비트값들 각각은 갈로아 필드 곱셈기(521)에 순차적으로 입력된다. 갈로아 필드 곱셈기(521)는, 입력되는 n비트의 코드워드(230-3)의 비트들 각각에 대해 갈로아 필드의 원시근들((αⁱ)^r, i=1, ..., n-1, r=1, ..., 2t)과의 순차적인 갈로아 필드 곱셈 연산을 수행한다. 첫번째 신드롬(S₀)을 연산하기 위해, 코드워드(230-3)의 각각의 비트들 및 갈로아 필드의 원시근((αⁱ), i=1, ..., n-1)에 대한 갈로아 필드 곱셈 연산이 첫번째 신드롬 연산 블록(510-1)에 의해 순차적으로 수행된다. 예컨대 첫번째 신드롬 연산 블록(510-1)에 의한 갈로아 필드 곱셈 연산은, 코드워드(230-3)의 m번째 비트값 및 갈로아 필드 원시근(α^m-1)과 갈로아 필드 곱셈 연산으로 수행된다. 마찬가지로 코드워드(230-3)의 n번째 비트값은 갈로아 필드 원시근(α^n-1)과 갈로아 필드 곱셈 연산된다. 따라서 첫번째 신드롬(S₀)을 연산하기 위한 코드워드(230-3)의 모든 비트값들에 대한 갈로아 필드 곱셈 연산은 코드워드(230-3)의 비트수(n)와 동일한 횟수만큼 수행된다. 갈로아 필드 곱셈 연산들의 결과들은 XOR 연산기(522)에 의해 XOR 연산되고, 그 결과는 첫번째 신드롬(S₀)을 구성한다.Each bit value of the filtered codeword (230-3) from the redundancy filter (320) is sequentially input to the Galois field multiplier (521). The Galois field multiplier (521) performs a sequential Galois field multiplication operation with the primitive roots ((α ⁱ ) ^r , i=1, ..., n-1, r=1, ..., 2t) of the Galois field for each bit of the input n-bit codeword (230-3). In order to operate the first syndrome (S ₀ ), the Galois field multiplication operation with the primitive roots ((α ⁱ ), i=1, ..., n-1) of the Galois field is sequentially performed by the first syndrome operation block (510-1). For example, the Galois field multiplication operation by the first syndrome operation block (510-1) is performed by multiplying the m-th bit value of the codeword (230-3) and the Galois field primitive root (α ^m-1 ). Similarly, the n-th bit value of the codeword (230-3) is multiplied by the Galois field primitive root (α ^n-1 ). Therefore, the Galois field multiplication operation for all bit values of the codeword (230-3) to calculate the first syndrome (S ₀ ) is performed a number of times equal to the number of bits (n) of the codeword (230-3). The results of the Galois field multiplication operations are XOR-operated by the XOR operator (522), and the result constitutes the first syndrome (S ₀ ).

마찬가지로 2t번째 신드롬(S_2t-1)을 연산하기 위해, 코드워드(230-3)의 각각의 비트들 및 갈로아 필드의 원시근((αⁱ)^2t, i=1, ..., n-1)에 대한 갈로아 필드 곱셈 연산이 2t번째 신드롬 연산 블록(510-2t)에 의해 순차적으로 수행된다. 예컨대 2t번째 신드롬 연산 블록(510-2t)에 의한 갈로아 필드 곱셈 연산은, 코드워드(230-3)의 m번째 비트값 및 갈로아 필드 원시근((α^m-1)^2t)에 대한 갈로아 필드 곱셈 연산으로 수행된다. 마찬가지로 코드워드(230-3)의 n번째 비트값은 갈로아 필드 원시근((α^n-1)^2t)과 갈로아 필드 곱셈 연산된다. 따라서 2t번째 신드롬(S_2t-1)을 연산하기 위한 코드워드(230-3)의 모든 비트들에 대한 갈로아 필드 곱셈 연산도 또한, 코드워드(230-3)의 비트수(n)와 동일한 횟수만큼 수행된다. 갈로아 필드 곱셈 연산들의 결과들은 XOR 연산기(522)에 의해 XOR 연산되고, 그 결과값은 2t번째 신드롬(S_2t-1)을 구성한다.Likewise, to compute the 2t-th syndrome (S _2t-1 ), a Galois field multiplication operation for each bit of the codeword (230-3) and the primitive root ((α ⁱ ) ^2t , i=1, ..., n-1) of the Galois field is sequentially performed by the 2t-th syndrome operation block (510-2t ). For example, the Galois field multiplication operation by the 2t-th syndrome operation block (510-2t) is performed as a Galois field multiplication operation for the m-th bit value of the codeword (230-3) and the Galois field primitive root ((α ^m-1 ) ^2t ). Similarly, the n-th bit value of the codeword (230-3) is subjected to a Galois field multiplication operation and the Galois field primitive root ((α ^n-1 ) ^2t ). Therefore, the Galois field multiplication operation for all bits of the codeword (230-3) for calculating the 2t-th syndrome (S _2t-1 ) is also performed a number of times equal to the number of bits (n) of the codeword (230-3). The results of the Galois field multiplication operations are XOR-operated by the XOR operator (522), and the resulting value constitutes the 2t-th syndrome (S _2t-1 ).

본 예에 따른 신드롬 연산부(410-2)에 있어서, 필터링된 코드워드가 모든 신드롬 연산 블록들(510-1, ..., 510-2t)에 대해 공통으로 입력되므로, 신드롬 연산 블록들(510-1, ..., 510-2t) 각각의 신드롬 연산 동작은 병렬로 이루어지며, 2t개의 신드롬들(S₀, ..., S_2t-1)도 병렬로 출력된다. 결과적으로, 2t개의 신드롬들(Sr, r=0, ..., 2t-1)을 연산하기 위한 신드롬 연산 과정에는 모두 n 클럭이 소요된다. 도 10을 참조하여 설명한 바와 같이, 2비트의 최대 에러 정정 능력을 갖는 경우, 111비트의 제로-패딩 비트들이 제거되어 128비트의 오리지널 데이터와 16비트의 패리티 비트들만으로 구성되는 144비트의 필터링된 코드워드(230-3)에 대한 신드롬 연산부(410-2)의 신드롬 연산 과정에는 144 클럭들이 소요된다. 이에 반하여 2비트의 최대 에러 정정 능력 조건 및 111비트의 제로-패딩 비트들이 제거되지 않은 상태, 즉 255비트의 코드워드(220-3)의 경우, 신드롬 연산부(410-2)에 의한 신드롬 연산 과정에는 255 클럭들이 소요된다. 따라서 본 예에 따른 신드롬 연산부(410-2)는, 제로-패딩 비트들이 제거되지 않은 경우에 비하여, 신드롬 연산 동작을 수행하는데 있어서 상대적으로 적은 클럭이 소요되며, 그 결과 신드롬 연산 동작의 속도를 향상시킬 수 있다.In the syndrome operation unit (410-2) according to the present example, since the filtered codeword is commonly input to all syndrome operation blocks (510-1, ..., 510-2t), the syndrome operation of each of the syndrome operation blocks (510-1, ..., 510-2t) is performed in parallel, and 2t syndromes (S ₀ , ..., S _2t-1 ) are also output in parallel. As a result, the syndrome operation process for operating 2t syndromes (Sr, r=0, ..., 2t-1) requires a total of n clocks. As described with reference to FIG. 10, in the case of a maximum error correction capability of 2 bits, the syndrome operation process of the syndrome operation unit (410-2) for a 144-bit filtered codeword (230-3) consisting of only 128 bits of original data and 16 bits of parity bits after 111 bits of zero-padding bits are removed takes 144 clocks. In contrast, in the case of a 255-bit codeword (220-3) under the condition of a maximum error correction capability of 2 bits and in which 111 bits of zero-padding bits are not removed, 255 clocks are required for the syndrome operation process by the syndrome operation unit (410-2). Accordingly, the syndrome operation unit (410-2) according to the present example requires relatively fewer clocks to perform the syndrome operation compared to the case where zero-padding bits are not removed, and as a result, the speed of the syndrome operation can be improved.

도 13은 도 4의 ECC 디코더(120)의 신드롬 연산부의 또 다른 예를 나타내 보인 회로도이다. 도 13을 참조하면, 본 예에 따른 신드롬 연산부(410-3)는 2t개의 신드롬 연산 블록들(530-1, ..., 530-2t)을 포함한다. 신드롬 연산 블록들(530-1, ..., 530-2t) 각각은, 필터링된 코드워드(230-3) 및 갈로아 필드의 원시근들((αⁱ)^r, i=1, ..., n-1, r=1, ..., 2t)을 입력받는다. 본 예에 따른 신드롬 연산부(410-3)의 경우, 신드롬 연산 블록들(530-1, ..., 530-2t) 각각에 입력되는 필터링된 코드워드(230-3)는 각각의 비트값이 병렬로 입력된다. 신드롬 연산 블록들(530-1, ..., 530-2t) 각각은 2t개의 신드롬들(S₀, ..., S_2t-1)을 병렬로 발생시킨다.FIG. 13 is a circuit diagram showing another example of a syndrome operation unit of the ECC decoder (120) of FIG. 4. Referring to FIG. 13, the syndrome operation unit (410-3) according to the present example includes 2t syndrome operation blocks (530-1, ..., 530-2t). Each of the syndrome operation blocks (530-1, ..., 530-2t) receives a filtered codeword (230-3) and primitive roots ((α ⁱ ) ^r , i=1, ..., n-1, r=1, ..., 2t) of a Galois field. In the case of the syndrome operation unit (410-3) according to the present example, each bit value of the filtered codeword (230-3) input to each of the syndrome operation blocks (530-1, ..., 530-2t) is input in parallel. Each of the syndrome operation blocks (530-1, ..., 530-2t) generates 2t syndromes (S ₀ , ..., S _2t-1 ) in parallel.

신드롬 연산 블록들(530-1, ..., 530-2t) 각각은, (n-1)개의 갈로아 필드 곱셈기들(541(1), 541(2), ..., 541(n-2), 541(n-1)) 및 XOR연산기(551)를 포함한다. 갈로아 필드 곱셈기들(541(1), 541(2), ..., 541(n-2), 541(n-1)) 각각은, 리던던시 필터(320)로부터의 필터링된 코드워드(230-3)의 비트값들 중 첫번째 비트값을 제외한 나머지 비트값들 각각을 입력받는다. 예컨대 갈로아 필드 곱셈기(541(1))에는 필터링된 코드워드(230-3)의 두번째 비트값이 입력되고, 갈로아 필드 곱셈기(541(2))에는 필터링된 코드워드(230-3)의 세번째 비트값이 입력되고, 갈로아 필드 곱셈기(541(n-2))에는 필터링된 코드워드(230-3)의 (n-1)번째 비트값이 입력되며, 그리고 갈로아 필드 곱셈기(541(n-1))에는 필터링된 코드워드(230-3)의 n번째 비트값이 입력된다.Each of the syndrome operation blocks (530-1, ..., 530-2t) includes (n-1) Galois field multipliers (541(1), 541(2), ..., 541(n-2), 541(n-1)) and an XOR operator (551). Each of the Galois field multipliers (541(1), 541(2), ..., 541(n-2), 541(n-1)) receives each of the bit values of the filtered codeword (230-3) from the redundancy filter (320) except for the first bit value. For example, the second bit value of the filtered codeword (230-3) is input to the Galois field multiplier (541(1)), the third bit value of the filtered codeword (230-3) is input to the Galois field multiplier (541(2)), the (n-1)th bit value of the filtered codeword (230-3) is input to the Galois field multiplier (541(n-2)), and the nth bit value of the filtered codeword (230-3) is input to the Galois field multiplier (541(n-1)).

갈로아 필드 곱셈기들(541(1), 541(2), ..., 541(n-2), 541(n-1)) 각각에는 갈로아 필드의 원시근들((αⁱ)^r, i=1, ..., n-1, r=1, ..., 2t-1) 각각이 입력된다. 첫번째 신드롬 연산 블록(530-1)의 갈로아 필드 곱셈기들(541(1), 541(2), ..., 541(n-2), 541(n-1)) 각각에는 갈로아 필드의 원시근들(αⁱ, i=1, ..., n-1) 각각이 입력된다. 예컨대 갈로아 필드 곱셈기(541(1))에는 갈로아 필드의 원시근(α¹)이 입력되고, 갈로아 필드 곱셈기(541(2))에는 갈로아 필드의 원시근(α²)이 입력되고, 갈로아 필드 곱셈기(541(n-2))에는 갈로아 필드의 원시근(α^n-2)이 입력되며, 그리고 갈로아 필드 곱셈기(541(n-1))에는 갈로아 필드의 원시근(α^n-1)이 입력된다. 마찬가지로 2t번째 신드롬 연산 블록(530-2t)의 갈로아 필드 곱셈기들(541(1), 541(2), ..., 541(n-2), 541(n-1)) 각각에는 갈로아 필드의 원시근들(αⁱ, i=0, ..., n-1) 각각이 입력된다. 예컨대 갈로아 필드 곱셈기(541(1))에는 갈로아 필드의 원시근((α¹)^2t)이 입력되고, 갈로아 필드 곱셈기(541(2))에는 갈로아 필드의 원시근((α²)^2t)이 입력되고, 갈로아 필드 곱셈기(541(n-2))에는 갈로아 필드의 원시근((α^n-2)^2t)이 입력되며, 그리고 갈로아 필드 곱셈기(541(n-1))에는 갈로아 필드의 원시근((α^n-1)^2t)이 입력된다.Each of the Galois field multipliers (541(1), 541(2), ..., 541(n-2), 541(n-1)) receives one primitive root ((α ⁱ ) ^r , i=1, ..., n-1, r=1, ..., 2t-1) of the Galois field. Each of the Galois field multipliers (541(1), 541(2), ..., 541(n-2), 541(n-1)) of the first syndrome operation block (530-1) receives one primitive root (α ⁱ , i=1, ..., n-1) of the Galois field. For example, a primitive root (α ¹ ) of a Galois field is input to a Galois field multiplier (541(1)), a primitive root (α ² ) of a Galois field is input to a Galois field multiplier (541(2)), a primitive root (α ^{n-2 ) of a Galois field is input to a Galois field multiplier (541(n-2} )), and a primitive root (α ^n-1 ) of a Galois field is input to a Galois field multiplier (541(n-1)). Similarly, primitive roots (α i , i=0, ..., n-1) of a Galois field are input to each of the Galois field multipliers (541(1), 541(2 ⁾ , ..., 541(n-2), 541(n-1)) of the 2t-th syndrome operation block (530-2t). For example, a primitive root ((α ¹ ) ^2t ) of a Galois field is input to a Galois field multiplier (541(1)), a primitive root ((α ² ) ^2t ) of a Galois field is input to a Galois field multiplier (541(2)), a primitive root ((α n-2 ) ^2t ) of a Galois field is input to a Galois field multiplier (541( ^n-2 )), and a primitive root ((α n-1 ) ^2t ) of a Galois field is input to a Galois field multiplier (541( ^n-1 )).

신드롬 연산 블록들(530-1, ..., 530-2t) 각각의 갈로아 필드 곱셈기들(541(1), 541(2), ..., 541(n-2), 541(n-1)) 각각은, 입력되는 필터링된 코드워드(230-3)의 비트값과 갈로아 필드의 원시근에 대한 갈로아 필드 곱셈 연산을 수행하여 출력한다. 이 갈로아 필드 곱셈 연산의 결과값들은, 필터링된 코드워드(230-3)의 첫번째 비트값과 함께 XOR 연산기(551)에 입력된다. XOR 연산기(551)는 입력되는 값들에 대한 XOR 연산을 수행하여 출력한다. XOR 연산기(551)의 출력값들 각각은, 신드롬들(Sr, r=0, ..., 2t-1) 각각을 구성한다.Each of the Galois field multipliers (541(1), 541(2), ..., 541(n-2), 541(n-1)) of the syndrome operation blocks (530-1, ..., 530-2t) performs a Galois field multiplication operation on the bit value of the input filtered codeword (230-3) and the primitive root of the Galois field and outputs the result. The result values of the Galois field multiplication operation are input to the XOR operator (551) together with the first bit value of the filtered codeword (230-3). The XOR operator (551) performs an XOR operation on the input values and outputs the result. Each of the output values of the XOR operator (551) constitutes each of the syndromes (Sr, r=0, ..., 2t-1).

본 예에 따른 신드롬 연산기(410-3)의 경우, 갈로아 필드 곱셈 연산이 필터링된 코드워드(230-3)의 비트값들 각각에 대해 병렬로 이루어짐에 따라, 2t개의 신드롬들(Sr, r=0, ..., 2t-1)을 연산하기 위한 신드롬 연산 과정에는 단지 1 클럭만이 소요된다. 다만 이 경우 요구되는 갈로아 필드 곱셈 연산기나 XOR 연산기의 개수가 증가하여 전체 로직이 차지하는 면적이 증가될 수 있다. 도 10을 참조하여 설명한 바와 같이, 2비트의 최대 에러 정정 능력을 갖는 경우, 111비트의 제로-패딩 비트들이 제거되어 128비트의 오리지널 데이터와 16비트의 패리티 비트들만으로 구성되는 144비트의 필터링된 코드워드(230-3)에 대한 신드롬 연산부(410-3)는, 모두 143×4=572개의 갈로아 필드 곱셈기들을 갖는다. 반면에 2비트의 최대 에러 정정 능력 조건 및 111비트의 제로-패딩 비트들이 제거되지 않은 상태, 즉 255비트의 코드워드(220-3)의 경우, 신드롬 연산부(410-3)는 254×4=1,016개의 갈로아 필드 곱셈기를 갖는다. 따라서 본 예에 따른 신드롬 연산부(410-3)는, 제로-패딩 비트들이 제거되지 않은 경우에 비하여, 상대적으로 적은 면적의 로직이 요구된다.In the case of the syndrome operator (410-3) according to the present example, since the Galois field multiplication operation is performed in parallel for each bit value of the filtered codeword (230-3), only 1 clock is required for the syndrome operation process for calculating 2t syndromes (Sr, r=0, ..., 2t-1). However, in this case, the number of Galois field multiplication operators or XOR operators required may increase, which may increase the area occupied by the entire logic. As described with reference to FIG. 10, in the case of having a maximum error correction capability of 2 bits, the syndrome operation unit (410-3) for the 144-bit filtered codeword (230-3), which consists of only 128-bit original data and 16-bit parity bits by removing 111-bit zero-padding bits, has a total of 143×4=572 Galois field multipliers. On the other hand, in the case of a 255-bit codeword (220-3) with a maximum error correction capability of 2 bits and 111 bits of zero-padding bits not removed, the syndrome operation unit (410-3) has 254×4=1,016 Galois field multipliers. Therefore, the syndrome operation unit (410-3) according to the present example requires a relatively small area of logic compared to the case where the zero-padding bits are not removed.

도 14는 도 4의 ECC 디코더(120)의 에러 정정부(440)의 일 예를 나타내 보인 회로도이다. 도 14를 참조하면, 본 예에 따른 에러 정정부(440-1)는, 에러 위치 연산부(430)의 출력값들(X(α_i), i=0, ..., n-1)을 제어신호로 입력받는 멀티플렉서(641)와, 멀티플렉서(641)에 반전신호를 입력하기 위한 인버터(642)를 포함한다. 멀티플렉서(641)는, 인버터(642)의 출력값이 입력되는 제1 입력단자(IN1)와, 필터링된 코드워드(230-3)가 입력되는 제2 입력단자(IN2)를 갖는다. 멀티플렉서(641)의 출력단자를 통해서는 디코딩 출력데이터(DEC_OUT(i), i=0, ..., n-1)가 출력된다. 필터링된 코드워드(230-3)의 비트값들 각각은 순차적으로 인버터(642) 및 멀티플렉서(641)의 제2 입력단자(IN2)에 입력된다. 인버터(642)는 데이터 값을 반전시킨 후에 출력시키므로, 멀티플렉서(641)의 제2 입력단자(IN2)에는 필터링된 코드워드(230-3)의 비트값이 그대로 입력되고, 멀티플렉서(641)의 제1 입력단자(IN1)에는 필터링된 코드워드(230-3)의 비트값의 반전값이 입력된다.FIG. 14 is a circuit diagram showing an example of an error correction unit (440) of an ECC decoder (120) of FIG. 4. Referring to FIG. 14, an error correction unit (440-1) according to the present example includes a multiplexer (641) which receives output values (X(α_i), i=0, ..., n-1) of an error location calculation unit (430) as a control signal, and an inverter (642) for inputting an inversion signal to the multiplexer (641). The multiplexer (641) has a first input terminal (IN1) into which the output value of the inverter (642) is input, and a second input terminal (IN2) into which a filtered codeword (230-3) is input. Decoded output data (DEC_OUT(i), i=0, ..., n-1) is output through the output terminal of the multiplexer (641). Each bit value of the filtered codeword (230-3) is sequentially input to the inverter (642) and the second input terminal (IN2) of the multiplexer (641). Since the inverter (642) inverts the data value and then outputs it, the bit value of the filtered codeword (230-3) is input as is to the second input terminal (IN2) of the multiplexer (641), and the inverted value of the bit value of the filtered codeword (230-3) is input to the first input terminal (IN1) of the multiplexer (641).

입력되는 필터링된 코드워드(230-3)의 비트값의 비트 위치, 즉 i번째 비트에 대응되는 에러 위치 연산부(430)의 출력값(X(α_i), i=0, ..., n-1)에 따라 제1 입력단자(IN1)로의 입력값 또는 제2 입력단자(IN2)로의 입력값이 출력된다. 일 예에서, 에러 위치 연산부(430)의 출력값(X(α_i), i=0, ..., n-1)이 하이(high), 즉 데이터 "1"인 경우, 그 비트 위치에 있는 데이터에 에러가 발생한 경우이며, 따라서 이 경우 그 비트값을 반전시킨 제1 입력단자(IN1)의 입력값이 출력된다. 반면에 에러 위치 연산부(430)의 출력값(X(α_i), i=0, ..., n-1)이 로우(low), 즉 데이터 "0"인 경우, 그 비트 위치에 있는 데이터에 에러가 발생하지 않은 경우이며, 따라서 이 경우 그 비트값이 그대로 입력되는 제2 입력단자(IN2)의 입력값이 출력된다.Depending on the bit position of the bit value of the input filtered codeword (230-3), i.e., the output value (X(α_i), i=0, ..., n-1) of the error position calculation unit (430) corresponding to the i-th bit, the input value to the first input terminal (IN1) or the input value to the second input terminal (IN2) is output. In one example, if the output value (X(α_i), i=0, ..., n-1) of the error position calculation unit (430) is high, i.e., data "1", this means that an error has occurred in the data at that bit position, and therefore, in this case, the input value of the first input terminal (IN1) with the bit value inverted is output. On the other hand, if the output value (X(α_i), i=0, ..., n-1) of the error location operation unit (430) is low, i.e., data "0", then no error has occurred in the data at that bit location, and therefore, in this case, the input value of the second input terminal (IN2), into which the bit value is input as is, is output.

이와 같은 에러 정정 과정은, 필터링된 코드워드(230-3)의 모든 비트값들 각각에 대해 순차적으로 이루어진다. 따라서 n비트의 필터링된 코드워드(230-3)에 대한 에러 정정 과정에는 n 클럭이 소요된다. 도 10을 참조하여 설명한 바와 같이, 2비트의 최대 에러 정정 능력을 갖는 경우, 111비트의 제로-패딩 비트들이 제거되어 128비트의 오리지널 데이터와 16비트의 패리티 비트들만으로 구성되는 144비트의 필터링된 코드워드(230-3)에 대한 에러 정정부(440-1)에 의한 에러 정정 동작에 모두 144 클럭이 요구된다. 반면에 2비트의 최대 에러 정정 능력 조건 및 111비트의 제로-패딩 비트들이 제거되지 않은 상태, 즉 255비트의 코드워드(220-3)의 경우, 에러 정정부(440-1)에 의한 에러 정정 동작에 모두 255 클럭이 요구된다. 따라서 본 예에 따른 에러 정정부(440-1)는, 제로-패딩 비트들이 제거되지 않은 경우에 비하여, 에러 정정 동작을 수행하는데 있어서 상대적으로 적은 클럭이 소요되며, 그 결과 에러 정정 동작의 속도를 향상시킬 수 있다.This error correction process is sequentially performed for each of all bit values of the filtered codeword (230-3). Therefore, n clocks are required for the error correction process for the n-bit filtered codeword (230-3). As described with reference to FIG. 10, in the case of the maximum error correction capability of 2 bits, 144 clocks are required for the error correction operation by the error correction unit (440-1) for the 144-bit filtered codeword (230-3) composed of only 128 bits of original data and 16 bits of parity bits after 111 bits of zero-padding bits are removed. On the other hand, in the case of the maximum error correction capability of 2 bits and the state in which the 111 bits of zero-padding bits are not removed, i.e., the 255-bit codeword (220-3), 255 clocks are required for the error correction operation by the error correction unit (440-1). Therefore, the error correction unit (440-1) according to the present example requires relatively fewer clocks to perform the error correction operation compared to the case where zero-padding bits are not removed, and as a result, the speed of the error correction operation can be improved.

도 15는 도 4의 ECC 디코더(120)의 에러 정정부(440)의 다른 예를 나타내 보인 회로도이다. 도 15를 참조하면, 본 예에 따른 에러 정정부(440-2)는 n개의 에러 정정 블록들(610-1, ..., 610-n)을 포함한다. n개의 에러 정정 블록들(610-1, ..., 610-n) 각각은, 에러 위치 연산부(430)의 출력값들(X(α_i), i=0, ..., n-1) 각각을 제어신호로 입력받는 멀티플렉서(641)와, 멀티플렉서(641)에 반전신호를 입력하기 위한 인버터(642)를 포함한다. 예컨대 첫번째 에러 정정 블록(610-1)의 멀티플렉서(641)에는 첫번째 비트에 대한 에러 위치 연산부(430)의 출력값(X(α-0))이 제어신호로 입력되고, n번째 에러 정정 블록(610-n)의 멀티플렉서(641)에는 n번째 비트에 대한 에러 위치 연산부(430)의 출력값(X(α_n-1))이 제어신호로 입력된다.FIG. 15 is a circuit diagram showing another example of an error correction unit (440) of an ECC decoder (120) of FIG. 4. Referring to FIG. 15, an error correction unit (440-2) according to the present example includes n error correction blocks (610-1, ..., 610-n). Each of the n error correction blocks (610-1, ..., 610-n) includes a multiplexer (641) which receives each of the output values (X(α_i), i=0, ..., n-1) of an error location calculation unit (430) as a control signal, and an inverter (642) for inputting an inversion signal to the multiplexer (641). For example, the output value (X(α-0)) of the error location calculation unit (430) for the first bit is input as a control signal to the multiplexer (641) of the first error correction block (610-1), and the output value (X(α_n-1)) of the error location calculation unit (430) for the nth bit is input as a control signal to the multiplexer (641) of the nth error correction block (610-n).

에러 정정 블록들(610-1, ..., 610-n) 각각의 멀티플렉서(641)는, 인버터(642)의 출력값이 입력되는 제1 입력단자(IN1)와, 필터링된 코드워드(230-3)의 비트값들 중 하나가 입력되는 제2 입력단자(IN2)를 갖는다. 멀티플렉서(641)의 출력단자를 통해서는 디코딩 출력데이터(DEC_OUT(i), i=0, ..., n-1) 각각이 출력된다. 필터링된 코드워드(230-3)의 비트값들 각각은, 첫번째 에러 정정 블록(610-1)으로부터 n번째 에러 정정 블록(610-n)까지 순차적으로 입력된다. 예컨대 필터링된 코드워드(230-3)의 첫번째 비트값은 첫번째 에러 정정 블록(610-1)에 입력되고, 필터링된 코드워드(230-3)의 n번째 비트값은 n번째 에러 정정 블록(610-n)에 입력된다. 이에 따라 첫번째 에러 정정 블록(610-1)을 통해 필터링된 코드워드(230-3)의 첫번째 비트의 에러가 정정된 출력데이터(DEC_OUT(0))가 발생된다. 마찬가지로 n번째 에러 정정 블록(610-n)을 통해 필터링된 코드워드(230-3)의 n번째 비트의 에러가 정정된 출력데이터(DEC_OUT(n-1))가 발생된다.Each multiplexer (641) of the error correction blocks (610-1, ..., 610-n) has a first input terminal (IN1) into which the output value of the inverter (642) is input, and a second input terminal (IN2) into which one of the bit values of the filtered codeword (230-3) is input. Each decoded output data (DEC_OUT(i), i=0, ..., n-1) is output through the output terminal of the multiplexer (641). Each of the bit values of the filtered codeword (230-3) is sequentially input from the first error correction block (610-1) to the nth error correction block (610-n). For example, the first bit value of the filtered codeword (230-3) is input to the first error correction block (610-1), and the n-th bit value of the filtered codeword (230-3) is input to the n-th error correction block (610-n). Accordingly, output data (DEC_OUT(0)) in which the error of the first bit of the filtered codeword (230-3) is corrected is generated through the first error correction block (610-1). Similarly, output data (DEC_OUT(n-1)) in which the error of the n-th bit of the filtered codeword (230-3) is corrected is generated through the n-th error correction block (610-n).

본 예에 따른 에러 정정부(440-2)의 경우, 필터링된 코드워드(230-3)의 비트값들 각각에 대한 에러 정정 동작이 병렬로 이루어짐에 따라, n비트의 필터링된 코드워드(230-3)에 대한 에러 정정 과정에는 단지 1 클럭만이 소요된다. 다만 이 경우 요구되는 멀티플렉서 및 인버터의 개수가 증가하여 전체 로직이 차지하는 면적이 증가될 수 있다. 도 10을 참조하여 설명한 바와 같이, 2비트의 최대 에러 정정 능력을 갖는 경우, 111비트의 제로-패딩 비트들이 제거되어 128비트의 오리지널 데이터와 16비트의 패리티 비트들만으로 구성되는 144비트의 필터링된 코드워드(230-3)에 대한 에러 정정부(440-2)는, 모두 144개의 멀티플렉서들 및 인버터들을 갖는다. 반면에 2비트의 최대 에러 정정 능력 조건 및 111비트의 제로-패딩 비트들이 제거되지 않은 상태, 즉 255비트의 코드워드(220-3)의 경우, 에러 정정부(440-2)는 255개의 멀티플렉서들 및 인버터들를 갖는다. 따라서 본 예에 따른 에러 정정부(440-2)는, 제로-패딩 비트들이 제거되지 않은 경우에 비하여, 상대적으로 적은 면적의 로직이 요구된다.In the case of the error correction unit (440-2) according to the present example, since the error correction operation for each bit value of the filtered codeword (230-3) is performed in parallel, only 1 clock is required for the error correction process for the n-bit filtered codeword (230-3). However, in this case, the number of required multiplexers and inverters may increase, which may increase the area occupied by the entire logic. As described with reference to FIG. 10, in the case of having a maximum error correction capability of 2 bits, the error correction unit (440-2) for the 144-bit filtered codeword (230-3), which consists of only 128 bits of original data and 16 bits of parity bits by removing 111 bits of zero-padding bits, has a total of 144 multiplexers and inverters. On the other hand, in the case of a 255-bit codeword (220-3) with a maximum error correction capability condition of 2 bits and 111 bits of zero-padding bits not removed, the error correction unit (440-2) has 255 multiplexers and inverters. Therefore, the error correction unit (440-2) according to the present example requires a relatively small area of logic compared to the case where the zero-padding bits are not removed.

상술한 바와 같이 본 출원의 실시 형태들을 도면들을 예시하며 설명하지만, 이는 본 출원에서 제시하고자 하는 바를 설명하기 위한 것이며, 세밀하게 제시된 형상으로 본 출원에서 제시하고자 하는 바를 한정하고자 한 것은 아니다.As described above, the embodiments of the present application are described by way of examples and drawings, but this is only for the purpose of explaining what is intended to be presented in the present application, and is not intended to limit what is intended to be presented in the present application to the shapes presented in detail.

100...메모리 컨트롤러 110...ECC 인코더
120...ECC 디코더 210...오리지널 데이터
220...코드워드 240...에러 정정된 코드워드
300...제로-패딩 비트 제거부 310...리던던시 체크부
320...리던던시 필터부 410...신드롬 연산부
420...에러 위치 다항식 연산부 430...에러 위치 연산부
440...에러 정정부100...Memory Controller 110...ECC Encoder
120...ECC decoder 210...Original data
220...Codeword 240...Error corrected codeword
300...Zero-Padding Bit Removal Section 310...Redundancy Check Section
320...Redundancy filter section 410...Syndrome operation section
420... Error location polynomial operation unit 430... Error location operation unit
440...Error Correction Department

Claims

A zero-padding bit removal unit that removes zero-padding bits from an input codeword to generate a filtered codeword;
A syndrome operation unit that outputs syndromes for the above filtered codewords;
An error location polynomial calculation unit that outputs coefficients of an error location polynomial using the above syndromes;
An error location calculation unit that calculates and outputs the error location using the above coefficients; and
An error correction code decoder including an error correction unit that corrects errors in bits corresponding to the above error locations.

In the first paragraph,
An error correction code decoder in which the input codeword is composed of n bits including z bits (z ≥ 0) of zero-padding bits, k bits of original data, and (nkz) bits of parity bits.

In the second paragraph, the zero-padding bit removal unit,
A redundancy checker that inputs the number of bits (k) of the original data and the number of parity bits (nk) required for error correction and outputs the number of zero-padding bits; and
An error correction code decoder including a redundancy filter that receives the n-bit codeword and the number of zero-padding bits, removes the zero-padding bits from the n-bit codeword, and outputs a filtered codeword.

In the third paragraph,
An error correction code decoder, wherein the number of bits (n) of the above codeword is defined by the equation n = 2 ^m -1 (m is an integer greater than or equal to 3), and the number of parity bits (nk) required for error correction is defined by the equation nk ≤ mt (t is the maximum error correction capability).

In the first paragraph, the syndrome operation unit,
A Galois field multiplier that inputs the bit values of the above filtered codeword and the Galois field primitive roots, performs a Galois field operation, and outputs the results; and
An error correction code decoder including an XOR operator that performs an XOR operation on the output values of the above Galois field multiplier to output the syndromes.

In the first paragraph,
The above syndrome operation unit includes 2t syndrome operation blocks (t is the maximum error correction capability) in which the bit values of the filtered codeword are commonly input.
Each of the above syndrome operation blocks,
A Galois field multiplier that inputs the bit values of the above filtered codeword and the Galois field primitive roots, performs a Galois field operation, and outputs the results; and
An error correction code decoder including an XOR operator that performs an XOR operation on the output values of the above Galois field multiplier to output the syndrome.

In the first paragraph,
The above syndrome operation unit includes 2t syndrome operation blocks (t is the maximum error correction capability) in which each bit value of the filtered codeword is commonly input.
Each of the above syndrome operation blocks,
A plurality of Galois field multipliers that input each bit value of the above filtered codeword and a Galois field primitive root, perform a Galois field operation, and output the result; and
An error correction code decoder including an XOR operator that performs an XOR operation on the output values of the above Galois field multipliers to output the syndrome.

In the first paragraph, the error correction unit,
A multiplexer that receives the output value of the above error location operation unit as a control signal and outputs the input value of the first input terminal or the input value of the second input terminal as decoded output data; and
Including an inverter that sequentially receives bit values of the above filtered codeword, inverts them, and then inputs them to the first input terminal,
An error correction code decoder in which the bit values of the above filtered codeword are sequentially input to the second input terminal.

In the first paragraph,
The above error correction unit includes a plurality of error correction blocks that receive each bit value of the filtered codeword in parallel,
Each of the above error correction blocks,
A multiplexer that outputs the input value of the first input terminal or the input value of the second input terminal as decoded output data according to the output value of the error location calculation unit corresponding to the bit of the input filtered codeword; and
Including an inverter that receives the bit value of the above filtered codeword, inverts it, and then inputs it to the first input terminal,
An error correction code decoder in which the bit value of the above filtered codeword is input to the second input terminal.

In a memory controller that controls the memory device by a command from the host between the host and the memory device,
An ECC encoder that performs error correction encoding on data to be written to the memory device to generate a code word with added parity bits; and
Including an ECC decoder that performs error correction decoding on data read from the above memory device,
The above ECC decoder,
A zero-padding bit removal unit that removes zero-padding bits from an input codeword to generate a filtered codeword;
A syndrome operation unit that outputs syndromes for the above filtered codewords;
An error location polynomial calculation unit that outputs coefficients of an error location polynomial using the above syndromes;
An error location calculation unit that calculates and outputs the error location using the above coefficients; and
A memory controller including an error correction unit that corrects an error of a bit corresponding to the above error location.

In Article 10,
A memory controller in which the above input codeword is composed of n bits including z bits (z ≥ 0) of zero-padding bits, k bits of original data, and (nkz) bits of parity bits.

In the 11th paragraph, the zero-padding bit removal unit,
A redundancy checker that inputs the number of bits (k) of the original data and the number of parity bits (nk) required for error correction and outputs the number of zero-padding bits; and
A memory controller including a redundancy filter that receives the n-bit codeword and the number of zero-padding bits, removes the zero-padding bits from the n-bit codeword, and outputs a filtered codeword.

In Article 12,
A memory controller in which the number of bits (n) of the above codeword is defined by the equation n = 2 ^m -1 (m is an integer greater than or equal to 3), and the number of parity bits (nk) required for error correction is defined by the equation nk ≤ mt (t is the maximum error correction capability).

A step of generating a filtered codeword by removing zero-padding bits from an input codeword;
A step of outputting syndromes for the above filtered codewords;
A step of outputting coefficients of an error location polynomial using the above syndromes;
A step of calculating and outputting an error location using the above coefficients; and
An error correction code decoding method comprising a step of correcting an error of a bit corresponding to the above error location.

In Article 14,
An error correction code decoding method in which the input codeword is composed of n bits including z bits (z ≥ 0) of zero-padding bits, k bits of original data, and (nkz) bits of parity bits.

In the 15th paragraph, the step of generating a filtered codeword by removing zero-padding bits from the input codeword is:
A step of inputting the number of bits (k) of the original data and the number of parity bits (nk) required for error correction and outputting the number of zero-padding bits; and
An error correction code decoding method comprising the step of receiving the n-bit codeword and the number of zero-padding bits, removing the zero-padding bits from the n-bit codeword, and outputting the filtered codeword.

In Article 16,
An error correction code decoding method, wherein the number of bits (n) of the above codeword is defined by the formula n = 2 ^m -1 (m is an integer greater than or equal to 3), and the number of parity bits (nk) required for error correction is defined by the formula nk ≤ mt (t is the maximum error correction capability).