KR19990078237A

KR19990078237A - 비터비 알고리즘을 구현하는 가산 비교 선택 회로 및 방법

Info

Publication number: KR19990078237A
Application number: KR1019990010205A
Authority: KR
Inventors: 이인규; 손태그제프리리
Original assignee: 슈나이티 비.에스.; 루센트 테크놀러지스 인크
Priority date: 1998-03-26
Filing date: 1999-03-25
Publication date: 1999-10-25
Also published as: TW436682B; JPH11355152A; JP3261109B2; US6148431A

Abstract

본 발명은 비터비(Viterbi) 알고리즘을 이용하는 검출기 시스템에 관한 것으로, 검출기 시스템은 채널 출력 샘플의 관측된 시퀀스에 대해서 최적의 수신 심볼 시퀀스(most likely received symbol sequence)를 결정하는 이중 상태 트렐리스 구조(double-state trellis structure)를 구성하는 장치 및 방법을 포함한다. 이중 상태 트렐리스에 있어서, 동일한 분기 메트릭을 갖고 경로 선택 동안에 동일한 결정을 갖는 상태 쌍이 식별되어, 이들 상태 쌍이 이전 상태 메트릭의 비교 동작에 공유되도록 한다. 따라서, 갱신 또는 현재 상태 메트릭 값을 계산하기 위해서, 가산, 비교 및 선택(ACS) 회로는 이전 상태 메트릭 값만을 비교하여 두 상태 사이에서의 천이에 대한 최소 값을 결정하는 반면, 각 이전 상태 메트릭 값과 그에 대응하는 분기 메트릭을 조합하여 갱신 또는 현재의 상태 메트릭 값을 제공한다.

Description

비터비 알고리즘을 구현하는 가산 비교 선택 회로 및 방법{AN ADD-COMPARE-SELECT CIRCUIT AND METHOD IMPLEMENTING A VITERBI ALGORITHM}

본 발명은 전반적으로 심볼 시퀀스(symbol sequence)를 디코딩하기 위한 회로에 관한 것으로, 보다 상세하게는, 비터비(Viterbi) 알고리즘을 구현하는 ACS(add-compare-select) 회로를 개선하는 것에 관한 것이다.

많은 디지털 시스템은 전송된 디지털 신호에 잡음이 추가되는 통신 채널 형태를 통해 전송된 심볼의 시퀀스를 나타내는 신호를 보다 잘 검출하기 위해 최우 시퀀스 검출(maximum likelihood sequence detection : MLSD)을 통상적으로 사용한다. 예를 들어, 자기 기록 시스템은 에러 정정 및 변조 부호화를 이용하여 먼저 데이터를 부호화한 다음, 부호화된 데이터를 자기 매체 상에 심볼 시퀀스로 기록되는 심볼로 변환한다. 그러므로, 매체는 검출된 심볼의 시퀀스를 제공하도록 독출될 수 있다. 그 다음, 검출기는 시퀀스 검출 알고리즘을 사용하여 자기 매체로부터 독출된 채널 출력 샘플의 시퀀스에 상응하는 심볼의 최우 시퀀스를 결정한다.

이러한 시스템에 사용되는 비터비 알고리즘(Viterbi algorithm : VA)은, 잡음에서 관찰되는 이산 시간 마르코프 처리기(discrete time Markov process)인 유한 상태의 상태 시퀀스에 대한 최대 귀납 추정(a posteriori estimate)을 제공한다. 부가적인 잡음으로 인해 손상된 수신 채널 출력 샘플의 시퀀스가 주어지는 경우, VA는 사전에 정의된 메트릭에 따라서 수신된 채널 출력 샘플 시퀀스에 가장 가까운 트렐리스(trellis) 구조 내의 심볼 시퀀스를 구한다. 알려진 바와 같이, 부가 백색 가우시안 잡음(additive white gaussian noise : AWGN)을 갖는 통신 채널에서, VA는 최적의 최우 시퀀스 검출 알고리즘으로 보일 수 있다. 유클리드 거리(Euclidian distance)가 트렐리스 구조에 대한 메트릭으로서 사용될 수도 있다.

또한, 많은 디지털 통신 시스템은 에러 검출 확률을 향상하기 위해서 에러 제어 코드(error-control code)나 콘볼루션 코드(convolution code)를 보편적으로 사용한다. 원격 통신 시스템은 버스트 잡음(bursty noise)으로 인한 전송 에러를 최소화하기 위해 에러 정정 인코딩을 한 후 흔히 비트 인터리빙(bit interleaving)을 수행한 다음, 콘볼루션 복호화된 데이터를 심볼 시퀀스로서 전송한다. 예를 들어, VA는 에러 정정 코드를 디코딩하기 위해 채널 내에서 사용될 수도 있다.

따라서, VA를 사용하는 시스템은 세 가지 단계를 반복적으로 수행하는데, 편의상, 상태들간의 천이(transition)는 일반적으로 트렐리스 구조도에 의해 표현된다. 첫째, 한 트렐리스에 대한 분기 메트릭(branch metric)은 현재 상태에 대해서 계산되고, 둘째, 상태 메트릭의 갱신은 모든 상태에 대해서 이루어지며, 셋째, 생존 경로(survivor path)가 결정된다. 생존 경로는 유클리드 거리에 따라, 잡음이 있는 수신된 심볼의 시퀀스에 가장 가까운 주어진 상태로 들어가는 심볼의 시퀀스를 나타낸다. 한 상태에 대한 분기 메트릭은 수신된 심볼과 그 상태에 대응하는 이상적인 채널 출력 샘플 사이의 유클리드 거리로 정의된다. 가장 수신될 가능성이 있는 전체 또는 포괄적인 시퀀스를 산정하기 위해서, VA는 모든 상태에 대한 상태 메트릭을 반복적으로 계산하고 갱신한다.

전술한 MLSD 알고리즘에서, 이 기술 분야에서 잘 알려진 바와 같이, 소정의 천이에 대한 분기 메트릭은 수신된 잡음성 채널 출력 샘플(y_n, 여기서 n = 1, 2, ...,)과 천이에 대응하는 이상적인 채널 출력 샘플에 대한 최우 함수의 부정(negative) 알고리즘으로서 정의된다. 그러므로, 예시적인 MLSD 알고리즘에서, 시간 n에서의 i번째 상태에서 시간 n+1에서의 k번째 상태까지의 천이에 대한 분기 메트릭()은 수학식 1로 주어진다.

