KR100414152B1 - 프로그래머블 프로세서에서의 비터비 디코딩 연산방법 및그 연산방법을 실행하기 위한 연산회로 - Google Patents

Abstract

본 발명은 통신용 에러 정정을 위해 널리 사용되고 있는 알고리즘 가운데 하나인 비터비 디코딩(decoding)을 프로그래머블 프로세서에서 효율적으로 처리할 수 있는 비터비 디코딩 연산회로 및 그 연산방법에 관한 것이다.

Description

프로그래머블 프로세서에서의 비터비 디코딩 연산방법 및 그 연산방법을 실행하기 위한 연산회로{The Processing Method and Circuits for Viterbi Decoding Algorithm on Programmable Processors}

본 발명은 통신용 에러 정정을 위해 널리 사용되고 있는 알고리즘 중에 하나인 비터비 디코딩(decoding)을 프로그래머블 프로세서(디지털 신호처리 프로세서, 마이크로프로세서 등)에서 효율적으로 처리할 수 있는 비터비 디코딩 연산방법 및 연산회로에 관한 것이다.

현재까지 통신용 에러를 정정하기 위해 전용 비터비 프로세서를 사용하는 경우가 대부분이지만 전력소모를 줄이고 수정의 용이성을 위해 전용 하드웨어 구조에서 차츰 프로그래머블 프로세서를 이용한 비터비 디코더를 구현해야 할 필요성이 증대되고 있다.

일반적으로 비터비 디코딩 알로리즘 블록의 전체 구성은 수신된 부호어와 인코더의 쉬프트 레지스터 상태에 따라 발생하는 부호어와의 차이를 계산하는 BMC(Branch Metric Calculation) 블록과, BMC 블록으로부터 발생된 BM(Branch Metric) 값에 현재의 상태 값을 더한 뒤 두 값을 비교해 작은 값을 선택하는 ACS(Add and Compare and Select) 블록, 그리고 마지막으로 ACS 블록으로부터 선택된 최소거리를 갖는 경로들을 저장하고 디코딩하는 생존자 경로 메모리 블록 등 크게 3개의 블록으로 구성된다.

상기 BMC 블록은 강/연판정으로 얻어진 데이터로부터 BM 값을 계산한다. 부호율이 1/2인 콘볼루션 코드에서는 생성되는 부호어가 2비트이므로 BM은 모두 4가지 종류가 존재할 수 있고, 이것은 인코더에서 생성되는 코드에 따라 BM00, BM01, BM10, BM11로 구분된다. 강판정 결과에 따른 BM 값들을 표1에 기재하였다.

BM부호어	BM00	BM01	BM10	BM11
00	0	1	1	2
01	1	0	2	1
10	1	2	0	1
11	2	1	1	0

강판정을 사용할 경우에는 입력되는 부호어와 각 BM들의 해밍거리를 계산한다. 연판정의 경우에는 m 비트로 양자화된 입력 데이터와의 유클리드 거리(Euclid distance)를 계산하여 출력한다. 강판정의 경우에는 각 BM들 사이의 최대 차이가 2인 반면에 연판정의 경우에는 최대 14까지 차이가 나게 된다. 따라서 연판정을 사용할 경우 에러 가 발생하더라도 생존자 경로를 잘못 선택할 확률이 적어지므로 강판정에 비해 디코딩 에러 발생확률이 적다.

연판정 비터비 복호기는 수신된 신호에 연판정된 데이터 S1, S2가 BMC연산 블록으로 입력되는 구조를 가진다. 상기 S1, S2가 3비트로 연판정된 데이터라 하면, 각 BM들의 값은 수학식1에 의해 얻어진다. 수학식1은 연판정을 사용할 경우 BM값을 계산하는 방법이다.

여기서, m은 연판정된 비트 수이므로 3이다. 즉, 입력으로 S1이 5(101₂)이고 S2가 2(010₂)라고 가정했을 경우에 각 BM 값은 표2에 기재된 바와 같다.

	BM1	BM2	유클리드 거리
BM00	5	2	7
BM01	5	5	10
BM10	2	2	4
BM11	2	5	7

수학식1에서 알 수 있듯이 S1, S2가 모두 0(000₂)인 경우 최대 차이가 14로 강판정을 사용할 경우보다 BM들 사이의 값 차이가 큰 것을 알 수 있다.

격자도 상에서 각 BM들의 값을 BMC 블록을 통해 계산하였다. 상기 계산된 BM들은 현재 스테이트로 입력되는 경로 중 작은 값을 찾기 위한 ACS 블록에 입력된다. 부호율이 1/2인 코드에서는 하나의 상태에 두 개의 입력 경로가 존재하므로 이전의 PM(Path Metric)과 현재 BM을 더해 작은 값을 갖는 경로 값이 다음 상태의 PM이 된다.

도1은 격자도 상의 상태 천이 관계를 나타낸 버터플라이 구조이다. S는 PM을 계산하기 위한 현재 스테이지까지의 최소 거리(minimum distance)이며, 이것이 저장된 것을 SM(Survivor Memory)이라 한다. 연속적으로 수행되는 한쌍의 버터플라이 구조의 ACS 연산과정을 수식으로 나타내면 수학식2와 같다. 수학식2는 두 개의 값중 작은 값을 선택하는 것을 의미한다.

수학식2의 첫 번째 식을 예로 들면, S₀와 BM_l을 더한 값과 S₁과 BM_h를 더한 값을 비교하여 이 두 값 중 적은 값이 새로운 S₀값이 된다.

구속장의 길이가 K일 때 2^(K-1)개의 상태가 존재하게 되며 그 만큼의 ACS 연산을 필요로 한다. 즉, N은 2^(K-1)가 된다.

