Design and Analysis of Nonuniform-Quantized SC Polar Decoder and SDDC Decoder for Communication and Memory Systems

Abstract

본 논문은 통신 및 메모리 시스템에 관한 연구 주제에 대해 다음 두 가지 기여를 포함한다. - 가산 백색 가우스 잡음(Additive white Gaussian noise) 채널에서 균일 양자화 연속 제거(Successive cancellation) 복호기 대비 높은 오류 정정 성능과 낮은 복호 복잡도 및 높은 메모리 효율성을 갖는 극 부호(Polar code)의 비균일 양자화 연속 제거 복호화 기법 - DRAM 시스템의 단일 DRAM 장치에서 발생하는 모든 오류를 정정하는 단일 장치 데이터 정정(Single device data correction)을 위한 순환 중복 검사 부호의 구성 방법 먼저, 가산 백색 가우스 잡음 채널에 대한 극 부호의 비균일 양자화 연속 제거 복호화 기법을 제안한다. 극 부호는 부호/복호 복잡도가 낮은 용량 달성(Capacity-achieving) 부호이며 이 부호에 대해 효율적인 구현 방법과 유한한 부호 길이에 대한 오류 정정 성능 향상 기법에 대한 다양한 연구가 진행되어 왔다. 양자화는 중요한 구현 문제이기 때문에 본 논문에서는 가산 백색 가우스 잡음 채널에 대해 양자화 레벨 분석을 기반으로 양자화 경계 값을 찾는 극 부호의 연속 제거 복호화에 대한 비균일 양자화 기법을 제안한다. 차세대 통신 및 메모리 시스템에서는 낮은 계산 복잡도와 높은 데이터 신뢰성, 효율적인 메모리 관리가 요구되므로 제안하는 비균일 양자화 기법은 2-4비트 정밀도(Precision) 레벨에 집중한다. 양자화 레벨 개수와 소거(Erasure) 유무에 따라 양자화 레벨을 세 가지 유형으로 구분하고, 유형별로 메시지 알파벳과 업데이트 규칙을 결정한다. 또한, 제안하는 비균일 양자화 연속 제거 복호기에 적합한 극 부호의 구성 방법을 제안한다. 이는 밀도 진화 분석과 블록 오류 확률의 상한을 기반으로 정보 집합과 양자화 경계 값을 동시에 결정하는 방법이다. 양자화 경계 값이 하나의 간격 크기로 결정되는 균일 양자화 기법과 달리 비균일 양자화 기법에서는 양자화 경계간의 간격들이 다르기 때문에 하나의 매개변수로 양자화 경계 값을 결정할 수 없다. 이 문제를 해결하기 위해 다변수 목적함수를 정의하고 이 목적함수를 최소화하기 위한 반복적 거친-미세(Coarse-to-fine) 탐색 알고리즘을 제안한다. 또한, 양자화기의 양자화 레벨 개수가 복호기의 양자화 레벨 개수보다 작은 경우 양자화기의 출력 값을 스케일링하는 방법을 제안한다. 마지막으로, 시뮬레이션을 통해 제안하는 비균일 양자화 연속 제거 복호기가 균일 양자화 연속 제거 복호기와 비교하여 높은 오류 정정 성능과 낮은 복호 복잡도 및 높은 메모리 효율성을 보임을 확인한다. 다음으로, DRAM 시스템에서 단일 장치 데이터 정정을 위한 순환 중복 검사 부호의 구성 방법을 제안한다. 최근 다양한 결함(Fault)으로 인한 오류로 인해 DRAM 시스템에서 오류 정정 부호의 중요성이 증대되고 있다. 서버에서 DRAM 장치의 고장(Hard-failure)으로 인한 문제에 대해 인텔의 오류 검사 및 정정 기법인 단일 장치 데이터 정정 기법은 DRAM 시스템의 안정성, 가용성 및 서비스 가능성에 대한 주요 기능을 담당한다. 하나의 DRAM 장치에서 발생하는 오류를 정정하기 위해 단일 장치 데이터 정정 기법에는 순환 중복 검사 비트와 짝수 패리티 비트가 사용된다. 구체적으로, 짝수 패리티 비트를 이용하여 오류 패턴을 결정하고, 결정된 오류 패턴과 순환 중복 검사 비트를 이용하여 오류 위치를 결정한다. 그러나 오류 위치를 고유하게 결정하지 않으면 오정정이 발생하여 오류 정정 성능의 저하를 초래한다. 본 논문에서는 검출된 오류 패턴을 이용하여 오류 위치를 고유하게 결정하는 단일 장치 데이터 정정 기법을 제안한다. 오류 위치를 고유하게 결정하기 위해 이진 순환 중복 검사 부호의 생성 다항식에 대한 요구조건을 도출한다. 도출한 요구조건을 기반으로 이진 순환 중복 검사 부호의 생성 다항식에 대한 구성 방법을 제안하고 이 요구조건을 만족하는 대표적인 생성 다항식을 제시한다. 마지막으로 제안한 순환 중복 검사 부호의 생성 다항식에 대한 구성 방법이 Reed-Solomon 부호 기반의 구성 방법보다 일반적임을 확인한다. 주요어: DRAM 시스템, Reed-Solomon 부호, 극 부호, 단일 장치 데이터 정정, 밀도 진화, 반복적 거친-미세 탐색 알고리즘, 블록 오류 확률, 비균일 양자화, 생성 다항식, 순환 중복 검사, 연속 제거 복호화, 오류 정정 부호, 최소화 문제.|This dissertation contains the following two contributions to the research topics on communication and memory systems: - A nonuniform-quantized successive cancellation (SC) decoding of polar codes over additive white Gaussian noise (AWGN) channels, which has better error-correction performance, lower decoding complexity, and higher memory efficiency compared to the best known uniform-quantized SC decoder. - A construction method of cyclic redundancy check (CRC) codes for single device data correction (SDDC) decoding in DRAM systems, which has the capability to correct all errors which occur in a single DRAM device. First, a nonuniform-quantized successive cancellation decoding of polar codes over AWGN channels is proposed. Since polar codes are capacity-achieving codes with low encoding/decoding complexity, there have been various research works devoted to devising efficient implementation methods as well as improving error-correction performance for finite-length cases. Since quantization is a critical implementation issue, a nonuniform quantization method is proposed for the SC decoder of polar codes, which finds quantization boundary values based on the analysis of quantization levels over the AWGN channels. Since low computational complexity, high reliability, and efficient memory management are required in the next-generation communication and memory systems, the proposed nonuniform quantization method is focused on 2-4 bit precision levels. Depending on the number of quantization levels and the presence of erasure, quantization levels are divided into three types, and the message alphabets and update rules are determined for each type. Also, a construction method of polar codes suitable for the proposed nonuniform-quantized SC decoder is proposed, which simultaneously determines the information set and the quantization boundary values based on density evolution analysis and an upper bound of the block error probability. Unlike uniform quantization methods in which quantization boundary values are determined by one interval size, quantization intervals are different in nonuniform quantization methods and so quantization boundary values cannot be determined with one parameter. In order to solve this problem, a multivariate objective function is defined and an iterative coarse-to-fine search algorithm to minimize this objective function is proposed. In addition, a method for scaling output values of quantizer is proposed for the case when the number of quantization levels of quantizer is smaller than the number of quantization levels of decoder. Finally, simulation results are provided to confirm that the proposed nonuniform-quantized SC decoder shows better error-correction performance, lower decoding complexity, and higher memory efficiency compared to the best known uniform-quantized SC decoder.