여기서, "i"는 시작 상태를 나타내고, "n"은 시간 n을 나타내며, t_n는 i번째 상태에서 k번째 상태까지의 천이에 대응하는 이상적인 채널 출력 샘플이고, f(*)는 가우시안 잡음 시퀀스의 확률 밀도 함수이다.

또한, 채널 응답 다항식 H(D)(여기서, D는 지연 연산자)로 나타내어진 y의 수신된 시퀀스가 주어지는 경우, VA는 각 상태에 대한 분기 메트릭을 누산함으로써 최우 경로를 반복적으로 최적화한다. 상태의 수는 M^N으로 주어지며, 여기서 M이 입력 알파벳 또는 입력 레벨의 크기를 나타내고 N은 채널 메모리 길이를 나타낸다. VA에 대해, 시간 n에서 상태 메트릭 값이 각 상태에 부여되고, 시간 n＋1에서 새로운 값이 수신되면, 각 상태 메트릭 값이 갱신된다. 도 1A는 i_(m)번째와 K번째 상태 사이에서의 천이에 대한 상태 메트릭(SM_i(m), m = 1, 2, .. M)의 갱신 동작을 도시한다. 시간 n＋1에서 트렐리스 구조의 각각의 상태 메트릭에 대해서는, 시간 n에서의 상태 i(m)에서 이전의 상태 메트릭과 i_(m)번째에서 k번째 상태로 진행하는 대응하는 분기 메트릭이 함께 더해진다. 따라서, k번째 상태에 대한 상태 메트릭은, 수학식 2에 주어진 바와 같이 최소한의 모든 가능한 경우를 선택함으로써 현재의 SM_k가 되도록 갱신된다.

여기서, "i_(m)"은 시작 상태를 나타내고, "n"은 시간 n을 나타내며,는 i번째 상태에서 k번째 상태로의 천이와 연관된 시간 n＋1에서의 분기 메트릭을 나타낸다. 편의상, "n"과 "n＋1" 표기는 당업자에 의해 예측되고, 통상적으로 생략된다.

이러한 동작을 구현하는 회로는 통상적으로 ACS(add-compare-select) 회로로 지칭된다. 2진 입력 시퀀스에 대해, 도 2는 이진 경우(M=2)에 도 1에 도시되고 수학식 2로 주어진 상태 메트릭값 갱신(SM_k)을 계산하는 종래의 ACS 회로를 도시하고 있다. ACS 회로(202)는 전형적으로 가산기(210, 212)와, 비교기(214) 및 비교기(214)의 출력 신호에 의해 제어되는 2-1 멀티플렉서일 수 있는 선택 회로(216)를 이용한다.

도 2에 도시한 바와 같이, 가산기(210)는 상태 메트릭(SM_i)과 대응하는 분기 메트릭(BM_i,k)을 수신하여 제 1 갱신된 상태 메트릭으로 조합하며, 가산기(212)는 상태 메트릭(SM_j)과 대응하는 분기 메트릭(BM_j,k)을 수신하여 제 2 갱신된 상태 메트릭으로 조합한다. 가산기(210, 212)의 제 1 및 제 2 갱신된 상태 메트릭 값은 비교기(214)에서 비교되며, 비교기(214)는 제 1 및 제 2 갱신된 상태 메트릭 값 중에서 최소값인 어느 하나를 나타내는 최소 표시기(indicator) 신호(D_k)를 제공한다. 갱신된 제 1 및 제 2 상태 메트릭 값과 최소 표시기 신호(D_k)는 선택 회로(216)에 제공된 후, 선택 회로(216)는 최소 표시기 신호(D_k)에 응답하여 제 1 및 제 2 갱신된 상태 메트릭 값 중 최소 값을 새로운 상태 메트릭 값(SM_k)으로써 제공한다.

종래 기술의 ACS 회로(202)에서는 각 갱신 동작이 연속적으로 수행되기 때문에, ACS(202)는 VA 검출기를 사용하는 시스템의 속도와 처리량을 제어할 수 있다. 따라서, ACS에는 전체 시스템 회로의 처리량을 증가시키는 병목 현상이 있을 수 있다. 그러므로, 비터비 또는 이와 유사한 알고리즘을 사용하는 디코더의 ACS 회로에 대한 속도를 증가시킬 수 있는 새로운 상태 메트릭 갱신 구조가 요구된다.

본 발명은 각각의 이전 상태 메트릭 값을 갖는 이전 상태의 세트로부터 현재 상태의 현재 상태 메트릭 값을 제공하기 위해 이중 상태(double-state) 트렐리스 구조의 ACS(add-compare-select) 기능을 수행하는 회로 및 방법에 관한 것이다. 이 회로 및 방법은, 1) 이전 상태 세트의 각각의 이전 상태 메트릭 값과 이전 상태 세트의 각 하나와 현재 상태 사이의 천이를 위해 정의된 각각의 분기 메트릭 값을 조합하여 각각의 갱신된 상태 메트릭 값을 제공하되, 각 분기 메트릭 값은 서로 동일하고, 2) 이전 상태 세트의 각 이전 상태 메트릭 값을 비교하여 최소값을 갖는 하나의 소정의 이전 상태 메트릭 값을 결정하며, 3) 최소값을 갖는 하나의 이전 상태 메트릭 값에 대응하는 선택 신호를 제공하고, 4) 선택 신호에 응답하여, 하나의 최소값을 갖는 이전 상태 메트릭 값과 각각의 분기 매트릭 값의 조합으로부터 제공된 각각의 갱신된 상태 메트릭 값을 현재 상태 메트릭 값으로써 선택한다.

도 1은 비터비 알고리즘의 i_(m)번째와 k번째 상태 사이에서의 천이에 대한 상태 메트릭 갱신 동작을 도시하는 도면,

도 2는 도 1B에 도시한 상태 메트릭 갱신을 계산하는 종래 기술의 ACS(add-compare-select) 회로를 도시하는 도면,

도 3은 본 발명의 일 실시예를 이용한 비터비 알고리즘 기반 검출기를 도시하는 블럭도,

도 4는 채널 응답 다항식 H(D) = 1+D에 대한 종래 기술의 두 가지 상태 트렐리스 구조도,

도 5는 채널 응답 다항식 H(D) = 1+D+0*D²에 대한 본 발명의 예시적인 실시예에 따른 이중 상태 트렐리스 구조도,

도 6은 본 발명에 따른 예시적인 ACS 회로를 도시하는 도면,

도 7은 본 발명의 다른 실시예에 따른 다른 예시적인 ACS 회로를 도시하는 도면,