도2는 전용 비터비 디코더에서 사용하는 ACS 구조를 나타낸 것이다, 하나의 PE(Processing Element)가 한 상태의 ACS 연산을 수행하므로 이론적으로 총 2^(K-1)개의 PE를 사용하면 PE들 간에 데이터의 상관 관계는 없으므로 모든 상태에 대한 연산을 동시에 할 수 있다. 그러나 실제 DSP 칩이나 전용 ASIC 칩들은 하드웨어 부담이 크므로 여러 개의 PE를 갖지 못하는 것이 실정이다. 각 PE에서는 격자도 상의 상태들 중 하나의 상태를 처리하며 ACS 연산을 수행해 각 상태로 입력되는 현재 경로값들과 누적 경로값들을 더한 값을 비교하여 작은 값을 갖는 경로를 선택한다. 상기 BMC 블록에서 3비트로 입력된 데이터로부터 현재 경로값을 구한다. 구속장K=7일 경우, 한 스테이지에 2^(K-1)개의 상태가 존재하므로 64개의 PE를 사용하면 매 클럭마다 격자도 상의 한 스테이지를 처리할 수 있다. 상기 PE는 상위로부터의 경로값 BM_h와 이전까지의 누적 경로값인 SM_h를 더한 값과 BM_l과 SM_l을 더한 값을 비교한다.

다음에, 도3은 비터비 전용 역추적 방식 생존자 경로 계산 회로의 구조이다. 상기 역추적 방식은 ACS 연산 결과로 얻은 결정 비트들을 디코딩 깊이에 해당하는 만큼 메모리에 저장한 다음 순차적인 방법으로 메모리에 저장되어 있는 값을 읽어내어 현재 상태값으로부터 이전 스테이지의 생존자 경로를 추적해 낸다.

도시된 바와 같이 역추적 회로는 메모리, 멀티플렉서(Multiplexer) 그리고 쉬프트 레지스터로 구성된다. 구속장 K=7인 콘볼루션 인코더를 사용할 경우 메모리에 저장되어 있는 64비트의 데이터 중 현재 상태값으로 임의의 상태를 선택하여 멀티플렉서의 선택 비트로 사용한다. 상기 멀티플렉서 출력으로 선택된 1비트는 쉬프트 레지스터에 입력되어 다음 상태 값 결정을 위한 멀티플렉서의 선택 비트로 사용된다. 역추적을 시작하는 현재 상태 값은 임의로 선택할 수 있지만 쉬프트 레지스터의 초기화와 연관해 보통 0에서 시작하도록 사용된다. 상기와 같은 방법으로 순차적으로 이전 상태를 추적하다가 일정 깊이의 디코딩 깊이를 지나면 복원된 데이터를 얻는다. 디코딩 깊이는 대개 구속장 K의 4~5 배정도 이상이면 안정되고 신뢰도가 높은 비트 오류율을 얻게 된다. 그러나 구속장의 길이가 커질수록 연산 회수가 많아지게 되어 연산속도에 많은 제약을 받게 된다. 즉, 매번 1비트 데이터를 디코딩하기 위해서는 디코딩 깊이에 해당하는 연산을 반복 수행해야 하기 때문이다. 실제로 전용 비터비 복호기는 이러한 연산 속도 제약을 해결하기 위하여 레지스터 교환방식을 사용한다. 그러나 프로그래머블 DSP 칩에서는 하드웨어 구조상 구현이 용이하지 않다.

상기 DSP 칩 개발사들은 비터비 알고리즘 연산의 고속화 경향에 맞추어 새로운 명령어 구조들을 선보이고 있으나 비터비 알고리즘 중의 일부 연산을 수행하기 위한 국한된 명령어들만을 지원하고 있어 수행 속도를 크게 향상시키지 못하고 있다. 상기 비터비 디코딩의 가속을 지원하는 상용 DSP 칩들로는 디에스피 그룹(DSP Group)의 OakDSP, 텍사스 인스트루먼트(Texas Instrument)사의 TMS320C55x, 모토롤라(Motorol ra)사의 DSP56600 패밀리가 있으며, 이들 모두 ACS 연산 부분만을 가속하고 있다.

다음에 도4는 종래의 프로그래머블 프로세서(DSP 포함)에서의 ACS 연산과정을 수행하기 위한 하드웨어를 나타낸 것으로, 상기 ACS 연산은 한 쌍의 산술연산, 비교, 선택 및 저장의 과정을 거쳐야 한다. 즉 ①의 과정에서 두쌍의 PM과 BM을 더하며, ②의 과정에서 비교를 수행하여 플래그 레지스터에 그 신호를 저장한다. ③의 과정에서는 비교 결과 신호 1비트를 메모리에 저장하고, ④ 과정에서는 비교시 결정된 최소 거리의 값을 쉬프트시켜 메모리에 저장한다. 그러나 이런한 일련의 과정들은 DSP 칩이 보유하고 있는 ALU 및 레지스터 파일의 사양에 따라 각각 여러 클록 싸이클이 걸릴 수 있다. 또한 ③과 같은 경우는 비교 결과인 선택 신호를 메모리에 저장하기 전에 모든 상태에 대한 ACS 연산 결과의 선택 신호들을 쉬프트하여 정렬시킨 후 워드 단위로 메모리에 저장하여야 하기 때문에 여러 싸이클이 걸릴 수 있다.

