KR100912600B1

KR100912600B1 - 임의 개수의 정보 비트들을 위한 테일바이팅 터보 코드

Info

Publication number: KR100912600B1
Application number: KR1020070096967A
Authority: KR
Inventors: 바-종 쉔; 탁 케이. 리
Original assignee: 브로드콤 코포레이션
Priority date: 2006-09-28
Filing date: 2007-09-21
Publication date: 2009-08-19
Anticipated expiration: 2027-09-21
Also published as: KR20080030493A; EP1906536A3; TW200832936A; US20080092018A1; EP1906536A2

Abstract

임의의 개수의 정보 비트들을 위한 테일 바이팅 터보 코드가 개시된다. 대부분의 경우에서, 터보 인코더가 테일 바이팅에 따라 동작하는 것(즉, 터보 인코더의 시작 상태와 종료 상태가 동일하도록 동작)을 확실히 하기 위해 입력 시퀀스에 추가적인 심볼을 덧붙일 필요가 전혀 없는 새로운 수단이 제공된다. 가장 나쁜 경우를 상정하는 경우에도, 단지 하나의 심볼(또는 하나의 비트)만이 입력 시퀀스에 덧붙여질 뿐이다. 또한, 입력 시퀀스의 모든 입력 비트들이 터보 인코딩 내에서 인터리빙된다. 최대 하나의 심볼(또는 최대 하나의 비트)이 입력 시퀀스에 덧붙여질 필요가 있는 경우, 그 최대 하나의 심볼(또는 하나의 비트)은 역시 터보 인코딩 내에서 인터리빙된다. 더구나, 어떠한 크기의 입력 시퀀스도 테일 바이팅을 달성하기 위한 본 수단을 이용하여 수용될 수 있다.

Description

임의 개수의 정보 비트들을 위한 테일바이팅 터보 코드{TAIL-BITING TURBO CODE FOR ARBITRARY NUMBER OF INFORMATION BITS}

본 발명은 전반적으로 통신 시스템에 관련된 것이다. 더 상세하게는, 본 발명은 그러한 통신 시스템 내에서 터보 코드를 이용하여 입력 시퀀스를 인코딩할 경우의 테일 바이팅(tail-biting)에 관련된 것이다.

데이터 통신 시스템들은 오랜 기간 동안 계속적인 발전이 이뤄지고 있다. 최근에 상당한 관심을 끌게 된 통신 시스템으로는, 반복적 오류 정정 코드들(iterative error correction codes)을 채택한 통신 시스템이 있다. 그러한 통신 시스템으로서 근래 몇 년 사이에 관심을 받아온 통신 시스템은 터보 코드(반복적 오류 정정 코드의 한 형태)를 채용한 종류의 기술이었다. 반복 코드들을 가지는 통신 시스템들은 주어진 신호 대 잡음비(signal to noise ratio, SNR)에 대해서, 종종 다른 형태의 코드들에 비해 더 낮은 비트 오류율(bit error rate, BER)을 달성할 수 있다.