도 8은 이진 1 + D 채널에서 비터비 알고리즘을 사용하는 종래 기술에 대한 디코더의 두 가지 상태 트렐리스 구조를 도시하는 도면,

도 9는 이진 1 + D + 0*D²채널에서 비터비 알고리즘을 사용하는 본 발명에 따라 사용되는 이중 상태 트렐리스 구조를 도시하는 도면.

도면의 주요 부분에 대한 부호의 설명

302 : 분기 메트릭 계산 처리기 304 : 옵션 정규화 처리기

306 : ACS 처리기 308 : 상태 메트릭 메모리

309 : 경로 메모리 310 : 최우 결정 처리기

312 : 옵션 심볼 디코더 322 : 필터

324 : 샘플링 처리기 326 : 헤드

328 : 자기 매체

본 발명의 전술한 특징 및 장점은 첨부된 도면과 관련하여 수행되는 상세한 설명을 참조함으로써 보다 더 잘 이해 될 것이다.

검출 시스템

본 발명은 모든 가능한 시퀀스의 세트 사이에서 최적의 수신 심볼을 결정하는 위한 이중 상태 트렐리스 구조를 정의하는 비터비 알고리즘을 구현하는 ACS 회로 및 방법에 관한 것이다. 이중 상태 트렐리스에 있어서는, 동일한 분기 메트릭을 갖고 경로 선택 동안에 동일한 결정도 갖는 상태 쌍(pair)이 식별되어, 이들 상태 쌍이 이전 상태 메트릭의 비교 동작에 공유되도록 한다. 따라서, 갱신된 또는 현재의 상태 메트릭 값을 계산하기 위해서, 단지 상태 메트릭 값만을 비교하여 두 상태 사이의 천이에 대한 최소값을 결정하고, ACS 회로는 또한 각 이전 상태 메트릭 값과 그에 대응하는 분기 메트릭을 조합하여 병렬 동작에서 갱신된 또는 현재 상태 메트릭 값을 제공한다. 또한, 동일한 결정을 갖는 상태 쌍이 식별되기 때문에, 상태 쌍에 대한 두 개의 현재 상태 갱신이 동시에 수행될 수 있다.

이하의 설명에서, 본 발명의 특징은, 예를 들어, 자기 기록 및 재생 시스템의 ML 검출기에서 사용되는 채널 출력 샘플 시퀀스를 수신하는 검출기 내에서 사용되는 MLSD 알고리즘을 참조하여 제공된다. 그러나, 알려진 바와 같이, 비터비 알고리즘은 콘볼루션 디코딩 시스템과 같은 많은 상이한 응용 분야에서 사용될 수 있다. 따라서, 본 발명은 본 명세서에서 기술한 바와 같은 ML 검출기와 디코더에 한정되지 않고, VA가 사용되는 어떠한 응용 분야에서도 사용될 수 있다.

도 3은 본 발명의 일 실시예를 이용하는 VA 기반 검출기(300)를 도시하는 블럭도이다. 도 3에 도시하는 바와 같이, 도시하지 않은 처리기 제어를 받는 검출기 시스템(300)은 분기 메트릭 계산(branch metric calculation : BMC) 처리기(302), 옵션(optional) 정규화 처리기(304), ACS(add-compare-select) 처리기(306), 상태 메트릭 메모리(308), 경로 메모리(309), 최우 결정(maximum likelihood decision : MLD) 처리기(310), 옵션 심볼 디코더(312)를 포함한다.

BMC 처리기(302)는 통신 채널로부터 잡음성 채널 출력 데이터(y_n)를 수신하고, 예를 들어, 수학식 1에서 주어진 계산식을 이용하여 각 상태에 대한 분기 메트릭을 계산한다. 옵션 정규화 처리기(304)는 분기 메트릭과 심볼 값(y_n)을 수신하여 사전 정의된 알고리즘에 따라 수신된 심볼 및/또는 분기 메트릭 값을 정규화한다. 이들 정규화 알고리즘은 이 기술 분야에서 잘 알려져 있으며 이상적인 채널 분기 메트릭 값을 사용하는 통신 채널 응답의 추정에 의한 정규화에 기반을 둔다. 이 기술 분야에서 알려진 바와 같이, 옵션 정규화 처리기(304)의 정규화 프로세스는 BMC 처리기(302) 내에 포함될 수도 있다.

본 발명에 따른 ACS 처리기(306)는 이전 상태 메트릭 값을 사용하여 갱신된 현재 상태 메트릭 값을 계산한다. 상태 메트릭 메모리(308)는 상태 메트릭 갱신 계산을 위해 ACS 처리기(306)에 의해 처리된 이전 및 현재 상태 메트릭 값을 포함한다. 경로 메모리(309)는 상태들 사이에서 선택된 경로 세그먼트(path segment)에 관한 정보를 포함한다.

최우 결정 MLD 처리기(310)는 생존 경로 정보는 물론 과거 및 현재 상태에 대한 정보를 수신한다. 처음에는, 초기의 채널 출력 샘플로부터 사전 정의된 반복 횟수, 예를 들어, 10회 동안 결정이 지연된다. 트렐리스 구조도를 통해 시간 n에서 현재 상태의 최우 경로가 시간 n-10에서 그 상태의 초기 채널 출력 샘플에 대응하는 심볼에 대한 결정을 위해 결정된다. 따라서, 전술한 예에서 수신된 10번째 심볼에서, 첫 번째 심볼에 대한 결정이 이루어진다. 다음 채널 출력 샘플 천이에서, 또는 11번째 심볼이 수신되는 경우에, 두 번째 심볼에 대한 결정이 이루어진다. 당업자에게 명확한 바와 같이, 심볼 결정 기법에 대한 많은 변경이 본 발명의 사상 내에서 이루어질 수 있다.

옵션 심볼 디코더(312)는 MLD 처리기로부터 결정된 심볼을 수신하고, 이들 심볼을 디코딩하여 데이터 스트림(d_n)을 제공한다. 이러한 심볼 디코더(312)는, 예를 들어, 심볼 스트림의 실행 길이(run-length) 및/또는 에러 정정 복호화를 포함할 수 있다. 이들 부호화 및 복호화 방식은 비트 에러를 정정하기 위한 데이터 스트림(d_n)내에서 에러 가능성을 더 감소시킨다. 당업자에게 명확한 바와 같이, 본 발명은 심볼 스트림을 제공하는 데 사용되는 엔코딩 및 디코딩 방식에 의해 제한되지 않는다.