상술한 비터비 복호화를 위해 특정 사양을 가지는 상용 DSP의 명령어는 단지 2쌍의 데이터를 동시 비교할 수 있는 비교문만을 지원하고 있다. 즉, 비교 이전의 산술연산과 비교 연산 이후 최소거리의 선택 및 저장 과정은 여러 개의 일반 DSP 명령어를 사용하여 처리함으로써 많은 클록 싸이클을 소모하고 있다. 따라서 도4의 ②, ③ 과정에서 걸리는 싸이클을 다소 감소시키고 있다. 또한, 생존자 경로 저장시 1비트를 쉬프트시켜서 저장하는 상기 DSP56600의 VSL 명령어는 비교를 수행하는 MAX 명령어와 파이프 라이닝하여 처리하면 데이터 의존성이 없어 한 클록 싸이클에 동시 수행하면 효율적이나 하드웨어 구조가 뒷받침되지 않아 각각 다른 싸이클에 계산을 하고 있어 VSL 명령어의 장점을 살리지 못하고 있다. 특히, 범용 DSP 칩에서 가장 처리하기 까다로운 생존자 경로 계산을 위한 특정 명령어는 지원되고 있지 않다. 즉, 아무리 ACS 연산을 빨리 수행한다 하더라도 데이터가 복원되어 나오는 비트율은 생존자 경로 계산을 얼마나 빠르게 처리하느냐에 달린 것인데 이를 위한 연산 구조는 지원되지 않아 매우 느린 비트 복원율을 가질 수밖에 없다는 문제점이 있었다. 따라서 종래의 DSP 칩들은 음성서비스와 같은 15kbps 미만의 저속 데이터 통신에 국한되어 사용될 수 밖에 없고, 고속의 데이터 통신에 적용하기 어렵다는 문제점이 있었다.

따라서, 본 발명은 비터비 디코딩 알고리즘을 프로그래머블 프로세서 기반으로 구현시 종래의 비효율적인 측면을 제거하기 위해 프로그래머블 프로세서 상에서 고속의 비터비 디코딩 연산을 가능하게 하는 연산방법 및 이 방법을 실행하기 위한 회로를 제공하는 것을 목적으로 한다.

또한, 본 발명은 최소의 회로를 추가하여 프로그래머블 프로세서의 성능을 향상시키므로써 휴대용 단말기의 고속 에러 정정 알고리즘을 프로그래머블 프로세서 상에서 구현 가능케 함으로써 멀티미디어 단말기의 원칩화(one-chip)를 이루는 것을 목적으로 한다.

상기 목적을 달성하기 위하여 본 발명은 4쌍의 입력 데이터를 2개의 ACS 연산으로 처리하는 비터비 연산방법에 있어서, 상기 각 쌍의 입력 데이터들의 덧셈을 수행한 후 그 결과값을 4개의 9비트 레지스터에 저장하는 제1단계와; 상기 4개의 9비트 레지스터에 저장된 연산이 수행된 결과값을 두 개의 9비트 레지스터로부터 출력되는 결과값과 비교하여 작은 값을 쉬프트 레지스터에 저장하고, 비교 결과 선택 비트 2비트는 64비트 쉬프트 레지스터에 2비트씩 저장하는 제2단계와; 동시에 상기 제1단계가 반복되어 새로운 4쌍의 데이터를 입력하여 덧셈을 수행한 후 상기 9비트 레지스터에 저장하는 제3단계와; 상기 최초 입력된 4쌍의 데이터의 ACS 연산결과 생성된 최소값 2개를 쉬프터에서 출력하여 버스를 통해 이중 포트 메모리로 저장하는 제4단계와; 상기 제1 단계 내지 제 4 단계를 반복하여 64비트 쉬프트 레지스터를 완전히 채운 후, 출력되는 64비트 값을 버스를 통해 레지스터 파일로 전송하는제5 단계와; 상기 레지스터 파일이 64 비트 값 32개를 저장할 공간을 가지고 있을 경우, 64x1 멀티플렉서를 사용하여 데스티네이션 레지스터의 6비트 데이터로 상기 레지스터 파일의 첫번째 번지의 64비트 중 1비트를 선택하여 데스티네이션 레지스터의 LSB로 삽입하고 기존의 6비트를 왼쪽으로 1비트씩 쉬프트하며, 이때 비터비 디코딩된 MSB 1비트를 출력하는 제6단계를 포함하는 비터비 디코딩 연산방법을 특징으로 한다.

또한, 비터비 디코딩 연산방법을 실행하기 위하여, 입력되는 4쌍의 8비트 입력 데이터의 덧셈을 수행하기 위한 4개의 덧셈기와; 상기 각각의 덧셈기에서 연산이 수행된 결과값들을 저장하기 위한 4개의 9비트 레지스터와; 상기 레지스터에 저장되어 있는 연산값들 중 2개의 레지스터에서 출력되는 연산 값들을 비교한 후, 작은 값을 선택하도록하는 선택신호 값을 출력하는 2개의 비교기와; 상기 비교기로 입력되는 2개의 레지스터에서 출력된 연산값들과 동일한 두개의 9비트 데이터를 입력으로 받고 비교기의 비교 결과값 1비트를 선택비트로 받아 작은 값을 선택하도록 하는 두 개의 멀티플렉서와; 상기 멀티플렉서의 연산 결과값을 쉬프트하기 위한 두 개의 쉬프터와; 상기 비교기에서 출력된 선택신호 값을 저장하며, 꽉찰 경우 출력하는 64비트 쉬프트 레지스터와; 상기 쉬프터에서 출력된 결과값을 구속장이 7인 경우 64비트 쉬프트 레지스터의 출력값으로 통과시키는 버스와; 상기 버스를 통과한 쉬프트된 결과값을 저장하는 이중 포트 메모리와; 상기 버스를 통과한 64비트 쉬프트 레지스터에서 출력된 값을 저장한 후 꽉 찼을 경우 최선의 값부터 출력하는 32비트 레지스터 파일과; 상기 32비트 레지스터 파일에서 출력되는 64비트 데이터의 곱셈 연산을 수행하기 위한 64x1 멀티플렉서와; 상기 64x1 멀티플렉서에서 출력을 사용하여 6비트 데이터로 상기 레지스터 파일의 첫 번째 번지의 64비트 중 1비트를 선택하여 삽입하고, 기존의 6비트는 1비트씩 왼쪽으로 쉬프트하여 MSB 1비트를 밖으로 출력하는 데스티네이션 레지스터를 포함하는 것을 특징으로 하는 프로그래머블 프로세서에서의 비터비 디코딩 연산회로를 특징으로 한다.