이 분야의 기술 개발에 있어서, 지속적이고 중요한 방향은, 어떤 통신 시스템 내에서 주어진 BER을 달성하는 데에 요구되는 SNR을 낮추려고 끊임없이 시도하 는 것이었다. 이상적인 목표는 통신 채널에서 샤논의 한계(Shannon's limit)에 도달할 수 있도록 노력하는 것이었다. 샤논의 한계는, 어떤 특정한 SNR을 가지는 어떤 통신 채널 내에서, 그 통신 채널을 통해 오류가 전혀 없는 전송을 이룩할 수 있을 경우의 데이터 전송율(data rate)이라고 볼 수 있다. 다른 말로 표현하면, 샤논의 한계는 어떤 주어진 변조 방식 및 코드 레이트(code rate)에 대해서, 채널 용량이 가질 수 있는 이론상의 경계라 할 수 있다.

상대적으로 낮은 오류율을 제공하는 터보 코드 기법은, 비록 상대적으로 낮은 데이터 처리율(data throughput rate)을 가지고 동작하기는 하지만, 통신 채널 내에 대량의 잡음을 가지는 통신 시스템들, 그리고 실질적으로 오류가 없는 통신이 가장 중요한 장점으로 여겨지는 경우의 맥락에서 광범위하게 사용되어 왔다. 터보 코딩을 이용하는 분야에서, 가장 초기의 몇몇 응용 분야 격전지들은, 정확한(즉, 이상적으로 말하면 오류가 전혀 없는) 통신이 종종 가장 핵심적인 설계 기준으로 여겨지던 우주 분야와 관련된 것들이었다. 기술 개발의 방향은 곧이어 지상 이용 분야 및 소비자 관련 응용 분야들을 개발하는 쪽으로 옮겨갔다. 여전히, 우주 관련 분야의 유산에 기초하여, 터보 코딩 기술에서 연구 노력의 초점은 계속해서 상대적으로 낮은 오류 바닥면(error floors)을 이루어내는 것이었으며, 특별히 더 높은 처리 능력을 달성하려는 쪽은 아니었다.

시간이 지남에 따라, 이 기술 분야의 초점은, 터보 코드 환경 내에서 제공되는 오류 바닥면을 상대적으로 낮게 유지하면서도, 더 높은 처리 능력을 지원하면서 동작할 수 있도록 터보 코딩과, 그 변형예들을 발전시키는 쪽으로 나아갔다.

일반적으로 말하면, 터보 코드들을 채용한 통신 시스템들이라는 맥락 내에서 보면, 통신 채널의 한쪽 끝에는 인코더 기능을 가지는 첫 번째 통신 장치가 있고, 그 통신 채널의 다른 쪽 끝에는 디코더 기능을 가지는 두 번째 통신 장치가 있는 것이다. 많은 예에서, 이들 두 통신 장치들 중 하나 또는 둘 모두는 인코더 및 디코더 기능을 가지고 있다(예를 들어, 양방향 통신 시스템의 경우).

터보 코딩의 테일 바이팅 터미네이션에 대해, 종래 기술들은 어떤 특정 입력 시퀀스 블록 크기를 가지는 특정 형태의 터보 코드에 대해 테일 바이팅을 제공할 수 있는데, 이러한 수단들은 테일 바이팅을 지원할 수 있도록 하기 위해 거의 완전히 들어내고 설계하지는 않고 다양한 블록 크기들이 수용될 수 있는 수단들을 제공한다. 달리 말하면, 이러한 수단들은 쉽게 말해 입력 시퀀스 내에 어떤 임의 개수의 정보 비트들을 수용하지는 못한다.

본 발명은 도면의 간단한 설명, 발명의 상세한 설명 및 청구범위 등을 통해 더욱 자세히 설명될 장치 및 그 동작 방법에 관한 것이다.

본 발명의 일 측면에 따르면, 입력 시퀀스(input sequence)를 인코딩할 때에 테일 바이팅(tail-biting)을 수행하도록 동작하는 인코더에 있어서,

상기 입력 시퀀스를 수신하도록 동작하는 버퍼;

상기 버퍼로부터 상기 입력 시퀀스를 수신하고 상기 입력 시퀀스를 인코딩하도록 동작하는 터보 인코더(turbo-encoder); 및

상기 입력 시퀀스의 첫 번째 심볼을 인코딩하기 전의 터보 인코더의 상태(state)가, 상기 입력 시퀀스의 마지막 심볼(symbol) 또는 상기 입력 시퀀스에 덧붙여진 최대 하나의 심볼 중 어느 하나를 인코딩하는 시점의 상기 터보 인코더의 상태와 동일하도록, 터보 인코더의 상기 상태와, 상기 입력 시퀀스에 덧붙여지는 최대 하나의 심볼을 상기 입력 시퀀스에 기초하여 결정하도록 동작하는 프로세싱 모듈(processing module)을 포함하며,

상기 버퍼는 상기 프로세싱 모듈이 상기 상태를 결정하면, 상기 터보 인코더에 상기 입력 시퀀스를 제공하도록 동작하며,

상기 터보 인코더는, 상기 입력 시퀀스의 첫 번째 심볼을 인코딩하기 이전, 그리고 상기 입력 시퀀스의 마지막 심볼 또는 상기 입력 시퀀스에 덧붙여진 최대 하나의 심볼 중 어느 하나를 인코딩한 이후에, 상기 프로세싱 모듈에 의해 결정된 상기 상태를 갖는다.

바람직하게는, 상기 첫 번째 심볼 및 두 번째 심볼 중 적어도 하나는 오직 하나의 비트만을 포함한다.

바람직하게는, 상기 프로세싱 모듈은 상기 버퍼가 상기 입력 시퀀스를 상기 터보 인코더에 제공한 후에, 상기 입력 시퀀스에 덧붙여지는 최대 하나의 심볼을 상기 터보 인코더로 제공하도록 동작한다.

바람직하게는, 상기 인코더는 상기 터보 인코더로부터 출력되는 인코딩된 시퀀스 내의 적어도 한 비트에 대해 펑처링(puncture)하도록 동작하는 펑처링 모듈(puncturing module)을 더 포함한다.

바람직하게는, 상기 입력 시퀀스에 기초하여, 상기 프로세싱 모듈이, 상기 입력 시퀀스의 첫 번째 심볼을 인코딩하기 전의 터보 인코더의 상기 상태가 상기 입력 시퀀스의 마지막 심볼을 인코딩하는 시점의 상기 터보 인코더의 상태와 동일하게 되는 것을 확실하게 할 수 있도록, 심볼이 상기 입력 시퀀스에 덧붙여질 필요 가 없는지를 결정하도록 동작한다.

바람직하게는, 상기 인코더는

상기 프로세싱 모듈에 연결되고, 상기 프로세싱 모듈로 하여금, 상기 입력 시퀀스에 기초하여, 상기 터보 인코더가 상기 입력 시퀀스의 첫 번째 심볼을 인코딩할 때에 상기 상태에 있고, 또한 상기 입력 시퀀스의 마지막 심볼을 인코딩할 때에 상기 상태에 있도록 상기 터보 인코더의 상태를 결정할 수 있게 하는 동작 명령어들을 저장하도록 동작하는 메모리를 더 포함한다.

바람직하게는, 상기 상태는 제1 상태이고,

상기 입력 시퀀스는 제1 입력 시퀀스이며,

상기 최대 하나의 심볼은 제1 최대 하나의 심볼이고,

상기 터보 인코더는, 상기 제1 입력 시퀀스의 첫 번째 심볼을 인코딩하기 전에, 그리고 상기 제1 입력 시퀀스의 마지막 심볼 또는 상기 제1 입력 시퀀스에 덧붙여진 상기 제1 최대 하나의 심볼을 인코딩한 후에, 상기 제1 상태로 되며,

상기 터보 인코더는, 상기 제2 입력 시퀀스의 첫 번째 심볼을 인코딩하기 전에, 그리고 상기 제2 입력 시퀀스의 마지막 심볼 또는 상기 제2 입력 시퀀스에 덧붙여진 상기 제2 최대 하나의 심볼을 인코딩한 후에, 제2 상태로 된다.

바람직하게는, 상기 터보 인코더는 m 개 상태(m은 정수)를 갖는 인코더이고,

최대 하나의 심볼은 상기 터보 인코더가 테일 바이팅을 수행하는 것을 보조하기 위해 상기 입력 시퀀스에 덧붙여진다.

바람직하게는, 상기 터보 인코더는 인터리버를 포함하며,

상기 입력 시퀀스의 모든 심볼들은, 또한 상기 프로세싱 모듈에 의해 필요하다고 결정된 경우에 상기 입력 시퀀스에 덧붙여진 최대 하나의 심볼을 포함하여, 상기 터보 인코더의 상기 인터리버 내에서 인터리빙을 거친다.

바람직하게는, 상기 인코더는 통신 장치 내에 구현되며,

상기 통신 장치는 위성 통신 시스템, 무선 통신 시스템, 유선 통신 시스템 및 광 통신 시스템 중 적어도 하나의 시스템 내에 구현된다.

본 발명의 일 측면에 따르면, 입력 시퀀스를 인코딩할 때에 테일 바이팅을 수행하도록 동작하는 인코더에 있어서,

입력 시퀀스를 수신하고, 상기 입력 시퀀스; 또는 상기 입력 시퀀스 및 그 입력 시퀀스에 덧붙여진 최대 하나의 0의 값을 가진(zero valued) 심볼; 중 어느 한 쪽을 인코딩하도록 동작하는 터보 인코더; 및

상기 입력 시퀀스에 기초하여 상기 터보 디코더의 시작 상태(starting state)를 결정하며, 상기 터보 디코더에 상기 시작 상태를 제공하도록 동작하며, 그럼으로써 상기 입력 시퀀스의 첫 번째 심볼을 인코딩하기 전의 터보 인코더의 시작 상태가, 상기 입력 시퀀스의 마지막 심볼 또는 상기 입력 시퀀스에 덧붙여진 상기 최대 하나의 0의 값을 가진 심볼 중, 어느 하나를 인코딩하는 시점의 상기 터보 인코더의 종료 상태(ending state)와 동일하도록 동작하는 프로세싱 모듈을 포함한다.

바람직하게는, 상기 인코더는 상기 입력 시퀀스를 수신하도록 동작하는 버퍼를 더 포함하며,

상기 버퍼는, 상기 프로세싱 모듈이 상기 인코더의 상기 시작 상태를 결정한 후에 상기 터보 인코더에 상기 입력 시퀀스를 제공하도록 동작하고,

상기 프로세싱 모듈은, 상기 프로세싱 모듈에 의해 필요하다고 결정된 경우에, 상기 버퍼가 상기 터보 인코더에 상기 입력 시퀀스를 제공한 후에, 상기 터보 인코더에 최대 하나의 0의 값을 가지는 심볼을 제공한다.

바람직하게는, 상기 인코더는 통신 장치 내에 구현되며,

본 발명의 일 측면에 따르면, 입력 시퀀스를 인코딩하는 터보 인코더 내에서 테일 바이팅을 수행하는 방법에 있어서,

상기 입력 시퀀스의 첫 번째 심볼을 인코딩하기 전의 터보 인코더의 상태가, 상기 입력 시퀀스의 마지막 심볼 또는 필요에 따라 상기 입력 시퀀스에 덧붙여진 최대 하나의 심볼 중 어느 하나를 인코딩하는 시점의 상기 터보 인코더의 상태와 동일하도록, 터보 인코더의 상태, 그리고 상기 입력 시퀀스에 덧붙여지는 최대 하나의 심볼을 결정하는 단계; 및

상기 터보 인코더가 상기 입력 시퀀스의 첫 번째 심볼을 인코딩하기 전에 상기 상태로 되고, 또한 상기 입력 시퀀스의 마지막 심볼 또는 필요에 따라 상기 입력 시퀀스에 덧붙여진 최대 하나의 심볼 중 어느 하나를 인코딩한 후에도 상기 상태로 되도록, 상기 입력 시퀀스 또는, 필요에 따라 상기 입력 시퀀스 및 상기 최대 하나의 심볼 중 어느 하나에 대해 터보 인코딩을 수행하는 단계를 포함한다.

바람직하게는, 상기 방법은 상기 첫 번째 심볼 및 두 번째 심볼 중 적어도 하나는 오직 하나의 비트만을 포함한다는 점을 포함한다.

바람직하게는, 상기 최대 하나의 심볼은 오직 하나의 비트를 포함하는 0의 값을 갖는 심볼이다.

바람직하게는, 상기 방법은, 상기 프로세싱 모듈에 의해 필요하다고 결정된 경우에 상기 입력 시퀀스에 덧붙여진 최대 하나의 심볼을 포함하여 상기 입력 시퀀스의 모든 심볼들에 대해 인터리빙을 수행한다.

바람직하게는, 상기 방법은 통신 장치 내에서 수행되며,

본 발명에 관한 이러한 장점들 그리고 그 밖의 장점들, 측면들 및 신규한 특징들은 이와 관련하여 예시된 실시예들의 세부사항들과 더불어, 다음의 상세한 설명 및 도면들로부터 더 완벽하게 이해될 수 있을 것이다.

이러한 점에서, 여하한 개수의 정보 비트들을 지원하도록 반복적 컨볼루셔널 인코더에 대해 테일 바이팅을 수행할 수 있는 새로운 수단이 제공된다. 이 새로운 수단의 오버헤드(overhead)는, 입력 시퀀스에 덧붙여지는 추가 심볼들(또는 비트들)이 전혀 없던가, 또는 상기 입력 시퀀스에 단지 최대 하나의 더미 심볼(또는 비트)이 덧붙여지던가 둘 중 하나이다. 더구나, 그렇게 추가되는 하나의 비트도 또한 인터리빙된다. 이러한 수단을 이용하면, 다른 접근 방식들에 비하여 성능상의 손실이 전혀 없다.

많은 통신 시스템들이 터보 코드를 사용하여 구현되고 있다. 이러한 터보 인코더들 내에서 입력 시퀀스의 인코딩을 수행할 때에, 인코더의 시작 상태(beginning state) 내지 적어도 종료 상태(ending state)가 알려진 상태이라는 점을 확실히 하는 것이 종종 바람직하다.

인코더가 입력 시퀀스의 인코딩이 끝날 시점에 알려진 상태(known state)로 돌아가게 만들 수 있는 수단은 다음과 같이, (1) 2^m 개의 상태들(여기서 m은 정수)을 가지는 구성 컨볼루션 인코더(constituent convolution encoder)에 대해, 상기 터보 인코더의 인터리버(interleaver)의 바깥쪽에 2m 비트들을 더하는 방법과, (2) 공동으로 양도된 미국 특허번호 7,085,985 "Close two constituent trellis of a turbo encoder within the interleaver block" 내에서 제공되는 것과 같은 수단을 포함한다.

어떤 주어진 입력 시퀀스에 대해, 인코더의 처음 상태와 마지막 상태가 모두 동일할 때에, 이를 "테일 바이팅(tail-biting)"이라고 부른다. 또한, 터보 코딩된 신호들의 디코딩에 관하여, 순방향 및 역방향 터보 디코딩 기법들은, 그 터보 코딩된 신호를 생성하는 바로 그 입력 시퀀스를 인코딩할 때의 상기 인코더의 알려진 초기 상태 및 최종 상태들에 의존한다.

어떤 입력 시퀀스에 대한 인코딩의 처음과 끝이 동일한 상태가 되도록 하는 테일 바이팅 터미네이션(tail-biting termination)은 이러한 목적에 부합한다. 본 명세서에서는 어떤 형태로도 터미네이팅 심볼들(terminating symbols)(또는 비트들)을 부가하지 않으면서 인코더의 테일 바이팅 터미네이션을 수행하도록 하는 수단이 제공된다.

일부 접근 방식들은 어떤 특정 입력 시퀀스 블록 크기를 가지는 특정 형태의 터보 코드에 대해 테일 바이팅을 제공할 수 있는데, 이러한 수단들은 테일 바이팅을 지원할 수 있도록 하기 위해 거의 완전히 들어내어 설계하지 않고도 다양한 블록 크기들이 수용될 수 있는 수단들을 제공한다. 달리 말하면, 이러한 수단들은 쉽게 말해 입력 시퀀스 내에 어떤 임의 개수의 정보 비트들을 수용하지는 못하는 것이다.

LTE 인코더들과 같은 몇몇 응용예에서, 연속하는 범위의 정수들 중에서 선택된 임의의 개수의 정보 비트들을 지원하는 것(예를 들어, 개정판 6(Rel.6)은 40부터 5114까지의 크기를 지원한다)은 바람직할 수 있다. R1-062157 [1]에서 지적한 것과 같이, 개정판 6 터보 인코더[2]는 모든 가능한 정보 시퀀스의 1/7에 대해서는 테일 바이팅 상태를 제공할 수 없다.

본 명세서에서, 먼저 모든 터보 코드들이 유사한 문제를 가지고 있음을 보인 다. 모든 가능한 8 상태 터보 코드(8 states turbo codes) 중에서 하나의 테일 바이팅 인코더를 선택하기 위한 상세한 분석이 제공된다. 이후에, 모든 가능한 정보 시퀀스들을 수용할 수 있고, 또한 터보 인코더의 인터리브 블록(interleaved block)을 통과하는, 최대 하나의 추가 심볼(또는 비트)을 가지는 테일 바이팅 터미네이션을 제공할 수 있는 새로운 접근 방식이 제공된다.

UTRA-UTRAN LTE(Long Term Evolution) 및 3GPP SAE(System Architecture Evolution)에 관한 추가적인 정보는 다음의 인터넷 웹 사이트 www.3gpp.org에서 발견될 수 있다.

위 사이트에서 제안된 일 구현예에 있어서, 현재의 채널 코딩은 6 터미네이션 비트들이 부가된 8 상태 터보 코드를 이용하는데, 이들 6 터미네이션 비트들은 그 터보 인코더의 인터리브 블록을 통과하지 않는다. 전송율 손실을 아끼고 성능을 향상시킬 수 있도록, 테일 바이팅 반복적 컨볼루셔널 인코더(tail-biting recursive convolutional encoder)를 터보 인코더의 구성 인코더들로서 이용하는 것이 바람직할 수 있다.

그런데, 이 기술 분야의 많은 기술자들은, 반복적 컨볼루셔널 인코더가 어떤 임의의 개수의 정보 비트들에 대해 테일 바이팅 상태를 가지는 것이 가능하지 않다는 가설에 대해 연구하고 있다.

이러한 점에서, 여하한 개수의 정보 비트들을 지원하도록 반복적 컨볼루셔널 인코더에 대해 테일 바이팅을 수행할 수 있는 새로운 수단이 제공된다. 이 새로운 수단의 오버헤드(overhead)는, 입력 시퀀스에 덧붙여지는 추가 심볼들(또는 비트 들)이 전혀 없던가, 또는 상기 입력 시퀀스에 단지 최대 하나의 더미 심볼(또는 비트)이 덧붙여지던가 둘 중 하나이다. 더구나, 그렇게 추가되는 하나의 비트도 또한 인터리빙된다. 이러한 수단을 이용하면, 다른 접근 방식들에 비하여 성능상의 손실이 전혀 없다.

디지털 통신 시스템들의 목표는 디지털 데이터를 어느 한 장소 또는 하부 시스템에서 오류가 전혀 없이 또는 용인될 만큼의 낮은 오류 발생율을 가지고, 다른 장소 또는 하부 시스템으로 전송하는 것이다. 도 1에 나타낸 것과 같이, 데이터는 매우 다양한 통신 시스템들 내에서 다양한 통신 채널들, 즉 자기 매체(magnetic media), 유선, 무선, 광섬유, 구리선이나 물론 그 밖의 다른 형태의 매체들을 거쳐 전송될 수 있다.

도 1은 통신 시스템(100)의 일 실시예를 예시한 것이다.

도 1을 참조하면, 이 실시예의 통신 시스템(100)은 통신 채널(199)로서, 상기 통신 채널(199)의 한쪽 끝에 위치하게 된 한 통신 장치(110)(인코더(114)를 가지는 송신기(112)와, 디코더(118)를 가지는 수신기(116)를 포함함)를, 상기 통신 채널(199)의 다른 쪽 끝에 위치하게 된 다른 통신 장치(120)(인코더(128)를 가지는 송신기(126)와, 디코더(124)를 가지는 수신기(122)를 포함함)에 통신가능하도록 결합시킨다. 어떤 실시예에서는, 상기 통신 장치들(110, 120)의 각각은 단지 한 송신기 또는 한 수신기만을 포함할 수 있다. 상기 통신 채널(199)을 구현할 수 있는 매체에는 다양한 서로 다른 종류들(예를 들어, 위성 접시들(132, 134)을 이용하는 위성 통신 채널(130), 통신탑들(142, 144)과 지역 안테나들(152, 154)을 이용하는 무 선 통신 채널(140), 유선 통신 채널(150) 내지 전기 광 인터페이스(electrical to optical(E/O) interface)(162) 및 광 전기 인터페이스(O/E interface)(164)를 이용하는 광섬유 통신 채널(160) 등)이 있다. 추가적으로, 하나 이상의 여러 형태의 매체들이 함께 구현되고, 서로 인터페이싱되어, 통신 채널(199)을 형성할 수도 있다.

통신 시스템 내에서 원치 않게 발생할 수 있는 전송 오류들을 감소시키고자, 오류 정정 구성 및 채널 코딩 구성(error correction and channel coding schemes)이 종종 이용된다. 일반적으로 말해서, 이러한 오류 정정 및 채널 코딩 구성들은 송신기 측에서는 인코더를, 수신기 측에서는 디코더를 사용하도록 만든다.

도 2는 통신 시스템(200)의 다른 실시예를 예시한 것이다. 도 2를 참조하면, 통신 시스템(200)은 통신 채널(299)을 통해 통신 장치(210)가 다른 장치(290)에 연결된다. 상기 통신 장치(210)는 인코더(211)를 포함하는데, 물론 디코더를 포함할 수도 있다.

상기 통신 장치(210)가 상기 통신 채널(299)을 통해 연결된 상기 다른 하나의 장치(290)는 또 하나의 통신 장치(292)일 수도 있고, 저장 매체(294)(예를 들어, 하드디스크 드라이브(hard disk drive, HDD)의 맥락에 속하는 것과 같은), 또는 그 밖의 여하한 형태의, 신호들을 수신하고 송신할 수 있는 장치들이 될 수 있다. 일부 실시예들에서는, 상기 통신 채널(299)은, 제1 시간 동안에는 제1 신호의 송신을 수행하고, 제2 시간 동안에는 제2 신호의 수신을 수행하도록 동작하는 양방향 통신 채널이다. 만약 원한다면, 완전 이중화 통신(full duplex communication)도 또한 채용될 수 있으며, 이 경우에는 상기 통신 장치들(210, 290)의 각각이 서 로에 대해 동시에 송신 및 수신할 수 있다.

상기 통신 장치(210)의 인코더(221)는 터보 인코더(220)와 프로세싱 모듈(230)을 포함한다. 상기 프로세싱 모듈(230)은 또한 메모리(240)와 연결되어 있어, 상기 프로세싱 모듈(230)이 특정 기능들을 수행하도록 활성화시키는 동작 명령어들을 저장한다. 일반적으로 말해서, 특정 입력 시퀀스에 기초하여, 상기 프로세싱 모듈(230)은, 그 입력 시퀀스를 인코딩할 때에, 상기 터보 인코더가 테일 바이팅을 지원할 수 있도록 하려면 어느 상태에서 시작해야하는 지에 대한 결정을 수행하도록 동작한다.

상기 프로세싱 모듈(230)은 회로의 형태로서 엄밀한 의미로 구현될 수 있다는 점을 주목한다. 이와 달리, 상기 프로세싱 모듈(230)이, 마치 디지털 신호 처리장치(digital signal processor, DSP) 내지 유사한 형태의 장치 내에서 이용될 수 있는 것과 같은 소프트웨어의 형태로서 엄밀한 의미로 구현될 수 있다. 또 다른 실시예에서는, 상기 프로세싱 모듈(230)은 물론, 본 발명의 범위 및 사상으로부터 벗어남이 없이, 하드웨어 및 소프트웨어의 조합으로서 구현될 수도 있다.

또 다른 실시예에 있어서, 상기 프로세싱 모듈(230)은 공유되는 처리 장치(shared processing device)나, 개별적인 처리 장치들(individual processing devices), 또는 복수의 처리 장치들을 이용하여 구현될 수 있다. 그러한 처리 장치는 마이크로프로세서(microprocessor), 마이크로컨트롤러(microcontroller), 디지털 신호 처리 장치(digital signal processor), 마이크로컴퓨터(microcomputer), 중앙 처리 장치(central processing unit), FPGA(field programmable gate array), PLD(programmable logic device), 상태 머신(state machine), 논리 회로, 아날로그 회로, 디지털 회로, 내지 그 밖에 동작을 지시하는 명령어들에 기초하여 신호들(아날로그 신호 또는 디지털 신호)을 조작할 수 있는 여하한 장치들이 될 수 있다. 상기 프로세싱 모듈(230)은, 상기 프로세싱 모듈(230)로 하여금, 상기 터보 인코더(220)에 의해 테일 바이팅 동작을 확실히 할 수 있도록 입력 시퀀스의 인코딩을 시작할 때에 이용될 적절한 상태를 결정하는 것을 수행하도록 하는, 그러한 동작 명령어들을 저장하도록 동작하는 상기 메모리(240)에 연결될 수 있다.

그러한 메모리(240)는 단일한 메모리 장치 또는 복수의 메모리 장치들일 수 있다. 그러한 메모리 장치는 읽기 전용 메모리(read-only memory), 임의 접근 메모리(random access memory), 휘발성 메모리(volatile memory), 비휘발성 메모리(non-volatile memory), 정적 메모리(static memory), 동적 메모리(dynamic memory), 플래쉬 메모리(flash memory) 및 기타 디지털 정보를 저장할 수 있는 여하한 장치가 될 수 있다. 상기 프로세싱 모듈(230)이 그 기능들 중 하나 또는 그 이상의 기능들을 상태 머신, 아날로그 회로, 디지털 회로 내지 논리 회로를 통해 구현한 경우에, 상기 상응하는 동작에 관한 명령어들을 저장하는 메모리는 상기의 상태 머신, 아날로그 회로, 디지털 회로 내지 논리 회로들로 구성된 회로부와 함께 칩에 내장될 수 있다는 점을 주목한다.

인코더(221) 내에서, 상기 터보 인코더(220)는 입력 시퀀스를 수신하고, (1) 입력 시퀀스를 인코딩하거나, 또는 (2) 상기 입력 시퀀스와 함께, 그 입력 시퀀스에 덧붙여진, 최대 하나의 0의 값을 가진 심볼(또는 비트)을 인코딩하거나 둘 중 하나를 하도록 동작한다.

입력 시퀀스에 기초하여, 상기 프로세싱 모듈(230)은 상기 터보 인코더(220)의 시작 상태를 결정하도록 동작하며, 그러한 시작 상태를 상기 터보 인코더(220)에 제공하도록 동작함으로써, 입력 시퀀스의 첫 심볼을 인코딩하기에 전인 상기 터보 인코더(220)의 시작 상태는, 그 입력 시퀀스의 마지막 심볼 또는 그 입력 시퀀스에 덧붙여진 최대 하나의 0의 값을 가진 심볼 중에서 어느 하나를 인코딩하는 시점인 상기 터보 인코더의 종료 상태와 동일하게 된다.

도 3 및 도 4는 터보 인코딩을 수행하는 통신 장치들(300, 400)의 실시예들을 예시한 것들이다.

도 3을 참조하면, 상기 통신 장치(300)는 터보 코드를 이용하여 입력 시퀀스를 인코딩할 때에 테일 바이팅을 수행하도록 동작하는 인코더를 포함한다. 상기 통신 장치(300)는 버퍼(310), 프로세싱 모듈(3300, 터보 인코더(320)를 포함하며, 또한 메모리(340) 및 펑처링 모듈(puncturing module)(350)을 포함할 수 있다.

상기 버퍼(310)는 인코딩될 입력 시퀀스를 수신하도록 동작한다. 상기 터보 인코더(320)는 상기 버퍼(310)로부터 입력 시퀀스를 수신하고, 그 입력 시퀀스를 인코딩하도록 동작한다. 입력 시퀀스에 기초하여, 상기 프로세싱 모듈(330)은, 터보 인코더(320)의 상태와 상기 입력 시퀀스에 덧붙여질 최대 하나의 심볼을 결정하여, 그럼으로써, 상기 입력 시퀀스의 맨 처음 심볼을 인코딩하기 전의 상기 터보 인코더(320)의 상태가, 상기 입력 시퀀스의 최종 심볼을 인코딩하는 시점 또는 그 입력 시퀀스에 덧붙여진 최대 하나의 심볼을 인코딩하는 시점의 터보 인코더의 상 태와 동일해지도록 동작한다. 다른 말로 하면, 상기 터보 인코더(320)는 버퍼(310)로부터 입력 시퀀스를 수신하고, (1) 참조 번호(301)이라고 지시된 입력 시퀀스, 또는 (2) 참조 번호(302)로 지시된, 상기 입력 시퀀스와, 그 입력 시퀀스에 덧붙여지는 최대 하나의 0의 값을 가지는 심볼(또는 비트)을 더한 것 중의 어느 하나를 인코딩하도록 동작한다. 최대 하나의 0의 값을 가지는 심볼(또는 비트)가 입력 시퀀스에 덧붙여질 경우에, 이렇게 "변형된" 입력 시퀀스는 확장 입력 시퀀스(extended input sequence)(302)라고 참조될 수 있다.

상기 버퍼(310)는 프로세싱 모듈이 '상태'를 결정한 후에 상기 터보 인코더(320)에 입력 시퀀스를 제공하도록 동작하며, 이때에, 상기 터보 인코더는, 상기 입력 시퀀스의 첫 번째 심볼을 인코딩하기 전과, 상기 입력 시퀀스의 마지막 심볼 또는 그 입력 시퀀스에 덧붙여진 최대 하나의 심볼을 인코딩한 후에, 상기 프로세싱 모듈에 의해 결정된 '상태'로 된다. 만약 원한다면, 상기 펑처링 모듈(350)은 상기 터보 인코더(303)로부터 출력되는 인코딩된 시퀀스로부터 하나 또는 그 이상의 비트들을 펑처링하도록 동작한다.

도 4를 참조하면, 상기 통신 장치(400)는, 제1 구성 인코더(411) 및 제2 구성 인코더(412), 인터리버 (π)(410) 및 펑처링 모듈(450)을 포함하는 터보 인코딩 구성을 채택한 것이다. 만약 u₀, u₁,...,u_k _-1을 터보 코드의 상기 인코더들 중 하나(예를 들어 제1 구성 인코더(411))에 인가되는 입력 시퀀스(u(401)으로 참조됨)라 한다면, S₀, S₁, ..., S_k는 각각 상응하는 상태 시퀀스(states sequence)이다. 상기 인코딩은 이러한 주어진 정보 시퀀스에 대해, 오직 만약 S₀=S_k인 경우에만, 테일 바이팅(또는 순환(circular))이라고 할 수 있다.

상기 입력 시퀀스(401)는 상기 제1 구성 인코더(411)로, 그리고 상기 인터리버(π)(410)로 제공된다. 상기 제1 구성 인코더(411)의 출력은 c1(421)으로 나타낸다. 상기 인터리버(π)(410)의 출력은 이어서 상기 제2 구성 인코더(412)로 제공되며, 상기 제2 구성 인코더(412)의 출력은 c2(422)로 표시되어 있다. c1(421) 및 c2(422) 각각은 상기 펑처링 모듈(431)로 제공되며, 상기 펑처링 모듈(431)에서는 어느 비트도 펑처링되지 않거나 또는 c1(421) 및 c2(422) 중에서 하나 또는 그 이상의 비트들이 펑처링되며, 출력들인 c'1(431) 및 c'2(432)를 생성한다. 정보 비트들은, 도면의 윗 부분에 u(401)로 나타나 있는데, 마찬가지로 상기 통신 장치(400)로부터 제공되는 출력으로서 이용될 수 있다.

도 5는 다양한 방식의 터보 코딩 사이의 성능 비교(500)를 예시한 것이다. 이러한 설명에 있어서, 이 성능 도표는 측정된 BER(Bit Error Rate) 대 E_b/N_o (비트당 에너지 E_b와 스펙트럼 잡음 농도(Spectral Noise Density) N_o의 비)라는 맥락에서 설명된다. 몇몇 다른 통신 시스템 응용 분야에서는, 성능은 BER 대 E_b/N_o의 관점에서 바라볼 수 있다. 이 용어 E_b/N_o는 디지털 통신 시스템의 경우에 대한 신호대 잡음비(SNR)를 측정한 것이다. 이러한 성능 곡선들을 보면, BER이 어떤 주어진 E_b/N_o(또는 SNR)에 대해 결정될 수 있고, 그럼으로써 디코딩 방식의 성능에 대해 상 대적으로 간결하게 제시할 수 있다.

도 5에 나타난 성능 곡선은 참고 문헌[3]에서 인용한 것으로, 테일 바이팅 인코딩을 사용하는 경우의 장점을 나타낸다. 몇몇 서로 다른 방식의 코딩이 이 도표에 나타나 있는데, 이 도표는 전달 함수 제한(transfer function bound)(참조 번호 510), 코딩되지 않은 BPSK(Binary Phase Shift Keying)(참조 번호 511), 코딩된 BPSK(3 개의 코딩된 BPSK 성능 곡선들을 묶은 참조 번호 513), VA(Viterbi Algorithm) 디코더로서 시작 상태와 종료 상태들을 알 수 없는 경우(참조 번호 501), VA 디코더로서 인코더들을 터미네이팅하기 위해 6 비트를 이용하는 경우(예를 들어 2 개의 구성 인코더들 각각에 3 비트씩)(참조 번호 502), VA BCJR(Bahl-Cocke-Jelinek-Raviv) 알고리즘 3(참조 번호 504) 및 테일 바이팅 VA 디코더(503)을 포함한다.

도 6은 터보 인코더 내에서 구현될 수 있는 Rel.6 방식의 제1 구성 인코더 (600)이다.

컨볼루셔널 인코더를 상태 공간에서 표현한다는 것의 정의는 본 명세서에서는 참고 문헌[4-6]에서 설명된 바와 같은 것으로서 채택된다. 테일 바이팅 최소 인코더의 필요 충분 조건을 이렇게 표현한 것을 이용한, 새로운 방법이 여하한 임의의 크기를 가지는 정보 시퀀스를 수용할 수 있도록 제공된다.

비율이 k₀/n₀이고 차수 m인 컨볼루셔널 인코더를 고려하여, 입력 시퀀스가 다음과 같다고 하면,

, 이때

이고, 출력 시퀀스 는

, 이때,

이다.

더 나아가,

를 시간 t의 인코딩 상태라고 하자. 그러면, 다음 수학식 1을 만족하는, 상기 인코더에 관한 상태 공간 표현이라고 불리는 m×m 행렬 A, m×k₀ 행렬 B, k₀×m 행렬 C 및 k₀×n₀ 행렬 D가 존재한다.

그리고,

이다. 이 컨볼루셔널 인코더의 생성 행렬은 다음 수학식 2와 같다.

< 예제 1 >

도 6에 묘사된 개정판 6(Rel.6) 터보 코드 내의 컨볼루셔널 인코더를 고려해본다. 상기 인코더는 차수가 3이며,

이다. 따라서,

이다.

참고 문헌[7]에서, 주어진 블록 크기를 가지는 어떠한 정보 시퀀스에 대해서도 어떤 인코더가 테일 바이팅일 수 있는 충분 조건이 주어진다. 이후에는, 이러한 조건이, 최소 차수(즉, 상태들의 개수가 더 줄어들 수 없음)를 가지는 인코더에 대해서 필요 조건임을 증명한다.

< 가설 1 >

행렬

가 최소 차수 m을 가지는 컨볼루셔널 인코더를 상태공간에서 표현한 것(state-space realization)이라 하자. 이 인코더는, 만약

이 가역(invertible) 행렬인 경우에, N≥m인 블록 크기를 갖는 어떠한 정보 시퀀스에 대해서도 테일 바이팅이라 할 수 있다.

<증명>

크기가 N의 정보 시퀀스는

이고,

는 상기 주어진 정보 시퀀스에 대한 인코딩의 최종 상태라고 하자. 그렇다면, 수학식 1에 의해, 다음과 같은 식을 얻는다.

따라서, 이 인코더는 오직

인 경우에만, 주어진 시퀀스에 대해 테일 바이팅이 가능하다. 이는 상기 인코딩이, 오직 다음 선 형 방정식들을 가진 시스템에 대해 해가 존재하는 경우에만, 테일 바이팅임을 암시한다.

여기서, I_m은 m x m 이진 단위 행렬(binary identity matrix)이다. 이와 달리, 참고 문헌 [6]에 의해, 차수 m은 m 개의 행렬

가 선형 독립적(linear independent)인 경우에만 최소이다. 이는 크기가 N인 모든 가능한 입력 시퀀스에 대해 N≥m일 때에

가 전 공간 {0,1}^m 상에서 계산될 수 있음을 의미한다. 이는 수학식 3이, 오직

이 가역인 경우에만, 모든 가능한 정보 시퀀스들에 대해 해를 가질 수 있음을 의미한다.

< 터보 코드에 대한 테일 바이팅 상태들의 부존재 >

< 가설 2 >

최소 차수의 구성 인코더들을 가지는 어떤 주어진 터보 인코더 E에 대해, 그 크기가 tP(t>0)인 어떤 정보 시퀀스들에 대해 E가 테일 바이팅 터미네이션을 할 수 없는 양의 정수 P가 존재한다.

< 증명 >

를 2^m개의 상태들을 가지는 주어진 터보 코드의 컨볼루셔널 인코더들 중 하나에 대한 상태 공간 표현이라고 하자. 한정된 개수의 m x m 이진 행렬들이 존재하기 때문에,

인 2 개의 양의 정수들 u 및 v가 존재한다. u < v라고 가정하자. 그러면,

이다. 만약 P=v-u라고 한다면, 다음 경우를 얻을 수 있다.

a)

및

은 모두 비가역적이다.

b)