수신된 채널 출력 샘플 시퀀스(y_n)는, 예를 들어, 자기 매체 독출(magnetic media reading : MMR) 소자(320)에 의해 제공될 수 있다. MMR 장치(320)는 자기 매체(328)로부터 복호화된 데이터를 수신하는 헤드(326)와, 헤드(326)로부터의 아날로그 신호를 샘플링하는 샘플링 처리기(324) 및 유한 임펄스 응답 필터(finite impulse response filter : FIR)일 수 있는 필터(322)를 포함한다.

이중 상태 트렐리스 아키텍쳐

본 발명은 단일 트렐리스 상태도로부터 구한 이중 상태 트렐리스에 따라 구한 상태 메트릭 갱신을 사용한다. 예시적인 실시예에서, M이 2인 식으로 입력 알파벳이 2진수라고 가정하며, 당업자에게 명확한 바와 같이, 본 발명은 이에 한정되지 않고 2 보다 큰 임의의 M에 대해 확장될 수 있다.

수신된 시퀀스는 수학식 3에서 주어진 바와 같이, N차 채널 길이 메모리를 갖는 채널 응답 다항식 H(D)로 나타낼 수 있다.

도 4는 수학식 3으로 주어진 바와 같은 채널 응답 다항식 H(D) = 1＋D에 대한 종래의 두 가지 상태 트렐리스도를 도시하고 있다. 예시적인 실시예에서 M이 2로 주어지는 경우, N은 1이다. 그들 상태에 이어지는 다음에 각 숫자는 시간 n과 시간 n＋1에서의 수신된 입력 시퀀스 값을 나타낸다. 시간 n에서, 이전 상태 t="0" 또는 "1"이 n＋1에서 현재 상태 "0"또는 "1"로 천이된다. 천이 화살표(401)는 시간 n과 n＋1 사이에서의 각 상태 천이를 나타낸다. 천이 화살표(401)와 연관된 숫자는 주어진 천이에 대한 이상적인 채널 출력 샘플을 나타낸다. 수학식 2가 주어지면, 시간 n＋1에서 현재 상태 "0"에 대한 상태 메트릭은 수학식 2a로 주어진다.

도 5는 수학식 3으로 주어진 바와 같이, 가정된 채널 응답 다항식 H(D) = 1＋D＋0*D²에 대해 정의된 본 발명에 따른 네 가지 상태 트렐리스 구조도를 도시한다. 이중 상태 트렐리스 구조는 일반적으로 채널 응답 다항식의 마지막 항이 "0"의 계수(h_N)를 갖는 것으로 가정하고 보통의 경우에서 상태의 수를 두 배로 함으로써 전반적으로 형성된다. 전술한 바와 같이, 그들 상태에 이어지는 써클(circle) 내의 숫자는 수신된 입력 시퀀스 값을 나타낸다. 예를 들어, 도 5를 참조하면, 상태 트렐리스의 좌측 상에서의 시퀀스 "10"은 각각 시간 n-1과 n에서 입력 "0"에 의해 진행되는 입력 "1"을 나타낸다. 천이 화살표(501)는 시간 n과 n+1 사이에서의 각각의 상태 천이를 나타낸다. 각각의 천이 화살표(501)와 연관된 레이블 값은 천이와 연관된 이상적인 채널 출력 값을 보인다. 예시를 위해, 이전의 상태 "11"과 "1" 및 현재 상태 "10"과 "11"은 상태 쌍(503)을 형성한다. 마찬가지로, 이전 상태 "0"과 "10" 및 현재 상태 "0"과 "1"은 상태 쌍(504)을 형성한다.

마지막 계수가 0의 계수를 갖는 채널 다항식H(D)의 경우에 대해서는, 각기 동일한 종료 상태를 갖는 두 천이에 대한 분기 메트릭이 동일한데, 이는 두 시작 상태가 가장 오래된 비트 위치에서만 상이하기 때문이다. 이와 같은 채널 다항식H(D)의 경우에서, H(D)가 N차 다항식일지라도, 도 3의 검출기는 2^N+1상태를 갖는다. 따라서, H(D)가 h_N=0 이기 때문에 트렐리스도 내에는 이중 상태가 있고, 이러한 구조는 하나의 상태에서 분기 메트릭 종료를 동일하게 한다. 도 5의 이중 상태 트렐리스도에 대해서, 검출기는 상태 k(SM_k)에서 상태 메트릭을 각각이 수학식 4로 주어진 바와 같은 각각의 분기 메트릭과 조합된 두 개의 이전 상태 메트릭(SM_i와 SM_j) 사이에서의 최소값으로서 계산할 수도 있다.

따라서, 수학식 4로 주어진 바와 같은 SM_i＋BM_i,k와 SM_j＋BM_j,k사이에서 최소인 상태 k로의 천이에 대한 시간 n에서의 두 가지 가능한 상태 메트릭 사이의 최소값은 두 가지 이전 상태 메트릭 SM_i와 SM_j사이에서의 최소값을 계산한 다음 각각의 분기 메트릭을 가산함으로써 선택될 수 있다. 이 경우에, 검출기는 분기 메트릭 값을 각각의 이전 상태 메트릭(SM_j, SM_k)에 가산하기까지 대기할 필요로 없는데, 이는 BM_i,k가 임의의 n에 대하여 BM_j,k(BM_k로 정의됨)와 동일하기 때문이다. 그러므로, 검출기는 수학식 5에서 정의된 바와 같이 수학식 4의 반복적인 동작을 수행한다.

예를 들면, 도 5의 우측 상에서 현재 상태가 "0"인 경우, 이전 상태로부터 두 경로(502)는 각각 "0"과 "10"이며, 각 경로는 동일한 분기 메트릭과 이상적인 채널 출력 샘플 값 0을 갖는다. 일반적으로, 도 5의 이중 상태 트렐리스 아키텍쳐에서, 각 상태 "k₁"에 대하여 동일한 시작 상태(originating state) "i" 및 "j"를 갖는 관련 상태 "k₂"가 있다. 이들 상태에서 이루어진 판단은 동일한데, 이는 이들 모두가 동일한 시작 상태 메트릭을 비교하기 때문이다. 다른 현재 상태에 대하여 유사한 관계를 갖는데, 이는 이중 상태 트렐리스에서 시간 n-1에서 가장 오래된 이전 입력 값이 각 상태에 대한 현재 상태 천이의 분기 메트릭을 계산하는데 기여하지 못하기 때문이다. 따라서, 2^N결정은 2^N의 경로 메모리(309)(도 3)에 대한 경로 메모리 폭(width)을 필요로 하는 이중 상태 트렐리스 아키텍쳐 내에 존재할 수 있다.

