KR100996029B1

KR100996029B1 - 저밀도 패리티 검사 코드의 부호화 장치 및 방법

Info

Publication number: KR100996029B1
Application number: KR1020030027348A
Authority: KR
Inventors: 유남열; 김민구; 길강미
Original assignee: 삼성전자주식회사
Priority date: 2003-04-29
Filing date: 2003-04-29
Publication date: 2010-11-22
Also published as: KR20040092922A; US20040221223A1; US7178082B2

Abstract

가. 청구범위에 기재된 발명이 속한 기술분야

본 발명은 통신 시스템에서 저밀도 패리티 검사(Low Density Parity Check : LDPC) 코드의 부호화 장치 및 방법에 관한 것이다.

나. 발명이 해결하고자 하는 기술적 과제

본 발명에서는 실시간 처리가 가능하며, 부호의 확장이 용이하고, 장치가 간단하며, 복호 시 역행렬을 쉽게 구할 수 있는 LDPC 코드의 부호화 장치 및 방법을 제공함에 있다.

다. 발명의 해결방법의 요지

본 발명에 따른 방법은, 이중 사선 행렬을 패리티 부분으로 가지는 저밀도 패리티 검사 코드인 부호화 행렬의 생성 방법으로서, 상기 부호화 행렬의 정보의 부분행렬을 미리 결정된 부호율에 따라 소정 개수의 정방 행렬들로 구성하고, 상기 각 정방 행렬들은, 행과 열의 가중치가 1이고, 각각 다른 옵셋 값을 가지도록 상기 정보의 부분행렬을 생성하고, 상기 정보의 부분행렬과 상기 이중 사선 행렬이 결합된 형태로 저밀도 패리티 검사코드를 위한 행렬을 구성하는 제1과정과, 상기 정보의 부분행렬들의 각 행들의 순서를 임의의 순서가 되도록 내부 열 치환하는 제2과정을 포함함을 특징으로 한다.

라. 발명의 중요한 용도

저 밀도 패리티 검사 코드의 발생 장치에 사용한다.

저밀도 패리티 검사 코드, 실시간 처리, 부호 확장

Description

저밀도 패리티 검사 코드의 부호화 장치 및 방법 {APPARATUS AND METHOD FOR CODING OF LOW DENSITY PARITY CHECK CODE}

도 1a 내지 도 1d는 Mackay & Neal에 의해 제안된 LDPC 코드의 패리티 검사 행렬 생성 방법에 따른 행렬 구조도,

도 2는 MacKay에 의해 제안된 LDPC 코드의 패리티 검사 행렬 생성 방법에 따른 행렬 구조도,

도 3은 T.Zahng & K. Parhi에 의해 제안된 LDPC 코드의 패리티 검사 행렬 생성 방법에 따른 행렬 구조도,

도 4는 본 발명의 바람직한 실시 예에 따라 부호화율이 1/2인 패리티 검사 행렬의 형태를 도시한 도면,

도 5는 초기 인터리빙 룰에 따라 인터리빙 주소

(j)를 생성하는 과정을 나타낸 흐름도,

도 6a 내지 도 6c는 상기한 방식을 통해서 구해지는 LDPC 코드의 패리티 검사 행렬들의 구성도,

도 7은 본 발명의 일 실시 예에 따라 LDPC 코드 생성을 위한 행렬 발생기 및 부호화 장치의 블록 구성도,

도 8은 본 발명의 바람직한 실시 예에 따른 LDPC 코드 생성을 위한 부호화기의 블록 구성도,

도 9는 n=4000, k=2000, R=1/2인 LDPC 코드의 BER 및 FER 성능을 시뮬레이션 한 그래프,

도 10은 동일한 부호 율(code rate)에 대해 블록 크기(block size)를 5000으로 증가시켰을 때의 BER 및 FER 성능을 시뮬레이션 한 그래프,

도 11은 부호 율이 1/2인 경우에 대해 블록 크기가 2000, 5000, 10000, 20000인 경우의 FER 성능을 시뮬레이션 한 그래프.

본 발명은 통신 시스템에서 부호화 장치 및 방법에 관한 것으로, 특히 통신 시스템에서 저밀도 패리티 검사(Low Density Parity Check : LDPC) 코드의 부호화 장치 및 방법에 관한 것이다.

통상적으로 통신 시스템에서는 전송할 데이터를 가공하지 않은 정보 그대로를 전송하지 않고, 부호화를 수행한 이후에 이를 전송하게 된다. 이러한 부호화 방법으로는 반복 부호화 기법과, 길쌈(convolution) 부호화 기법과, 터보(Turbo) 부호화 기법 및 저밀도 패리티 부호화 기법 등이 있다. 상기한 각 부호화 기법들은 각각의 특성에 따라 사용될 수 있으며, 차세대 이동통신 시스템에서 사용하기 위해 저밀도 패리티 비트 부호화 기법에 대하여 활발한 개발이 진행되고 있다.

상기한 부호화 기법들 중 저밀도 패리티 부호화 방법은 정보 비트들을 부호화를 위한 행렬을 사용하여 전송하기 전에 부호화하는 블록 부호화의 일종이다. 이러한 블록 부호화를 수행할 때 사용되는 행렬에 "1"의 원소가 매우 작은 즉, 대부분의 원소가 "0"의 값을 가지는 부호화 행렬을 사용하는 방법을 저밀도 패리티 부호화 방법이라 말한다. 이와 같이 저밀도 패리티 부호화 방법은 아주 적은(sparse) 양의 "1" 값을 가지는 행(row)과 열(column)로 구성된 패리티 검사 행렬을 사용한다. 이러한 열과 행들은 각각 검사 노드(check node)와 변수 노드(variable node)로 대응시킨 펙터 그래프(factor graph)를 이용하여 코드(code)의 구조를 표현할 수 있다. 상기 펙터 그래프 상에서 정의되는 sum-product algorithm을 기본으로 하여 반복 디코딩(iterative decoding)이 가능하다. 그리고, 이 펙터 그래프(factor graph)상에서 이루어지는 반복 복호 과정은 병렬 구조로 구현이 가능하며, 이러한 병렬 처리에 따라 복호 시간을 획기적으로 감소시킬 수 있다. 또한, LDPC 코드는 블록의 크기(block size)가 증가할수록 터보 코드(turbo code)에 비해 큰 최소 거리(minimum distance)를 갖게 되므로, 터보 코드(turbo code)에 비해 낮은 프레임 에러 율(frame error rate)을 갖는다. 또한 비교적 높은 신호대 잡음비(SNR : Signal to Noise Ratio)에서도 오류 마루(error floor)를 보이지 않는 것이 일반적이다. 그리고, 코드워드(codeword)와 패리티 검사 행렬(parity check matrix)의 직교성(orthogonality)을 이용하여 CRC없이도 복호된 코드워드(codeword)에 대한 오류 검출과 효율적인 복호 정지가 가능하다.