는 가역적이지만,

(즉, 비가역적)이다.

c)

는 가역적이지만,

이다.

이때 c)는

가 다항식 행렬(참고 문헌[8])이라는 것을 의미한다. 따라서, 상기 인코더는 반복적일 수 없다(non-recursive). 이는 터보 코드(참고 문헌[9])의 정의와 모순된다.

따라서,

는 비가역적이어야 한다. 더 나아가, 어떤 정수 t>0에 대해서,

가 가역적이라고 가정한다. 그러면,

인 m x m 행렬 V가 존재한다.

이는 즉

가 가역적이라는 것으로, 앞서의 결론과 모순된다. 따라서,

도 또한 비가역적이다. 즉, 가설 1에 의해, 상기 터보 인코더는 크기가 tP인 일부 정보 시퀀스에 대해서는 테일 바이팅 터미네이션을 제공할 수 없다.

가설 2에 따라, 테일 바이팅을 목적으로 다른 터보 코드를 선택할 필요가 없다.

< 8 상태 (m=3) 터보 코드 >

이 장에서는, 터보 코드를 위한 차수가 3인 모든 가능한 컨볼루셔널 인코더들을 조사하고, 어떤 것이 테일 바이팅에 가장 최적인 것인 지를 찾아보도록 하겠다. 두 m x m 행렬들의 유사도에 대한 정의를 다시 상기한다면, 두 m x m 행렬 A₁ 및 A₂은