현재 상태에서 VA의 "선택" 동작이 현재 상태 "0"으로의 이동을 결정하고 이전 상태 "0"으로부터 다른 경로를 선택하는 대신에 이전 상태 "10"으로부터 하나의 경로를 선택하는 경우, 선택 동작과 동일한 경로 결정이 현재 상태 "1"에 대해서 이루어질 것이다. 현재 상태 "10"과 "11"의 다른 상태 쌍(503)에 대해서도 동일한 동작이 제공된다. 따라서, 이중 상태 구조 내에는 상태 쌍, 예를 들어 상태 쌍(503, 504)이 있는데, 각각은 ACS의 선택 동작에 대하여 동일한 결정을 공유하는 피쳐를 갖는다. 본 발명에 따른 이중 상태 아키텍쳐를 사용함으로써, 수학식 5의 "비교" 동작은 회로에 의해 수학식 5의 "가산" 동작과 동시에 수행될 수 있다. 당업자에게 명확한 바와 같이, 이와 같은 이중 트렐리스 구조도의 특성은 m의 경우로 확장될 수 있다.

ACS 회로

도 6은 수학식 5의 동작을 구현할 수 있는 본 발명에 따른 예시적인 ACS 회로를 도시하고 있으며, 이제 이 구조가 설명될 것이다. ACS 회로(602)는 가산기(610, 612), 비교기(614) 및 비교기(614)의 출력 신호에 의해 제어되는 2-1 멀티플렉서일 수 있는 선택 회로(616)를 사용한다. 도 6의 예시적인 ACS의 신호 시퀀스는 도 5의 실시예에 대해서 기술되며, 여기서 상태 k의 갱신된 상태 메트릭(SM_k)이 계산된다.

도 6에 도시한 바와 같이, 가산기(610)는 i번째 상태(SM_i)의 상태 메트릭과 분기 메트릭(BM_i,k=BM_j,k)을 수신하고 조합하여, 제 1 갱신된 상태 메트릭을 제공하며, 가산기(612)는 j번째 상태 메트릭과 대응하는 분기 메트릭(BM_j,k=BM_i,k)을 수신하고 조합하여 제 1 갱신된 상태 메트릭을 제공한다. 상태 메트릭 값(SM_i, SM_j)은 비교기(641)에서 비교되고, 비교기(641)는 상태 메트릭 값들 중 최소값을 갖는 하나를 나타내는 최소 표시기 신호(D_k)를 제공한다. 갱신된 제 1 및 제 2 갱신 상태 메트릭 값과 최소 표시기 신호(D_k)는 선택 회로(616)에 제공되고, 선택 회로(616)는 최소 표시기 신호(D_k)에 응답하여 제 1 및 제 2 갱신된 상태 메트릭 값중 최소 상태 메트릭 값을 새로운 상태 메트릭 값(SM_k)으로서 제공한다.

그러나, 각 숫자 상태 "k_i"에 대해 동일한 시작 상태 "i"와 "k"를 갖는 관련된 상태 "k₂"가 있으므로, 도 5의 이중 상태 트렐리스 아키텍쳐는 이와 다른 실시예가 도 6에 도시한 ACS 회로를 통해 회로 구성 요소를 감소시킬 수 있음을 보여 주는데, 이는 상태 "k₁"과 "k₂"의 두 갱신된 상태 메트릭이 동일한 구간 내에서 계산될 수 있기 때문이다. 도 7은 본 발명의 이와 다른 실시예에 따른 다른 예시적인 ACS 회로(702)를 도시하고 있다. ACS 회로(702)는 가산기(710, 712, 714, 716), 비교기(704) 및 비교기(704)의 출력 신호에 의해 제어되는 2-1 멀티플렉서일 수 있는 선택 회로(706, 708)를 구비한다. 도 7의 예시적인 ACS의 신호 시퀀스는 도 5의 실시예에 대해서 기술되며, 여기서 상태 "k₁"과 "k₂"의 갱신된 상태 메트릭 SM_k1과 SM_k2가 각기 동시에 계산된다.

도 7에 도시한 바와 같이, 가산기(710, 712)는 i번째 상태 메트릭 SM_i및 j번째 상태 메트릭 SM_j을 각각 수신하고 분기 메트릭(BM_i,k1=BM_j,k1)과 조합하여 제 1 및 제 2 갱신된 상태 메트릭을 제공하며, 가산기(714, 716)는 i번째 상태 메트릭 SM_i과 j번째 상태 메트릭 SM_j을 각각 수신하고 분기 메트릭(BM_i,k2=BM_j,k2)과 조합하여 제 3 및 제 4 갱신된 상태 메트릭을 각각 제공한다. 상태 메트릭 값 SM_i와 SM_j는 비교기(704)에서 비교되고, 비교기(704)는 상태 메트릭 값들(SM_i와SM_j)중 최소값을 갖는 하나를 나타내는 최소 표시기 신호(D_k)를 제공한다. 제 1 및 제 2 갱신된 상태 메트릭 값과 최소 표시기 신호(D_k)는 선택 회로(706)에 제공되고, 선택 회로(706)는 최소 표시기 신호(D_k)에 응답하는 제 1 및 제 2 갱신된 상태 메트릭 값중 최소의 상태 메트릭 값을 새로운 상태 메트릭 값(SM_k1)으로서 제공한다. 제 3 및 제 4 갱신된 상태 메트릭 값과 최소 표시기 신호(D_k) 역시 선택 회로(708)에 제공되고, 선택 회로(708)는 최소 표시기 신호(D_k)에 응답하는 제 1 및 제 2 갱신된 상태 메트릭 값중 최소의 상태 메트릭 값을 새로운 상태 메트릭 값으로서 제공한다.

예를 들어, 도 4의 예에 도시된 바와 같은 통상적인 트렐리스 구조의 상태 메트릭 계산에서, 분기 및 상태 메트릭이 트렐리스 내의 매 천이에 대해서 계산되어야 할 필요가 있다. 하지만, 도 5에 도시된 바와 같은 이중 상태 트렐리스 구조 내에서는 그럴 필요가 없다. 전술한 바와 같이, 현재 상태의 쌍은 계산 동작을 반복하게 되어, 이중 상태 트렐리스 구조 내에서 천이의 절반에 대해서만 계산 동작을 하면 된다.