하지만, LDPC 코드(code)는 패리티 검사 행렬(parity check matrix)을 이용하여 입력 정보 (information)에 대한 코드워드(codeword)를 구하는 부호화 과정이 터보 코드(turbo code)에 비해 복잡한 단점이 있다. 즉, 터보 코드는 recursive systematic convolutional encoder와 반복을 통해 실시간 부호화(real-time encoding)가 쉽게 가능한데 비해, LDPC 코드는 코드를 정의하는 패리티 검사 행렬의 구성에 따라 블록 길이의 제곱에 가까운 부호화 복잡도를 가진다.

그러면 현재까지 알려진 LDPC 코드의 패리티 검사 행렬의 생성 방법들에 대하여 살펴본다.

Construction method by MacKay & Neal

MacKay와 Neal은 LDPC code를 새롭게 소개한 논문에서 아래와 같은 방식의 MxN parity check matrix 생성 방식을 제안하였다.

<구조 1>

MxN 패리티 검사 행렬을 각 열(column)의 1의 개수가 t로 일정하고, 각 행(row)의 1의 개수는 가능한 한 일정하도록 랜덤(random)하게 생성한다. 그리고, 길이가 4인 사이클(cycle)이 발생하지 않도록 임의의 두 열(column) 사이의 중복(overlap)이 1을 넘지 않도록 한다. 도 1a에는 부호화율이 1/2이고, 각 열의 1의 개수가 3개로 구성되는 행렬의 구조를 도시하였다. 상기 도 1a에서 참조부호 101 및 103과 같은 원의 화살표는 상기 행렬에서 어떠한 행과 어떠한 열을 선택하여도 "1"의 숫자가 3개임을 의미한다.

<구조 2>

M/2개의 열(column)까지는 임의의 두 열(column)이 전혀 중복(overlap)되지 않도록 가중치(weight) 2인 열(column)을 생성하고, 나머지 열(column)들은 가중치(weight)가 3이면서 임의의 두 열(column) 사이의 중복(overlap)이 1을 넘지 않도록 랜덤(random)하게 생성한다. 도 1b에는 부화율이 1/3이고, 가중치가 3인 임의의 두 열 사이에 중복이 1을 넘지 않도록 구성하기 위한 행렬의 구조를 도시하였다. 상기 도 1b에서 참조부호 111 및 113의 대각선은 행렬에서 상기와 같은 형태로 "1"의 숫자가 존재함을 의미하고, 참조부호 115와 같은 원의 화살표는 상기 행렬에서 어떠한 행과 어떠한 열을 선택하여도 "1"의 숫자가 3개임을 의미한다.

<구조 1 & 구조 2>

상기 도 1a 및 도 1b에 의해 생성된 패리티 검사 행렬을 펙터 그래프(factor graph)로 표현하였을 때, 임의의 길이 l만큼의 사이클(cycle)이 발생하지 않도록 패리티 검사 행렬(parity check matrix)에서 몇몇 열(column)을 제거한다. 이러한 방법으로 구성하면, 상기 도 1a 및 도 1b에 도시한 바와 같은 두 구조를 만족하는 구성을 가질 수 있다.

그리고 이 밖에도 non-overlapping permutation 행렬을 통해 도 1c 및 도 1d와 같은 패리티 검사 행렬을 생성할 수 있다. 상기한 도 1a 내지 도 1d에서 화살표의 원형 또는 타원형은 열(column)의 random permutation을 의미한다. 상기 도 1c의 방식은 Gallager가 제안한 패리티 검사 행렬의 생성 방법과 동일하다. 이후 MacKay는 효율적인 부호화와 복호 성능을 고려하여 도 2와 같은 패리티 검사 행렬 의 생성을 제안하였다. 상기 도 2와 같은 형태의 행렬은 전체 행의 크기를 n개라 하고, 전체 열의 크기를 n-k개라 가정할 때, k+1번째부터 n-k 개의 원소에 대하여는 참조부호 201과 같이 대각선으로 "1"을 배열하고, 참조부호 203과 같은 마지막 부분에 어떠한 행과 어떠한 열을 선택하여도 "1"의 숫자가 3개가 되도록 구성하면, 복호 시에 성능이 향상됨을 알게 되었으며, 또한 그 밖의 구성은 도 2에 도시한 바와 같이 구성하여 부호화를 수행하는 방법이 개시되어 있다.

Mackay & Neal이 제안한 이와 같은 방법들은 LDPC 코드 생성 방법의 초기 형태에 해당한다. 그러나, 이와 같은 방식으로 패리티 검사 행렬을 생성하는 것은 부호화 복잡도를 줄이는데 문제가 있으며, 또한 다양한 부호율(code rate)과 블록 크기(block size)의 LDPC 코드를 생성하는데 어려움이 있는 단점이 있다.

Construction method by Generalized LDPC code

T. Zahng과 K. K. Parhi는 일반화된 LDPC 코드 구조에 기반을 둔 효율적인 부호화 및 복호화가 가능한 패리티 검사 행렬을 생성하고, 이를 이용하여 LDPC 코드에 대한 54Mbps 디코더를 FPGA로 구현하였다. Zahng & Parhi는 다음과 같은 형태로 패리티 검사 행렬을 구성하여 (3, 6) 정규(regular) LDPC 코드를 생성하고, 이를 위한 부분적 병렬 디코더(partly parallel decoder) 구조를 제안하였다. 이와 같이 제안된 구조는 하기 <수식>과 같은 형태를 취한다.
<수식>

상기 도 3에서는 H_l을 이루는 각 부분행렬(sub-matrix) I_x,y는 LxL 단위 행렬이고, H₂을 이루는 각 부분행렬 P_x,y는 LxL 단위 행렬의 순환 이동(cyclic shift)된 형태이다. 즉, T^u(Q)를 행렬 Q의 각 열(column)을 u만큼의 오른쪽 이동 동작(right shift operation)이라 하면, P_x,y는 하기 <수학식 1>을 만족시키는 LxL 행렬이다.