도1은 일반적인 격자도 상의 상태 천이 관계를 나타낸 버터플라이 구조의 도면.

도2는 일반적인 전용 비터비 디코더에 사용하는 ACS 구조를 나타낸 도면.

도3은 일반적인 비터비 전용 역추적 방식 생존자 경로 계산 회로의 구조를 나타낸 도면.

도4는 종래의 프로그래머블 프로세서(DSP 포함)에서 ACS 연산 수행과정을 나타낸 도면.

도5는 종래의 ASIC으로 구현된 전용 비터비 디코더 아키텍쳐를 나타낸 도면.

도6은 본 발명에 따른 PACS 명령어를 수행하기 위한 블록을 나타낸 도면.

도7은 본 발명에 따른 SLBIT 명령어의 동작을 나타낸 도면.

도8 은 본 발명에 따른 PACS 및 SLBIT 명령어를 실행하기 위한 하드웨어의 구조를 나타낸 도면.

이하, 첨부된 도면을 참조로 하여 본 발명을 상세히 설명하기로 한다.

도5는 ASIC으로 구현된 전용 비터비 디코더의 아키텍쳐를 나타낸 것이다.

본 발명에 따른 프로그래머블 프로세서 명령어 집합은 ASIC으로 구현한 전용 비터비 디코더의 구조와 유사한 구조를 가지고 있어 대등한 성능을 나타낸다. 본 발명의 명령어들은 PACS(Packed Add and Compare and Select)와 SLBIT(Shift Left BIT)이며, 단지 2개의 명령어들로 비터비 디코딩 알고리즘의 대부분을 구현하게 된다. 즉, 도5의 ACS 연산 블록과 생존자 경로 계산 블록을 위한 각각 하나씩의 명령어를 한 클록 싸이클에 동시 수행하도록 하여 전용 비터비 구조의 성능과 대등하게 되도록 하였다. 참고로 수학식 1에 기재된 바와 같이 BMC 연산 블록은 단순한 산술 연산을 수행하므로 특별한 명령어나 하드웨어를 사용하지 않아도 종래 프로그래머블 프로세서들의 일반적인 구조의 ALU를 사용하여 쉽게 구현가능하기 때문에 BMC 알고리즘 블록을 위한 명령어는 고려하지 않는다.

도6은 본 발명에 따른 비터비 알고리즘의 ACS 블록을 하나의 명령어로 처리하는 PACS 명령어를 수행하는 블록도를 나타낸 것으로, 32비트 DSP 칩인 경우 1개의 ALU 안에 있는 연산 유닛들을 이용하여 도2에 도시된 PE 구조 2개를 나타낸 것이다. 상기 연산 유닛은 종래의 것들을 사용하여 구현할 수 있고, 단지 파이프라이닝에 의하여 덧셈과 비교를 연속적으로 수행할 수 있도록 데이터 패스 회로만을 추가하여 구현한다. 도6은 레지스터 파일이 바이트 단위로 억세스 가능하다는 것을 전제로 하는 구조이며(최신 DSP 칩들은 모두 바이트 단위 억세스가 가능함), 2개의 32비트 워드 데이터를 바이트 단위로 처리하여 2개의 ACS PE 역할을 수행하는 구조이다. 이러한 명령어 처리 구조는 2 싸이클마다 4개의 ACS 연산 결과를 출력할 수 있다.

그 동작을 설명하면 a, b, c, d는 BM값들이 들어 있는 8 비트 레지스터의 소스 오퍼런드(Source Operand)이고, a', b', c', d'는 PM값들이 들어 있는 또 다른 8 비트 레지스터의 소스 오퍼런드이다. 상기 값들이 덧셈기인 Ex1을 통해 PM + BM 연산의 결과가 1, 2, 3, 4의 파이프라인 레지스터에 저장되고, 상기 저장된 결과는 비교기(>/s)를 통해 비교 후 작은 값을 선택하고 선택 신호를 1 비트 발생하는 기능을 수행하여 선택결과와 선택신호를 출력한다. 상기 선택결과는 쉬프터1, 2에서 PM + BM 값이 9비트이며 연속적인 덧셈에 의해 발생하는 오버플로우를 방지하기 위한 정규화를 수행하여 오른쪽으로 1 비트 쉬프트되어 SM으로 전송되고, 선택신호들은 하나의 큰 64 비트 쉬프트 레지스터에 저장하며, 이는 한 클록 싸이클마다 PE 개수 만큼씩 왼쪽으로 쉬프트되어 PM으로 전송된다.

여러 개의 ALU를 갖는 프로그래머블 프로세서나 32비트 또는 추후 개발될 64비트, 128비트 프로그래머블 프로세서 등에서도 제6도의 기본 구조를 단순히 병렬적으로 확장하면 ACS 연산은 서로간에 데이터 의존성이 없으므로 고속 병렬 처리가 가능하다. 한 예로써, 64비트 칩인 경우 ALU 하나로 ACS PE를 4개, 128비트 칩인 경우는 ACS PE 8개를 구성할 수 있다. 또한 ALU가 2개 이상이면 결국 ACS PE도 2배 이상 늘어나게 된다.