본 발명에 따른 ACS 회로를 사용하는 검출 회로의 구현에서, 이중 상태 트렐리스 구조는 가산기와 상태 메트릭 레지스터 및 멀티플렉서의 수가 도 2에 도시된 ACS 회로에 비해서 두 배이다. 집적 회로(integrated circuit : IC) 상에서 구현되는 경우, 이들 부가적인 회로 요소는 검출기의 실제 점유 면적을 약 50% 정도 증가시킬 수도 있다. 그러나, 검출기는 전형적으로 IC 회로의 작은 부분에 불과하기 때문에, 많은 원격 통신 IC 응용 분야에서 대한 실제 점유 영역의 증가는 무시될 수 있다. 그러나, 당업자에게 명확한 바와 같이, 본 발명에 따른 이중 상태 트렐리스 구조를 사용하는 검출기는 더 빠르게 처리량을 처리할 수 있어, 도 2에 도시한 종래 기술의 ACS 회로보다 속도를 약 33% 더 빠르게 할 수 있다.

통상적인 ACS 회로와 이중 상태 ACS 회로의 비교

도 8과 도 9는 예시적인 채널에 대하여 통상적인 것과 이중 트렐리스 구조에 대한 비교 예를 함께 도시한다. 도 8은 이진 1＋D 채널에서 비터비 알고리즘을 사용하는 검출기의 종래 기술의 통상적인 트렐리스 구조를 도시하고 있다. 도 9는 이진 1＋D＋0*D²채널에서 비터비 알고리즘을 사용하는 검출기의 본 발명에 따른 이중 트렐리스 구조를 도시하고 있다. 수신된 채널 출력 샘플 값(y_n)은 각 시간 n(n = 1, 2, ..., 5)에 대하여 부여되어 있다. 도 8 및 도 9의 전형적인 채널에 대해서, 각 경로 세그먼트(segment)에 이어서 부여된 분기 메트릭 값이 정규화된 수학식 6을 이용하여 계산된다.

여기서 y'는 이상적인 채널 출력 값이다. 도 8과 도 9에서, 실선은 생존 경로를 나타내고, 점선은 심볼 결정까지 유지된 경로를 나타내며, 대시 선은 폐기된 경로를 나타낸다.

생존 경로 세그먼트 메트릭 값을 비교하면, 도 8 및 도 9의 경로 결정 프로세스는 동일한 것으로 보이지만, 도 8의 통상적인 트렐리스 구조와 도 9의 이중 상태 트렐리스 구조의 비교는 대기 시간(latency)이 부가됨을 나타낸다. 예를 들면, 통상적인 트렐리스 구조가 시간 n=4에서 메트릭 -0.775인 경로 위의 메트릭 -1.3인 경로를 선택하는 선택 동작 결정을 포함하는 반면, 본 발명에 따른 이중 상태 트렐리스 구조를 사용하는 검출기는 n=5에서 동일한 결정을 한다. 이 대기 시간은 정정될 수도 있는데, 이는 결정을 위해 현재 샘플 값을 알 필요가 없기 때문이다. 또한, n=0인 초기 단계에서 이중 상태 트렐리스 구조는 무시될 수 있는 임의 결정을 시작할 수 있다.

비록 본 명세서에서 소정의 특정 실시예를 참조하여 도시하고 기술하였지만, 그럼에도 불구하고 본 발명은 도시한 상세한 설명에 국한되는 것으로 의도되지 않아야 한다. 또한, 본 발명의 사상을 이탈하지 않고 특허 청구범위와 동일한 범주 및 범위 내에서 상세한 설명의 다양한 변형이 이루어질 수 있다.

이상 설명한 바와 같이 본 발명에 따르면, 이중 상태(double-state) 트렐리스 구조의 ACS(add-compare-select) 기능을 사용함으로써, 비터비 알고리즘을 사용하는 디코더의 ACS 회로에 대한 속도를 증가시킬 수 있는 효과가 있다.

Claims

ACS(add-compare-select) 회로를 구비하되, 상기 ACS 회로는 이전 상태의 세트로부터 현재 상태의 현재 상태 메트릭 값을 제공하는 위한 ACS 기능을 수행하며, 각 이전 상태는 각각의 이전 상태 메트릭 값을 갖는 ACS 회로에 있어서,

다수의 ACS 회로 ― 다수의 조합 회로의 각각이 이전 상태의 상기 세트중 대응하는 하나의 각 이전 상태 메트릭 값을 수신하고, 상기 대응하는 하나의 각 이전 상태 메트릭 값과 상기 이전 상태의 세트중 각 하나와 상기 현재 상태 사이에서의 천이를 위해 정의된 각각의 분기 메트릭 값(branch metric value)을 조합하여 각각의 갱신된 상태 메트릭 값을 제공하며 상기 각 분기 메트릭 값은 서로 동일함 ― 와,

상기 이전 상태 세트의 각 이전 상태 메트릭 값을 비교하여 최소값을 갖는 하나의 이전 상태 메트릭 값을 결정하고 대응하는 선택 신호를 제공하는 비교 회로와,

상기 선택 신호에 응답하여, 상기 하나의 최소 이전 상태 메트릭 값을 수신하는 상기 다수의 조합 회로의 상기 하나에 의해 제공되는 상기 각각의 갱신된 상태 메트릭 값을 상기 현재 상태 메트릭 값으로서 선택하는 멀티플렉서를 포함하되,

상기 ACS 회로가 이중 상태 트렐리스 구조(double state trellis structure)로 구현되는

ACS 회로.
제 1 항에 있어서,

상기 다수의 조합 회로가 제 1 가산 회로 및 제 2 가산 회로이고, 상기 이전 상태의 세트는 제 1 이전 상태 및 제 2 이전 상태를 포함하며, 상기 제 1 가산 회로가 상기 제 1 이전 상태의 상기 각각의 이전 상태 메트릭 값과 상기 분기 메트릭 값을 조합하고, 상기 제 2 가산 회로가 상기 제 2 이전 상태의 상기 각각의 이전 상태 메트릭 값과 상기 분기 메트릭 값을 조합하며, 상기 비교기가 상기 제 1 및 제 2 이전 상태의 상기 각각의 이전 상태 메트릭 값을 비교하여, 상기 하나의 최소 이전 상태 메트릭 값을 검출하고, 상기 멀티플렉서가 상기 결정된 최소 값인 상기 각각의 이전 상태 값을 수신하는 상기 제 1 및 제 2 가산 회로중 상기 대응하는 하나에 의해 제공된 상기 하나의 갱신된 이전 상태 메트릭을 선택하는 ACS 회로.
제 1 항에 있어서,

상기 현재 상태는 제 1 현재 상태 및 제 2 현재 상태중 하나이고, 상기 ACS 회로가 상기 제 1 및 제 2 현재 상태의 상기 각각의 상태 메트릭 값을 제공하며,