상기 <수학식 1>에서 알 수 있는 바와 같이 상기 도 3의 맨 아래에 위치한 부분 행렬 H₃으로 LDPC 코드의 패리티 검사 행렬을 구성하면, H가 순환(cycle) 값 4를 갖지 않는 랜덤 패리티 검사 행렬(random parity check matrix)이 된다. 상기 도 3에 도시한 바와 같은 구조를 가지는 T. Zahng & K. Parhi의 패리티 검사 행렬을 통해 각각의 부분행렬에 대한 변수 노드(variable node) 및 검사 노드(check node) 처리(processing)를 동시에 수행하는 partly parallel LDPC decoder를 구현하였다. 즉, L개의 메모리 위치(memory location)를 갖는 변수 노드부(variable node unit : VNU)를 모두 k²만큼 갖고, 각 부분행렬마다 k개의 검사 노드부(check node unit : CNU)를 가지며, 이들에 대한 연결(connection)을 통해 매 클록(clock)마다 메모리 위치(memory location)를 갱신시켜가도록 디코더를 구현하였다. 따라서, 한 번의 반복(iteration)이 이루어지기 위해서는 2L 클록이 필요하게 된다.

상기한 바와 같은 디코더의 구조는 일반화된 LDPC 구조의 개념을 바탕으로 하여 LDPC 코드를 디자인(design)하고, 이에 대한 partly parallel decoder를 실제로 Xilinx Virtex FPGA를 통해 구현하였다는데 의의가 있다. 그러나 보다 다양한 부호율과 블록 크기(block size)를 위한 유연성(flexibility)이 부족하고 효율적인 시스터메틱 부호화(systematic encoding)가 역시 간단하지 않다는 문제점을 가진다.

Construction by semi-random parity check matrix

L. Ping등은 semi-random technique을 이용하여 LDPC 코드를 위한 패리티 검사 행렬을 구성하는 새로운 방법을 제시하였다. 즉, 패리티 검사 행렬을 두 개의 부분행렬로 구분하여 하나의 부분행렬 부분만을 랜덤(random)한 방식으로 생성하고, 나머지 하나의 부분행렬은 deterministic한 방식으로 생성하는 방법을 제시하였다. 그리고, 이러한 방식으로 패리티 검사 행렬을 구성하여 보다 효율적인 실시간 부호화(real-time encoding)가 가능함을 보이고, 복호 성능도 전체적인 랜덤 패리티 검사 행렬(fully random parity check matrix)에 뒤지지 않음을 실험을 통해 보였다.

Semi-random parity check matrix를 H라 하고, H = [H^d | H^p]과 같이 두 부분의 부분행렬로 구성한다. 이 때, H^p 는 패리티 검사 행렬 H의 패리티(parity) 부분에 해당하는 (n-k)x(n-k) 부분행렬(sub-matrix)이며, H^d는 정보(information) 부분에 해당하는 (n-k)xk 부분행렬(sub-matrix)이다. 그리고, 임의의 코드워드(codeword) c 역시 c = [c^d | c^p]의 형태로 구성하면, c^d는 시스터메틱 정보(systematic information) 심볼에 해당하는 부분이고, c^p는 코드워드(codeword)의 패리티(parity) 심볼에 해당하는 부분이다. 패리티 검사 행렬 H의 패리티 부분 H^p는 다음과 같이 deterministic한 이중 대각선 행렬(dual-diagonal matrix) 형태로 구성하며, 이를 수학식으로 도시하면 하기 <수학식 2>와 같이 도시할 수 있다.

그리고, 패리티 검사 행렬의 정보 부분 H^d는 열 가중치(column weight)와 행 가중치(row weight)가 각각 일정하도록 유지하면서 랜덤하게 생성하는 방식을 제안하였다. 이와 같이 H^P와 H^d를 구성하고, 이에 따라 패리티 검사 행렬을 구성하면 패리티 검사 행렬과 코드워드의 직교성을 이용하여 각 패리티(parity) 심볼은 하기 <수학식 3>과 같은 구조를 가진다.

상기 <수학식 3>을 사용하면 입력 정보 심볼을 가지고, (n-k)개의 패리티 심 볼을 매우 간단하게 실시간(real-time)으로 구할 수 있다.

R. Echard등은 이중 대각선 행렬(dual-diagonal matrix)의 역행렬(inverse matrix)이 삼각 행렬(triangular matrix)임을 이용하여 하기 <수학식 4>를 이용하여 실시간 부호화(real-time encoding)가 가능한 간단한 인코더(encoder) 구조를 제시하였다.

또한, R. Echard등은 효율적인 디코더(decoder) 구조를 위해 H^d부분행렬(sub-matrix)을 다시 새로운 부분행렬(sub-matrix)들로 나누어 구성하였다. 그리고, 각 부분행렬(sub-matrix)들은 임의의 한 permutation matrix에 대한

-rotation 패턴(pattern)에 의해 정의하였다. Rate = 1/2인 LDPC 코드를 위한 패리티 검사 행렬의 부분행렬(sub-matrix) H^d를 하기 <수학식 5>와 같이 구성한다.

H^d를 이루는 부분행렬(sub-matrix)

_A를 임의의 단위 행렬에 대한 permutation matrix라 하면, 부분행렬(sub-matrix)

_B,

_C,

_D는

_A를 각각 -

/2,

,

/2만큼 회전 이동시킨 형태의 행렬이다.

R. Echard등은 이와 같은 방식으로 패리티 검사 행렬을 구성하여 비교적 우수한 성능을 얻을 수 있으면서도 부호화가 간단한 LDPC 코드를 제안하였다. 하지만, rate 1/2를 제외한 다른 부호율(code rate)에 해당하는 패리티 검사 행렬을 생성하기 위한

-rotation 패턴(pattern)에 대하여는 거의 설명되어 있지 않다. 따라서 이러한 부분에 대하여는 많은 연구가 이루어져야 하며 현 상태를 그대로 시스템에 적용하기 어려운 문제를 가진다.

이상에서 설명한 3가지의 LDPC 코드에 대하여 각 코드마다 각각 장점들을 가지지만 그에 못지 않은 문제점들을 가지고 있다. 따라서 실시간 처리가 불가능하거나 또는 부호의 확장이 용이하지 않은 문제 등이 있고, 매우 제한적으로만 사용할 수 있도록 구성되어 있다. 따라서 현재의 이동통신 시스템에서 부호화 기법으로 LDPC 코드를 사용하기 어려움이 있으며, 차후에도 상기한 방법들로는 시스템에 적용하기 어려운 문제들을 가진다.