한쌍의 ACS 버터플라이 연산 구조는 4개의 ACS PE를 필요로 하므로 결국, 앞서 설명한 상용 프로그래머블 프로세서의 ACS 연산 소스리스트를 PACS 명령어 두 개로 처리할 수 있는 것이다. 따라서 상용 프로그래머블 프로세서보다 수행 싸이클 면에서 3~5 배 이상 빠르게 ACS 연산 블록을 처리할 수 있다. 상기 도4에 도시된 종래 프로그래머블 프로세서의 ALU 구조 처리방식은 ALU 안에 여러 가지 기능을 하는 연산 유닛들이 각기 연산을 취하는 방식이었으나 그 연산 유닛들 간에 데이터 흐름 경로를 놓아주면 도6의 연산 흐름이 가능하다. 다시 말해서, 도6의 구조는 종래 프로그래머블 프로세서의 연산 유닛들에 연속연산(한쌍의 덧셈 연산 직후 비교 연산)이 가능하도록 하는 데이터 패스 구조와 2^(K-1)비트의 쉬프트 레지스터(쉬프터 0 : 선택신호 저장)만을 추가하여 구현 가능하므로 하드웨어 부담이 적고, 다른 DSP 알고리즘의 연산 수행도 원활히 수행할 수 있다.

다음에, 본 발명에 따른 또 다른 명령어인 SLBIT는 도3의 역추적 방식 생존자 경로 계산 회로를 위한 출력 레지스터를 그대로 구현한 것으로, 도7은 이러한 SLBIT 명령어의 동작을 나타낸 것이다. 즉 구속장 K=7인 경우 ACS 연산 결과 생성된 선택 신호 1비트들이 모여 2^(7-1)=64 비트 쉬프트 레지스터를 채우면 64비트의 데이터는 경로 메모리(PM) 역할을 하는 레지스터 파일에 저장되고, 그 저장된 값들을 소스 오퍼런드로 하여 도7에 도시된 바와 같이 연산을 수행한다. 데스티네이션 하위 6 비트의 조합만으로 2⁶=64 비트를 비트단위로 선택 가능하므로 소스 오퍼랜드의 1비트를 선택하고 그 1비트가 데스티네이션의 LSB(Least Significant Bit)로 들어오면서 왼쪽으로 쉬프트되어 새로운 6비트를 구성하고, 이 6비트를 가지고 같은 방식의 연산을 반복 수행한다. 상기 반복 연산은 PM의 처음(0번지)부터 끝(K의 4~5배 번지)까지 수행하여야 하며 이렇게 전체 PM을 트레이스 백하면 1비트의 복호화 결과가 출력되는데, 여기에서 출력되는 값이 복호화된 원시 데이터이다.

도7의 동작을 설명하면 먼저, 데스티네이션 오퍼런드의 하위 K 비트가 가리키는 소스 오퍼런드의 비트를 선택한 후, 상기 데스티네이션 오퍼런드의 원래값을 1 비트 쉬프트시키고, 선택된 비트를 데스티네이션의 LSB로 복사한다.

도7의 동작을 수행하기 위해서는 종래 DSP의 레지스터 파일에 단순히 2^(K-1)x1 멀티플렉서만 추가되면 구현 가능하다. 선택신호들이 저장되는 레지스터 파일 안의 레지스터들은 2^(K-1)비트 이상 단위로 억세스 가능한 구조를 가져야 한다(K=7인 경우 32비트 칩에서 레지스터 2개를 연결하여 64비트 단위로 억세스 가능하여야 함). 일반적으로 구속장 K가 7인 경우를 가장 많이 사용하나 7이 아닌 경우에도 사용이 용이하도록 K값을 충분하게 선택하여 하드웨어를 구성하는 것이 좋다.

이를 통하여, 종래 DSP로는 쉬프트와 인덱스 어드레싱으로 데이터를 이동시켜 약 5싸이클에 걸쳐 처리를 해야 하는 것을 1싸이클로 줄일 수 있다. 그러나 1비트의 디코딩 데이터를 산출하기 위해서는 구속장 K가 7인 경우 일반적으로 4~5배 즉, 28~35개의 2^(7-1)= 64비트 PM 값들을 전부 역추적 해야 하기 때문에 아무리 ACS 연산을 수행한다 하더라도 고속 연산을 수행하기 어렵다. 종래 DSP에서는 PM 값들을 내부 메모리에 저장시켜 놓고 임시 레지스터에 1개씩 옮겨가면서 역추적 연산을 수행하고 메모리로부터 한번에 64비트씩 레지스터로 이동하는 것 또한 불가능하기 때문에 많은 수행 싸이클이 소모된다. 한 예로서, 메모리 억세스 싸이클이 3이고 메모리 데이터의 비트수가 8인 경우에는 대략 8 x 3 + 5 = 29 싸이클이 걸리게 된다. 따라서 PM 값들을 억세스 싸이클이 1인 레지스터 파일을 사용하여 처리해야 하며, 레지스터 파일에 64비트 레지스터 개수가 28~35개 미만인 경우 내부 메모리와 레지스터 파일간의 데이터도 병렬로 이동하는 구조를 반드시 가져야 한다.