인 가역 행렬 S가 존재할 때 서로 유사하다고 할 수 있다. 상태 공간 표현 (A,B,C,D)를 가지는 코드와

가 동일한 인코더 행렬 G(x)를 갖는다(참고 문헌[10])는 점은 쉽게 증명된다. 모든 3x3 이진 행렬들의 집합은 몇몇 그룹들로 나뉘어질 수 있고, 각각의 그룹들은 모두 유사한 행렬들을 포함한다. 이들 그룹들은 또한 3 개의 큰 카테고리들로 분할될 수 있는데, (1) 멱영 (nilpotent) 행렬을 가지는 카테고리, (2) 비가역적이고 또한 멱영인 행렬들의 카테고리, (3) 가역적인 행렬들의 카테고리이다. 실제로는 14 개의 그룹들이 있다. 따라서, 각 그룹들을 대표할 수 있는 14 개의 행렬들만 고려한다.

(1) 멱영 행렬(3 개의 대표 행렬들이 있음)

명백하게, 이들 행렬들은 반복적(recursive)이지 않으며, 터보 코드의 구성 인코더로 고려될 수 없다.

(2) 비가역적 및 비 멱영 행렬(5 개의 대표 행렬들)

이들 네 개의 상태 행렬들을 가지는 인코더는 불연속(disconnected)적인 메모리를 제공하게 된다. 불연속적인 메모리를 가지는 인코더는 터보 코드에 의해 요구되는 최적의 d₂를 줄 수 없다(참고 문헌[10]).