따라서 본 발명의 목적은 실시간 처리가 가능한 LDPC 코드의 부호화 장치 및 방법을 제공함에 있다.

본 발명의 다른 목적은 부호의 확장이 용이한 LDPC 코드의 부호화 장치 및 방법을 제공함에 있다.

본 발명의 또 다른 목적은 역행렬을 쉽게 구할 수 있는 LDPC 코드의 부호화 장치 및 방법을 제공함에 있다.

상기한 목적들을 달성하기 위한 본 발명의 장치는, 이중 사선 행렬을 패리티 부분으로 가지는 저밀도 패리티 검사 코드인 부호화 행렬의 생성 장치로서, 상기 부호화 행렬의 정보의 부분행렬을 미리 결정된 부호율에 따라 정보부분을 행과 열의 가중치가 1인 각 정방 행렬들에 각각 다른 소정의 옵셋 값을 가지도록 정방행렬을 생성하고, 상기 각 정방 행렬들과 상기 이중 사선 행렬이 결합된 형태로 저밀도 패리티 검사코드를 위한 행렬을 구성하는 행렬 구성기와, 상기 정보의 부분행렬들의 각 행들의 순서를 임의의 순서가 되도록 내부 행 치환하는 내부 행 치환 장치를 포함한다.

상기한 목적들을 달성하기 위한 본 발명의 방법은, 이중 사선 행렬을 패리티 부분으로 가지는 저밀도 패리티 검사 코드인 부호화 행렬의 생성 방법으로서, 상기 부호화 행렬의 정보의 부분행렬을 미리 결정된 부호율에 따라 소정 개수의 정방 행렬들로 구성하고, 상기 각 정방 행렬들은 행과 열의 가중치가 1이고 각각 다른 옵셋값을 가지도록 상기 정보의 부분행렬을 생성하고, 상기 정보의 부분행렬과 상기 이중 사선 행렬이 결합된 형태로 저밀도 패리티 검사코드를 위한 행렬을 구성하는 제1과정과, 상기 정보의 부분행렬들의 각 행들의 순서를 임의의 순서가 되도록 내부 행 치환하는 제2과정을 포함하며,

상기 제2과정은;

상기 정보의 부분행렬에 대한 행의 수 보다 큰 값들 중 상기 행의 숫자에 가장 가까운 소수를 결정하는 단계와, 상기 결정된 소수 바로 전까지의 모든 자연수를 거듭제곱의 모듈러 연산에 따른 형태로 표현할 수 있는 원시 원소를 계산하는 단계와, 상기 계산된 원시 원소에 따라 각 행들의 순서를 변경하는 내부 행 치환을 수행하는 단계를 포함한다.

이하 본 발명의 바람직한 실시 예를 첨부한 도면을 참조하여 상세히 설명한다. 우선 각 도면의 구성 요소들에 참조 부호를 부가함에 있어서, 동일한 구성 요소들에 한해서는 비록 다른 도면상에 표시되더라도 가능한 한 동일한 부호를 가지도록 하고 있음에 유의해야 한다.

또한 하기 설명에서는 구체적인 메시지 또는 신호 등과 같은 많은 특정(特定) 사항들이 나타나고 있는데, 이는 본 발명의 보다 전반적인 이해를 돕기 위해서 제공된 것일 뿐 이러한 특정 사항들 없이도 본 발명이 실시될 수 있음은 이 기술 분야에서 통상의 지식을 가진 자에게는 자명하다 할 것이다. 그리고 본 발명을 설명함에 있어, 관련된 공지 기능 혹은 구성에 대한 구체적인 설명이 본 발명의 요지를 불필요하게 흐릴 수 있다고 판단되는 경우 그 상세한 설명을 생략한다.

본 발명에서 제안하는 정규화(Regular) LDPC 코드는 종래기술에서 설명한 semi-random LDPC 코드의 구조를 바탕으로 구성한다. 본 발명에 따른 LDPC 코드의 구조는 도 4와 같이 도시된다. 도 4는 본 발명의 바람직한 실시 예에 따라 부호화율이 1/2인 패리티 검사 행렬의 형태를 도시한 도면이다. 본 발명에 따른 저밀도 패리티 검사 코드인 부호화를 위한 행렬은 크게 하기의 2 과정으로 구성된다.

먼저 첫 번째 과정을 살펴보면 하기와 같다. 상기 도 4에서 도시한 바와 같이 LDPC 코드를 구현하는 것은 부호화 구조를 보다 간단하게 구현할 수 있고, 실시간 부호화(real-time encoding)가 가능하도록 하기 위함이다. 상기 도 4에서 L = (n-k)/(column weight in H^d) = k/(row weight in H^d)이며, 부호율(rate) = 1/2인 경우 정보(information) 부분에 해당하는 부분행렬(sub-matrix) H^d의 행(row)(502)과, 열(column)(501)의 가중치(weight)는 모두 4이다. 즉, P₁부터 P₁₆까지의 각 부분행렬들은 L xL의 크기를 가지는 정방 행렬이며, 각 P₁부터 P₁₆까지의 부분행렬들은 어떠한 행과 어떠한 열을 선택하더라도 "1"의 숫자가 모두 1개인 행렬이 된다. 즉, 행과 열의 가중치가 1인 정방행렬이 된다. 상기한 P₁부터 P₁₆까지의 부분행렬들의 집합이 정보를 의미하는 행렬이 된다. 또한 참조부호 503의 부분은 이중 대각선 행렬을 가진다. 따라서 참조부호 510, 511은 패리티 부분행렬에서 1의 배열 상태를 의미한다. 즉, 상기 정보부분의 행렬과 이중 사선 행렬을 결합하여 하나의 저밀도 패리티 검사 코드인 부호화를 위한 행렬을 구하는 것이다. 상기 정보의 값을 알리는 부분행렬 P_i는 임의의 옵셋 값(offset value) b_i에 의한 단위행렬의 permutation matrix이다. 즉, 단위행렬의 각 열(column)을 오른쪽으로 b_i만큼 순환 이동(cyclic shift)시켜 얻은 행렬(matrix)이다. b_i의 값은 b_i와 b_i-1의 차가임의의 integer q의 거듭제곱 qⁱ이 되도록 정의한다. 이와 같이 형태를 구성하는 과정이 본 발명에 따른 첫 번째 과정이다. 즉, 행렬의 형태를 구성하는 과정이다.