다음에 도8은 본 발명에 따른 PACS와 SLBIT 명령어들을 효율적으로 처리하기 위한 K=7인 경우의 회로를 나타낸 것으로, 입력되는 4쌍의 8비트 입력 데이터의 덧셈을 수행하기 위한 4개의 덧셈기와; 상기 각각의 덧셈기에서 연산이 수행된 결과값들을 저장하기 위한 4개의 9비트 레지스터와; 상기 레지스터에 저장되어 있는 연산값들 중 2개의 레지스터에서 출력되는 연산 값들을 비교한 후, 작은 값을 선택하도록하는 선택신호 값을 출력하는 2개의 비교기와; 상기 비교기로 입력되는 2개의 레지스터에서 출력된 연산값들과 동일한 두개의 9비트 데이터를 입력으로 받고 비교기의 비교 결과값 1비트를 선택비트로 받아 작은 값을 선택하도록 하는 두 개의 멀티플렉서와; 상기 멀티플렉서의 연산 결과값을 쉬프트하기 위한 두 개의 쉬프터와; 상기 비교기에서 출력된 선택신호 값을 저장하며, 꽉찰 경우 출력하는 64비트 쉬프트 레지스터와; 상기 쉬프터에서 출력된 결과값을 구속장이 7인 경우 64비트 쉬프트 레지스터의 출력값으로 통과시키는 버스와; 상기 버스를 통과한 쉬프트된 결과값을 저장하는 이중 포트 메모리와; 상기 버스를 통과한 64비트 쉬프트 레지스터에서 출력된 값을 저장한 후 꽉 찼을 경우 최선의 값부터 출력하는 32비트 레지스터 파일과; 상기 32비트 레지스터 파일에서 출력되는 64비트 데이터의 곱셈 연산을 수행하기 위한 64x1 멀티플렉서와; 상기 64x1 멀티플렉서에서 출력을 사용하여 6비트 데이터로 상기 레지스터 파일의 첫 번째 번지의 64비트 중 1비트를 선택하여 삽입하고, 기존의 6비트는 1비트씩 왼쪽으로 쉬프트하여 MSB 1비트를 밖으로 출력하는 데스티네이션 레지스터로 구성된다.

상기 시스템 버스의 상단부 구조는 PACS 명령어 처리를 위한 세부 회로로 도6의 PE 구조를 사용한 것이며 2개의 PE를 가진다. 따라서 32비트 머신의 ALU 1개로 구현 가능하다. 상기 회로는 구속장 K가 7인 경우를 임의로 나타낸 것이며, ACS 연산부는 PACS 명령어에서 설명한 바와 같이 병렬로 확장한다면 더 빠른 ACS 연산이 가능하다. 첫 번째 클럭 싸이클에서 한 쌍의 BM과 한 쌍의 SM으로부터 8비트의 데이터 쌍이 들어와 더해짐으로써 두 경로의 현재 스테이지까지의 PM을 계산한다. 또한 두 번째 클럭 싸이클에서 두쌍 PM 값들의 크기를 비교기를 이용하여 작은값을 선택하도록 하는 선택신호를 출력하고, 이 선택신호는 멀티플렉서로 입력되어 입력되는 값들 중 작은 값을 선택하도록 한다. 상기 선택된 결과를 각각 1비트의 신호들로써 64비트 레지스터의 LSB에 저장하고 작은 것으로 판명된 생존자를 정규화하기 위하여 1비트 오른쪽으로 쉬프트하여 SM에 저장한다.

도8에서는 두 개의 ACS 연산을 독립적으로 처리하여 출력된 두 개의 작은 값들을 시스템 버스를 통해 메모리에 저장하는 구조를 가지고 있으며, 이러한 메모리가 생존자를 저장하는 SM 역할을 수행하며 이중 포트 메모리를 사용할 경우 명령어 수행 사이클을 줄일 수 있다. 또한, 선택 신호 2비트가 저장되는 64비트 쉬프트 레지스터는 매 클럭마다 2비트씩 왼쪽으로 쉬프트하여 64비트를 채울 때까지 동작한다. 도8과 같이 ACS PE가 두 개인 경우 2비트 단위로 쉬프트하여(ACS PE의 개수 단위로 쉬프트) 64비트가 차게 되면 레지스터 파일의 32비트 레지스터 두 개에 나누어 저장된다.

상기 저장된 PM은 도8의 좌측 하단부에 도시된 SLBIT 명령어의 하드웨어 구조를 통해 64비트 데이터중 1비트가 64 x 1 멀티플렉서에서 선택되어 데스티네이션 레지스터에 LSB로 삽입되고, 이 레지스터는 동시에 왼쪽으로 1비트 쉬프트된다. 상기와 같은 연산을 반복하여 PM의 마지막 데이터까지 처리되면 이때 데스티네이션 레지스터의 7-1=6 번째 비트값이 최종 디코딩된 1비트 값이 된다.

상기 PACS 명령어 하드웨어는 처리 데이터가 8비트 단위로 억세스만 가능하면 프로그래머블 프로세서의 비트 수에 상관없이 구현 가능하고, 프로그래머블 프로세서의 처리 비트가 클 경우 즉, 64비트 머신이나 128 비트 머신인 경우 PE의 수가 늘어나므로 특별한 회로의 추가없이 그 만큼의 병렬처리 효과를 가져올 수 있다. 그러나 반드시 생존자 경로 계산의 수행 싸이클과 조화를 이루어야만 고속의 동작이 가능하다.

상술한 바와 같이 ACS가 아무리 빨리 처리된다 하더라도 생존자 경로 계산이 늦어지면 고속의 ACS연산은 성능을 발휘할 수 없다. 따라서 생존자 경로 계산은 레지스터 파일과 같은 1싸이클 억세스가 가능한 저장매체를 대상으로 해야 하며, 도8의 하단부에 도시된 바와 같이 레지스터 파일이 전체 PM 메모리 역할을 하기에 공간이 부족한 경우는 내부 램 또는 캐쉬 메모리와 레지스터 파일간의 병렬이동이 용이한 구조를 가져야 병목 현상을 없앨 수 있다. 또한, 도8의 맨 하단에 생존자 경로를 계산하기 위한 6비트의 쉬프트 레지스터는 일반 쉬프트 레지스터를 사용하여도 되며, 반드시 ACS 연산과 병렬적으로 처리되어야 고속 수행이 가능하다.