이 비가역적이기 때문에, 가설 1에 따르면 상기 인코더 (A,B,C,D) 는 최소 차수가 아니거나, 또는 일부 정보 시퀀스들에 대해서는 테일 바이팅이지 못하거나 둘 중 하나이다. 예를 들어, a) B=[1 1 1]^T라 하면,

이고, 또한

이다. 그렇다면, 수학식 3은 크기가 2 이상인 상당 수의 정보 시퀀스들에 대해 해를 가지지 못한다. b) B=[1 1 0]^T라 하면, 상기 인코더는 다음과 같이

및

인, 차수 2의 인코더 (A',B',C',D')로 감소될 수 있다.

(3) 가역적(6 개의 대표 행렬들)

A₉=I₃은 불연속적인 메모리를 갖는 인코더를 제공한다.

이러한 행렬들을 가지는 인코더들은 불연속적인 메모리를 갖는다.

개정판 6의 터보 코드는 A₁₃을 상태 행렬로 하는 컨볼루셔널 인코더를 이용한다. 추가적으로 다음과 같다.

도 7은 이중 바이너리 터보 인코더(duo-binary turbo encoder)(700)의 실시예를 예시한 것이다. 이중 바이너리 터보 코드(참고 문헌[11])는 A₁₄를 상기 이중 바이너리 터보 인코더(700) 내에 나타낸 구성 인코더로서 이용한다.