다음으로 상기한 형태를 가지는 행렬을 이용하여 저밀도 패리티 검사 코드인 부호화를 위한 행렬을 완성하는 과정에 대하여 설명한다. 상기한 값에서 qⁱ가 L보다 큰 경우에는 L보다 크면서 L에 가장 가까운 소수(prime integer) p_L로 모듈러(modulo)시킨다. qⁱ와 b_i는 하기 <수학식 6>과 같이 정의된다.

상기 <수학식 6>에서 임의의 integer q는 실험적으로 정의한다. 상기한 바와 같이 구성하는 이유는 상기 각 행의 값들의 위치를 변경함으로써 발생할 수 있는 오류를 줄이기 위함이다. 이를 예를 들어 설명하면 하기와 같다. 먼저 각 행이 6개로 구성된다면, 6보다 크면서 가장 가까운 소수는 7이 된다. 따라서 7에 가까우면서 거듭제곱의 형태로 모든 자연수를 7에 대한 모듈러 연산을 통해 계산할 수 있는 원시 원소를 구한다. 이때, 상기 행들을 정확하게 순서를 변경하여 혼합하기 위해 서는 하기의 2가지 조건을 충족해야 한다.

(1) 0, 1, 2, 3, …, 6의 순서를 가지지 않아야 한다.

(2) 상기한 집합에 포함된 모든 숫자들이 단 1회씩 나타나야 한다.

즉, 순서가 랜덤하게 발생하기 위해서는 상기한 2가지 조건을 만족해야 하는데, 이를 구현하기 위해 본 발명에서는 상기 <수학식 6>과 같은 연산방법을 택하였다. 이하의 설명에서 상기 <수학식 6>과 같은 연산을 "소수 모듈러 연산"이라 칭한다. 상기한 소수 모듈러 연산을 상기 예를 통해 설명하면, 실험적으로 선택된 원시 원소 값은 3이 될 수 있다. 이와 같이 3의 값을 가진다면, 각 행의 순서는 하기와 같이 변형된다.

먼저 3의 1승은 "3¹= 3"이므로, 첫 번째 행은 3번째 행으로 위치하게 된다. 다음으로 3의 2승은 "3²= 9"이므로, 7의 모듈러 연산에 의해 2가 결정되며, 2번째 행은 2번째 행으로 위치가 변경된다. 그리고, 3의 3승은 "3³= 27"이므로, 7의 모듈러 연산에 의해 3번째 행은 6번째 행 위치로 변경되며, 3의 4승은 "3⁴= 81"이므로, 7의 모듈러 연산에 의해 4번째 행은 4번째 행 위치로 변경되고, 3의 5승은 "3⁵=243"이므로, 7의 모듈러 연산에 의해 5번째 행은 5번째 행으로 위치가 변경되고, 3의 6승은 "3⁶= 729"이므로, 6번째 행은 1번째 행으로 위치가 변경된다. 즉, 이와 같이 구성하면, 중복되는 행 없이 행의 위치를 모두 변경할 수 있다. 이와 같이 구 성함으로써, 부호화된 심볼들의 오류 발생 확률을 줄일 수 있다.

상기한 방법들을 다시 정리하면, 상기 도 4와 같은 행렬을 구성한 후, (n-k)xk의 정보(information) 부분의 부분행렬(sub-matrix) H^d를 다음과 같은 규칙(rule)에 의해 내부 행 치환(inter-row permutation)시킨다.

(1) 정보의 부분행렬(sub-matrix)에 대한 행(row)의 수 (n-k)보다 크면서 (n-k)에 가장 가까운 소수(prime integer) p_M을 구한다.

(2) 1부터 (p_M-1)까지의 모든 자연수를 거듭제곱의 형태로 표현할 수 있는 원시 원소(primitive element) p_e를 구한다.

(3) 1부터 (n-k)까지의 행(row)의 숫자(number)를 j라 할 때, 각 행(row)에 대해 하기 <표 1>과 같은 매핑(mapping)에 의해 내부-행 치환(inter-row permutation)

(j)을 수행한다.

(1) = p_e
for (j=2; j<=n-k; j++)

(j) = (

(j-1) x p_e) mod p_M
if (

(j)>n-k)
do

(j) = (

(j) x p_e) mod p_M
while (

(j)>n-k)
end do
end if
end for

상기 <표 1>의 과정을 통해 하나의 행(row)을 의사 랜덤(pseudo-random)한 규칙(rule)에 의해 다른 하나의 행(row)으로 일대일 매핑(mapping)시키는 것이 가 능하다. 이와 같은 내부-행 치환(inter-row permutation)을 수행하면, 낮은 가중치 코드워드(low weight codeword)의 발생을 없앨 수 있다. 낮은 가중치 코드워드가 발생하면, 디코딩 시에 오류 마루(error floor)를 발생시킨다. 그리고, 검출되지 않는 오류(undetected error)를 발생시키게 되므로 LDPC 코드의 성능 열화를 초래하는 원인이 된다. 이러한 낮은 가중치 코드워드는 패리티 검사 행렬을 구성할 때, 발생하면 안되는 헤밍 가중치(Hamming Weight)를 가지는 코드워드가 발생하기 때문이다. 이와 같이 정보 행렬의 행들에 대한 순서를 변경하는 과정이 본 발명의 두 번째 과정이다.

도 5는 상기 <표 1>과 같은 소수 인터리빙 규칙(prime interleaving rule)에 따라 인터리빙 주소(interleaving address)

(j)를 생성하는 과정을 나타낸 흐름도이다.

600단계에서 상기 (1)의 과정에서 구한 정보의 부분행렬에 대하여 행의 수 보다 크면서 행의 수에 가장 가까운 소수(prime integer) p_M과 원시 원소(primitive element) p_e를 설정한다. 그런 후 602단계에서 i 값을 1로 설정하며, 내부-행 치환을 위한 첫 번째 행

(1)를 원시 원소 P_e로 설정한다. 이와 같은 설정이 이루어지면, 604단계에서 j 값을 1증가시키고, 606단계에서 j 번째 열의

(j)를 하기 <수학식 7>과 같이 계산한다.