또한, 구속장 K가 7인 경우 64개의 상태가 존재하고, 본 발명의 연산회로에서 ACS PE가 2개이므로 32싸이클이 걸린다. 그리고, 동시에 선택 신호들은 2 비트씩 왼쪽으로 쉬프트 되어 64비트 쉬프트 레지스터를 가득 채우게 된다. 가득 찬 64 비트 값을 레지스터 파일내에 있는 2개의 32 비트 레지스터에 저장하고, PACS 연산은 같은 순서로 계속된다.

한편 레지스터 파일이 PM의 깊이인 K의 4~5배의 공간 즉, 28~35개의 레지스터를 갖거나 메모리와 병렬 데이터 이동이 가능한 구조를 가지면, SLBIT 연산은 28~35의 싸이클 만에 처리가 되고, 그 결과 1 비트의 데이터가 복호화되어 출력된다. 따라서, PACS와 SLBIT는 연산이 독립적이고 수행 싸이클이 거의 비슷하므로 TMS320C54x의 경우 처럼 심볼 '∥'(병렬연산)을 사용하여 PACS∥SLBIT의 형태로 두명령어의 동시 수행이 가능하다.

쉬프터는 일반 산술연산 유닛에 존재하는 쉬프터에 데이터 경로를 생성하여 구현할 수 있다. 멀티플랙서는 6비트의 선택신호를 받아 경로 메모리의 데이터를 가지고 있는 PM 레지스터의 하위 비트로 삽입되고 그 레지스터의 데이터가 전체적으로 왼쪽으로 쉬프트를 하게 되면서 역추적 과정을 수행하게 되는 것이다. 즉, 약 32 싸이클마다 1비트 데이터를 출력하므로 100MHz의 동작 주파수를 가지는 DSP 칩인 경우라도 100,000,000/32 = 3.125 Mbps의 복호화 성능을 낼수 있으며, 부호율이 1/2이므로 6.25 Mbps의 고속 전송률을 갖는 통신 환경에서도 사용 가능하다.

표 3 은 구속장 K=7 인 경우의 기존 DSP 칩과의 비터비 디코딩 수행 싸이클의 비교표이다. ACS 연산의 경우 상용 DSP 칩들의 벤치마크 프로그램에서 ACS 버터플라이 연산 프로그램과 수행 싸이클만 설명하고 있기 때문에 실제 64/4 = 16쌍의 버터플라이 연산을 반복 수행하면서 루프문 동작시 결과 데이터 저장 및 분기 등으로 소모되는 데이터 지연 싸이클 수는 α로 표기하였으며, 대략 버터플라이 연산 수행 싸이클의 1/3정도를 더 소모한다.

구조연산블럭	OakDSPTM	TMS320C55x	DSP56600	본 발명의 구조
ACS 연산 블록	약 152+α	약 96+α	약 128+α	32
생존자 경로 계산	약 910 (= 26 × 7 × 5)	35
전체	약 1062+α	약 1006+α	약 1038+α	35

상기 표 3은 구속장 K=7 인 경우의 수행 싸이클 비교한 것이다.

또한, 기존 프로그래머블 프로세서에서는 ACS 연산과 생존자 경로 계산을 따로 수행하였으나, 본 발명에서는 ACS와 생존자 경로 계산의 동시 수행이 가능하므로 전체적으로 약 30배 이상의 성능 향상을 보일 수 있다. 본 발명의 비터비 전용 프로그래머블 프로세서 명령어 회로는 제 8도에 @기호로 나타낸 2^(K-1)비트 쉬프트 레지스터, 2^(K-1)×1 멀티플렉서들만 제외하면 기존 DSP에서 널리 사용되는 연산 유닛들로 구성되어 있다.

상술한 바와 같이 본 발명은 칩 제작시 기존 연산 모듈들 대부분이 재사용 가능하고 연속적인 연산이 가능하도록 하는 파이프라이닝 데이터 패스 회로들만 추가하면 되므로 설계 비용 측면에서도 경제적이다. 또한, ACS 연산 블록의 경우 같은 구조를 단순히 반복하여 쉽게 병렬로 확장이 가능하며 생존자 경로 계산의 경우 K 값을 넉넉히 고려할 경우 단순히 2^(K-1)×1 멀티플렉서 비트 수만 좀더 커지고, 한 상태의 PM값을 저장하기 위해 서로 결합되는 레지스터들의 수(32비트 칩에서 K=7인 경우 2개, K=8인 경우 4개, K=9인 경우 8개)만 늘어나면 되는 매우 유연한 구조가 된다.

또한, 기존 DSP 기술에서 15Kbps 대의 전송률을 보이던 것을 본 발명이 제안하는 구조를 가지고 100MHz 동작 주파수를 갖는 DSP 칩에서 동작한다면 6.25 Mbps의 전송률을 가지고 있어 IMT-2000과 같은 무선 멀티미디어 서비스의 요구전송률인2Mbps 환경에서도 사용 가능하다. 실제로 최근 DSP 공정 기술은 수백 MHz 이상의 동작을 가능하게 하고 있으며, 레지스터 파일의 집적도도 매우 커지고 있어, 앞으로 반도체 공정 기술이 더욱 발달하면서 처리 가능 전송률은 더 높아질 수 있고, 본 발명에서 제안한 구조들은 병렬적으로 확장가능하므로 수~수십 Mbps까지 가능할 것이다. 따라서, 현재 음성 데이터 전송에 국한된 DSP 기술을 LMDS(Local Multipoint Distribution Systems) 서비스나 MCNS(Multimedia Cable Network System)등의 표준안을 만족하는 CATV나 VOD 등의 멀티미디어 통신 서비스까지도 구현할 수 있는 영역으로 끌어올릴 수 있을 것이다.