상기 다수의 조합 회로가,

제 1 조합 회로 세트와 제 2 조합 회로 세트를 더 포함하되, 상기 제 1 조합 회로 세트의 각각이 상기 각각의 이전 상태 메트릭 값과 각각의 제 1 분기 메트릭 값을 조합하여, 상기 각각의 제 1 갱신된 상태 메트릭 값을 제공하고, 각 제 1 분기 메트릭 값은 상기 각각의 이전 상태와 상기 제 1 현재 상태 사이에서 정의되고 서로 동일하며, 상기 각각의 제 2 조합 회로 세트의 각각이 각각의 이전 상태 메트릭 값과 각각의 제 2 분기 메트릭 값을 조합하여 각각의 제 2 갱신된 상태 메트릭 값을 제공하며, 각 제 2 분기 메트릭 값이 상기 각각의 이전 상태와 상기 제 2 현재 상태 사이에서 정의되고 서로 동일하며,

상기 멀티플렉서가 상기 선택 신호에 응답하여, 상기 하나의 최소 이전 상태 메트릭 값을 수신하는 다수의 조합 회로중 각각의 대응하는 회로에 의해 제공된 하나의 제 1 갱신된 상태 메트릭 값과 하나의 제 2 갱신된 상태 메트릭 값을 상기 제 1 및 제 2 현재 상태 메트릭으로 각각 선택하는 ACS 회로.
제 3 항에 있어서,

상기 제 1 조합 회로 세트는 제 1 이전 상태 메트릭 값을 수신하는 제 1 가산 회로와 제 2 이전 상태 메트릭 값을 수신하는 제 2 가산 회로이고, 상기 제 2 조합 회로 세트는 상기 제 2 이전 상태 메트릭 값을 수신하는 제 3 가산 회로와 상기 제 1 이전 상태 메트릭 값을 수신하는 제 4 가산 회로이며, 상기 제 1 가산 회로와 상기 제 2 가산 회로의 각각은 제 1 및 제 2 이전 상태 메트릭 값들 중 각각의 상태 메트릭 값과 상기 제 1 및 제 2 이전 상태에서 상기 제 1 현재 상태로의 상기 천이와 각각 연관된 상기 분기 메트릭 값을 조합하며, 상기 제 3 가산 회로와 제 4 가산 회로의 각각은 상기 제 1 및 제 2 이전 상태 메트릭 값중 상기 각각의 상태 메트릭 값과 상기 제 1 및 제 2 이전 상태에서 상기 제 2 현재 상태로의 상기 천이와 각각 연관된 상기 분기 메트릭 값을 조합하고,

상기 비교 회로는 상기 제 1 이전 상태 메트릭 값을 상기 제 2 이전 상태 메트릭 값과 비교하며,

상기 멀티플렉서는 제 1 및 제 2 멀티플렉서를 포함하되, 상기 제 1 멀티플렉서는 상기 제 1 및 제 2 가산 회로의 상기 각각의 제 1 갱신된 상태 메트릭 값을 수신하며, 상기 제 2 멀티플렉서는 상기 제 3 및 제 4 가산 회로의 상기 각각의 제 2 갱신된 상태 메트릭 값을 수신하고,

상기 제 1 멀티플렉서는 상기 최소값을 갖는 하나의 이전 상태 메트릭 값을 수신하는 상기 제 1 및 제 2 가산 회로중 하나에 대응하는 상기 제 1 갱신된 상태 메트릭 값을 상기 제 1 현재 상태 메트릭 값으로서 수신하며, 상기 제 2 멀티플렉서는 상기 최소값을 갖는 하나의 이전 상태 메트릭 값을 수신하는 상기 제 3 및 제 4 가산 회로중 하나에 대응하는 상기 제 2 갱신된 상태 메트릭 값을 상기 제 2 현재 상태 메트릭 값으로서 수신하는 ACS 회로.
제 1 항에 있어서,

상기 ACS 회로는 채널 출력 샘플을 수신하는 시퀀스 검출 회로에 포함되고, 각 채널 출력 샘플은 심볼과 이전 및 현재 상태 세트의 연속적인 쌍의 특징을 갖는 채널 출력 샘플의 연속적인 시퀀스 쌍으로부터 구해지며, 상기 시퀀스 검출 회로는,

사전 정의된 구간 내에서 수신된 상기 채널 출력 시퀀스의 일부분에서의 하나의 수신된 채널 출력 샘플에 따라 각각의 이전 상태로부터 상기 현재 상태로의 각 천이에 대한 분기 메트릭 값을 계산하되, 상기 하나의 수신된 채널 출력 샘플은 상기 현재 상태에 대응하는 분기 메트릭 계산 수단과,

상기 연속적인 이전 상태 세트중 각 이전 상태의 각각의 이전 상태 메트릭 값을 저장하는 상태 메트릭 메모리와,

다수의 경로 선택을 저장하되, 각각의 경로 선택은 상기 선택 신호에 대응하는 이전 상태 세트와 현재 상태의 연속적인 쌍들 사이에서 반복적으로 결정되는 경로 메모리와,

상기 하나의 수신된 채널 출력 샘플 이전에 수신된 상기 채널 출력 샘플 시퀀스의 상기 일부분에서의 초기 채널 출력 샘플에 대응하는 데이터 심볼 값을 검출하되, 상기 현재 상태에 대응하는 상기 하나의 수신된 채널 출력 샘플에 대해 결정된 상기 경로 선택에서 다수의 경로 선택 종료의 시퀀스에 의거하여 상기 데이터 심볼 값을 검출하는 검출 수단을 더 포함하는 ACS 회로.
제 5 항에 있어서,

상기 시퀀스 검출 회로가 자기 기록 채널로부터 변조 부호화된 데이터를 수신하고 상기 변조 부호화된 데이터를 복조하여 상기 수신된 채널 출력 샘플 시퀀스를 제공하는 자기 매체 역판독(readback) 소자 내에 포함되는 ACS 회로.
제 5 항에 있어서,

상기 ACS 회로는 원격 통신 채널로부터 변조 부호화된 데이터를 수신하는 원격 통신 수신기의 디코더 내에 포함되되, 상기 원격 통신 수신기는 상기 변조된 부호화된 데이터를 복조하여, 상기 수신된 채널 출력 샘플 시퀀스로서 엔코딩된 데이터를 제공하고 상기 부호화된 데이터는 상기 심볼 시퀀스로서 콘볼루션 부호화되며 상기 ACS 회로는 상기 콘볼루션 부호화된 데이터를 디코딩하는 ACS 회로.
제 1 항에 있어서,