상기 <수학식 7>은 설정된 행의 값을 변경하기 위한 계산이다. 즉, 상기 원시 원소의 거듭제곱된 값을 상기 계산된 소수로 모듈러 연산을 수행하여 새로 이동할 행의 위치를 결정함을 의미하는 것이다.

상기 606단계에서 상기 <수학식 7>의 계산을 수행한 이후에 608단계로 진행한다. 상기 608단계는 계산된 값이 행의 숫자보다 큰 값을 가지는가를 검사하는 것이다. 즉, 전체 행의 값이 10이고, 현재 행의 값이 2인데, 이동할 행의 값이 11 또는 12와 같은 값을 가진다면, 행이 이동할 수 없는 값이 된다. 따라서 이러한 현상을 방지하기 위해 계산된 값이 전체 행의 값보다 큰 값인가를 검사한다. 만일 계산된 값이 전체 행의 값보다 큰 값이라면, 612단계로 진행하여 하기 <수학식 8>의 계산을 수행한다. 하기 <수학식 8>은 상기 <수학식 7>과 동일한 계산으로, 차이점은 계산되는 j의 값이 1 증가한다는 것이다. 이러한 계산을 통해 동일한 값이 단 1회만 나오게 되므로 그 이후에는 동일한 값이 나오지 않게 된다. 또한 행의 값보다 큰 값이 2 이상 존재할 수도 있는데, 이러한 경우도 612단계를 수행한 이후에 다시 608단계를 수행하도록 함으로써, 행의 숫자보다 큰 행으로의 이동을 방지할 수 있다.

상기 <수학식 8>과 같은 계산을 통하거나 또는 608단계의 검사결과 행의 숫자보다 크지 않은 숫자가 계산되면, 610단계로 진행한다. 상기 610단계는 상기 내부 행 치환이 행의 숫자만큼 반복되었는가를 검사하는 과정이다. 만일 내부 행의 숫자만큼 반복되었다면, 상기 루틴을 종료한다. 즉, 하나의 부호화된 심볼 추출을 위한 행렬이 완성되는 것이다. 그러나 행렬이 완성되지 않은 경우 604단계로 진행하여 상기한 과정들을 반복한다.

도 6a 내지 도 6c는 상기한 방식을 통해서 구해지는 LDPC 코드의 패리티 검사 행렬들의 구성도이다. 도 6a는 부호율이 1/3인 경우를 도시하고 있으며, 도 6b는 부호율이 1/4인 경우를 도시하고 있고, 도 6c는 부호율이 3/4인 경우를 도시하고 있다.

도 7은 본 발명의 일 실시 예에 따라 LDPC 코드 생성을 위한 행렬 발생기 및 부호화 장치의 블록 구성도이다. 그러면 본 발명의 실시 예에 따라 도 6a 내지 도 6c와 같은 LDPC 코드의 생성기와 그에 따른 부호화 장치의 블록 구성 및 각 구성의 동작에 대하여 설명한다.

행렬 구성기(710)는 설정된 부호율 정보를 수신하여 전술한 바와 같은 초기 LDPC 코드의 행렬을 생성한다. 이러한 초기 LDPC 코드는 정보에 대응하는 부분행렬과 이중 사선 행렬을 구성하는 것을 의미한다. 또한 상기 정보에 대응하는 부분 행렬은 전술한 바와 같이 가중치 1을 가지는 정방행렬들의 조합을 통해 구성할 수 있다. 이때, 상기 가중치 1의 값을 가지는 단순한 행렬에 옵셋 값을 두어 이동시킨 정방행렬이 된다.

이와 같이 행렬 구성기(710)는 상기한 바와 같이 구성된 행렬을 출력하며, 동시에 도면에 점선으로 표시한 바와 같이 행의 숫자를 출력한다. 상기 행렬 구성기의 출력은 내부 행 치환 장치(720)로 입력된다. 상기 행의 숫자 값은 소수 및 원시원소 추출기(722)로 입력된다. 그러면 소수 및 원시원소 추출기(722)는 상기 행의 값에 따라 결정된 소수와 원시원소 값을 저장하고 있는 메모리(721)로부터 해당하는 소수 및 원시 원소를 추출한다. 그리고, 상기 추출된 값들을 정보 부분행렬 인터리버(724)로 출력한다.

한편 상기 행렬 구성기(710)로부터 출력된 행렬 값은 내부 행 치환 장치(720)의 행렬 분리기(723)로 입력된다. 상기 행렬 분리기(723)는 입력된 행렬 중 정보에 따른 부분행렬과 이중 사선 행렬에 따른 부분행렬을 구분하여 출력한다. 이와 같이 출력되는 각 부분행렬들은 서로 다른 장치로 입력된다. 먼저 정보 부분에 따른 행렬은 정보 부분행렬 인터리버(724)로 입력되며, 이중 사선 행렬의 부분행렬은 이중 사선 행렬 지연기(725)로 출력된다. 정보 부분 행렬 인터리버(724)는 상기 부분행렬의 행을 내부 행 치환하여 임의의 순서가 되도록 한다. 이러한 규칙은 상기 예시한 바와 같은 도 5에서 설명한 <수학식 7> 및 <수학식 8>과 같은 과정을 통해 행의 변환이 이루어진다. 따라서 상기 이중 사선 행렬 지연기(725)는 상기 정보 부분 행렬 인터리버(724)에서의 연산시간만큼 입력된 이중 사선 행렬을 지연시켜 출력한다.

이와 같이 정보에 대한 부분의 행렬이 인터리빙되어 출력된 부분행렬과 지연되어 출력된 이중사선 행렬 지연기(725)는 각각 행렬 결합기(726)로 입력된다. 상기 행렬 결합기(726)는 두 행렬을 분리될 때와 같은 형태로 다시 결합되어 출력된다. 이러한 과정을 통해 부호화를 위한 LDPC 부호화 행렬을 구성할 수 있다.

이러한 부호화 장치는 송신기에 구비하도록 구성할 수도 있다. 이와 달리 통 신 시스템에서 사용되는 부호율이 특정한 몇가지 부호율들이 선택적으로 사용된다면, 그에 맞추어 미리 부호화를 위한 행렬들을 생성한 후 메모리에서 이를 추출하여 사용하도록 구성할 수도 있다. 또 다른 방법으로 상기한 방법이 되도록 장치를 구현할 수도 있다. 이와 같이 특정한 장치를 통해 구현하는 경우의 예는 후술되는 도 8에서 설명하기로 한다.