추가적으로, 다음과 같다.

더 나아가, 다음 가정을 할 수 있다.

< 가정 1 >

A=A₁₃ 또는 A₁₄라고 하자. 그렇다면 어떤 양의 정수 n=7q+i, 0≤i≤6에 대해,

이며, 가정 1을 다음과 같이 확장할 수 있다.

< 가정 2 >

m=2,3,4,5,6이라고 하자.

인 m x m 이진 행렬 A가 존재한다. 더 나아가, 어떤 그러한 행렬 A 및 어떤 양의 정수

,

에 대해,

이다.

< 임의의 정보 길이를 가지는 경우의 새로운 테일 바이팅 터미네이션 방법 >

< 임의의 개수의 정보 심볼들에 대한 제안된 테일 바이팅 터미네이션 >

테일 바이팅을 수행하는 새로운 접근 방법은 가정 1에 기초한 것이다. 다음에서는 m=3인 경우의 방법만을 제시하고자 하는데, 이는 거의 확실히 3GPP LTE는 8 상태 터보 코드를 채용할 것이기 때문이다. m=2나, m>3인 경우에도, 방법은 유사하다.

(A,B,C,D)를 8 상태 컨볼루셔널 인코더의 상태 공간 표현이라고 하며, 상기 인코더는 앞 장에서 나열한 바와 같은 A₁₃ 또는 A₁₄ 중 어느 하나와 유사한 A를 가진다.

(1) 다음에 예시한 상태들을 i=1,2,3,4,5,6에 대해 사전 계산(pre-compute)한다.

(2) 상기 42 인덱스-상태(index-state) 쌍들을 룩업 테이블(look up table)

로서 사전 저장(pre-store)한다. 이때 b=1,2,3,4,5,6,7이고,

는 b의 3 비트 이진 표현이다. 더 나아가,

상태라고 하자.

(3) 정보 블록 크기가 k인 테일 바이팅 인코딩 기법이다.

를 정보 심볼들(비트들)이라고 하자.

(a)

라 한다. 만약 m=0이면,

인 심볼 하나를 더

덧붙이며, N=k+1 및 M=1로 한다. 그렇지 않다면 N=k 및 M=m으로 한다.

(b)

상태를 가지고서 정보 심볼들

을 인코딩하여

최종 상태

를 찾아낸다(인코딩된 심볼들은 저장하지 않는다). 이어서

룩업 테이블을 이용하여 초기 상태

를 찾는다.

몇몇 실시예에서는, 원할 경우

는 0으로 선택될 수 있다.

(c)

를 초기 상태로 이용하여

를 인코딩한다.

여기에서 제공되는 새로운 테일 바이팅 터미네이션 방식은 종전의 방식들에 비해 상당한 성능 향상을 제공한다. 이러한 새로운 수단은 다른 수단보다 훨씬 더 큰 유연성을 제공한다. 예를 들어, 어떠한 블록 크기 및 어떠한 크기를 가지는 입력 시퀀스도(즉, 그 입력 시퀀스 내에 여하한 개수의 정보 심볼들 내지 비트들이 있더라도) 여기서 제공되는 테일 바이팅 터미네이션 방식의 이점을 활용할 수 있 다. 또한, 본 명세서에서 제공되는 이러한 새로운 방식은 다른 접근 방식들에 비해 더 적은 오버헤드를 가진다. 최대 1 심볼(또는 1 비트)의 오버헤드가 필요할 수 있다. 대부분의 경우에는, 테일 바이팅 터미네이션을 보장하는 데에 추가적인 심볼들(또는 비트들)이 전혀 필요없기 때문에, 오버헤드도 전혀 발생하지 않는다. 또, 본 명세서에서 제공되는 이러한 새로운 수단은, 3GPP Rel.6 터보 코드들 및 그 밖의 터보 코드들에서 사용되는 것과 같은 2^m(즉, 2^m)개의 상태를 가지는 컨볼루셔널 코드를 위해서 2m 개의 오버헤드 터미네이션 심볼들(또는 비트들)을 단순히 추가하는 다른 방식들에 비해, 상대적으로 나은 처리 능력/데이터 전송율을 가진다. 2m 개의 오버헤드 터미네이션 심볼들(또는 비트들)을 단순히 추가하는 방식은 처리 능력 및 데이터 전송율을 감소시킨다. 본 명세서에서 개시하는 새로운 방식은 또한 다른 방식들에 비해 상대적으로 나은 성능을 가진다. 본 명세서에서 개시하는 새로운 방식에서는, 모든 비트들(입력 시퀀스에 덧붙여지는 상기 최대 하나의 심볼(또는 비트)를 포함하여)이 터보 인코딩 시에 인터리빙된다. 2m 개의 오버헤드 터미네이션 심볼들 또는 비트들을 이용하는(예를 들어, 8 상태 인코더에서는 6 터미네이션 심볼들 내지 비트들이 요구되며, 각 구성 인코더들의 각각에 대해 36 터미네이션 심볼들 내지 비트들이 요구됨) 방식들과 같은 그 밖의 방식들에 비교하면, 그러한 2m 오버헤드 터미네이션 심볼들 또는 비트들은 인터리빙되지 않는다. 본 명세서에서 개시하는 새로운 방식에서는, 입력 시퀀스의 모든 심볼들 내지 비트들(입력 시퀀스에 덧붙여지는 상기 최대 하나의 심볼(또는 비트)를 포함하여)은 인터리빙을 거친다.

위에서, 이전의 어떠한 종래 기술도 모든 구성 인코더들(예를 들어 터보 인코더 내에 이용되는 것들과 같은)에 대해, 모든 정보 시퀀스 크기에 대해서, 완전한 테일 바이팅 동작을 제공하지 못했다.