상기 이중 상태 트렐리스 구조가 상태 트렐리스 구조에 관련되며, 상기 상태 트렐리스 구조가 현재 상태를 포함하고 대응하는 수의 상태 천이를 갖는 상태의 세트로부터 구해지며, 상기 이중 상태 트렐리스 구조는 상기 상태 트렐리스 구조의 상기 상태 세트중 각 상태마다 상기 대응하는 수의 상태 천이와 동일한 상기 현재 상태에 대한 상태 천이 수를 갖는 상기 이중 상태 트렐리스 구조의 상기 상태 트렐리스 구조에 관련되는 ACS 회로.
제 8 항에 있어서,

상기 이중 상태 트렐리스 구조의 상기 수신된 채널 출력 샘플 시퀀스가 채널 길이 메모리 N을 구비하고 H(D) = h₀+ h₁D + ．．．+ h_N-1D^N-1+ h_ND^N(여기서, h_N=0)으로 정의된 채널 응답 다항식(channel response polynomial)으로 표현되는 ACS 회로.
제 9 항에 있어서,

상기 이중 상태 트렐리스 구조는 각 심볼이 이진 값을 나타내며 H(D) = h₀+ h₁D + ．．．+ h_N-1D^N-1로 정의된 채널 응답 다항식을 갖는 상기 상태 트렐리스 구조에서의 다수의 상태 세트가 증가되어 H(D) = h₀+ h₁D + ．．．+h_N-1D^N-1+0D^N로서 정의된 상기 채널 응답 다항식을 갖는 상기 이중 상태 트렐리스 구조를 형성하도록 구현되는 ACS 회로.
분기 메트릭 계산기를 포함하되, 상기 분기 메트릭 계산기가 채널 출력 샘플 시퀀스의 수신된 채널 출력 샘플에 의거하여 이전 상태 세트의 각각으로부터 현재 상태 k(k는 정수)로의 각 천이마다 각각의 분기 메트릭 값(BM_k)을 계산하며, 상기 이전 상태 세트의 각각이 이전 상태 메트릭 값(SM_t)을 가지며, t가 정수인 최우 시퀀스 검출기(maximum likelihood sequence detector)에 있어서,

ACS(add-compare-select) 기능을 수행하여 현재 상태 k의 현재의 상태 메트릭 값(SM_k)을 제공하는 회로를 포함하되, 상기 회로가 상기 이전 상태 세트에 대한 이중 상태 트렐리스 구조로 구현되고, 상기 이중 상태 트렐리스 구조가 현재 상태 k로 천이하는 이전 상태 세트중 M개의 이전 상태(M은 정수)로 이루어진 적어도 하나의 세트에서 정의되며, 상기 현재 상태 k로의 상기 각각의 천이는 서로 동일한 각각의 분기 메트릭 값(BM_k)을 가지며, 상기 회로가를 계산하는 처리기

를 포함하는 최우 시퀀스 검출기.
제 11 항에 있어서,

상기 이중 상태 트렐리스 구조가 M=2인 이진(binary) 경우에서 정의되고 상기 현재 상태(k)가 X개의 현재 상태 중 하나로 정의되며, 상기 X개의 현재 상태의 제 1 쌍에서 상기 제 1 쌍의 각각은 서로 동일한 M개의 이전 상태의 상기 하나의 세트로부터 각각의 분기 메트릭 값을 가지며, 상기 X개의 현재 상태의 제 2 쌍에서 각각은 상기 M개의 이전 상태의 하나의 세트를 포함하지 않는 M개의 이전 상태의 다른 세트로부터 각각의 분기 메트릭 값을 각각 갖고, 상기 제 2 쌍의 상기 각각의 분기 메트릭 값은 서로 동일한 최우 시퀀스 검출기.
제 12 항에 있어서,

상기 처리기가 상기 X개의 현재 상태의 상기 제 1 및 제 2 쌍 중 적어도 하나에 대한 상기 X개의 현재 상태의 각각의 현재 상태 메트릭 값을 병렬로 계산하는 처리기인 ACS 회로.
ACS(add-compare-select) 기능을 수행하여 이전 상태의 세트로부터 현재 상태의 현재 메트릭 값을 제공하되, 각각이 각각의 이전 상태 메트릭 값을 갖는 방법에 있어서,

① 상기 이전 상태 세트의 각각의 이전 상태 메트릭 값과 상기 이전 상태 세트중 각각의 상태와 상기 현재 상태 사이에서의 천이를 위해 정의된 각각의 분기 메트릭 값을 조합하여 각각의 갱신된 상태 메트릭 값을 제공하되, 각 분기 메트릭 값이 서로 동일한 단계와,

② 상기 이전 상태 세트의 각 이전 상태 메트릭 값을 비교하여 최소값을 갖는 하나의 이전 상태 메트릭 값을 결정하는 단계와,

③ 최소 값을 갖는 하나의 이전 상태 메트릭 값에 대응하는 선택 신호를 제공하는 단계와,

④ 상기 선택 신호에 응답하여, 상기 하나의 최소값을 갖는 이전 상태 메트릭 값과 상기 각각의 분기 메트릭 값의 조합으로부터 제공되는 상기 각각의 갱신된 상태 메트릭 값을 상기 현재 상태 메트릭 값으로 선택하는 단계를

포함하는 ACS 기능 수행 방법.
ACS(add-compare-select) 기능을 수행하여 이전 상태의 세트로부터 현재 상태 k(k는 정수)의 현재 상태 메트릭 값을 제공하되, 상기 이전 상태 세트의 각각이 각각의 이전 상태 메트릭 값(SM_t,t는 정수)을 갖는 방법에 있어서,

① 채널 출력 샘플 시퀀스의 수신된 채널 출력 샘플에 의거하여 상기 이전 상태 세트의 각각으로부터 현재 상태 k로의 각 천이마다 각각의 분기 메트릭 값(BM_k)을 계산하고,

② 상기 이전 상태 세트에 대한 이중 상태 트렐리스 구조를 구현하되, 상기 이중 상태 트렐리스 구조가 현재 상태 k로 천이하는 이전 상태 세트중 M개의 이전 상태(M은 정수)로 이루어진 적어도 하나의 세트에서 정의되고, 상기 현재 상태 k로의 상기 각각의 천이는 서로 동일한 각각의 분기 메트릭 값(BM_k)을 가지며,

③로 상기 현재 상태 메트릭 값(SM_k)을 계산하는 단계를

포함하는 ACS 기능 수행 방법.