상기 행렬 값이 출력되면, 부호화 처리부(730)로 입력되며, 입력되는 정보(Information)에 따라 부호화 심볼들을 생성하여 출력한다.

그러면 이하에서는 이와 같은 동작을 수행하기 위한 본 발명의 장치에 대하여 도면을 참조하여 설명한다. 도 8은 본 발명의 바람직한 실시 예에 따른 LDPC 코드 생성을 위한 부호화기의 블록 구성도이다.

정보들은 일련의 비트들로 구성되며, 코드워드 버퍼(codeword buffer)의 시스테메틱(systematic) 부분(805)으로 입력되어 저장된다. 본 발명에서 명시한 LDPC 부호의 부호화 과정은 (n-k)개의 열에 해당하는 (n-k)개의 패리티(parity) 검사식을 적용하여 (n-k)개의 패리티(parity) 비트들을 각각 순차적으로 생성하는 일련의 과정에 해당하므로, 각 (n-k)개의 열에서 Hd 행렬 부분에 1이 존재하는 위치를 알려주는 장치가 필요하게 된다. 이러한 "1"의 위치는 도 4의 초기 P행렬들의 옵셋(offset) 값과, P행렬들로 구성되는 H^d 행렬의 내부 행 치환(inter-row permutation) 방식에 의해 정의되므로, 내부 행 치환 주소(inter-row permutation address) 발생기(801)와 옵셋(offset) 값이 필요하게 된다. 내부 행 치환 주소 발 생기(Inter-row address generator)(801)와 옵셋(offset) 값에 의해 생성할 수 있는 H^d 행렬의 각 열에 존재하는 1의 위치에 대한 시퀀스를 기본 시퀀스(base sequence)라 부르기로 하고, 이를 생성하는 장치를 기본 시퀀스 발생기(base sequence generator)(803)이라 부른다. 이 기본 시퀀스 발생기(base sequence generator)(803)에 의해 생성되는 시퀀스는 H^d의 임의의 한 열에서 1이 존재하는 위치를 나타내는 시퀀스이다. 그리고, 이 시퀀스에 따라 정보 비트가 저장된 시스테메틱 버퍼(systematic buffer)(805)에서 정보 비트를 읽어 이전 시간의 패리티(parity) 비트와 합하여 (807, modulo 2 sum) 현재의 새로운 패리티(parity) 비트를 생성한 후, 이러한 방식으로 생성된 패리티(parity) 비트를 패리티 버퍼(parity buffer)(811)에 저장한다. (n-k)개의 모든 열에 대해 이러한 과정을 수행하면 (n-k)개의 모든 패리티 비트의 패리티 버퍼(811)로의 저장이 완료되고 이에 따라 부호화된 LDPC 부호어가 코드워드 버퍼(codeword buffer)(805, 811)에 생성, 저장되어 있게 된다.

상기한 방식으로 LDPC 코드를 위한 패리티 검사 행렬을 거의 정규화(almost regular) 한 형태로 생성하면 부호화기를 구현함에 있어 매우 규칙적인 방법으로 부호화가 가능한 이점이 있다. 또한 터보 부호화기(turbo encoder)와 같이 실시간 부호화(real-time encoding)가 가능하게 된다. 뿐만 아니라 병렬(parallel) LDPC 디코더를 위한 변수 노드(variable node)의 메모리 수를 각 노드(node)마다 일정하게 정의할 수 있는 장점이 있다. 따라서 디코더의 구현에 있어서도 비정규(irregular) LDPC 코드에 비해 용이하게 된다.

< 모의 실험 및 분석 >

이 절에서는 본 발명에 따른 방법으로 LDPC 코드를 생성하는 경우에 대한 모의 실험 결과 및 이에 따른 BER & FER 성능을 보인다. 본 문서에서 제안한 LDPC 코드의 구성 방법이 부호율(code rate)과 블록의 크기(block size)에 따라 안정적인 성능을 보일 수 있는지 검증하기 위해 다양한 부호율(code rate)과 블록 크기(block size)에 대한 실험을 수행하였다.

LDPC code의 성능을 위해 설정한 실험 환경은 다음과 같다.

- Floating point simulation

- BPSK modulation and AWGN channel

- Iterative belief propagation decoding

- maximum 100 or 50 iterations

도 9는 n=4000, k=2000, R=1/2인 LDPC 코드의 BER 및 FER 성능을 시뮬레이션 한 그래프이다. 패리티 검사 행렬(Parity check matrix)의 생성을 위한 초기 값 q는 18로 하였다. 실험 과정에서 비검출 오류(undetected error)는 발생하지 않았다. 높은 SNR에서 비검출 오류(undetected error)가 거의 발생하지 않는 것이 LDPC 코드의 일반적인 특성이다. 또한, 주의 깊게 관찰해야 할 것은 터보 코드(turbo code)와는 달리 BER과 FER의 차이가 그리 크지 않다는 점이다. 이는 오류(error)가 발생한 프레임(frame)에서는 비교적 많은 오류(error)가 한꺼번에 발생함을 의미한 다. 이와 달리 터보 코드는 높은 SNR에서 한 프레임에서 2 ~ 4 bit정도의 비교적 작은 수의 오류가 발생하는 프레임이 많이 존재한다. 이와 같이 오류가 발생한 프레임에서 한 번에 많은 오류가 발생하는 것은 LDPC 코드의 최소 거리(minimum distance)가 터보 코드에 비해 크기 때문이다. 이에 따라 LDPC 코드에서 비검출 오류의 발생률이 적고 동일한 비트의 오류율(bit error rate)을 갖는 E_b/N₀에서 프레임 오류율(frame error rate)도 터보 코드에 비해 우수하게 된다.

도 10은 동일한 부호율(code rate)에 대해 블록 크기(block size)를 5000으로 증가시켰을 때의 BER 및 FER 성능을 시뮬레이션 한 그래프이다. 패리티 검사 행렬의 생성을 위한 초기 값 q도 19로 변경하였다. 블록의 크기가 2000에서 5000으로 증가함에 따라 동일한 부호율에서 보다 우수한 성능을 보임을 알 수 있다. 그리고, 블록 크기가 증가함에 따라 패리티 검사 행렬에서 낮은 가중치 코드워드(low weight codeword)가 발생할 확률 또한 감소하여 SNR이 증가하여도 오류 마루(error floor)는 발생하지 않음을 알 수 있다. 이번 실험의 경우에도 비검출 오류(undetected error)는 발생하지 않았고, 오류가 발생하는 프레임에서는 최소 수십 ~ 수백 bit의 오류가 한꺼번에 발생하는 현상을 확인할 수 있었다.