본 명세서에서는, 터보 인코더에 제공될 수 있는 모든 가능한 크기의 입력 시퀀스들에 대해, 테일 바이팅 터미네이션을 가능하게 하는 새로운 방식이 제시된다. 일 예를 들면, 이 방식은 3GPP LTE 터보 코딩에서 쓰일 수 있는 모든 입력 시퀀스 크기에 대해 적용될 수 있다. 또한, 테일 바이팅 기능을 달성하기 위해서, 단지 최대 하나의 오버헤드 심볼 또는 비트만이 입력 시퀀스에 덧붙여져야 할 수 있다. 다른 종래 기술의 방식들은, 그 구성 인코더들이 2^m(즉, 2^m) 상태들을 가지는 터보 인코더를 이용하여 동작할 경우, 적어도 2m 심볼들 또는 비트들이 필요하다.

일 실시예에 있어서, 3GPP LTE 터보 코딩을 고려하면, 본 명세서에서 제공하는 새로운 수단에 따라, 모든 가능한 입력 시퀀스 크기들 중의 1/7에 대해, 최대 하나의 더미 심볼 또는 비트가 추가된다. 상기 응용 분야(3GPP LTE 터보 코딩)에 있어서, 나머지 6/7의 입력 시퀀스 크기들에 대해서는, 추가되어야 하는 별도의 심볼 또는 비트가 전혀 없다(즉, 덧붙이는 것이 전혀 없다). 이러한 새로운 방식은 어떤 임의의 크기의 정보 시퀀스 블록 크기를 포함하는 입력 시퀀스들에 대해 테일 바이팅 터미네이션이 가능하게 한다. 본 명세서에서 제공되는 새로운 테일 바이팅 방식은, 그 입력 시퀀스 내에 임의의 정보 비트들을 지원하는 터보 코딩 시스템에 대해 이용될 수 있다. 실제로, 본 명세서에서 제공되는 이러한 새로운 방식은 임의의 개수의 정보 비트들을 지원할 수 있는 모든 통신 시스템에 대해 적용될 수 있다. 예를 들어, 3GPP LTE에 적합하도록 설계된 것과 같이, 다양한 크기의 입력 시퀀스 크기들이 지원되어야 하는 터보 코딩은, 어떠한 입력 시퀀스 크기도 수용할 수 있는 이러한 새로운 방식의 능력으로부터 큰 혜택을 받을 수 있다.

더구나, 본 명세서에서 제공되는 새로운 수단은, 터보 인코더의 인터리버 외부에서 터미네이션 동작을 구현하는 그러한 종래 기술의 방식들(즉, 그러한 종래 기술의 방식들에서는, 적어도 2m 심볼들 또는 비트들이 터미네이션을 위해 이용되는데, 이들은 터보 인코더의 인터리버를 통과하지 않는다)에서 나타나는 바람직하지 못한 손실에 비하면, 아무런 성능 상의 손실을 초래하지 않는다.

도 8은 입력 시퀀스를 인코딩하는 터보 인코더 내에서 테일 바이팅을 수행하는 방법(800)에 관한 일 실시예를 예시한 것이다. 블록(810)에서는, 상기 방법(800)은, 입력 시퀀스의 첫 번째 심볼을 인코딩하기 전의 터보 인코더의 상태가, 상기 입력 시퀀스의 마지막 심볼 또는 필요에 따라 상기 입력 시퀀스에 덧붙여진 최대 하나의 심볼 중 어느 하나를 인코딩하는 시점의 상기 터보 인코더의 상태와 동일하도록, 터보 인코더의 상태와, 상기 입력 시퀀스에 덧붙여지는 최대 하나의 심볼을 결정하는 단계로부터 시작한다. 이후에, 블록(820)에 나타낸 바와 같이, 상기 방법(800)은, 상기 터보 인코더가 상기 입력 시퀀스의 첫 번째 심볼을 인코딩하기 전에 상기 상태로 되고, 또한 상기 입력 시퀀스의 마지막 심볼 또는 필요에 따라 상기 입력 시퀀스에 덧붙여진 최대 하나의 심볼 중 어느 하나를 인코딩한 후에 도 상기 상태로 되도록, 상기 입력 시퀀스 또는, 필요에 따라 상기 입력 시퀀스에 상기 최대 하나의 심볼을 부가한 것 중 어느 하나에 대해 터보 인코딩을 수행하는 단계로 이어진다.

본 발명은 지금까지 특정된 기능들의 수행 및 이들 사이의 관계들을 예시한 방법 단계들을 이용하여 위와 같이 설명되었다. 이러한 기능적인 구성 블록들 및 방법 단계들의 경계 및 순서(boundaries and sequences)는 설명의 편의를 위해 임의적으로 설명되었다. 이러한 특정 기능들 및 이들 사이의 관계들이 적절하게 수행되는 한, 그와 다른 경계 및 순서도 정의될 수 있다. 그러한 어떠한 다른 경계 또는 순서들도 청구 범위에 기재된 발명의 영역 및 사상 내에 포함된다.

본 발명은 또한 몇몇 중요 기능들의 수행을 예시한 기능적인 구성 블록들을 이용하여 위와 같이 설명되었다. 이러한 구성 블록들의 경계는 설명의 편의를 위해 임의적으로 정의되었다. 상기 중요 기능들이 적절히 수행되는 한, 이와 다른 경계도 정의될 수 있다. 유사하게, 순서도의 블록들도 역시 중요한 기능(functionality)을 예시하기 위해 정의되었다. 순서도 블록의 경계들 및 순서는 다른 식으로 정의되었어도 여전히 그러한 중요한 기능을 수행할 수 있을 것이다. 기능적인 구성 블록들과 순서도 블록들 및 순서들에 대한 그러한 다른 식의 정의들은 따라서 청구 범위에 기재된 발명의 영역 및 사상 내에 포함된다.

당해 기술 분야의 통상의 기술을 가진 자는 또한 이러한 기능적 구성 블록들 및 이 명세서에 있는 그 밖의 예시적인 블록들, 모듈 및 구성품은, 예시된 대로 구현되거나, 또는 개별 부품, 주문형 집적 회로(application specific integrate circuits, ASIC), 적절한 소프트웨어나 이와 유사한 것을 실행하는 프로세서들, 또는 이들의 조합들에 의해 구현될 수 있다.

더 나아가, 비록 상술한 실시예를 이용하여 간단 명료함 및 이해를 목적으로 상세하게 설명하였지만, 본 발명은 이러한 실시예들에 한정되지 않는다. 본 발명의 사상과 범위가 첨부된 청구 범위의 기재에 의해서만 제한되는 바대로, 당해 기술 분야의 동상의 지식을 가진 자에게 본 발명의 사상과 범위 내에서 다양한 변화와 변경이 실시될 수 있음은 명백할 것이다.

[참고 문헌들(References)]

[1] System immpact of Rel'6 turbo coding tail-bits removal, R1-062157.

[2] 3GPP TS 25.212 V6.8.0 (2006-06), 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Multiplexing and channel coding (FDD)(Release 6)

[3] John B. Anderson and Stephen M. Hladik, "Tailbiting MAP Decoders," IEEE Journal on Selected Areas in Communications, Vol. 16, No. 2, Feburary 1998, pp.297-302.

[4] J.L. Massey and M.K. Sain, "Codes, automata, and continuous systems: Explicit interconnections," IEEE Trans . Automat . Contr ., vol. AC-12, no. 6, pp. 644-650, 1967.

[5] Robert J. McEliece. The Algebraic Theory of Convolutional Codes. In Handbook of Coding Theory, R. Brualdi, W.C. Human and V. Pless (eds.). Elsevier Science Publishers, Amsterdam, The Netherlands, 1998.

[6] J. Rosenthal, and E. V. York, "BCH Convolutional Codes," IEEE Transactions on Information Theory, Vol.45, No.6, PP.1833-1842, Sept. 1999.

[7] C. Weiβ, C. Bettstetter and S. Riedel, "Code Construction and Decoding of Parallel Concatenated Tail-Biting Codes," IEEE Transactions on Information Theory, Vol.47, No. 1, pp. 366-386, Jan. 2001.

[8] H. Gluesing-Luerssen and G. Schneider, "State space realizations and monomial equivalence for convolutional codes," arXiv : cs . IT /0603049, Mar. 2006.

[9] Claude Berrou, Alain Glavieux, and Punya Thitimajshima, "Near Shannon limit error-correcting coding and decoding: turbo codes", Proc , of IEEE ICC '93, Geneva, May 1993, pp.1064-1070.