Second, a construction method of CRC codes for SDDC decoding in DRAM systems is proposed. In recent years, the importance of error-correction codes in DRAM systems has been increasing due to the errors from various faults. SDDC, an Intel's error checking and correcting scheme, is a main reliability, availability, and serviceability feature of DRAM systems in servers due to the significant hard-failure rate associated with DRAM devices. To correct errors in one DRAM device, CRC bits and even parity bits are used in SDDC decoding. Specifically, error pattern is determined by using the even parity bits and error location is determined by using the obtained error pattern and CRC bits. However, if the error location is not uniquely determined, miscorrection occurs, which results in degradation of error-correction performance. In this dissertation, an SDDC decoding scheme is proposed, which uniquely determines the error location by using the detected error pattern. In order to uniquely determine the error location, requirements for generator polynomials of binary CRC codes are derived. Based on the derived requirements, a construction method of CRC generator polynomials is proposed and various generator polynomials are presented. Finally, it is confirmed that the proposed construction method of CRC generator polynomials is more general than the construction methods based on Reed-Solomon codes. Keywords: Block error probability, cyclic redundancy check (CRC), density evolution, DRAM systems, error-correction codes, generator polynomial, iterative coarse-to-fine (C2F) search algorithm, minimization problem, nonuniform quantization, polar codes, Reed-Solomon (RS) codes, single device data correction (SDDC), successive cancellation decoding.