도 11은 부호율이 1/2인 경우에 대해 블록 크기가 2000, 5000, 10000, 20000인 경우의 FER 성능을 시뮬레이션 한 그래프이다. 블록의 크기가 10000, 20000인 경우, 각각의 q값은 22로 하였다.

상기 도 11에서 동일한 부호율에 대해 블록 크기가 증가함에 따라 FER의 performance 성능의 기울기는 점점 더 급격해짐을 알 수 있다. 이는 블록 크기가 증가함에 따라 LDPC 코드의 가중치 분배(weight distribution)가 점점 더 나은 성능을 보이는 쪽으로 향상됨을 나타내고 있는 것이라 하겠다. 부호율(Code rate) = 1/2인 모든 경우에 대한 실험에서 비검출 오류는 발생하지 않았다. 이는 본 발명에서 제안한 LDPC 코드가 충분히 큰 최소 거리(minimum distance)를 가짐을 보이는 것이다.

이상에서 상술한 바와 같이 본 발명에 따른 저밀도 패리티 부호화 방법을 사용하면, 부호의 확장이 용이하며, 실시간 처리가 가능해지는 이점이 있다. 뿐만 아니라 부호화기의 구조가 간단해질 뿐 아니라 복호 시에 필요한 역행렬을 구하는 방법도 용이하게 계산할 수 있는 이점이 있다.

Claims

이중 사선 행렬을 패리티 부분으로 가지는 저밀도 패리티 검사 코드인 부호화 행렬의 생성 방법에 있어서,

상기 부호화 행렬의 정보의 부분행렬을 미리 결정된 부호율에 따라 소정 개수의 정방 행렬들로 구성하고, 상기 각 정방 행렬들은, 행과 열의 가중치가 1이고, 각각 다른 옵셋값을 가지도록 상기 정보의 부분행렬을 생성하고, 상기 정보의 부분 행렬과 상기 이중 사선 행렬이 결합된 형태로 저밀도 패리티 검사코드를 위한 행렬을 구성하는 제1과정과,

상기 정보의 부분행렬들의 각 행들의 순서를 임의의 순서가 되도록 내부 행 치환하는 제2과정을 포함함을 특징으로 하는 저밀도 패리티 검사 코드의 부호화 행렬 생성 방법.
제1항에 있어서, 상기 제2과정은,

상기 정보의 부분행렬에 대한 행의 수 보다 큰 값들 중 상기 행의 숫자에 가장 가까운 소수를 결정하는 단계와,

상기 결정된 소수 바로 전까지의 모든 자연수를 거듭제곱의 모듈러 연산에 따른 형태로 표현할 수 있는 원시 원소를 계산하는 단계와,

상기 계산된 원시 원소에 따라 각 행들의 순서를 변경하는 내부 행 치환을 수행하는 단계를 포함함을 특징으로 하는 저밀도 패리티 검사 코드의 부호화 행렬 생성 방법.
이중 사선 행렬을 패리티 부분으로 가지는 저밀도 패리티 검사 코드인 부호화 행렬의 생성 장치에 있어서,

상기 부호화 행렬의 정보의 부분행렬을 미리 결정된 부호율에 따라 정보부분을 행과 열의 가중치가 1인 각 정방 행렬들에 각각 다른 소정의 옵셋값을 가지도록 정방행렬을 생성하고, 상기 각 정방 행렬들과 상기 이중 사선 행렬이 결합된 형태로 저밀도 패리티 검사코드를 위한 행렬을 구성하는 행렬 구성기와,

상기 정보의 부분행렬들의 각 행들의 순서를 임의의 순서가 되도록 내부 행 치환하는 내부 행 치환 장치를 포함함을 특징으로 하는 저밀도 패리티 검사 코드의 부호화 행렬 생성 장치.
제3항에 있어서,

상기 내부 행 치환 장치의 출력 행렬을 이용하여 입력되는 정보를 부호화하는 부호화 처리부를 더 포함함을 특징으로 하는 저밀도 패리티 검사 코드의 부호화 행렬 생성 장치.
제3항 또는 제4항에 있어서, 상기 내부 행 치환 장치는,

상기 행렬 구성기에서 생성된 행렬의 행의 숫자에 따라 결정되는 소수와 원시 원소를 결정하는 소수 및 원시원소 추출기와,

상기 행렬 구성기로부터 출력되는 행렬을 정보에 대한 부분행렬과 이중 사선 부분행렬로 분리하여 출력하는 행렬 분리기와,

상기 행렬의 정보에 대한 부분행렬의 각 행들을 상기 원시 원소와 소수를 이용하여 내부 행 치환을 수행하는 정보 부분행렬 인터리버와,

상기 이중 사선 부분행렬의 값을 소정 시간만큼 지연하여 출력하는 이중 사선 행렬 지연기와,

상기 이중 사선 행렬 지연기의 출력과 상기 정보 부분행렬 인터리버의 출력을 결합하여 출력하는 행렬 결합기를 포함함을 특징으로 하는 저밀도 패리티 검사 코드의 부호화 행렬 생성 장치.
이중 사선 행렬을 패리티 부분으로 가지는 저밀도 패리티 검사 코드인 부호화 행렬의 생성 장치에 있어서,

상기 부호화 행렬의 정보의 부분행렬 중 1의 위치 값을 출력하는 내부 열 주소 발생기와,

상기 정보의 부분행렬에 대한 옵셋 값을 수신하여 상기 1의 위치에 대한 기본 시퀀스를 발생하는 기본 시퀀스 발생기와,

입력되는 정보를 저장하고, 상기 기본 시퀀스 발생기로부터 출력되는 기본 시퀀스에 따른 위치의 정보를 출력하는 시스테메틱 장치와,

상기 시스테메틱 장치로부터 출력된 정보와 이전 패리티 값을 수신하여 가산하여 패리티 값을 생성하는 가산기와,

상기 가산기의 출력을 미리 결정된 시간만큼 지연하여 상기 가산기로 출력하는 지연기를 포함함을 특징으로 하는 저밀도 패리티 검사 코드의 부호화 행렬 생성 장치.