[10] C. Fragouli and R. Wesel, "Turbo-Encoder Design for Symbol-Interleaved Parallel Concatenated Trellis-Coded Modulation," IEEE Transactions on Communcations, Vol. 49, No. 3, pp.425-435, March 2001.

[11] Duo-Binary Turbo Codes for Evolved UTRA, 3 GPP TSG RAN WG1 #46, R1 -061973.

도 1은 통신 시스템의 일 실시예를 예시한 것이다.

도 2는 통신 시스템의 다른 실시예를 예시한 것이다.

도 3 및 도 4는 터보 인코딩을 수행하는 통신 장치들의 실시예들을 예시한 것들이다.

도 5는 다양한 방식의 터보 코딩 사이의 성능 비교를 예시한 것이다.

도 6은 터보 인코더 내에서 구현될 수 있는 Rel.6 방식의 제1 구성 인코더이다.

도 7은 이중 바이너리 터보 인코더(duo-binary turbo encoder)의 실시예를 예시한 것이다.

도 8은 입력 시퀀스를 인코딩하는 터보 인코더 내에서 테일 바이팅을 수행하는 방법에 관한 일 실시예를 예시한 것이다.

Claims

입력 시퀀스(input sequence)를 인코딩할 때에 테일 바이팅(tail-biting)을 수행하도록 동작하는 인코더에 있어서,

상기 입력 시퀀스를 수신하도록 동작하는 버퍼;

상기 버퍼로부터 상기 입력 시퀀스를 수신하고 상기 입력 시퀀스를 인코딩하도록 동작하는 터보 인코더(turbo-encoder); 및

상기 입력 시퀀스의 첫 번째 심볼을 인코딩하기 전의 터보 인코더의 상태(state)가, 상기 입력 시퀀스의 마지막 심볼(symbol) 또는 상기 입력 시퀀스의 마지막 심볼에 덧붙여진 최대 하나의 심볼 중 어느 하나를 인코딩하는 시점의 상기 터보 인코더의 상태와 동일하도록, 터보 인코더의 상기 상태와, 상기 입력 시퀀스의 마지막 심볼에 덧붙여지는 최대 하나의 심볼을 상기 입력 시퀀스에 기초하여 결정하도록 동작하는 프로세싱 모듈(processing module)을 포함하며,

상기 버퍼는 상기 프로세싱 모듈이 상기 상태를 결정하면, 상기 터보 인코더에 상기 입력 시퀀스를 제공하도록 동작하며,

상기 터보 인코더는, 상기 입력 시퀀스의 첫 번째 심볼을 인코딩하기 이전과, 상기 입력 시퀀스의 마지막 심볼 또는 상기 입력 시퀀스의 마지막 심볼에 덧붙여진 최대 하나의 심볼 중 어느 하나를 인코딩한 이후에, 상기 프로세싱 모듈에 의해 결정된 상기 상태로 되는 것을 특징으로 하는 인코더.
청구항 1에 있어서, 상기 첫 번째 심볼 및 두 번째 심볼 중 적어도 하나는 오직 하나의 비트만을 포함하는 것을 특징으로 하는 인코더.
청구항 1에 있어서, 상기 프로세싱 모듈은 상기 버퍼가 상기 입력 시퀀스를 상기 터보 인코더에 제공한 후에, 상기 입력 시퀀스의 마지막 심볼에 덧붙여지는 최대 하나의 심볼을 상기 터보 인코더로 제공하도록 동작하는 것을 특징으로 하는 인코더.
청구항 1에 있어서, 상기 터보 인코더로부터 출력되는 인코딩된 시퀀스 내의 적어도 한 비트에 대해 펑처링(puncture)하도록 동작하는 펑처링 모듈(puncturing module)을 더 포함하는 것을 특징으로 하는 인코더.
청구항 1에 있어서, 상기 입력 시퀀스에 기초하여, 상기 프로세싱 모듈이, 상기 입력 시퀀스의 첫 번째 심볼을 인코딩하기 전의 터보 인코더의 상기 상태가 상기 입력 시퀀스의 마지막 심볼, 또는 상기 입력 시퀀스의 마지막 심볼에 덧붙여진 최대 하나의 심볼을 인코딩하는 시점의 상기 터보 인코더의 상태와 동일하게 되는 것을 확실하게 할 수 있도록, 상기 최대 하나의 심볼이 상기 입력 시퀀스의 마지막 심볼에 덧붙여질 필요가 없는 지를 결정하도록 동작하는 것을 특징으로 하는 인코더.
입력 시퀀스(input sequence)를 인코딩할 때에 테일 바이팅(tail-biting)을 수행하도록 동작하는 인코더에 있어서,

입력 시퀀스를 수신하고, 상기 입력 시퀀스; 또는 상기 입력 시퀀스 및 상기 입력 시퀀스의 마지막 심볼에 덧붙여진 최대 하나의 0의 값을 가진(zero valued) 심볼; 중 어느 한 쪽을 인코딩하도록 동작하는 터보 인코더; 및

상기 입력 시퀀스에 기초하여 상기 터보 디코더의 시작 상태(starting state)를 결정하며, 상기 터보 디코더에 상기 시작 상태를 제공하도록 동작하며, 그럼으로써 상기 입력 시퀀스의 첫 번째 심볼을 인코딩하기 전의 터보 인코더의 시작 상태가, 상기 입력 시퀀스의 마지막 심볼 또는 상기 입력 시퀀스의 마지막 심볼에 덧붙여진 상기 최대 하나의 0의 값을 가진 심볼 중, 어느 하나를 인코딩하는 시점의 상기 터보 인코더의 종료 상태(ending state)와 동일하도록 동작하는 프로세싱 모듈을 포함하는 인코더.
청구항 6에 있어서, 상기 첫 번째 심볼 및 두 번째 심볼 중 적어도 하나는 오직 하나의 비트만을 포함하는 것을 특징으로 하는 인코더.
청구항 6에 있어서, 상기 입력 시퀀스를 수신하도록 동작하는 버퍼를 더 포함하며,

상기 버퍼는, 상기 프로세싱 모듈이 상기 인코더의 상기 시작 상태를 결정한 후에 상기 터보 인코더에 상기 입력 시퀀스를 제공하도록 동작하며,

상기 프로세싱 모듈은, 상기 프로세싱 모듈에 의해 필요하다고 결정된 경우에, 상기 버퍼가 상기 터보 인코더에 상기 입력 시퀀스를 제공한 후에, 상기 터보 인코더에 최대 하나의 0의 값을 가지는 심볼을 제공하는 것을 특징으로 하는 인코 더.
입력 시퀀스를 인코딩하는 터보 인코더 내에서 테일 바이팅을 수행하는 방법에 있어서,

상기 입력 시퀀스의 첫 번째 심볼을 인코딩하기 전의 상기 터보 인코더의 상태가, 상기 입력 시퀀스의 마지막 심볼, 또는 상기 입력 시퀀스의 마지막 심볼이 상기 입력 시퀀스의 첫 번째 심볼과 동일하지 않을 경우 상기 입력 시퀀스의 마지막 심볼에 덧붙여진 최대 하나의 심볼 중 어느 하나를 인코딩하는 시점의 상기 터보 인코더의 상태와 동일하도록, 상기 터보 인코더의 상태와, 상기 입력 시퀀스의 마지막 심볼에 덧붙여지는 최대 하나의 심볼을 결정하는 단계; 및

상기 터보 인코더가 상기 입력 시퀀스의 첫 번째 심볼을 인코딩하기 전에 상기 상태로 되고, 또한 상기 입력 시퀀스의 마지막 심볼, 또는 상기 입력 시퀀스의 마지막 심볼이 상기 입력 시퀀스의 첫 번째 심볼과 동일하지 않을 경우 상기 입력 시퀀스의 마지막 심볼에 덧붙여진 최대 하나의 심볼 중 어느 하나를 인코딩한 후에도 상기 상태로 되도록, 상기 입력 시퀀스의 마지막 심볼 또는, 상기 입력 시퀀스의 마지막 심볼이 상기 입력 시퀀스의 첫 번째 심볼과 동일하지 않을 경우 상기 입력 시퀀스의 마지막 심볼에 상기 최대 하나의 심볼을 덧붙인 것 중 어느 하나에 대해 터보 인코딩을 수행하는 단계를 포함하는 터보 인코더 내 테일 바이팅 수행 방법.
청구항 9에 있어서, 상기 첫 번째 심볼 및 두 번째 심볼 중 적어도 하나는 오직 하나의 비트만을 포함하는 것을 특징으로 하는 터보 인코더 내 테일 바이팅 수행 방법.