또한, 종래의 통신 전용의 ASIC들이 주류를 이룬 통신용 FEC(Forward Error Correction)에 있어서의 이를 통신 변복조와 함께 수행할 수 있는 DSP를 제조하여 해결할 수 있게 함으로써 원가 절감과 휴대용 단말기의 저전력화 및 소형화를 이룰 수 있다.

Claims (7)

1. 비터비 디코딩 연산방법을 실행하기 위하여,

   입력되는 4쌍의 8비트 입력 데이터의 덧셈을 수행하기 위한 4개의 덧셈기와;

   상기 각각의 덧셈기에서 연산이 수행된 결과값들을 저장하기 위한 4개의 9비트 레지스터와;

   상기 레지스터에 저장되어 있는 연산값들 중 2개의 레지스터에서 출력되는 연산 값들을 비교한 후, 작은 값을 선택하도록하는 선택신호 값을 출력하는 2개의 비교기와;

   상기 비교기로 입력되는 2개의 레지스터에서 출력된 연산값들과 동일한 두개의 9비트 데이터를 입력으로 받고 비교기의 비교 결과값 1비트를 선택비트로 받아 작은 값을 선택하도록 하는 두 개의 멀티플렉서와;

   상기 멀티플렉서의 연산 결과값을 쉬프트하기 위한 두 개의 쉬프터와;

   상기 비교기에서 출력된 선택신호 값을 저장하며, 꽉찰 경우 출력하는 64비트 쉬프트 레지스터와;

   상기 쉬프터에서 출력된 결과값을 구속장이 7인 경우 64비트 쉬프트 레지스터의 출력값으로 통과시키는 버스와;

   상기 버스를 통과한 쉬프트된 결과값을 저장하는 이중 포트 메모리와; 상기 버스를 통과한 64비트 쉬프트 레지스터에서 출력된 값을 저장한 후 꽉 찼을 경우 최선의 값부터 출력하는 32비트 레지스터 파일과;

   상기 32비트 레지스터 파일에서 출력되는 64비트 데이터의 곱셈 연산을 수행하기 위한 64x1 멀티플렉서와;

   상기 64x1 멀티플렉서에서 출력을 사용하여 6비트 데이터로 상기 레지스터 파일의 첫 번째 번지의 64비트 중 1비트를 선택하여 삽입하고, 기존의 6비트는 1비트씩 왼쪽으로 쉬프트하여 MSB 1비트를 밖으로 출력하는 데스티네이션 레지스터를 포함하는 것을 특징으로 하는 프로그래머블 프로세서에서의 비터비 디코딩 연산회로.
2. 제 1 항에 있어서,

   입력되는 데이터의 비트수가 증가할 경우 상기 회로를 병렬로 정렬하여 사용할 수 있는 것을 특징으로 하는 프로그래머블 프로세서에서의 비터비 디코딩 연산회로.
3. 제 1 항에 있어서,

   상기 32비트 레지스터 파일의 저장공간이 부족할 경우 내부 램 또는 캐쉬 메모리를 사용하며, 여러 개씩 한꺼번에 동시에 이동 가능한 구조를 갖는 것을 특징으로 하는 프로그래머블 프로세서에서의 비터비 디코딩 연산회로.
4. 제 1 항에 있어서,

   상기 최초의 입출력 데이터의 비트 수가 변하더라도 제1항에서의 회로와 동일한 구성을 갖는 것을 특징으로 하는 프로그래머블 프로세서에서의 비터비 디코딩연산회로.
5. 제 1 항에 있어서,

   상기 구속장의 수가 변하더라도 상기 회로와 동일한 구성을 갖는 것을 특징으로 하는 프로그래머블 프로세서에서의 비터비 디코딩 연산회로
6. 삭제
7. 제1항의 비터비 디코딩 연산회로를 이용하여 4쌍의 입력 데이터를 2개의 ACS 연산으로 처리하는 비터비 디코딩 연산방법에 있어서,

   상기 각 쌍의 입력 데이터들의 덧셈을 수행한 후 그 결과값을 4개의 9비트 레지스터에 저장하는 제1단계와;

   상기 4개의 9비트 레지스터에 저장된 결과값을 2개의 9비트 레지스터로부터 출력되는 결과값과 비교하여 작은 값을 쉬프트 레지스터에 저장하고, 비교 결과 선택 비트 2비트는 64비트 쉬프트 레지스터에 2비트씩 저장하는 제2단계와;

   동시에 상기 제1단계가 반복되어 새로운 4쌍의 데이터를 입력하여 덧셈을 수행한 후 상기 9비트 레지스터에 저장하는 제3단계와;

   상기 최초 입력된 4쌍의 데이터의 ACS 연산결과 생성된 최소값 2개를 쉬프터에서 출력하여 버스를 통해 이중 포트 메모리로 저장하는 제4단계와;

   상기 제1 단계 내지 제 4 단계를 반복하여 64비트 쉬프트 레지스터를 완전히 채운 후, 출력되는 64비트 값을 버스를 통해 레지스터 파일로 전송하는 제5 단계와;

   상기 레지스터 파일이 64 비트 값 32개를 저장할 공간을 가지고 있을 경우, 64x1 멀티플렉서를 사용하여 데스티네이션 레지스터의 6비트 데이터로 상기 레지스터 파일의 첫 번째 번지의 64비트 중 1비트를 선택하여 데스티네이션 레지스터의 LSB로 삽입하고 기존의 6비트를 왼쪽으로 1비트씩 쉬프트하며, 이때 비터비 디코딩된 MSB 1비트를 출력하는 제6단계를 포함하는 프로그래머블 프로세서에서의 비터비 디코딩 연산방법.