[go: up one dir, main page]

KR100566745B1 - 레이턴시를 줄인 ｓｉｓｏ 모듈 - Google Patents

레이턴시를 줄인 ｓｉｓｏ 모듈 Download PDF

Info

Publication number
KR100566745B1
KR100566745B1 KR1020027014808A KR20027014808A KR100566745B1 KR 100566745 B1 KR100566745 B1 KR 100566745B1 KR 1020027014808 A KR1020027014808 A KR 1020027014808A KR 20027014808 A KR20027014808 A KR 20027014808A KR 100566745 B1 KR100566745 B1 KR 100566745B1
Authority
KR
South Korea
Prior art keywords
soft
siso
tree structure
module
operations
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
KR1020027014808A
Other languages
English (en)
Other versions
KR20030005322A (ko
Inventor
비어럴피터에이
처그케이스엠
디모우조지오스디
씬비분푼삭
Original Assignee
유니버시티 오브 써던 캘리포니아
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 유니버시티 오브 써던 캘리포니아 filed Critical 유니버시티 오브 써던 캘리포니아
Publication of KR20030005322A publication Critical patent/KR20030005322A/ko
Application granted granted Critical
Publication of KR100566745B1 publication Critical patent/KR100566745B1/ko
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
    • H03M13/3905—Maximum a posteriori probability [MAP] decoding or approximations thereof based on trellis or lattice decoding, e.g. forward-backward algorithm, log-MAP decoding, max-log-MAP decoding
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/29—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
    • H03M13/2957—Turbo codes and decoding
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
    • H03M13/3966—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes based on architectures providing a highly parallelized implementation, e.g. based on systolic arrays
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/65—Purpose and implementation aspects
    • H03M13/6572—Implementations using a tree structure, e.g. implementations in which the complexity is reduced by a tree structure from O(n) to O (log(n))

Landscapes

  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Error Detection And Correction (AREA)
  • Detection And Prevention Of Errors In Transmission (AREA)
  • Detection And Correction Of Errors (AREA)

Abstract

인코딩된 신호(예컨대, 터보 인코딩된 신호, 블록 인코딩된 신호 등)의 디코딩은 소프트 정보를 산출하기 위하여 수신된 인코딩된 신호를 복조(13)하고, 하나 이상의 소프트-인/소프트-아웃(SISO) 모듈에서 반복적으로 처리함으로써, 수행될 수 있다. SISO 모듈(11) 중 적어도 하나는 트리 구조를 사용해서 순방향 및 역방향 상태 메트릭을 계산한다. 더 일반적으로, 반복 검출은 모듈 - 모듈의 소프트 인버스는 모듈의 격자 표현에 순방향-역방향 알고리즘을 실행함으로써 계산될 수 있음 - 의 하나 이상의 출력에 대응하는 입력 신호(11)를 수신하고, 트리 구조를 사용하여 수신된 입력 신호의 순방향 및 역방향 상태 메트릭을 계산하여 모듈의 소프트 인버스를 결정함으로써, 수행된다.

Description

레이턴시를 줄인 ＳＩＳＯ 모듈{REDUCED-LATENCY SOFT-IN/SOFT-OUT MODULE}
관련 출원
이 출원은 2000년 5월 3일에 제출된 미국 특허 가출원 번호 제60/201,583호(이 가출원은 참조로서 본 명세서의 일부를 이룸)의 이익을 주장한다.
발명의 출처
본 명세서에 기재된 연구 개발은 미국 국립 과학 재단(NSF; National Science Foundation)에 의해 입증되어, 허가 번호 제NCR-CCR-9726391호를 부여받았다. 미국 정부는 주장된 본 발명에 대해 일정한 권리를 가질 수 있다.
발명의 기술 분야
본 출원은 연접한(concatenated) 코드들을 반복적으로 검출하거나 디코딩하는 기술에 관한 것이다. 더 구체적으로 말하자면, 본 출원은 예컨대 터보 디코더에서 사용되는 유한 상태 기계(finite-state machine)[즉, 소프트-인/소프트-아웃("SISO") 모듈]의 소프트 인버스(soft-inverse)를 계산하는 것에 관한 것이다.
통신 채널에 존재하는 잡음으로 인해서, 수신된 신호는 반드시 송신된 신호와 동일한 것은 아니다. 채널 코딩, 즉 에러 검출 코딩은 통신 시스템의 수신기가 송신 데이터 스트림의 구성을 정확하게 검출할 수 있는 가능성을 증가시키는 기술에 관한 것이다. 통상적으로, 이것은 신호를 송신하기 전에 그 신호를 인코딩하여 리던던시(redundancy)를 부가함으로써 달성된다. 이러한 리던던시는 수신기가 인코딩된 신호를 정확하게 디코딩하여 원데이터를 복원할 수 있는 가능성을 증가시켜 준다.
비교적 새로운 것이긴 하지만 채널 코딩 기술로 널리 사용되고 있는 터보 코딩은 가능한 이론적인 한계에 가까운 전력 효율로 시그널링하고 있다. 터보 코드는 병렬 코드 연접, 조정 가능한 인터리빙, 그리고 반복 디코딩을 특징으로 한다. 터보 코드는 에너지 효율을 실질적으로 향상시킬 수 있으므로, 전력 및/또는 간섭이 제한된 채널에 사용하는 것은 매우 매력적이다.
터보 코드를 디코딩하는 데에는 터보 디코더가 사용될 수 있다. 터보 디코더는 반복적인 방식으로 함께 동작하는 2개의 SISO 디코딩 모듈을 포함할 수 있다.
SISO 디코딩 모듈은 유한 상태 기계들, 더 일반적으로는 서브시스템들의 네트워크를 갖는 시스템용으로 구축된 반복 검출 기술에 적합한 기본 빌딩 블록이다.
도 7a 및 도 7b는 각각 통상적인 터보 인코더(10) 및 터보 디코더(11) 구성의 블록도이다. 이 예에서, 터보 인코더(10)는 2개의 별도인 재귀 조직 컨벌루션(RSC; Recursive Systematic Convolutional) 인코더(RSC1, RSC2)를 사용한다. 각 RSC 인코더(RSC1, RSC2)는 일정수의 상태(통상적으로, 터보 인코더의 경우, 4 또는 8)와 이러한 상태 천이를 갖는 유한 상태 기계(FSM)로서 모델링될 수 있다. 채널을 통해 전송하기 위한 비트 스트림을 인코딩하기 위해서, 코딩되지 않은 데이터 비트 bk가 제1 인코더(RSC1)와 인터리버(I) 양자 모두에 입력된다. 인터리버(I)는 입력 시퀀스 bk를 셔플(shuffle)하여 임의성(randomness)을 증가시킨 후 그 셔플된 시퀀스 ak를 제2 인코더(RSC2)로 전달한다. 블록(12)은 인코더(RSC1, RSC2)의 출력 ck, dk를 각각 펑처(puncture) 및 변조하여 인코딩된 출력 xk(0), xk(1)을 생성한 후에, 채널을 통해 터보 디코더(11)로 전송한다.
터보 디코더(11)에서는, 인코딩된 출력이 잡음있는(noisy) 입력 zk(0), zk(1)로서 수신되어, 블록(13)에 의해 복조 및 디펑처되는데, 이것은 펑처 및 변조 블록(12)의 소프트 인버스이다. 블록(13)의 출력 M[ck(0)], M[ck(1)] 및 M[dk(1)]은 "소프트" 정보, 즉 코딩된 시퀀스 ck(0), ck(1) 및 dk(1)로 각각 송신된 정보 비트의 가장 적절한 시퀀스에 관한 추측 또는 확신이다. 디코딩 프로세스는 계속해서, 수신된 소프트 정보 M[ck(0)], M[ck(1)] 및 M[dk(1)]을 제1 디코더(SISO1)로 전달하면, 제1 디코더(SISO1)는 송신된 정보를 추정하여 소프트 출력 M[bk]를 생성한 후에, 인터리버(I)[터보 인코더(10)의 인터리버(I)와 동일한 인터리빙 맵핑을 사용함]로 전달하여 M[ak]를 생성한다. 제2 디코더(SISO2)는 M[ak]와 수신된 M[dk(1)]을 사용하여 정보를 재추정한다. 이러한 재추정은 인터리버의 소프트 인버스(I-1)를 경유해서 제1 디코더(SISO1)로 다시 루프되어, 추정 프로세스가 다시 시작된다. 반복 프로세스는 일정한 조건, 예컨대 일정한 반복 횟수가 충족될 때까지 계속되며, 이러한 충족 시점에서 최종 소프트 추정은 송신된 정보를 나타내는 "하드(hard)" 출력이 된다.
터보 디코더(11) 내의 각 SISO 디코더 모듈은 터보 인코더(10) 내의 대응하는 RSC 인코더의 소프트 인버스이다. 소프트 인버스를 계산하는 종래의 알고리즘은 G. David Forney, Jr., "The Forward-Backward Algorithm", Proceedings of the 34th Allerton Conference on Communications, Control and Computing, pp. 432-446(Oct. 1996)에 기재되어 있는 바와 같이, "순방향-역방향" 알고리즘(forward-backward algorithm)으로서 알려져 있다. 순방향-역방향 알고리즘에서, 데이터 비트의 값에 대한 추정은 SISO의 "격자(trellis)", 특히 FSM에서 가능한 모든 상태 천이를 나타내는 언폴드형(unfolded) 상태도에서 순방향과 역방향으로 [가산-비교-선택(ACS; add-compare-select) 연산을 통해] 최소 비용의 경로를 재귀적으로 계산함으로써 이루어진다. SISO의 격자에서의 각 경로는 수신된 잡음있는 입력에 기초한 대응하는 비용을 갖는데, 이러한 비용은 RSC 인코더가 데이터를 인코딩할 때 그 격자에서 특정 경로를 선택했을 가능성을 나타낸다. 통상적으로, 경로의 총비용이 낮을수록 RSC 인코더가 데이터를 인코딩할 때 그 대응하는 천이가 이루어졌을 가능성이 높아진다. 일반적으로, SISO에 의해 수행되는 순방향 및 역방향 ACS 리커전(재귀; recursion)은 직렬 또는 병렬로 계산될 수 있다. 그러한 리커전을 상기 두가지 방법 중 더 빠른 방법인 병렬로 수행하는 경우에는, 레이턴시 O(N)(여기서, N은 인코딩된 데이터의 블록 사이즈임)을 갖는 아키텍처를 초래한다. 본 명세서에서 사용되는 "레이턴시"는 N 비트의 블록을 디코딩하는 경우에 발생하는 종단간(end-to-end) 지연이다.
본 발명자는 디코더 또는 다른 검출 시스템에서 다른 구성 요소들의 레이턴시에 따라, SISO의 레이턴시를 줄임으로써, 상기 시스템의 처리량(시스템 아키텍처가 처리할 수 있는 초 당 비트수 측정량)을 상당히 향상시킬 수 있다는 것을 생각해 내었다. 그 결과로서, 본 발명자는 레이턴시를 줄일 수 있는 트리 구조형 SISO를 개발하였다.
트리 구조형 SISO를 실현하는 것은 아래와 같은 다양한 구성의 조합을 포함할 수 있다.
본 발명의 한가지 특징에 따르면, 인코딩된 신호(예컨대, 터보 인코딩된 신호, 블록 인코딩된 신호 등)를 디코딩하는 것이 예컨대 무선 통신 시스템에서, 소프트 정보를 산출하기 위하여 수신된 인코딩된 신호를 복조하고 하나 이상의 소프트-인/소프트-아웃(SISO) 모듈에서 반복적으로 처리함으로써 수행될 수 있다. 적어도 하나의 SISO 모듈은 예컨대 재귀적인 주변화-조합 연산을 수행하여 순방향 및 역방향 상태 메트릭을 계산하는 트리 구조를 사용한다. 여기에서 재귀적인 주변화-조합 연산은 최소-합 연산, 최소*-합 연산(min*=min(x,y)-ln(1+e-｜x-y｜)), 합-곱 연산 및/또는 최대-곱 연산을 포함할 수 있다.
인코딩된 신호는 적어도 하나의 터보 인코딩된 신호, 블록 터보 인코딩된 신호, 저밀도 패리티 체크 코딩된 신호, 곱 코딩된 신호, 컨벌루션 코딩된 신호, 병렬 연접 컨벌루션 코드 및/또는 직렬 연접 컨벌루션 코드를 포함할 수 있다.
반복 처리는 소정의 조건이 만족되었을 때, 예컨대, 반복에 대한 소정의 수가 완료되었을 때 종료할 수 있다. 반복 처리는 소프트 정보에 병렬 전위 연산 또는 병렬 후위 연산 또는 그 두가지 모두를 수행하는 것을 포함할 수 있다. 또한, 반복 처리는 제1 SISO의 소프트 출력을 다른 SISO의 소프트 입력으로 사용하는 것 및/또는 소프트-정보에 세미-링을 형성하는 주변화-조합 연산을 수행하는 것을 포함할 수 있다.
적어도 하나의 SISO에 의해 사용되는 트리 구조는 0(log2N)의 레이턴시를 갖는 SISO를 만드는 트리 구조(여기에서, N은 블록 사이즈임), 브랜트-쿵(Brent-Kung) 트리, 예컨대 양방향인 트리 구조 리커전을 포함하는 순방향-역방향 트리가 될 수 있다.
적어도 하나의 SISO에 의해 수행되는 처리는 관찰 간격을 서브간격으로 타일링하고, 각 서브간격에 최소 하프-윈도우 SISO 연산을 적용하는 것을 포함할 수 있다.
본 발명의 다른 특징에 따르면, SISO 모듈은 트리 구조로 배열되고 순방향 및 역방향 상태 메트릭을 계산하는데 적합한 복수의 퓨전 모듈을 포함할 수 있다. 각각의 퓨전 모듈은 아래의 수학식으로 정의될 수 있다.
Figure 112003004099852-pct00078
여기에서, c(k, m)은 sk와 sm 사이의 소프트 입력에 기초하여 상태쌍 sk와 sm의 최소 시퀀스 메트릭(MSM)의 매트릭스이다. 적어도 하나의 퓨전 모듈은 재귀적인 주변화-조합 연산을 수행함으로써 순방향 및 역방향 상태 메트릭을 계산할 수 있다.
본 발명의 다른 특징에 따르면, SISO 모듈은 순방향과 역방향 모두에서 주변화-조합 연산을 수행하는 하나 이상의 완성 퓨전 모듈(CFM)과, 순방향으로만 주변화-조합 연산을 수행하는 하나 이상의 순방향 퓨전 모듈(fFM)과, 역방향으로만 주변화-조합 연산을 수행하는 하나 이상의 역방향 퓨전 모듈(bFM)을 포함할 수 있다. 하나 이상의 CFM, fFM 및 bFM은 트리 구조(예컨대, 브랜트-쿵 트리, 순방향-역방향 트리)로 배열된다. CFM의 양은 소프트 인버스를 계산하는데 필요한 최소수로 설정될 수 있다. 일반적으로, fFM 및 bFM은 CFM이 가능한 모든 위치에서 트리 구조에 사용될 수 있다.
본 발명의 다른 특징에 따르면, 반복 검출은 유한 상태 기계(FSM)의 하나 이상의 출력에 대응하는 입력 신호(예컨대, 터보 인코딩된 신호 또는 컨벌루션 코딩된 신호)를 수신하는 것과 트리 구조를 사용하여 수신된 입력 신호의 순방향 및 역방향 상태 메트릭을 계산하는 것을 포함할 수 있다. 순방향 및 역방향 상태 메트릭은 예컨대, 주변화-조합 연산의 트리-구조 집합을 사용하여 하나 이상의 SISO 모듈에 의해 계산될 수 있다.
FSM의 소프트 인버스를 결정하는 것은 소프트 정보를 반복 처리하는 것, 예컨대 소프트 정보에 병렬 전위 연산 또는 병렬 후위 연산 또는 그 두가지 모두를 수행하는 것을 포함할 수 있다. 또한, 반복 처리는 제1 SISO의 소프트 출력을 다른 SISO의 소프트 입력으로 사용하는 것을 포함할 수 있다. 적어도 하나의 SISO는 또한, 관찰 간격을 서브간격으로 타일링하고, 각 서브간격에 최소 하프-윈도우 SISO 연산을 적용할 수 있다.
본 발명의 다른 특징에 따르면, 터보 디코더는 FSM에 의해 인코딩된 신호를 입력으로 수신하고, 그 수신된 신호와 관련된 소프트 정보를 산출하는데 적합한 복조기와, 그 복조기와 통신하고 트리 구조를 사용하여 FSM의 소프트 인버스를 계산하는데 적합한 적어도 하나의 SISO 모듈을 포함한다. 트리 구조는 병렬 전위 및 병렬 후위 연산의 조합을 수행한다.
터보 디코더는 적어도 2개의 SISO 모듈이 서로 통신하고, 그 SISO 모듈이 디코딩된 신호의 소프트 정보 측정값을 반복적으로 교환할 수 있다. 이 경우, 적어도 하나의 SISO 모듈이 수신된 신호의 순방향 및 역방향 상태 메트릭을 계산함으로써 FSM의 소프트 인버스를 계산할 수 있다.
본 발명의 다른 특징에 따르면, 하나 이상의 블록 인코딩 모듈의 출력에 대응하는 입력 신호를 수신하는 것과, 트리 구조를 사용하여 수신된 입력 신호의 순방향 및 역방향 상태 메트릭을 계산함으로써 하나 이상의 블록 인코딩 모듈의 소프트 인버스를 결정하는 것을 포함할 수 있다. 입력 신호는 블록 터보 인코딩된 신호, 저밀도 패리티 체크 코딩된 신호 및/또는 곱 코딩된 신호를 포함할 수 있다.
블록 인코딩된 모듈의 소프트 인버스를 결정하는 것은 소프트 정보를 반복 처리하는 것, 예컨대 소프트 정보에 병렬 전위 연산 또는 병렬 후위 연산 또는 그 두가지 모두를 수행하는 것을 포함할 수 있다.
본 발명의 다른 특징에 따르면, 블록 디코더는 블록 인코딩 모듈에 의해 인코딩된 신호를 입력으로 수신하고, 그 수신된 신호와 관련된 소프트 정보를 산출하는데 적합한 복조기와, 그 복조기와 통신하고 트리 구조를 사용하여 블록 인코딩 모듈의 소프트 인버스를 계산하는데 적합한 적어도 하나의 SISO 모듈을 포함할 수 있다. 트리 구조는 병렬 전위 및 병렬 후위 연산의 조합을 수행할 수 있다. 블록 디코더는 또한 서로 통신하고, 그 SISO 모듈이 디코딩 신호의 소프트 정보 측정값을 반복적으로 교환하는 적어도 2개의 SISO 모듈을 더 포함할 수 있다. 이 때, 적어도 하나의 SISO 모듈은 수신된 신호의 순방향 및 역방향 상태 메트릭을 계산함으로써 블록 인코딩 모듈의 소프트 인버스를 계산할 수 있다.
본 발명의 다른 특징에 따르면, 반복 검출은 모듈 - 모듈의 소프트 인버스는 모듈의 격자 표현에 순방향-역방향 알고리즘을 실행시킴으로써 계산될 수 있음 - 의 하나 이상의 출력에 대응하는 입력 신호(예컨대, 블록 에러 정정 인코딩된 신호, 블록 터보 인코딩된 신호, 저밀도 패리티 체크 코딩된 신호 및/또는 곱 코딩된 신호)를 수신하는 것과, 트리 구조를 사용하여 수신된 입력 신호의 순방향 및 역방향 상태 메트릭을 계산함으로써 모듈의 소프트 인버스를 결정하는 것을 포함할 수 있다.
본 발명에 따르면 아래와 같은 하나 이상의 장점을 얻을 수 있다. 종래의 SISO 기술이 순방향-역방향 리커전을 동시에 수행하고, 그 레이턴시 0(N)인 것과는 대조적으로, 본 명세서에 개시된 기술 및 방법은 0(lg N)[여기에서 N은 블록 사이즈이고, "lg"는 log2임]만큼 낮게 감소된 레이턴시를 갖는 트리 구조 SISO 모듈을 만든다. 레이턴시의 감소는 우선적으로 칩 면적의 비용에 영향을 미치고 어떤 경우에는 단지 계산의 복잡도에서 주변의 증가를 가져온다, 이러한 트리-구조 SISO는 고산출량의 터보 디코더 또는 보다 일반적인 반복 디코더를 설계하는데 사용될 수 있다. 다양한 서브윈도우 및 겹치지 않는 방책이 레이턴시를 개선시키기 위하여 부가적으로 사용될 수 있다.
이와 같이 감소된 레이턴시 SISO는 격자 상에 순방향-역방향 알고리즘을 실행하는 것이 바람직한 또는 필요한 임의의 가상 환경에서 사용될 수 있다. 예컨대, 트리-SISO는 무선 통신 및 다른 여러 형태의 디코딩(터보 디코딩, 블록 터보 디코딩, 병렬 연접 컨벌루션 코드 및 직렬 연접 컨벌루션 코드를 포함하는 컨벌루션 코딩, 저밀도 패리터 체크(LDPC) 코드를 포함하는 패리터 체크 코드, 곱 코드 및 반복 검출에서 보다 일반적인 기타 코드)에서 적용예를 발견한다. 감소된 레이턴시 SISO는 특히 일반적으로 4 또는 8 상태 중 하나를 갖는 터보 코드 FSM과 같이 비교적 작은 수의 상태를 갖는 FSM을 디코딩하는 것에 적용될 때 효과적이다.
하나 이상의 실시예에 대하여 아래 첨부하는 도면을 참조하여 상세하게 설명한다. 본 발명의 다른 특징, 목적 및 효과는 발명의 상세한 설명, 도면 및 특허 청구의 범위로부터 알 수 있다.
도 1은 C 퓨전 프로세스를 도시하는 도면.
도 2는 [k0, k0 + K]와 [k0 + K, k0 + 2K]에 대한 C 매트릭스의 완성 집합을 조합하여 [k0, k0 + 2K]에 대한 완성 집합을 얻기 위한 퓨전 모듈 어레이를 도시하는 도면.
도 3은 N = 16일 때 트리-SISO 아키텍처를 도시하는 도면.
도 4는 순방향-역방향 알고리즘에 기초한 타일형(tiled) 서브윈도우 방식을 도시하는 도면.
도 5는 d = 4 MHW SISO를 구현하기 위하여 N = 16일 때 윈도우 사이즈가 4인 4개의 트리-SISO를 갖는 타일형 서브윈도우 접근 방식을 나타내는 도면.
도 6은 다양한 하프-윈도우 사이즈, N = 1024, 10번 반복일 때 SISO에 대한 표준 터보 코드의 시뮬레이션을 도시하는 그래프.
도 7a 및 도 7b는 각각 터보 인코더와 터보 디코더의 예를 도시하는 도면.
도 8a 및 도 8b는 순방향-역방향 트리-SISO(FBT-SISO)의 구현예를 도시하는 도면.
도 9는 브랜트-쿵(Brent-Kung) 트리-SISO의 실시예를 도시하는 도면.
도 10은 도 9의 브렌트-쿵 트리-SISO 접근 방식에 대한 트랜지스터 총수 추정을 도시하는 그래프.
도 11은 표준 해밍 (7, 4) 코드의 패리티 체크에 대한 격자(trellis) 구조를 도시하는 도면.
도 12는 해밍 코드 패리티 체크의 트리 구조 표현을 도시하는 도면으로서, 여기서 순방향-역방향 트리-SISO 알고리즘이 이 트리에서 실행되어 메시지의 내향(상향) 집합이 V6으로 표시된 노드로 넘겨지고 다음에 메시지의 외향(하향) 집합이 넘겨져서 코딩된 비트에 대한 원하는 소프트-아웃 메트릭을 생성한다.
도 13은 LDPC 디코더(전체 코드율은 0.5)의 예를 도시하는 도면으로서, 이 디코더에서는 브로드캐스터 노드(broadcaster node)로부터 패리티 체크 노드로 고정 교환(permutation)을 통하여 확신(belief)이 넘겨지며, 패리티 체크 노드는 트리 구조형 SISO로서 구현될 수 있다.
본 발명의 발명자들은 전위(prefix) 연산과 후위(suffix) 연산의 조합을 사용하는 표준 SISO 계산의 재공식화를 개발하였다. 이러한 아키텍처는 트리-SISO라고 불리는데, 고속 가산기와 같은 VLSI(Very Large Scale Integration) 애플리케이션에 사용되는 고속 병렬 전위 계산을 위한 트리 구조에 기초를 두고 있다. 트리-SISO에 대한 자세한 내용과 다양한 다른 실시예가 아래에서 설명된다.
FSM(finite-state machine)의 "소프트 인버스"를 계산하는 것은 많은 데이터 검출/디코딩 알고리즘에서 중요한 연산이다. 더 일반적인 애플리케이션들 중의 하나는 1993년 5월 스위스 제네바에서 커뮤니케이션에 관한 국제 학회에서 베로우(Berrou) 등에 의해 발표된 "근접 샤논 한계 에러 정정 코딩 및 디코딩; 터보 코드(Near Shannon limit error-correcting coding and decoding: turbo-codes"의 1064-1070 페이지, 및 1996년 10월에 발간된 IEEE Trans. Commun. 44권 1261-1271 페이지에서 베로우 등이 발표한 "근접 최적 에러 정정 코딩 및 디코딩; 터보 코드(Near optimum error correcting coding and decoding: turbo-codes)"에 설명된 터보 코드와 같은 연접한 코드들의 반복 디코딩이다. 그러나, SISO(소프트 인/소프트 아웃) 모듈은 반복 및 비반복 수신기와 신호 처리 장치에 널리 응용 가능하다. SISO에 의해 생성된 소프트 출력은 또한 쓰레스홀드되어 최적의 하드 디시전(hard decision)을 얻을 수 있다[예를 들어, 비터비(Viterbi) 알고리즘(1973년 3월에 발행된 Proc. IEEE 61권 268-278 페이지에서 포니(G. D. Forney)가 발표한 "비터비 알고리즘") 또는 발(Bahl) 알고리즘(1974년 3월에 발행된 IEEE Trans. Inform. Theory의 IT-20권 284-287 페이지에서 발(L. R. Bahl), 코케(J. Cocke), 젤리넥(F. Jelinek), 및 라비브(J. Raviv)가 발표한 "심벌 에러율을 최소화하기 위한 선형 코드의 최적 디코딩(Optimal decoding of linear codes for minimizing symbol error rate)")과 동일한 디시전을 생성함]. 많은 애플리케이션에서 일반적인 경향은 데이터 속도가 높아지는 방향으로 간다는 것이고, 따라서, 고속의 알고리즘과 아키텍처가 요구된다.
데이터 검출 회로 아키텍처의 두가지 기본 성능(속도) 측면이 있다. 첫번째는 아키텍처가 디코딩할 수 있는 초 당 비트수의 측정값인 처리량이다. 두번째는 N 비트의 블록을 디코딩하는 경우의 종단간 지연인 레이턴시이다. 비파이프라인형 아닌 아키텍처는 한번에 하나의 블록만을 디코딩하는 아키텍처인데, 이 경우 처리량은 단순히 N을 레이턴시로 나눈 값이다. 반면에, 파이프라인형 아키텍처는 시간에 따라 쉬프트되면서 동시에 다수의 블록을 디코딩할 수 있기 때문에, 비파이프라인형 아키텍처보다 훨씬 더 높은 처리량을 얻을 수 있다.
애플리케이션에 따라, 데이터 검출 하드웨어의 처리량 및/또는 레이턴시는 중요할 수 있다. 예를 들어, 데이터 속도가 상대적으로 느린(100 kb/s 미만) 터보 코딩 시스템에서 인터리빙과 관련된 레이턴시는 아마 반복 디코딩 하드웨어의 레이턴시를 능가할 것이다. 그러나, 미래의 고속 시스템의 경우 인터리버로 인한 레이턴시는 상대적으로 낮아질 수 있으므로, 디코더의 레이턴시를 중요하게 한다. 파이프라인형 디코더는 흔히 처리량 요구 조건을 달성할 수 있는 반면에, 이러한 기술은 일반적으로 레이턴시를 실질적으로 감소시키지 못한다. 또한, 때때로 레이턴시는 전체 시스템 성능에 극적인 영향을 미친다. 예를 들어, (자기 하드 드라이브와 같은) 데이터 저장 시스템에서 검색 과정에서의 레이턴시는 마이크로프로세서와 전체 컴퓨터의 성능에 극적인 영향을 미친다. 이러한 자기 저장 채널들은 터보 코딩 접근 방식과 함께 고속 비터비 처리 방식을 사용할 수 있다.
표준 SISO 알고리즘은 순방향-역방향 알고리즘이다. 관련된 순방향 및 역방향 리커전 단계는 주어진 시간에 모든 FSM 상태에 대하여 병렬로 계산될 수 있으므로, O(N)(N은 블록 사이즈)의 계산 복잡도와 레이턴시를 가진 아키텍처를 가져온다. 이 논문의 중요 결과는 전위 연산과 후위 연산의 조합을 사용해서 표준 SISO 계산을 재공식화하여, O(lg N) 레이턴시를 가진 아키텍처를 가져온다는 것이다. "트리-SISO"라고 불리는 이 아키텍처는 VLSI(Very Large Scale Integration)(예를 들어, 고속 가산기) 논문에서 고속 평행 전위 계산을 위한 트리 구조에 기초를 두고 있다.
이러한 트리-SISO에 대한 레이턴시의 급격한 감소는 계산 복잡도와 영역이 증가한 것에 대한 댓가이다. 이러한 비용의 정확한 값은 FSM 구조(예를 들어, 상태의 수)와 그 구현의 세부 사항에 달려 있다. 그러나, 터보 코드에서 구성 요소로서 종종 사용되는 것과 같은 4 상태 컨벌루션 코드의 경우, 트리-SISO 아키텍처는 레이턴시가 O(lg N)이고 계산 복잡도가 O(N LG N)이다. 이러한 4 상태 예의 경우 트리-SISO 아키텍처의 계산 복잡도는 관련된 속도 증가에 대하여 서브리니어하게(sublinearly) 증가한다는 사실을 유의해야 한다. 이는 비터비 알고리듬(예를 들어, 1989년 8월에 발행된 IEEE Trans. Commun. 37권 785-790 페이지에서 페트바이스(Fettweis) 등이 발표한 "병렬 비터비 알고리듬 구현: ACS-병목을 깨는 것(Parallel Viterbi algorithm implementation: Breaking the ACS-bottleneck)"에 설명되어 있는 것)의 리니어-스케일 해결책보다 낫다. SISO 문제에 대한 해결책의 일반화는 항상 분명한 것은 아니다. 이러한 4 상태 코드 예에서, O(lgN)-레이턴시 트리-SISO와 관련된 영역은 O(N)이다.
소프트-인 소프트-아웃 모듈
병렬 상태 천이가 없고 일반적인 S 상태 격자가 있는 특정 종류의 FSM을 생각해 보자. 이러한 격자는 각 상태에서 출발하고 각 상태로 들어오는 S개에 이르는 천이를 가지고 있다. FSM은 대응하는 FSM 입력 및 FSM 출력에 의해 상태 천이를 식별함으로써 정의된다. tk = (sk, ak, sk+1) = (sk, ak) = (sk, sk+1)을 입력 ak에 대한 시간 k에의 상태 sk로부터 상태 sk+1로의 격자 천이라고 하자. 병렬 상태 천이가 없기 때문에, tk는 이러한 표현들 중 어느 것에 의해서도 고유하게 정의된다. 천이 tk가 일어난다고 하면, FSM 출력은 xk(tk)이다. 일반적으로 천이에서 출력으로 매핑하는 것은 k 값에 의존하도록 될 수 있다는 것을 유의해야 한다.
FSM을 디지털 입력 시퀀스 ak를 디지털 출력 시퀀스 xk로 매핑하는 시스템이라고 생각하자. 이러한 FSM의 주변(marginal) 소프트 인버스 또는 SISO는 입력 SI(ak)와 출력 SI(xk) 상의 소프트-인(SI) 정보를 ak 및/또는 xk에 대한 소프트-아웃(SO) 정보로 매핑하는 것으로서 정의될 수 있다. 이러한 매핑은 사용되는 조합 연산자와 주변화(marginalization) 연산자에 의해 정의된다. 이제 주변화 연산자와 조합 연산자에 대한 하나의 특정한 합리적인 선택을 고려하기만 하면 된다는 것과 그 결과는 관심있는 다른 연산자로 용이하게 변환된다는 것을 잘 이해할 것이다. 따라서, 그 초점은 최소-합(min-sum) 주변화-조합 연산에 있고, 그 결과는 표준 방식으로 최대-곱(max-product), 합-곱(sum-product), 최소*-합(min*-sum), 최대*-합(max*-sum)으로 변환된다. 모든 경우에, 지수 K1과 K2가 특정 양 uk(예를 들어, uk = sk, uk = ak, uk = tk, uk = xk, = (sk, sk+d), 등)에 대한 소프트-출력의 계산에 사용되는 조합 윈도우, 즉 스팬(span)의 시간 경계를 정의한다고 하자. 일반적으로 K1과 K2는 k의 함수이다. 표기를 간단히 하기 위하여, 이러한 의존성을 명시적으로 표시하지는 않는다. 최소-합 주변화-조합에 있어서, 양 uk의 최소 시퀀스 메트릭(minimum sequence metric, MSM)은 uk의 조건치와 일치하는 조합 윈도우, 즉 스팬에서 최단 경로, 또는 시퀀스의 메트릭(즉 길이)이다. 구체적으로 MSM은 다음의 수학식 1 내지 수학식 3으로서 정의된다. 표준 약정에서, FSM 구조에서는 일어날 수 없는 천이의 메트릭은 무한대인 것으로 해석된다.
Figure 112002036447415-pct00002
Figure 112002036447415-pct00003
Figure 112002036447415-pct00004
여기서, uk와 일치하는, 시간 K1에 시작해서 시간 K2에 끝나는 천이의 집합은
Figure 112003004099852-pct00005
로 표시되고,
Figure 112003004099852-pct00006
는 묵시적으로 천이의 시퀀스, tK1, tK1+1, ..., tK2를 정의한다.
특정 애플리케이션에 따라, 다음의 수학식 4 및 수학식 5와 같이 "외부(extrinsic)" 양들 중 하나 또는 양쪽 모두가 계산될 것이다.
Figure 112002036447415-pct00007
Figure 112002036447415-pct00008
SISO가 정의된 시스템은 FSM이므로, 수학식 2와 수학식 3에서의 조합 연산과 주변화 연산은 효율적으로 계산될 수 있다. 전통적인 접근 방식은 상태들의 MSM을 시간에 따라 순방향 및 역방향으로 재귀적으로 계산하는 순방향-역방향 알고리즘이다. 구체적으로, 천이 tk(k = 0, 1, ..., N-1)에 대한 소프트-인에 기초한 표준 고정-간격 알고리즘의 경우, 가산-비교-선택(ACS; add-compare-select) 연산에 기초한 다음 리커전의 결과는 다음의 수학식 6 및 수학식 7과 같이 된다.
Figure 112002036447415-pct00009
Figure 112002036447415-pct00010
여기서, f-1(S0)와 bN(SN)는 이용가능한 엣지 정보에 따라 초기화된다. 유의할 점은, 그 상태에 대하여 S개의 가능한 값이 있으므로, 이러한 상태 메트릭은 (S ×1) 벡터 fk와 bk로서 간주될 수 있다는 것이다. 수학식 4 및 수학식 5에서 최종 소프트-출력은 천이 tk의 MSM을 주변화함으로써 다음의 수학식 8이 얻어진다.
Figure 112002036447415-pct00011
여기서, uk는 xk 아니면 ak이다. 수학식 8에서의 연산은 완성 연산(completion operation)이라 부른다.
순방향-역방향 알고리즘이 계산적으로 효율적인 반면, 그것을 바로(straightforward) 구현한 것은 원인(causal) 및 반원인(anticausal) 상태의 MSM을 계산하는 데 있어서 ACS 병목 때문에 레이턴시가 크다(즉, O(N)).
전위 연산 및 후위 연산
전위 연산은 다음의 수학식 9 및 수학식 10에 따라 n개의 입력(y0, y1, ..., yn-1)을 받아 n개의 출력(z0, z1, ..., zn-1)을 생성하는 일반적인 계산 형태로서 정의된다.
Figure 112002036447415-pct00012
Figure 112002036447415-pct00013
여기서
Figure 112003004099852-pct00014
은 임의의 관련 이진 연산자(associative binary operator)이다.
마찬가지로, 후위 연산은 다음의 수학식 11 및 수학식 12에 따라 n개의 입력(y0, y1, ..., yn-1)을 받아 n개의 출력(z0, z1, ..., zn-1)을 생성하는 일반적인 계산 형태로서 정의된다.
Figure 112002036447415-pct00016
여기서
Figure 112003004099852-pct00017
은 임의의 관련 이진 연산자이다. 후위 연산은 단지 다른 엣지에서 앵커된(anchored) (역방향) 전위 연산이라는 것을 유의해야 한다.
전위 연산 및 후위 연산은 트리 구조형 아키텍처를 사용하여 낮은 레이턴시로 구현될 수 있는 알고리즘 부류를 가능하게 하기 때문에, 중요하다. 이 개념을 실현한 것 중에 가장 주목할 만한 것은 레이턴시 O(lgN)을 가진 VLSI N 비트 트리 가산기이다.
SISO 연산의 재공식화
제안된 저레이턴시 아키텍처는 전위 연산과 후위 연산의 조합에 의하여 SISO 계산을 공식화함으로써 유도된다. 이러한 공식을 얻기 위하여, C(sk, sm)(m > k)를 이들 사이의 소프트-입력에 기초한 상태쌍 sk와 sm의 MSM, 즉 C(sk, sm) = MSMk m-1(sk, sm)으로서 정의하자. MSM의 집합 C(sk, sm)은 (S ×S) 매트릭스 C(k, m)으로서 간주될 수 있다. 원인 상태의 MSM fk-1은 so에 대한 조건을 주변화(예컨대, 최소화)함으로써 C(0, k)로부터 얻어질 수 있다. 역방향 상태 메트릭은 비슷한 방식으로 얻어질 수 있다. 구체적으로, sk의 각 조건값에 대하여 다음의 수학식 13 및 수학식 14와 같다.
Figure 112002036447415-pct00018
Figure 112002036447415-pct00019
이러한 관측 결과에 의하면, 알고리즘의 하나의 기본적인 스텝은 k = 0, 1, ..., N-1인 경우에 C(0,k) 및 C(k,N)을 계산하는 것이다. 알고리즘의 입력은 k = 0, 1, ..., N-1인 경우에 C(k,k+1)로 기재될 수 있는 1 스텝 천이 메트릭(one-step transition metric)임에 주목해야 한다. 이 알고리즘이 어떻게 전위 계산(prefix computation) 및 후위 계산(suffix computation)으로 구현되는 지를 살펴보기 위해, C 매트릭스에 대한 최소-합 퓨전 연산자(min-sum fusion operator)를, 하나의 매트릭스의 좌엣지가 다른 하나의 매트릭스의 우엣지와 일치하는 2개의 매트릭스를 입력으로 하고, 중간점을 주변화하여 큰 스팬을 갖는 쌍별 상태 MSM를 얻기 위한 것으로서 정의한다. 구체적으로, C(k0,m) 및 C(m, k1)가 주어지면, C 퓨전 연산자, 즉
Figure 112003004099852-pct00020
연산자는 다음의 수학식 15로서 정의된다.
Figure 112002036447415-pct00021
Figure 112003004099852-pct00022
연산자는 2개의 매트릭스를 받아 하나의 매트릭스로 만들어주는 관련 이진 연산자이다. 이것은 도 1에서 설명되고 있다. 이러한 정의에 의하면, k = 0, 1, ..., N-1인 경우에 C(0,k) 및 C(k, N)는 다음과 같이 전위 및 후위 연산법을 통해 계산될 수 있다.
Figure 112002036447415-pct00023
일반적으로, SISO 알고리즘은 상태 조건화의 분리 특성(the decoupling property of state-conditioning)에 기초하고 있다. 구체적으로, 시각 k에서 가능한 모든 FSM 상태값에 대한 조건화는, 이 상태 조건의 양측에 대한 최단 경로 문제(예컨대, MSM 계산)를 독립적으로 푼 다음에 (예컨대, C 퓨전 연산자에 의해 수행되는 바와 같이) 함께 퓨전될 수 있다. 보다 일반적으로, SISO 연산은 관측 구간의 분할에 기초해서 분리될 수 있으며, 여기서 각 하위구간은 독립적으로 처리된 다음에 함께 퓨전될 수 있다. 예컨대, 순방향-역방향 알고리즘은 단일 천이 레벨로의 분할에 기초하고 있으며, 여기서 그 퓨전은 순방향과 역방향으로 순차적으로 이루어진다. 대조적으로, 다른 SISO 알고리즘은 그러한 분할과, 그 하위 문제들에 대한 해(solution)를 함께 퓨전하는 스케줄을 규정함으로써 정의될 수 있다. 이것은 관련 방식을 상기 전위-후위 연산(구문으로 그룹화)으로 규정하는 것으로서 간주될 수 있다.
C 퓨전 연산은 일부 경우에는 관련 방식에 따라 단순화될 수 있다. 예를 들면, 순방향-역방향 알고리즘은 모든 C 퓨전 연산을 보다 단순한 순방향 및 역방향 ACS로 대체한다. 그러나, 레이턴시도 관련 방식의 함수이다. 쌍별 트리 구조형 그룹화(a pairwise tree-structured grouping)에 기초한 아키텍처가 아래에 제시된다. 이러한 구조에 의해서는 단지 C 퓨전 연산의 일부만이 단순화될 수 있으나, 순차적인 방식 대신에 병렬로 하위 문제들에 대한 해들을 퓨전함으로써 순방향-역방향 알고리즘에 비해 레이턴시가 현저하게 저감된다.
저레이턴시의 트리-SISO 아키텍처
전위 연산의 이진 트리 구조형 그룹화에 기초한 다수의 저레이턴시 병렬 아키텍처가 1982년 3월에 발간된 컴퓨터에 관한 IEEE 회보 C-31권 260 내지 264페이지에 실린 Brent 등의 명칭이 "병렬 가산기의 레귤러 레이아웃(A regular layout for parallel adders"인 논문과; T. H. Cormen 등의 알고리즘 입문(Introduction to Algorithms), 캠브리지 수학(1990년 MIT 출판사); A. E. Despain의 새로운 컴퓨터 아키텍처의 2장에 실린 "고성능을 위한 컴퓨터 아키텍처에 대한 주해(Notes on computer architecture for high performance)"(1984년 아카데미 출판사)에 기재된 바와 같이 SISO에 채용될 수 있다. 이것들 모두는 관련 이진 연산자가 간단한 1 비트 가산인 n 비트 가산기 설계를 목표로 했다. 본 발명자는 병렬 전위-후위 아키텍처가 1 비트 가산보다 실질적으로 더 복잡한 관련 이진 연산자에 기초한 알고리즘에 적용될 수 있음을 처음으로 인식하였다. 종래의 병렬 전위 아키텍처는 면적 축소 대신에 고레이턴시를 선택하여, 각 계산 모듈의 제한된 팬아웃을 2차적으로 제한한다. 이러한 후자의 제한 사항은 계산 모듈이 소형이고 버퍼 및 와이어의 지연(가산기 설계에 있어서)에 견줄만한 지연을 가지는 경우에 중요하다. 그러나 퓨전 연산자는 비교적 크다. 따라서, 현재의 VLSI 추세로 보면, 가까운 장래에 전체적인 지연이 해소될 것이라 생각된다. 따라서, 여기서 기술하는 아키텍처는 팬아웃을 고려하지 않고 최소수의 계산 모듈로 레이턴시를 최소화한다.
특히, k=1, 2, ..., N의 경우 순방향 및 역방향 메트릭 f k-1 및 b N-k를 도 2에 도시한 퓨전 모듈(FM) 어레이에 기초한 계층적 트리 구조를 이용하여 구할 수 있다. 2K-1의 매트릭스 C(k0, k0+m), C(k0+m, k0+K)(m=1,2, ..., K-1) 및 C(k0, k0+K)로서 구간{k0, k0+K}에 대한 C 매트릭스의 완성 집합을 구할 수 있다. 이것은 격자에서 K 스텝의 스팬에 대한 모든 상태쌍의 MSM 정보이며, 하나의 상태는 그 구간의 좌엣지 또는 우엣지 중 어느 하나에 있게 된다. 도 2의 모듈은 2개의 인접한 스팬 K 구간에 대한 C 매트릭스의 완성 집합을 퓨전하여 사이즈 2K의 결합 스팬에 대한 C 매트릭스의 완성 집합을 생성한다. 4K-1의 출력 C 매트릭스 중 2K는 어떤 처리없이 2(2K-1)의 입력으로부터 구한다. 다른 2K-1의 출력 C 매트릭스는
Figure 112003004099852-pct00024
연산자를 구현하는 2K-1의 C 퓨전 모듈(CFM)로 구한다.
도 2에 도시한 기본적인 스팬 K 내지 스팬 2K의 FM 어레이를 이용하여 lgN 스테이지에서 전체 구간에 대한 C 매트릭스를 계산할 수 있다. 이것은 N=16인 특정 경우에 대해서 도 3에 도시되어 있다. i=1, 2, ..., n=lgN으로 좌에서 우로 스테이지를 색인화하면 스테이지 i에는 2n-i개의 FM 어레이가 있게 된다.
그러나, 최종 목적이 일반 상태 및 비일반 상태 메트릭을 계산하는 것이므로, 모든 FM이 모든 FM 어레이마다 CFM을 반드시 필요로 하는 것은 아니다. 특히, 순방향 상태 메트릭 f k-1은 다음의 수학식 16에 의해 f m-1 및 C(m,k)로부터 구할 수 있다.
Figure 112002036447415-pct00025
마찬가지로, 역방향 상태 메트릭은 다음의 수학식 17에 의해 갱신될 수 있다.
Figure 112002036447415-pct00026
수학식 16에 기술된 바와 같이 또 다른 f 벡터와 C 매트릭스로부터 f 벡터를 산출하는 처리 모듈을 f 퓨전 모듈(fFM)이라 한다. b 퓨전 모듈(bFM)은 수학식 17에서의 연산에 따라 유사하게 정의된다. 도 3은 어느 FM이 fFM 또는 bFM으로서 구현 가능한 지를 나타내고 있다.
이러한 전개의 중요성은 상태 메트릭의 계산이 0(lgN) 레이턴시를 갖는다는 것이다. 이것은 단지 데이터 종속성이 한 스테이지에서 다음 스테이지에 이어지므로 한 스테이지내의 모든 FM 어레이와 FM 어레이 내의 모든 FM이 병렬로 실행 가능하기 때문이며, FM 어레이 각각은 0(1) 레이턴시를 취한다. 이와 같이 레이턴스가 짧으면 비교적 큰 면적을 필요로 한다. 하나의 완화 요소는 트리의 스테이지가 시퀀스로 동작하므로 스테이지들간에 하드웨어를 공유할 수 있다는 것이다. 따라서, 가장 많은 하드웨어를 필요로 하는 스테이지가 필요한 하드웨어의 총수를 나타낸다. 이에 대한 대략적인 측정치는 N CFM이며, 그 각각은 관련 레지스터를 가진 S2개의 S식(way) ACS 유닛을 포함하고 있다. 가능한 경우에는 언제나 bFM과 fFM의 사용을 고려한 보다 상세한 분석이 이후의 "하드웨어 자원 요건" 섹션에서 자세히 설명된다. 도 3의 예 및 4 상태 FSM(즉, S=4)의 경우, 스테이지 2가 가장 많은 CFM(8)을 가지나, 스테이지 3이 처리 복잡도가 가장 크다. 특히, 4개의 4식 ACS 유닛을 고려하여 측정한 스테이지 i=1,2,3,4의 복잡도는 각각 26,36,32,16이다. 따라서, 하드웨어가 스테이지들간에 공유되면, 소정 스테이지에서 모든 FM을 병렬로 실행하기 위해서는 4개의 4식 ACS 유닛이 총 36 세트가 필요하다. 이러한 수의 ACS 유닛이 과중한 응용의 경우, S 팩터 만큼 하드웨어 요건을 줄일 수 있는데, 이에 대응해서 레이턴시가 선형 증가한다.
수학식 8에서 정의된 완성 연산의 구현 또한 고려되어야 한다. 필요한 기본적인 연산은 Q가 uk와 일치하는 천이수인 Q식 ACS 유닛이다. 기껏해야 천이의 절반이 uk와 일치할 것이라고 가정하면, Q는 S2/2로 상한이 정해진다. 따라서, S가 크면, 완성 단계의 저레이턴시의 면적 효율적인 구현이 중요한 문제가 될 수 있다. 다행히, 많은 저레이턴시의 구현예가 널리 알려져 있다[예컨대, P. J. Black의 고속 비터비 디코딩을 위한 알고리즘 및 아키텍처(Algorithms and Architectures for High Speed Viterbi Decoding)(캘리포니아 소재 스탠포드 대학 석사 학위 논문, 1993년 3월)에 기술되어 있다]. 하나의 간단한 구현예는 비교기의 이진 트리를 이용하고 0(lgS2)의 레이턴시를 갖는 구현예이다. S가 작은 경우, 이러한 추가 레이턴시는 일반적으로 중요하지 않다.
상태 메트릭 계산의 계산 복잡도는 도 2 및 도 3에 기초해서 간단한 표현을 통해 계산 가능하다. 이후의 "계산 복잡도 분석" 섹션에서 기술되는 바와 같이 S개의 S식 ACS 계산 유닛에서 측정된 총 계산수는 다음의 수학식 18로서 정의된다.
Figure 112002036447415-pct00027
도 3의 예와 4 상태 FSM의 경우, 110 세트 상당량의 4개의 4식 ACS 연산이 수행된다. 이것은 2N=32개의 그러한 연산을 수행하고 레이턴시가 4배인 베이스라인 아키텍처를 갖는 대응하는 순방향 역방향 알고리즘과 비교된다. 일반적으로, 레이턴시가 N에서 lgN으로 저감하는 경우, 계산은 대략 (1/2)(lgN - 3)S + 1의 팩터로 증가된다. 따라서, 관련 복잡도가 커지는 동안, 복잡도 스케일링은 N에 대해 서브리니어하다.
스파스 격자(sparse trellises)의 최적화
일반적으로, 상기 아키텍처는 완전히 연결된 격자에 대해서 가장 효율적이다. 그러나, 스파서 격자 구조의 경우, 초기 처리 모듈은 상태쌍의 MSM간에 천이 시퀀스가 없어 ∞로 설정된 요소를 포함하는 C 매트릭스를 처리해야 하므로, 처리 전력과 레이턴스를 낭비하게 된다. 대안의 실시예는 이러한 비효율성을 다루는 최적화를 구현할 수 있다.
S=ML 상태와 각각의 상태로 그리고 각각의 상태로부터의 정확한 M개의 천이를 갖는 표준 1 스텝 격자를 베이스라인으로서 간주하기로 하고, 여기에서 시각 sk에서 소정 상태로부터 소정 상태 sk+L로 진행하는 하나의 천이 시퀀스가 정확하게 존재한다. 하나의 최적화는 1 스텝 격자를 R 스텝 격자(1≤R≤L)로 프리컬랩싱(pre-collapsing)하고 트리 SISO 아키텍처를 컬랩싱된 격자에 적용하는 것이다. 또 다른 최적화는 가능한 한 C 퓨전 모듈을 단순화하는 것이다. 특히, R 스텝 격자의 SISO에 대해, 제1 lg(L/R) 스테이지를 멀티스텝 천이 메트릭의 입력쌍을 단순히 부가하는 가산 뱅크로 단순화할 수 있다.
보다 상세히 말하면, 프리컬랩싱에서는, 각각의 슈퍼천이(supertransition)
Figure 112003004099852-pct00028
(여기서, k = 0, 1, ..., (N-1)/R)의 천이 메트릭을 구성하는 R개의 1 스텝 천이 메트릭을 부가한다. SISO는 이들 입력을 받아서 순방향 및 역방향 MSM, 즉
Figure 112003004099852-pct00029
및
Figure 112003004099852-pct00030
(여기서, k = 0, 1, ..., N/R)을 생성한다. 프리컬랩싱의 한가지 중요한 이점은 SISO 입력의 수를 R의 팩터 만큼 감소시킴으로써 상태 메트릭 계산에 필요한 스테이지의 수를 lgR의 팩터 만큼 감소시킨다는 점이다. 프리컬랩싱의 한가지 단점이라고 할 수 있는 것은 보다 복잡하고 일반화된 완성 연산, 즉 이하의 수학식 19를 사용하여 원하는 소프트 출력을 계산해야만 한다는 점이다.
Figure 112002036447415-pct00031
한가지 주요한 문제로는, 각각의
Figure 112003004099852-pct00032
에 있어서 이 완성 단계에서는 1 스텝 격자에
Figure 112003004099852-pct00033
식 ACS가 필요한 것이 아니라
Figure 112003004099852-pct00034
식 ACS가 필요하다는 것이다.
이 두가지 최적화가 모두 수행된다고 가정할 때 최적 R(즉, 최소 레이턴시에 대한)을 식별하기 위해, 구성 연산들의 상대적 레이턴시가 필요하게 된다. 정확한 레이턴시는 구현의 세부적인 내용에 달려 있지만, 개략적인 추정치도 여전히 통찰력있는 결과를 가져올 수 있다. 특히, 상태 메트릭에 대한 프리컬랩싱 가산 및 ACS 연산 및 완성 연산 모두가 가산기/비교기의 이진 트리를 사용하여 구현되어 있고, 이들 연산의 예상 지연이 그의 입력들의 개수의 로그값으로 변한다고 가정하자. 한가지 발견되는 중요한 점은 프리컬랩싱이 lgR개의 단순화된 스테이지와 더불어 L개의 1 스텝 천이 메트릭들[완전히 연결된 L 스텝 격자에 대한 천이 메트릭을 생성함]을 가산하고, 따라서 추정된 lgL 시간 단위로 결합 구현될 수 있다는 것이다. 게다가, 상태 메트릭
Figure 112003004099852-pct00035
식 ACS 유닛들은
Figure 112003004099852-pct00036
시간 단위가 걸리고 완성 유닛 식 ACS는
Figure 112003004099852-pct00038
시간 단위가 걸린다. 최대 병렬성(maximal parallelism)을 가정할 경우, 이렇게 하면 총 레이턴시는 이하의 수학식 20과 같게 된다.
Figure 112002036447415-pct00039
따라서, 최소 레이턴시는 R - LlgR(여기서, 1 ≤ R ≤L임)이 최소일 때(R = L일 때) 발생한다. 이것으로부터 최소 레이턴시 아키텍처는 격자가 완전히 연결된 격자로 프리컬랩싱되고 또한 보다 복잡한 완성 유닛을 사용하여 계산된 주기적인 상태 메트릭으로부터 소프트 출력을 추출해내는 아키텍처라는 것을 알 수 있다.
이와 같은 레이턴시의 감소에 대한 대가로서, L 스텝 천이 메트릭을 생성하는 가산기들의 트리를 구현하는 데 부가의 면적이 필요하고 보다 복잡한 완성 연산을 구현하는 데 보다 큰 비교기들의 트리가 필요하게 된다. 그렇지만, 주의할 점은 이러한 면적에 대한 총비용은 각각의 트리의 스테이지들간에, 어떤 경우에는 레이턴시에 거의 영향을 주지 않는 트리들간에 가산기 및 비교기를 공유함으로써 완화될 수 있다.
타일형 서브윈도우 방식 사용
본 발명의 발명자들은 더 작은 조합 윈도우를 사용하면 레이턴시가 감소하고 소프트 인버스를 계산하는 처리 능력이 향상된다는 것을 알았다. 최소 하프 윈도우(minimum half-window, MHW) 알고리즘은 SISO의 한 부류로서 조합 윈도우 경계(K1, K2)는 관찰 윈도우의 경계로부터 k만큼 떨어진 모든 점에 대해 K1 ≤max(0, k-d) 및 K2 ≥min(N, k+d)(여기서, k = 0, ..., N-1)를 만족시키며, 소프트 출력은 좌우측 경계가 k로부터 적어도 d 포인트만큼 떨어져 있는 서브윈도우에 기초하고 있다.
종래의 순방향-역방향 알고리즘을 서브윈도우에 사용하여 MHW-SISO를 얻을 수 있다. 하나의 특정 방식으로는 타일형 서브윈도우 기법이 있으며, 여기서는 길이 2d + h의 조합 윈도우를 사용하여 모든 상태 메트릭을 도출한다. 이 방식에서는, 도 4에 도시한 바와 같이, 윈도우는 길이 2d의 오버랩을 갖는 타일형으로 되어 있으며 이러한 윈도우가
Figure 112003004099852-pct00040
개 있다. 내부의 서브윈도우 각각에 대한 순방향-역방향 리커전은 h개의 소프트 출력을 산출하며, 따라서 h가 감소함에 따라 오버랩 패널티(overlap penalty)가 증가한다.
그러한 i번째 윈도우의 경우, 순방향 및 역방향 상태 메트릭은 수학식 6 및 수학식 7의 리커전을 수정한 다음의 수학식 21 및 수학식 22의 리커전을 사용하여 계산된다.
Figure 112002036447415-pct00041
Figure 112002036447415-pct00042
모든 윈도우가 병렬로 처리되면, 이 아키텍처는 O(d+h)의 레이턴시를 초래한다.
트리-SISO 알고리즘은 오버랩 페널티가 전혀 없고 레이턴시가 O(lgd)인 MHW 방식에서 사용될 수 있다. 사이즈가 d인 N/d개의 조합 윈도우를 살펴보기로 하고, 트리-SISO가 C(id, id+j) 및 C((i+1)d, (i+1)d-j)(여기서, j= 0, ..., d-1이고 i= 0, ..., N/d-1임)를 계산하는 것으로 하자. 그런 다음에, 하나의 부가적인 논리 스테이지를 사용하여 i번째 윈도우(여기서, i = 0, ..., N/d-1)에 속하는 k개의 시간 인덱스 모두에 대한 순방향 및 역방향 상태 메트릭을 다음과 같이 계산한다[이것은 C(s-d, s0)가 초기의 좌측 경계 정보로 대체된 것으로 해석되어야만 하며 C(sN-1, sN+d-1)에 대해서도 마찬가지로 해석되어야만 한다].
Figure 112002036447415-pct00043
내부 최소화(inner minimization)는 수학식 13 및 수학식 14에서와 같이 C 정보를 f(b) 정보로 변환하는 것에 해당한다. 외부 최소화(outer minimization)는 fFM 또는 bFM에 해당한다. 이 최소화의 순서는 복잡도를 최소화하도록 선택되었다. 이것은 도 5에 도시한 이 방법의 일례에 반영되어 있으며, 여기서 4개의 트리-SISO 각각의 마지막 스테이지는 상기 최소화를 제안된 순서로 실행하도록 수정되어 있다. 이것을 수행하는 모듈은 2Cfb 모듈이라고 한다. 이 모듈은 도 3의 스테이지 2의 중앙 CFM을 특화시킨 것으로서 볼 수 있다. 서브윈도우 트리-SISO 출력의 상기의 조합은 하나의 부가적인 처리 스테이지를 추가함으로써 필요한 FM 스테이지 수는 lg(d) + 1이 된다.
계산 복잡도 비교
순방향-역방향 타일형 방식을 사용하는 상태 메트릭 계산의 계산 복잡도란, 윈도우의 개수와 각 윈도우에 대한 순방향-역방향 알고리즘 계산의 복잡도를 곱한 것을 말한다. 이것은 S개의 S식 ACS의 경우, N이 클 때 이하의 수학식 23과 같이 근사화될 수 있다.
Figure 112003004099852-pct00079
S개의 S식 ACS의 경우 트리-SISO 타일형 방식을 사용하는 상태 메트릭 계산의 계산 복잡도는 이와 유사하게 전개될 수 있으며, 이하의 수학식 24와 같이 된다.
Figure 112002036447415-pct00045
어떤 방식이 더 높은 계산 복잡도를 갖는지에 대한 결정은 h와 d의 상대적 사이즈에 따라 달라지게 된다. h가 감소되면, 표준의 순방향-역방향 방식은 레이턴시는 감소되고 계산 복잡도는 증가되는데, 그 이유는 오버랩된 윈도우의 개수가 증가하기 때문이다. 타일형 트리-SISO 아키텍처가 오버랩 패널티를 갖지 않기 때문에, 타일형 순방향-역방향 방식에서 h가 감소함에 따라, 상대적 계산 복잡도 절충(trade-off)은 트리-SISO 방법의 경우에 더욱 유리하게 된다. 사실,
Figure 112003004099852-pct00046
인 경우, 트리-SISO의 계산 복잡도는 타일형 순방향-역방향 방식에서보다 더 낮다.
설계예 : 4-상태 PCCC
살펴본 병렬성이 높은 아키텍처는 구현 면적을 많이 필요로 한다. 이 예에서, 가까운 장래에 구현하는 것이 가장 실현가능한 면적 요건을 갖는 실시예에 대해 기술한다. 구체적으로 설명하면, 4-상태 스파스(1-스텝) 격자에 기초한 반복 디코더에 대해 살펴본다. S가 더 큰 경우 트리-SISO에 있어서 더욱 인상적인 레이턴시 감소를 얻을 것이다. 이것은 병렬 타일형 순방향-역방향 아키텍처에 대해 트리-SISO 아키텍처가 달성하는 레이턴시의 감소가 최소 하프 윈도우 사이즈에 따라 달라지기 때문이다. 양호한 성능을 내기 위해서는 d의 값이 상태의 개수에 따라 증가할 필요가 있다는 것을 예상할 수 있다[즉, 스파스 격자에 대한 비터비 알고리즘에 있어서의 역추적 깊이(traceback depth)에 대한 경험칙과 유사함]. 이와 반대로, 프리컬랩싱을 살펴보면 보다 덜 인상적인 레이턴시 감소를 얻을 것이다. 예를 들어, 단일 스텝 격자에 대해 d = 16 이 필요한 경우, d = 8 의 유효값은 2-스텝 격자에 대해 충분할 것이다. 전자의 경우 트리-SISO와 관련된 레이턴시 감소율은 대략 4 이지만, 후자의 경우에는 단지 8/3이다. 그렇지만, 더 큰 S 및/또는 프리컬랩싱이면 더 큰 구현 면적을 초래할 것이며, 이들 알고리즘의 가까운 장래의 실현가능성을 현실적으로 판정하고자 하는 우리의 바램과 맞지 않는다.
특히, 2개의 4-상태 구성 코드 [1], [2]를 갖는 표준 병렬 연접 컨벌루션 코드(parallel concatenated convolutional code, PCCC)에 대해 살펴본다. 재귀 조직 구성 코드(recursive systematic constituent code) 각각은 생성 다항식 G(D) = (1 + D2)/(1 + D + D2)를 사용하여 패리티를 발생하며, 패리티 비트들은 레이트가 1/2인, 전체적인 조직 코드(overall systematic code)가 얻어지도록 펑처된다.
MHW-SISO에 사용될 d에 적합한 값을 결정하기 위해, 시뮬레이션을 수행하였으며, 이 때 각각의 SISO가 시각 k에서 소프트-출력을 계산하는 데 조합 윈도우 {k-d, ..., k+d}를 사용하였다. 이것은 h = 1인 타일형 순방향-역방향 방법에 의해 얻은 SISO 연산과 정확히 동등하다. 주의할 점은 d가 시뮬레이션에 대한 모든 (내부의) 하프 윈도우의 사이즈이기 때문에, d를 갖는 MHW-SISO에 기초한 어떤 아키텍처도 적어도 마찬가지로 수행될 것이다(예를 들면, h = 2의 타일형 순방향-역방향, d-타일형 트리-SISO 등). N = 1024의 인터리버 사이즈에 대한 시뮬레이션 결과는 도 6에 도시하였으며, 최소-합 주변화 및 조합 연산을 사용하여 10회 반복한 것이다. 여러가지 d에 대한 성능을 고정 구간(N = 1024)의 SISO의 성능과 함께 나타내었다. 어느 구성에서도 10회 이상에서는 어떤 중요한 반복 이익도 전혀 없었다. 그 결과를 보면 d = 16일 때 고정 구간인 경우에 가까운 성능을 나타낸다는 것을 보여준다. 이것은 비터비 디코더에 있어서의 역추적 깊이용 메모리의 5 내지 7배이라는 경험칙과 일치한다(즉, 개략적으로 d = 7 x 2 = 14 이면 충분할 것으로 예상된다).
요구되는 윈도우 사이즈가 d = 16 이기 때문에, 타일형 순방향-역방향 방식에 대한 트리-SISO의 레이턴시 개선은 4 = 16/lg(16)에 가깝다. 이들 2가지 방법의 계산 복잡도는 서로 비슷하며, 타일형 순방향-역방향 방법에 있어서의 h의 선택 및 구현의 세부 내용에 따라 다르다. 완벽하고 공평한 비교를 하려면 일반적으로 2가지 방법을 세밀하게 구현할 필요가 있다. 이하에서는, 트리-SISO 기반의 서브윈도우 아키텍처의 설계에 대해 설명한다.
아키텍처의 면적에 영향을 주는 요인으로는, 데이터 단위의 비트 폭이 있다. 시뮬레이션 결과들은 8 비트 데이터 경로로 충분하다는 것을 나타낸다. 개략적으로 말하자면, 이러한 예의 경우 트리 기반 아키텍처는 중간 상태 메트릭 결과를 저장하기 위해서 관련된 출력 레지스터와 함께 16개의 4식 ACS 유닛의 1024 세트를 필요로 할 것이다. 각각의 4식 ACS 유닛은 8 비트 4 대 1 멀티플렉서, 4개의 8 비트 가산기, 6개의 8 비트 비교기 및 1개의 8 비트 레지스터로 구현될 수 있다. 초기의 VLSI 설계시에는 이들 유닛들이 대략 2250개의 트랜지스터를 필요하였다. 따라서, 16 ×2250 ×1024
Figure 112003004099852-pct00047
4천만개의 트랜지스터를 필요로 한다는 것을 추정할 수 있다. 이러한 수의 논리 트랜지스터들은 현재의 VLSI 기술의 한계에 가깝지만, 곧 실현 가능하게 되어야 한다. 200 ㎒ 클록 주파수에서 트리의 스테이지마다 하나의 클록 사이클이 이용되는 아키텍처를 살펴보자. d = 16에 대하여, 각각의 SISO 연산은 그러한 6개의 클록 사이클에서 실행될 수 있다(완성 단계 동안에 하나의 클록 사이클을 이용). 또한, 상호 접속 네트워크를 갖는 1024 레지스터의 2개의 행으로 구성된 고정 배선 인터리버를 가정해보자. 이러한 인터리버는 현재의 메모리 기반 솔루션보다 크지만, 1 클록 사이클의 레이턴시를 가질 수 있다. 결과적으로, SISO, 하나의 인터리빙 및 하나의 디인터리빙의 2개의 어플리케이션으로 이루어지는 터보 디코더의 한번 반복에는 14개의 클록 사이클이 필요하다. 10번의 반복을 가정하면, 1024 비트의 디코딩에는 140 클록 사이클, 즉 정확히 700 ㎱의 레이턴시가 걸릴 것이다.
이러한 레이턴시는 또한 표준 파이프라이닝(pipelining) 기술로 더욱 개선될 수 있는 매우 높은 처리량을 암시한다. 특히, 비파이프라인형 구현은 700 ㎱ 당 1024 비트 = 1.5 Gb/초의 예상 처리량을 갖는다. 3개의 SISO 아키텍처를 이용하면 또한 인터리버 블록들에 걸쳐 파이프라이닝할 수 있는데, 이것에 대하여는 Masera 등의 논문["VLSI architectures for turbo codes," IEEE Transactions on VLSI, vol. 7, September 1999]에 개시되어 있다. 특히, 그러한 20개의 타일형 트리-SISO 및 관련된 인터리버들을 사용하여, 처리량을 20의 팩터로 증가시켜 30 Gb/초의 처리량을 달성할 수 있다.
또한, 순방향-역방향 알고리즘 기반 아키텍처와 다르게, 트리 SISO는 쉽게 내부적으로 파이프라이닝될 수 있는데, 이에 의해 하드웨어가 선형으로 스케일링되면서도 더 높은 처리량을 얻을 수 있다. 특히, 전용 하드웨어가 트리 SISO의 각 스테이지에서 이용되면, 내부적으로 트리 SISO를 파이프라이닝함으로써, 레이턴시의 증가없이, 처리량에서 1g(d)의 또 다른 팩터를 얻을 수 있다, d=16의 윈도우 사이즈에 대하여, 트리 기반 아키텍처는 120 Gb/초 이상을 지원할 수 있다. 즉, 이러한 사실은 그러한 하드웨어 비용이 실제 한도를 넘을 수도 있는 현재 기술로도 그것을 실현할 수 있다는 점에서 중요하다. 그러나, VLSI 기술에서 밀도가 지속적으로 증가된다면, 그러한 적극적인 아키텍처들이 장래에 비용면에서 효율적일 수 있다.
계산 복잡도 분석
필요한 스테이지의 수는 n = 1gN 이며, 스테이지 i에서 2n-i개의 FM 어레이를 갖는다. 스테이지 i 내의 각각의 이러한 FM 어레이들은 격자에서 스팬 2i를 차지하고, 2i-1개의 FM을 포함한다. 따라서, 스테이지 i에서 FM의 총수는 nFM(i) = (2i-1)2n-i이다. 퓨전 연산의 총수는 다음의 수학식 25와 같다.
Figure 112002036447415-pct00048
도 3의 일례의 경우, 이것은 NFM = 49로 줄어든다.
일례로서, 도 3을 이용하면, 스테이지 i에서 fFM으로서 구현될 수 있는 FM의 수는 nf(i) = 2i-1 이다. i = n이라는 특별한 경우에, 이것은 2K-1개의 CFM이 K개의 fFM과 K개의 bFM으로 대체된다. 예컨대, 도 3의 4번째 스테이지에서, 도 2에 암시된 15개의 CFM은 도시된 바와 같이 8개의 fFM과 8개의 bFM으로 대체될 수 있다. bFM으로서 구현될 수 있는 FM의 수는 동일하며, nb(i) =nf(i)=2i-1이다. 스테이지 i에서 요구되는 CFM의 수는 다음의 수학식 26 및 수학식 27과 같다.
Figure 112002036447415-pct00049
Figure 112002036447415-pct00050
여기서
Figure 112003004099852-pct00051
(j)는 크로네커 델타(Kronecker delta)이다. 퓨전 모듈의 총수는 다음의 수학식 28 및 수학식 29와 같다.
Figure 112002036447415-pct00052
Figure 112002036447415-pct00053
수학식 25와 수학식 29를 비교해보면, 비교적 큰 N에 대하여, CFM이 되어야 하는 FM의 분수가 (lg N - 3)/(lg N - 1)이라는 것을 알 수 있다. 보다 작은 N에 대하여, 그 분수는 약간 커진다. 예컨대, 도 3에서, Nf = Nb = 15이고, 20개의 CFM이 존재한다.
CFM은 fFM 및 bFM 연산보다 대략 S(즉, 상태의 수)배나 더 복잡하다. 이것은 수학식 16, 17과 수학식 15를 비교함으로써 알 수 있다. 특히, 수학식 15, 16, 17의 연산은 S식 ACS를 포함한다. CFM의 경우, S식 ACS는 수학식 15에서의 모든 가능한 상태쌍(Sko, Sk1), 즉 S2개의 상태쌍에 대하여 수행되어야 한다. 수학식 16 및 수학식 17의 S식 ACS 연산들은 단지 각각의 S개의 상태 sk에 대하여 계산하는 데에만 필요하다. 따라서, S 상태 격자 상에 S개의 S식 ACS인 기본 계산 유닛을 적용하면, 스테이지 i에 필요한 이러한 계산의 총수는 다음의 수학식 30과 같다.
Figure 112002036447415-pct00054
스테이지들을 합산하면, 다음의 수학식 31과 같이 S개의 S식 ACS 계산의 단위로 계산의 총수를 측정하여 얻는다.
Figure 112002036447415-pct00055
도 3의 일예 및 4 상태 FSM의 경우, 110 세트 상당량의 S개의 S식 ACS 연산이 수행된다. 이것은 2N = 32개의 그러한 연산을 수행하고 레이턴시가 4배인 베이스라인 아키텍처를 갖는 대응하는 순방향-역방향 알고리즘과 비교된다. 일반적으로, 주목할 점은 레이턴시가 N에서 lgN으로 감소하는 경우, 계산은 대략 (1/2)(lg N - 3)S + 1의 팩터 만큼 증가된다는 것이다. 따라서, 관련 복잡도가 증가하는 동안, 그 복잡도 스케일링은 N에 대해 서브리니어하다. S가 작은 경우, 이것은 리니어 스케일 솔루션 대 저레이턴시 비터비 알고리즘 구현[예컨대, P. J. Black의 "Algorithms and Architectures for High Speed Viterbi Decoding"(PhD thesis, Stanford University, California, March 1993) 및 Fettweis 등의 "Parallel Viterbi algorithm implementation : Breaking the ACS-bottleneck"(IEEE Trans. Commun., vol. 37, pp. 785-790, August 1989)]보다 좋다.
하드웨어 자원 요건
i에 대한 ns,s (i)의 최대값은 희망하는 최소 레이턴시를 달성하기 위한 최소 하드웨어 자원 요건을 결정하기 때문에 중요하다. 그 이유는 퓨전 모듈이 레이턴시에 거의 영향을 미치지 않으면서 스테이지들간에 공유될 수 있기 때문이다.
ns,s (i)의 최대값은 ns,s (i) ≥ns,s (i-1)에서 i의 조건을 고려함으로써 얻을 수 있다. 구체적으로, i ＜ n 이면, 다음의 수학식 32 내지 수학식 34와 같이 된다.
Figure 112002036447415-pct00056
Figure 112002036447415-pct00057
Figure 112002036447415-pct00058
다음에 ns,s (i)는 극대값을 갖지 않으며, 다음의 수학식 35를 이용하여 ns,s (i)의 최대값을 구할 수 있다.
Figure 112002036447415-pct00059
특히, 수학식 35가 i* ＜ n-1로 되면, 그 최대값은 i*에서 발생하고, 그렇지 않은 경우(i* = n-1)에는, 최대로 복잡한 스테이지를 결정하기 위하여 i = n - 1 및 i = 1인 경우를 비교해야 한다. S ≥4인 경우
Figure 112003004099852-pct00060
이므로, S ≥4 경우, 수학식 35는 다음의 수학식 36과 같이 줄어들 수 있다.
Figure 112002036447415-pct00061
트리 구조형 SISO의 다른 실시예
일반적으로, 트리 구조형 SISO를 구현함에 있어서, 시스템 설계자의 선호도에 따른 레이턴시, 계산 복잡도 및 IC 면적간의 절충을 나타내는 임의의 다른 트리 구조를 사용할 수 있다.
도 8a 및 도 8b는 순방향-역방향 트리-SISO(FBT-SISO)라고 하는 실시예를 나타내고 있다. FBT-SISO에 있어서, 트리 구조 리커전은 내향 및 외향의 양방향성이다. 그 결과, FBT-SISO의 레이턴시는 트리-SISO의 레이턴시의 2배이지만, 이것 또한 계산 복잡도를 크게 감소시키고 집적 회로(IC) 칩상에서 더 작은 면적을 차지한다.
일반화된 순방향-역방향 스케줄을 이용한 메세지 전달의 상세가 최소-합 처리시 도 8a 및 도 8b에 도시되어 있다. 내향 메세지는 도 8a에 도시하였다. 구체적으로, 초기에 MI[tk]가 일정하게 설정되며, MI[x(tk)] 및 MI[a(tk)]로부터 Mk[tk]를 계산하도록 서브시스템의 제1 레벨을 기동시킴으로써 알고리즘이 시작된다. 트리의 다음 레벨로 내향으로 전달된 메세지는 MSMk[sk, sk+1]이고, 이것은 병렬 천이가 없는 경우에 단순히 Mk[tk]이다. 이러한 내향 메세지 전달은 도시된 메세지와 함께 계속된다. s4 상의 2개의 메세지가 V4-s에 도달하면, 외향 전파가 시작되고 도 8b에 도시된 바와 같이 하향으로 진행된다. 또한, 트리의 소정의 레벨에 있는 모든 노드는 다음 레벨에 있는 임의의 노드를 기동하기 전에 기동된다. 바닥 레벨에서, (sk, sk+1)의 입력 메트릭은 MSM{k}c[sk, sk+1], 즉, 표준 순방향-역방향 알고리즘에서의 순방향 및 역방향 상태 메트릭의 합이다. 따라서, 바닥 레벨상의 노드의 최종 기동은 소망하는 외부 출력 메트릭을 생성한다.
이 FBT-SISO의 레이턴시는 메세지가 내향 및 외향의 양쪽으로 전파하여야 하기 때문에 트리-SISO의 레이턴시의 2배이다. 이러한 적당한 레이턴시의 증가는 계산 복잡도를 크게 감소시킨다. 특히, FBT-트리 SISO는 O(K)의 계산 복잡도와 O(log2K)의 레이턴시를 갖는다. 이것은 트리-SISO의 경우의 O(K log2K)의 계산 복잡도 및 O(log2K)의 레이턴시, 그리고 메시지가 표준 격자를 통과하는 경우의 O(K)의 계산 복잡도 및 O(K)의 레이턴시와 비교된다.
트리 구조형 SISO의 다른 실시예는 설계자의 목표 및 제약에 따라 장점을 가질 수 있다. 일반적으로, 트리 구조형 SISO는 사실상 모든 타입의 트리 구조를 사용하여 구성될 수 있다. 예를 들어, 장점의 결과들은 R.P.Brent 및 H.T. Kung의 "A regular layout for parallel adders," IEEE Transactions on Computers, C-31:260-264 (1982년 3월) (the "Brent-Kung tree"); A.E.Despain의 "New Computer Architectures," Chapter 2: Notes on computer architecture for high performance, Academic Press (1984); T.H. Cormen, C. Leiserson 및 R.L. Rivest의 "Introduction to Algorithms," The MIT Press (1990); 및/또는 S.M. Aji 및 R.J. McEliece의 "The generalized distributive law," IEEE Trans. Inform. Theory, 46(2):325-343 (2000년 3월)에 개시되어 있는 하나 이상의 트리 구조를 사용하는 트리 구조 SISO에 의해 얻어질 수 있다.
도 9는 d=16인 서브 윈도우에서의 브랜치 메트릭의 계산시 브랜트-쿵(Brent-Kung) 모델의 수정판을 사용하는 브랜트-쿵 트리-SISO의 대표예를 나타내고 있다. 브랜트-쿵 트리-SISO에는 6개의 파이프라인 스테이지가 있으며, 이들은 점선으로 표시되어 있다. 회색 노드들은 2식 ACS를 나타내고 흑색 노드들은 4식 ACS를 나타낸다.
브랜트-쿵 트리-SISO는 브랜트-쿵 병렬 가산기에 기초하는 것이다. 이것은 전위 가산기(prefix adder)의 팬아웃 문제를 해결하기 위해 만들어졌다. 또한 이것은 모든 메트릭의 계산에 필요한 하드웨어의 양을 감소시킨다. 여기에서도 또한 퓨전 연산이 사용되지만, 필요한 퓨전 연산의 양은 크게 감소된다. 브랜트-쿵 가산기에 있어서, 각 노드에서는 가산 연산 대신에 퓨전 연산이 수행된다. 이 형태에서는 순방향 정보만이 계산될 수 있다. 모델은 순방향 및 역방향 메트릭 둘다의 계산이 동시에 수행될 수 있도록 수정되었다.
이 모델은 먼저 ACS의 출력에 의해 구동되어야 하는 유닛의 수를 감소시킨다. 여기서 최악의 경우에는 4개의 유닛이 단일 스테이지의 출력(즉, 노드 C0,8)에 공급된다. 이것은 예전의 방법이 필요로 하였던 것의 거의 절반이다. 또한 2식 ACS 유닛만을 필요로 하는 상당한 수의 연산이 있다는 것을 알았다. 2식 ACS 유닛이 4식 ACS 유닛에서 필요로 하는 하드웨어의 절반 이하를 사용하는 것으로 간주하면, 회로의 전체 사이즈는 크게 감소되는 것을 기대할 수 있다. 전에 행하였던 분석과 유사한 분석을 행함으로써 이 직관적인 가정을 증명할 수 있다. 도 10에 그 결과를 요약하였다.
이 방법에 의해 나타나는 장점은 시스템 성능의 저하를 보충한다. 도 10의 블록도를 자세히 보면 계산을 위한 가장 긴 경로가 현재 6 사이클 길이라는 것을 알 수 있다. 순방향 및 역방향 메트릭 계산에 필요한 3개의 추가의 사이클들을 부가하면, 완성 단계 및 인터리빙 처리는 SISO 모듈의 전체 지연을 9 사이클로 되게 한다. 이것은 전체 디코딩 처리에 180 사이클이 소요됨을 의미한다. 구현시 동일한 셀들이 사용된다는 것을 가정하면, 이것은 1024 비트의 데이터 1블록의 처리에 540 나노초의 총 시간을 산출한다. 이 경우에 시스템의 처리량은 1.896 Gbps로 될 것이다. 각각의 ACS 단계 후에 파이프라이닝되는 언폴드형 설계를 사용하면, 각 단계 후에 1블록이 처리될 수 있고, 16.82 Gbps의 처리량이 실현될 수 있다. 20개의 SISO가 언폴드형 루프로 사용되면, 처리량은 341.32 Gbps로 될 것이다. 첫번째의 경우는 설계의 사이즈 때문에 관심이 있는 것이고 성능 저하는 약 24.1%에 불과하다. 동시에, 이 설계를 실시하는데 필요한 트랜지스터의 수는 거의 43.8%만큼 감소된다.
트리 구조형 SISO를 이용한 블록 코드 및 연접한 블록 디코딩
종래의 해법이 격자에서 표준형 순방향-역방향 알고리즘을 실행해야 하는 다른 관련 디코딩 문제점들이 있다. 여기에서 설명하는 방법 및 기술들은 그 응용에 있어서의 처리 레이턴시를 줄이기 위하여 순방향-역방향 알고리즘 대신에 또한 적용될 수 있다. 그 응용의 일례는 코드의 격자 표현을 이용하여 블록 에러 정정 코드의 소프트 인버스를 계산하는 것이다. 격자 표현을 이용한 블록 코드의 디코딩 방법은 Robert J. McEliece의 "On the BCJR Trellis for Linear Block Codes," IEEE Transactions on Information Theory," vol. 42, No. 4, (1996년 7월)에 설명되어 있다. 이 논문에서는 코드의 패리티 체크 구조에 기초하여 격자 표현을 구성하는 방법이 설명되어 있다. 디코딩, 또는 더 일반적으로 말하면 블록 코드의 소프트 인버스는 이 격자에서 순방향-역방향 알고리즘을 실행함으로써 달성될 수 있다. 여기에서 설명하는 방법 및 기술들은 FSM의 소프트 인버스를 위한 트리 구조형 방법과 유사한 방법으로 블록 코드의 소프트 인버스를 결정하기 위해 적용될 수 있다. 특히, 순방향 및 역방향 상태 메트릭은 트리 구조를 갖는 병렬 전위 계산 아키텍처를 사용하여 블록 코드의 소프트 인버스를 찾기 위해 계산될 수 있다.
패리티 체크 구조를 통해 블록 코드의 소프트 인버스를 구현하기 위한 트리-SISO 아키텍처를 적용하는 것은 몇개의 매력적인 터보형 코드가 간단한 패리티 체크 코드의 연접 구조에 기초하기 때문에 실제로 중요하다. 이 코드들은, 이들이 유사한 성능을 가지며 소프트 인버스 노드가 코딩된 비트에 대한 소프트 정보를 받아들이고 갱신하며 교환하는 반복 알고리즘을 사용하여 디코딩되기 때문에, 흔히 "터보형 코드"라고 부른다. 터보형 코드의 특수한 예로는 갤러거 코드(Gallager code)라고도 알려져 있는 저밀도 패리티 체크 코드(LDPC)와 (터보 블록 코드라고도 알려져 있는) 곱 코드가 있으며, 이들은 J. Hagenauer, E. Offer와 L. Papke의 "Iterative decoding of binary block and convolutional codes," IEEE Transactions on Information Theory, 42(2):429-445 (1996년 3월)와 R.G. Gallager의 "Low-Density Parity-Check Codes," MIT Press, Cambridge, MA, 1963에 설명되어 있다.
특수한 예로써, 표준형 해밍(7, 4) 코드용 패리티 체크 격자가 도 11에 도시되어 있다. 순방향-역방향 알고리즘은 7 정도의 레이턴시로 이 격자상에서 실행될 수 있다. 이와 달리, 트리-SISO 아키텍처를 사용하여 도 12에 도시된 계산 구조를 형성할 수 있다. FSM 소프트 인버스의 경우에서와 같이, 트리 구조형 계산은 종래의 해결 방법(즉, 격자상에서 표준형 순방향-역방향 알고리즘을 실행하는 방법)과 동일한 순방향 및 역방향 상태 메트릭을 계산하지만, 대수적 레이턴시(이 간단한 예에서는 레이턴시의 약 1/2)를 갖는다. 일반적으로, 길이 N인 블록 코드에 대하여, 순방향-역방향 알고리즘에 기초한 종래의 방법은 레이턴시 O(N)을 가질 것이며, 동일한 계산이 레이턴시 O(lg N)인 트리-SISO를 이용하여 계산될 수 있다.
도 12에 도시된 것과 같은 트리 구조형 패리티 체크 노드 SISO에 대한 특수한 사용예로써, 도 13에 도시된 것과 같은 LDPC용의 반복 디코더를 생각하자. 이 디코더는 2개의 기본 형태의 소프트 인버스 처리 노드, 즉 소프트 브로드캐스터 노드와 패리티 체크 SISO 노드를 갖는다. 일실시예에서, 디코더는 소프트 브로드캐스터 노드를 병렬로 기동시키고, 그 다음에 패리티 체크 SISO 노드로의 입력이 되는 발생된 소프트 정보를 교환함으로써 실행한다. 이 노드들은 기동되어 교환을 통해 역으로 전달되고 소프트 브로드캐스터에 입력되는 코드화 비트값에 대한 확신을 갱신한다. 이것은 단일 반복으로서 볼 수도 있다. 디코딩 절차를 완료하기까지는 수 회의 반복이 필요하다. 터보 디코딩에서와 같이, 정지 기준은 설계의 일부이고, 공통의 선택은 고정된 반복 횟수이다. 도 11에 도시된 계산은 양호한 실시예의 각각의 패리티 체크 SISO 노드에서 수행된다. 이와 달리, 트리 구조형 아키텍처는 각 패리티 체크 SISO 노드에서의 계산을 위해 사용될 수 있다. 가장 보편화된 형태에 있어서, LDPC 내의 패리티 체크 노드들은 단일 패리티 체크이고, 따라서, 2-상태 격자 표현을 갖는다.
결론
위에서는 병렬 전위/후위 연산의 관점에서의 SISO 연산의 설명에 기초하여 일련의 트리 구조형 아키텍처를 설명하였다. 베이스라인 순방향-역방향 알고리즘 아키텍처와 비교하여, 트리-SISO 아키텍처는 레이턴시를 O(N)에서 O(lgN)으로 감소시킨다. FBT-SISO와 같은 다른 트리 구조형 SISO는 레이턴시를 선형으로 증가시키는 것과 복잡도 및 면적을 실질적으로 더 낮추는 것을 맞바꾼다.
일반적으로, 효과적인 SISO 설계는 단일 트리-SISO를 이용하여 구축되지 않고, 오히려 중요한 구성 요소로서 다수의 트리-SISO를 이용하여 구축된다. 예를 들어, 위에서 설명한 바와 같이, 타일형 서브윈도우를 이용하여 SISO를 구성하기 위해 다수의 트리-SISO가 사용되었다. 그 예에서 레이턴시는 순방향-역방향 알고리즘에 기초한 완전히 병렬인 타일형 아키텍처에 대한 최소 하프 윈도우 사이즈에서의 선형으로부터 타일형 트리 SISO에 대한 d의 로그값으로 감소되었다.
일반적으로 트리-SISO의 잠재적인 레이턴시의 이점은 큰 조합 윈도우를 필요로 하는 응용에서 매우 중요하다. 대부분의 실제 설계에 있어서, 이것은 상태의 수가 증가할 때에 기대된다. 하나의 구체화된 4-상태 타일형 윈도우의 예를 생각하면, 레이턴시는 약 4의 팩터만큼 감소되었다. 이진 입력과 S개의 상태를 갖는 시스템에서는 d≒8 lg(S)이면 충분하다고 기대된다. 따라서, S가 증가할 때 약 8 lg(S) / lg(8 lg S)의 레이턴시에서의 잠재적인 감소가 존재하고, 이것은 매우 중요하다. 그러나, 이러한 잠재적인 레이턴시를 개선함에 있어서 주된 도전은 실시에 필요한 면적이다. 특히, 큰 S용으로 고속의 S식 ACS 유닛을 구축하는 것은 핵심적 도전이다. 성능 저하를 일으킴이 없이 상기 면적 요구 조건을 감소시키는 기술(예를 들면 비트-직렬 아키텍처)은 유망한 연구 분야이다. 사실상, 더 큰 S를 사용하는 것은 더 작은 인터리버를 사용가능하게 하고, 이로써 면적 요구 조건을 경감시키고 레이턴시를 감소시킨다.
여기에서 설명한 시스템 및 기술의 각종 실시예들이 디지털 전자 회로, 집적 회로, 특수 설계된 ASIC(application specific integrated circuit) 또는 컴퓨터 하드웨어, 펌웨어, 소프트웨어 또는 이들의 조합에서 실현될 수 있다.
지금까지 본 발명의 다수의 실시예들을 설명하였다. 그러나, 본 발명의 정신 및 범위로부터 일탈함이 없이 각종 변형이 이루어질 수 있다는 것을 이해할 것이다. 따라서, 다른 실시예들도 이하의 청구범위에 속하는 것으로 한다.

Claims (107)

  1. 디코딩 방법에 있어서,
    인코딩된 신호를 수신하는 단계와;
    상기 수신된 인코딩된 신호를 복조하여 소프트 정보를 생성하는 단계와;
    하나 이상의 소프트-인/소프트-아웃(SISO) 모듈 - 적어도 하나의 SISO 모듈은 병렬 전위(prefix) 연산 및 후위(suffix) 연산을 수행하도록 구성된 트리 구조를 사용하여 순방향 및 역방향 상태 메트릭을 계산함 - 을 사용하여 상기 소프트 정보를 반복적으로 처리하는 단계
    를 포함하는 디코딩 방법.
  2. 제1항에 있어서, 상기 적어도 하나의 SISO는 재귀적인 주변화-조합(marginalizationn-combining) 연산을 수행함으로써 상기 순방향 및 역방향 상태 메트릭을 계산하는 것인 디코딩 방법.
  3. 제2항에 있어서, 상기 재귀적인 주변화-조합 연산은 최소-합(min-sum) 연산을 포함하는 것인 디코딩 방법.
  4. 제2항에 있어서, 상기 재귀적인 주변화-조합 연산은 최소*-합(min*-sum) 연산을 포함하는 것인 디코딩 방법.
  5. 제4항에 있어서, min* = min(x, y) - ln(1 + e-｜x-y｜)인 것인 디코딩 방법.
  6. 제2항에 있어서, 상기 재귀적인 주변화-조합 연산은 합-곱(sum-product) 연산을 포함하는 것인 디코딩 방법.
  7. 제2항에 있어서, 상기 재귀적인 주변화-조합 연산은 최대-곱(max-product) 연산을 포함하는 것인 디코딩 방법.
  8. 제1항에 있어서, 상기 인코딩된 신호는 터보 인코딩된 신호, 블록 터보 인코딩된 신호, 저밀도 패리티 체크 코딩된 신호, 곱 코딩된 신호 및 컨벌루션 코딩된 신호 중 적어도 하나를 포함하는 것인 디코딩 방법.
  9. 제1항에 있어서, 상기 인코딩된 신호는 병렬 연접 컨벌루션 코드 및 직렬 연접 컨벌루션 코드 중 적어도 하나를 포함하는 것인 디코딩 방법.
  10. 제1항에 있어서, 무선 통신 시스템에서 반복 디코딩 방법을 사용하는 단계를 더 포함하는 것인 디코딩 방법.
  11. 제1항에 있어서, 소정의 조건이 발생하면 상기 반복 처리 단계를 종료하는 단계를 더 포함하는 것인 디코딩 방법.
  12. 제1항에 있어서, 상기 반복 처리 단계는 상기 소프트 정보에 대하여 병렬 전위 연산 또는 병렬 후위 연산 또는 양자 모두를 수행하는 단계를 포함하는 것인 디코딩 방법.
  13. 제1항에 있어서, 상기 반복 처리 단계는, 두개 이상의 SISO 모듈을 사용하고 제1 SISO의 소프트 출력을 다른 SISO의 소프트 입력으로서 사용하는 단계를 포함하는 것인 디코딩 방법.
  14. 제1항에 있어서, 적어도 하나의 SISO 모듈에 의해 사용되는 상기 트리 구조는 0(log2 N)(N은 블록 사이즈임)의 레이턴시를 갖는 SISO 모듈을 만드는 트리 구조를 포함하는 것인 디코딩 방법.
  15. 제1항에 있어서, 적어도 하나의 SISO 모듈에 의해 사용되는 상기 트리 구조는 브랜트-쿵(Brent-Kung) 트리를 포함하는 것인 디코딩 방법.
  16. 제1항에 있어서, 적어도 하나의 SISO 모듈에 의해 사용되는 상기 트리 구조는 순방향-역방향 트리를 포함하는 것인 디코딩 방법.
  17. 제16항에 있어서, 상기 순방향-역방향 트리는 양방향인 트리 구조 리커전을 포함하는 것인 디코딩 방법.
  18. 제1항에 있어서, 상기 적어도 하나의 SISO에 의해 수행되는 반복 처리 단계는,
    관찰 간격을 서브간격으로 타일링(tiling)하는 단계와,
    각 서브간격에 최소 하프-윈도우 SISO 연산을 적용하는 단계
    를 포함하는 것인 디코딩 방법.
  19. 제1항에 있어서, 상기 반복 처리 단계는 상기 소프트 정보에 대하여 세미-링을 형성하는 주변화-조합 연산을 수행하는 단계를 포함하는 것인 디코딩 방법.
  20. 병렬 전위 연산 및 후위 연산을 수행하기 위한 트리 구조로 배열되고 순방향 및 역방향 상태 메트릭을 계산하도록 구성된 복수의 퓨전 모듈을 포함하며,
    각 퓨전 모듈은 다음의 수학식으로서 정의되고,
    Figure 112005046256024-pct00062
    c(k, m)은 sk와 sm 사이의 소프트 입력에 기초한 상태 쌍 sk와 sm의 최소 시퀀스 메트릭(MSM)의 매트릭스인 것인 장치.
  21. 제20항에 있어서, 상기 퓨전 모듈 중 적어도 하나는 재귀적인 주변화-조합 연산을 수행함으로써 순방향 및 역방향 상태 메트릭을 계산하는 것인 장치.
  22. 제21항에 있어서, 상기 재귀적인 주변화-조합 연산은 최소-합 연산을 포함하는 것인 장치.
  23. 제21항에 있어서, 상기 재귀적인 주변화-조합 연산은 최소*-합(min*-sum) 연산을 포함하는 것인 장치.
  24. 제21항에 있어서, 상기 최소*는 min* = min(x, y) - ln(1 + e-｜x-y｜)인 것인 장치.
  25. 제21항에 있어서, 상기 재귀적인 주변화-조합 연산은 합-곱 연산을 포함하는 것인 장치.
  26. 제21항에 있어서, 상기 재귀적인 주변화-조합 연산은 최대-곱 연산을 포함하는 것인 장치.
  27. 순방향 및 역방향으로 주변화-조합 연산을 수행하는 하나 이상의 완성 퓨전 모듈(complete fusion modules, CFM)과;
    순방향으로만 주변화-조합 연산을 수행하는 하나 이상의 순방향 퓨전 모듈(forward fusion modules, fFM)과;
    역방향으로만 주변화-조합 연산을 수행하는 하나 이상의 역방향 퓨전 모듈(backward fusion modules, bFM)
    을 포함하며,
    상기 하나 이상의 CFM, fFM 및 bFM은 병렬 전위 연산 및 후위 연산을 수행하기 위한 트리 구조로 배열되는 것인 장치.
  28. 제27항에 있어서, 상기 CFM의 양은 소프트 인버스를 계산하는 데 필요한 최소수인 것인 장치.
  29. 제28항에 있어서, 상기 fFM 및 bFM은 가능한 모든 곳에서 CFM 대신에 상기 트리 구조에 사용되는 것인 장치.
  30. 제27항에 있어서, 상기 하나 이상의 퓨전 모듈에 의해 수행되는 주변화-조합 연산은 최소-합 연산을 포함하는 것인 장치.
  31. 제27항에 있어서, 상기 재귀적인 주변화-조합 연산은 최소*-합(min*-sum) 연산을 포함하는 것인 장치.
  32. 제31항에 있어서, 상기 최소*는 min* = min(x, y) - ln(1 + e-｜x-y｜)인 것인 장치.
  33. 제27항에 있어서, 상기 재귀적인 주변화-조합 연산은 합-곱 연산을 포함하는 것인 장치.
  34. 제27항에 있어서, 상기 재귀적인 주변화-조합 연산은 최대-곱 연산을 포함하는 것인 장치.
  35. 제27항에 있어서, 상기 트리 구조는 브랜트-쿵(Brent-Kung) 트리 및 순방향-역방향 트리(FBT) 중 적어도 하나를 포함하는 것인 장치.
  36. 유한 상태 기계(FSM)의 하나 이상의 출력에 대응하는 입력 신호를 수신하는 단계와;
    병렬 전위 연산 및 후위 연산을 수행하도록 배열된 트리 구조를 사용하여 상기 수신된 입력 신호의 순방향 및 역방향 상태 메트릭을 계산함으로써 상기 FSM의 소프트 인버스를 결정하는 단계를 포함하는 방법.
  37. 제36항에 있어서, 상기 순방향 및 역방향 상태 메트릭은 적어도 하나의 소프트-인/소프트-아웃(SISO) 모듈에 의해 계산되는 것인 방법.
  38. 제36항에 있어서, 상기 순방향 및 역방향 상태 메트릭은 주변화-조합 연산의 트리-구조 집합을 사용해서 계산되는 것인 방법.
  39. 제38항에 있어서, 상기 주변화-조합 연산은 최소-합 연산을 포함하는 것인 방법.
  40. 제38항에 있어서, 상기 주변화-조합 연산은 최소*-합(min*-sum) 연산을 포함하는 것인 방법.
  41. 제40항에 있어서, 상기 최소*는 min* = min(x, y) - ln(1 + e-｜x-y｜)인 것인 방법.
  42. 제38항에 있어서, 상기 주변화-조합 연산은 합-곱 연산을 포함하는 것인 방법.
  43. 제38항에 있어서, 상기 주변화-조합 연산은 최대-곱 연산을 포함하는 것인 방법.
  44. 제36항에 있어서, 상기 입력 신호는 터보 인코딩된 신호 및 컨벌루션 코딩된 신호 중 적어도 하나를 포함하는 것인 방법.
  45. 제36항에 있어서, 상기 입력 신호는 병렬 연접 컨벌루션 인코딩된 신호 및 직렬 연접 컨벌루션 인코딩된 신호 중 적어도 하나를 포함하는 것인 방법.
  46. 제36항에 있어서, 상기 FSM의 소프트 인버스를 결정하는 단계는 소프트 정보를 반복적으로 처리하는 단계를 포함하는 것인 방법.
  47. 제46항에 있어서, 상기 반복 처리 단계는 상기 소프트 정보에 대하여 병렬 전위 연산 또는 병렬 후위 연산 또는 양자 모두를 수행하는 단계를 포함하는 것인 방법.
  48. 제46항에 있어서, 상기 반복 처리 단계는 제1 SISO의 소프트 출력을 다른 SISO의 소프트 입력으로서 사용하는 단계를 포함하는 것인 방법.
  49. 제37항에 있어서, 사용되는 상기 트리 구조는 0(log2N)(N은 블록 사이즈임)의 레이턴시를 갖는 SISO 모듈을 만드는 트리 구조를 포함하는 것인 방법.
  50. 제36항에 있어서, 상기 트리 구조는 브랜트-쿵(Brent-Kung) 트리를 포함하는 것인 방법.
  51. 제36항에 있어서, 상기 트리 구조는 순방향-역방향 트리를 포함하는 것인 방법.
  52. 제51항에 있어서, 상기 순방향-역방향 트리는 양방향인 트리 구조 리커전을 포함하는 것인 방법.
  53. 제37항에 있어서, 상기 적어도 하나의 SISO는,
    관찰 간격을 서브간격으로 타일링하고,
    각 서브간격에 최소 하프-윈도우 SISO 연산을 적용하는 것인 방법.
  54. 유한 상태 기계(FSM)에 의해 인코딩된 신호를 입력으로서 수신하고, 그 수신된 신호와 관련된 소프트 정보를 생성하도록 구성된 복조기와;
    상기 복조기와 통신하고, 병렬 전위 연산 및 후위 연산을 수행하도록 배열된 트리 구조를 사용하여 상기 FSM의 소프트 인버스를 계산하도록 구성된 적어도 하나의 소프트-인/소프트-아웃(SISO) 모듈 장치를 포함하는 터보 디코더.
  55. 제54항에 있어서, 상기 트리 구조는 병렬 전위 연산 및 병렬 후위 연산을 수행하는 것인 터보 디코더.
  56. 제54항에 있어서, 서로 통신하는 적어도 2개의 SISO 모듈 장치들을 더 포함하며, 상기 SISO 모듈 장치들은 디코딩된 신호의 소프트 정보 측정값을 반복적으로 교환하는 것인 터보 디코더.
  57. 제54항에 있어서, 상기 적어도 하나의 SISO는 상기 수신된 신호의 순방향 및 역방향 상태 메트릭을 계산함으로써 상기 FSM의 소프트 인버스를 계산하는 것인 터보 디코더.
  58. 제54항에 있어서, 상기 적어도 하나의 SISO에 의해 사용되는 상기 트리 구조는 0(log2N)(N은 블록 사이즈임)의 레이턴시를 갖는 SISO를 만드는 트리 구조를 포함하는 것인 터보 디코더.
  59. 제54항에 있어서, 상기 적어도 하나의 SISO에 의해 사용되는 상기 트리 구조는 브랜트-쿵(Brent-Kung) 트리를 포함하는 것인 터보 디코더.
  60. 제54항에 있어서, 상기 적어도 하나의 SISO에 의해 사용되는 상기 트리 구조는 순방향-역방향 트리(FBT)를 포함하는 것인 터보 디코더.
  61. 하나 이상의 블록 인코딩 모듈의 출력에 대응하는 입력 신호를 수신하는 단계와;
    병렬 전위 연산 및 후위 연산을 수행하도록 배열된 트리 구조를 사용하여 상기 수신된 입력 신호의 순방향 및 역방향 상태 메트릭을 계산함으로써 상기 하나 이상의 블록 인코딩 모듈의 소프트 인버스를 결정하는 단계를 포함하는 방법.
  62. 제61항에 있어서, 상기 순방향 및 역방향 상태 메트릭은 적어도 하나의 소프트-인/소프트-아웃(SISO) 모듈에 의해 계산되는 것인 방법.
  63. 제61항에 있어서, 상기 순방향 및 역방향 상태 메트릭은 주변화-조합 연산의 트리-구조 집합을 사용해서 계산되는 것인 방법.
  64. 제63항에 있어서, 상기 주변화-조합 연산은 최소-합 연산을 포함하는 것인 방법.
  65. 제63항에 있어서, 상기 주변화-조합 연산은 최소*-합(min*-sum) 연산을 포함하는 것인 방법.
  66. 제65항에 있어서, 상기 최소*는 min* = min(x, y) - ln(1 + e-｜x-y｜)인 것인 방법.
  67. 제63항에 있어서, 상기 주변화-조합 연산은 합-곱 연산을 포함하는 것인 방법.
  68. 제63항에 있어서, 상기 주변화-조합 연산은 최대-곱 연산을 포함하는 것인 방법.
  69. 제63항에 있어서, 상기 입력 신호는 블록 터보 인코딩된 신호, 저밀도 패리티 체크 코딩된 신호 및 곱 코딩된 신호 중 적어도 하나를 포함하는 것인 방법.
  70. 제63항에 있어서, 상기 하나 이상의 블록 인코딩 모듈의 소프트 인버스를 결정하는 단계는 소프트 정보를 반복적으로 처리하는 단계를 포함하는 것인 방법.
  71. 제70항에 있어서, 상기 반복 처리 단계는 소프트 정보에 대하여 병렬 전위 연산 또는 병렬 후위 연산 또는 양자 모두를 수행하는 단계를 포함하는 것인 방법.
  72. 제70항에 있어서, 상기 반복 처리 단계는 제1 SISO의 소프트 출력을 다른 SISO의 소프트 입력으로서 사용하는 단계를 포함하는 것인 방법.
  73. 제62항에 있어서, 사용되는 상기 트리 구조는 0(log2N)(N은 블록 사이즈임)의 레이턴시를 갖는 SISO 모듈 장치를 만드는 트리 구조를 포함하는 것인 방법.
  74. 제61항에 있어서, 상기 트리 구조는 브랜트-쿵(Brent-Kung) 트리를 포함하는 것인 방법.
  75. 제61항에 있어서, 상기 트리 구조는 순방향-역방향 트리를 포함하는 것인 방법.
  76. 제75항에 있어서, 상기 순방향-역방향 트리는 양방향인 트리 구조 리커전을 포함하는 것인 방법.
  77. 제62항에 있어서, 상기 적어도 하나의 SISO는,
    관찰 간격을 서브간격으로 타일링하고,
    각 서브간격에 최소 하프-윈도우 SISO 연산을 적용하는 것인 방법.
  78. 블록 인코딩 모듈에 의해 인코딩된 신호를 입력으로서 수신하고, 그 수신된 신호와 관련된 소프트 정보를 생성하도록 구성된 복조기와;
    상기 복조기와 통신하고, 병렬 전위 연산 및 후위 연산을 수행하도록 배열된 트리 구조를 사용하여 상기 블록 인코딩 모듈의 소프트 인버스를 계산하도록 구성된 적어도 하나의 소프트-인/소프트-아웃(SISO) 모듈 장치를 포함하는 블록 디코더.
  79. 제78항에 있어서, 상기 트리 구조는 병렬 전위 연산 및 병렬 후위 연산의 조합을 수행하는 것인 블록 디코더.
  80. 제78항에 있어서, 서로 통신하는 적어도 2개의 SISO 모듈 장치들을 포함하며, 상기 SISO 모듈 장치들은 디코딩된 신호의 소프트 정보 측정값을 반복적으로 교환하는 것인 블록 디코더.
  81. 제78항에 있어서, 적어도 하나의 SISO는 상기 수신된 신호의 순방향 및 역방향 상태 메트릭을 계산함으로써 상기 블록 인코딩 모듈의 소프트 인버스를 계산하는 것인 블록 디코더.
  82. 제78항에 있어서, 적어도 하나의 SISO 모듈에 의해 사용되는 상기 트리 구조는 0(log2N)(N은 블록 사이즈임)의 레이턴시를 갖는 SISO 모듈을 만드는 트리 구조를 포함하는 것인 블록 디코더.
  83. 제78항에 있어서, 적어도 하나의 SISO 모듈에 의해 사용되는 상기 트리 구조는 브랜트-쿵(Brent-Kung) 트리를 포함하는 것인 블록 디코더.
  84. 제78항에 있어서, 적어도 하나의 SISO 모듈에 의해 사용되는 상기 트리 구조는 순방향-역방향 트리(FBT)를 포함하는 것인 블록 디코더.
  85. 모듈- 상기 모듈의 소프트 인버스는 모듈의 격자 표현에 순방향-역방향 알고리즘을 실행시킴으로써 계산될 수 있음 - 의 하나 이상의 출력에 대응하는 입력 신호를 수신하는 단계와;
    병렬 전위 연산 및 후위 연산을 수행하도록 배열된 트리 구조를 사용하여 상기 수신된 입력 신호의 순방향 및 역방향 상태 메트릭을 계산하여 상기 모듈의 소프트 인버스를 결정하는 단계
    를 포함하는 방법.
  86. 제85항에 있어서, 상기 입력 신호는 블록 에러 정정 인코딩된 신호, 블록 터보 인코딩된 신호, 저밀도 패리티 체크 코딩된 신호 및 곱 코딩된 신호 중 적어도 하나를 포함하는 것인 방법.
  87. 제85항에 있어서, 상기 입력 신호는 터보 인코딩된 신호 및 컨벌루션 코딩된 신호 중 적어도 하나를 포함하는 것인 방법.
  88. 제85항에 있어서, 상기 인코딩된 신호는 병렬 연접 컨벌루션 코드 및 직렬 연접 컨벌루션 코드 중 적어도 하나를 포함하는 것인 방법.
  89. 제85항에 있어서, 상기 모듈은 유한 상태 기계를 포함하는 것인 방법.
  90. 제85항에 있어서, 상기 모듈은 블록 인코딩 모듈을 포함하는 것인 방법.
  91. 디코딩 방법에 있어서,
    인코딩된 신호를 수신하는 단계와;
    상기 수신된 인코딩된 신호를 복조하여 소프트 정보를 생성하는 단계와;
    하나 이상의 소프트-인/소프트-아웃(SISO) 모듈 - 적어도 하나의 SISO 모듈은 병렬 전위 연산을 수행하기 위한 트리 구조를 사용하여 순방향 상태 메트릭을 계산함 - 을 사용하여 상기 소프트 정보를 반복적으로 처리하는 단계를 포함하는 디코딩 방법.
  92. 제91항에 있어서, 상기 트리 구조는 병렬 후위 연산을 수행함으로써 역방향 상태 메트릭을 계산하도록 더 구성된 것인 디코딩 방법.
  93. 유한 상태 기계(FSM)의 하나 이상의 출력에 대응하는 입력 신호를 수신하는 단계와;
    병렬 전위 연산을 수행하도록 배열된 트리 구조를 사용하여 상기 수신된 입력 신호의 순방향 상태 메트릭을 계산함으로써 상기 FSM의 소프트 인버스를 결정하는 단계를 포함하는 방법.
  94. 제93항에 있어서,
    상기 트리 구조는 병렬 후위 연산을 수행하도록 더 구성되고,
    상기 FSM의 소프트 인버스를 결정하는 단계는, 상기 트리 구조를 사용하여 상기 수신된 입력 신호의 역방향 상태 메트릭을 계산함으로써 상기 FSM의 소프트 인버스를 결정하는 단계를 더 포함하는 것인 방법.
  95. 유한 상태 기계(FSM)에 의해 인코딩된 신호를 입력으로서 수신하고, 그 수신된 신호와 관련된 소프트 정보를 생성하도록 구성된 복조기와;
    상기 복조기와 통신하고, 병렬 전위 연산을 수행하도록 배열된 트리 구조를 사용하여 상기 FSM의 소프트 인버스를 계산하도록 구성된 적어도 하나의 소프트-인/소프트-아웃(SISO) 모듈 장치를 포함하는 터보 디코더.
  96. 제95항에 있어서, 상기 트리 구조는 병렬 후위 연산을 수행하도록 더 구성된 것인 터보 디코더.
  97. 하나 이상의 블록 인코딩 모듈의 출력에 대응하는 입력 신호를 수신하는 단계와;
    병렬 전위 연산을 수행하도록 배열된 트리 구조를 사용하여 상기 수신된 입력 신호의 순방향 상태 메트릭을 계산함으로써 상기 하나 이상의 블록 인코딩 모듈의 소프트 인버스를 결정하는 단계를 포함하는 방법.
  98. 제97항에 있어서,
    상기 트리 구조는 병렬 후위 연산을 수행하도록 더 구성되고,
    상기 하나 이상의 블록 인코딩 모듈의 소프트 인버스를 결정하는 단계는, 상기 트리 구조를 사용하여 상기 수신된 입력 신호의 역방향 상태 메트릭을 계산함으로써 상기 하나 이상의 블록 인코딩 모듈의 소프트 인버스를 결정하는 단계를 더 포함하는 것인 방법.
  99. 블록 인코딩 모듈에 의해 인코딩된 신호를 입력으로서 수신하고, 그 수신된 신호와 관련된 소프트 정보를 생성하도록 구성된 복조기와;
    상기 복조기와 통신하고, 병렬 전위 연산을 수행하기 위한 트리 구조를 사용하여 상기 블록 인코딩 모듈의 소프트 인버스를 계산하도록 구성된 적어도 하나의 소프트-인/소프트-아웃(SISO) 모듈 장치를 포함하는 블록 디코더.
  100. 제99항에 있어서, 상기 트리 구조는 병렬 후위 연산을 수행하도록 더 구성된 것인 블록 디코더.
  101. 모듈- 상기 모듈의 소프트 인버스는 모듈의 격자 표현에 순방향-역방향 알고리즘을 실행시킴으로써 계산될 수 있음 - 의 하나 이상의 출력에 대응하는 입력 신호를 수신하는 단계와;
    병렬 전위 연산을 수행하도록 배열된 트리 구조를 사용하여 상기 수신된 입력 신호의 순방향 상태 메트릭을 계산하여 상기 모듈의 소프트 인버스를 결정하는 단계를 포함하는 방법.
  102. 제101항에 있어서,
    상기 트리 구조는 병렬 후위 연산을 수행하도록 더 구성되고,
    상기 모듈의 소프트 인버스를 결정하는 단계는, 상기 트리 구조를 사용하여 상기 수신된 입력 신호의 역방향 상태 메트릭을 계산함으로써 상기 모듈의 소프트 인버스를 결정하는 단계를 더 포함하는 것인 방법.
  103. 복수의 퓨전 모듈을 포함하는 구조를 가진 데이터를 저장하는 컴퓨터로 판독가능한 매체에 있어서,
    상기 복수의 퓨전 모듈은 병렬 전위 연산을 수행하기 위한 트리 구조로 배열되고 순방향 상태 메트릭을 계산하도록 구성되며,
    각 퓨전 모듈은 다음의 수학식으로서 정의되고,
    Figure 112005046256024-pct00078
    c(k, m)은 sk와 sm 사이의 소프트 입력에 기초한 상태 쌍 sk와 sm의 최소 시퀀스 메트릭(MSM)의 매트릭스인 것인 컴퓨터로 판독가능한 매체.
  104. 제103항에 있어서, 상기 복수의 퓨전 모듈은 병렬 후위 연산을 수행하기 위한 트리 구조로 또한 배열되고 역방향 상태 메트릭을 계산하도록 더 구성된 것인 컴퓨터로 판독가능한 매체.
  105. 순방향 및 역방향으로 주변화-조합 연산을 수행하는 하나 이상의 완성 퓨전 모듈(complete fusion modules, CFM)과;
    순방향으로만 주변화-조합 연산을 수행하는 하나 이상의 순방향 퓨전 모듈(forward fusion modules, fFM)과;
    역방향으로만 주변화-조합 연산을 수행하는 하나 이상의 역방향 퓨전 모듈(backward fusion modules, bFM)
    을 포함하는 구조를 가진 데이터를 저장하는 컴퓨터로 판독가능한 매체로서,
    상기 하나 이상의 CFM, fFM 및 bFM은 병렬 전위 연산 및 후위 연산을 수행하기 위한 트리 구조로 배열되는 것인 컴퓨터로 판독가능한 매체.
  106. 블록 인코딩 모듈에 의해 인코딩된 신호를 입력으로서 수신하고, 그 수신된 신호와 관련된 소프트 정보를 생성하도록 구성된 복조기와;
    상기 복조기와 통신하고, 병렬 전위 연산을 수행하기 위한 트리 구조를 사용하여 상기 블록 인코딩 모듈의 소프트 인버스를 계산하도록 구성된 적어도 하나의 소프트-인/소프트-아웃(SISO) 모듈을 포함하는 구조를 가진 데이터를 저장하는 컴퓨터로 판독가능한 매체.
  107. 제106항에 있어서, 상기 트리 구조는 병렬 후위 연산을 수행하도록 더 구성된 것인 컴퓨터로 판독가능한 매체.
KR1020027014808A 2000-05-03 2001-05-03 레이턴시를 줄인 ｓｉｓｏ 모듈 Expired - Fee Related KR100566745B1 (ko)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
US20158300P 2000-05-03 2000-05-03
US60/201,583 2000-05-03
PCT/US2001/014460 WO2001084720A1 (en) 2000-05-03 2001-05-03 Reduced-latency soft-in/soft-out module

Publications (2)

Publication Number Publication Date
KR20030005322A KR20030005322A (ko) 2003-01-17
KR100566745B1 true KR100566745B1 (ko) 2006-04-03

Family

ID=22746419

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020027014808A Expired - Fee Related KR100566745B1 (ko) 2000-05-03 2001-05-03 레이턴시를 줄인 ｓｉｓｏ 모듈

Country Status (5)

Country Link
US (2) US20020021770A1 (ko)
JP (1) JP3854155B2 (ko)
KR (1) KR100566745B1 (ko)
AU (2) AU2001259481B2 (ko)
WO (1) WO2001084720A1 (ko)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101323444B1 (ko) 2011-02-08 2013-10-29 인텔 모바일 커뮤니케이션스 게엠베하 반복적 디코더 및 반복적 디코딩 방법

Families Citing this family (36)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20010044919A1 (en) * 2000-05-05 2001-11-22 Edmonston Brian S. Method and apparatus for improved perormance sliding window decoding
EP1290802A1 (en) * 2000-06-16 2003-03-12 Aware, Inc. Systems and methods for ldpc coded modulation
US7096412B2 (en) * 2000-06-19 2006-08-22 Trellisware Technologies, Inc. Method for iterative and non-iterative data detection using reduced-state soft-input/soft-output algorithms for complexity reduction
US7246304B2 (en) * 2001-09-01 2007-07-17 Dsp Group Inc Decoding architecture for low density parity check codes
US7107512B2 (en) * 2002-05-31 2006-09-12 Broadcom Corporation TTCM decoder design
CN100440736C (zh) * 2002-07-03 2008-12-03 休斯电子公司 用于低密度奇偶校验码解码器中的路由的方法和系统
US7577207B2 (en) * 2002-07-03 2009-08-18 Dtvg Licensing, Inc. Bit labeling for amplitude phase shift constellation used with low density parity check (LDPC) codes
US7020829B2 (en) * 2002-07-03 2006-03-28 Hughes Electronics Corporation Method and system for decoding low density parity check (LDPC) codes
US20040019845A1 (en) * 2002-07-26 2004-01-29 Hughes Electronics Method and system for generating low density parity check codes
US7864869B2 (en) * 2002-07-26 2011-01-04 Dtvg Licensing, Inc. Satellite communication system utilizing low density parity check codes
US7173985B1 (en) * 2002-08-05 2007-02-06 Altera Corporation Method and apparatus for implementing a Viterbi decoder
WO2004028004A2 (en) * 2002-09-18 2004-04-01 Koninklijke Philips Electronics N.V. Method for decoding data using windows of data
WO2004112258A1 (en) * 2003-06-12 2004-12-23 Arithmatica Limited High speed viterbi decoding and detection using an iterative trellis collapsing algorithm
GB2407949B (en) 2003-11-04 2006-03-15 Arithmatica Ltd A calculating apparatus and method for use in a maximum likelihood
JP2005210238A (ja) * 2004-01-21 2005-08-04 Nec Corp ターボ復号装置及びその方法並びにその動作プログラム
US7487432B2 (en) * 2004-05-25 2009-02-03 Agere Systems Inc. Method and apparatus for multiple step Viterbi detection with local feedback
US7616695B1 (en) 2004-06-17 2009-11-10 Marvell International Ltd. MIMO equalizer design: an algorithmic perspective
CN101341659B (zh) * 2004-08-13 2012-12-12 Dtvg许可公司 用于多输入多输出通道的低密度奇偶校验码的码设计与实现的改进
US7206364B2 (en) * 2005-02-14 2007-04-17 Viasat, Inc. Iterative diversity reception
US7978759B1 (en) * 2005-03-24 2011-07-12 Marvell International Ltd. Scalable equalizer for multiple-in-multiple-out (MIMO) wireless transmission
KR20070025145A (ko) * 2005-08-31 2007-03-08 삼성전자주식회사 소프트 복호화 방법 및 장치, 에러 정정 방법 및 장치,소프트 출력 방법 및 장치
US20070113161A1 (en) * 2005-11-14 2007-05-17 Texas Instruments Incorporated Cascaded radix architecture for high-speed viterbi decoder
KR101351140B1 (ko) * 2005-11-22 2014-01-15 조지아 테크 리서치 코오포레이션 통신 시스템에서 신호 송수신 장치 및 방법
US8091009B2 (en) * 2006-03-23 2012-01-03 Broadcom Corporation Symbol by symbol map detection for signals corrupted by colored and/or signal dependent noise
EP1942578A1 (en) * 2006-11-29 2008-07-09 Broadcom Corporation Address generation for contention-free memory mappings of turbo codes with ARP (almost regular permutation) interleaves
US7986441B2 (en) * 2007-04-04 2011-07-26 Wong Technologies L.L.C. Embedding watermark into halftone image with low distortion using parity values for overlapping groups of candidate sites
US8259868B1 (en) 2007-09-25 2012-09-04 University Of Southern California Conditionally cycle-free generalized tanner graphs based decoding
US8077790B2 (en) * 2007-10-23 2011-12-13 Eric Morgan Dowling Tiled-building-block trellis encoders
US8156409B2 (en) * 2008-02-29 2012-04-10 Seagate Technology Llc Selectively applied hybrid min-sum approximation for constraint node updates of LDPC decoders
US8171384B2 (en) * 2008-06-27 2012-05-01 Freescale Semiconductor, Inc. Device having turbo decoding capabilities and a method for turbo decoding
TWI376105B (en) * 2009-06-15 2012-11-01 Univ Nat Taiwan Tree decoding method for linear block codes
KR101268061B1 (ko) 2011-10-21 2013-05-28 단국대학교 산학협력단 다상-누산 코드를 이용한 부호화 방법 및 복호화 방법
CN103532571A (zh) * 2012-07-05 2014-01-22 联芯科技有限公司 Log-MAP译码方法和译码器
US9008073B1 (en) * 2012-12-07 2015-04-14 Maxim Integrated Products, Inc. Routing for power line communication systems
US10075186B2 (en) 2015-11-18 2018-09-11 Cisco Technology, Inc. Trellis segment separation for low-complexity viterbi decoding of high-rate convolutional codes
US10367600B2 (en) * 2017-08-09 2019-07-30 Ciena Corporation Forward error correction with contrast coding

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE3750456T2 (de) * 1986-09-22 1995-04-20 Nippon Electric Co Fehlerkorrigierender, bitserieller Dekodierer.
US5014276A (en) * 1989-02-06 1991-05-07 Scientific Atlanta, Inc. Convolutional encoder and sequential decoder with parallel architecture and block coding properties
SG44761A1 (en) * 1991-01-09 1997-12-19 Philips Electronics Uk Ltd Signal transmission system
US6233290B1 (en) * 1995-04-13 2001-05-15 California Institute Of Technology Method for noncoherent coded modulation
US5933462A (en) * 1996-11-06 1999-08-03 Qualcomm Incorporated Soft decision output decoder for decoding convolutionally encoded codewords
US5930272A (en) * 1997-06-10 1999-07-27 Efficient Channel Coding, Inc. Block decoding with soft output information
US6484283B2 (en) * 1998-12-30 2002-11-19 International Business Machines Corporation Method and apparatus for encoding and decoding a turbo code in an integrated modem system
FI106416B (fi) * 1999-02-09 2001-01-31 Nokia Mobile Phones Ltd Menetelmä ja laite dekoodatun symbolisarjan luotettavuuden määrittämiseksi
US6304996B1 (en) * 1999-03-08 2001-10-16 General Electric Company High-speed turbo decoder
US6343103B1 (en) * 1999-09-03 2002-01-29 Agere Systems Guardian Corp. Methods and apparatus for representation of branch metrics in a communication system decoder
US6769007B2 (en) * 2001-04-05 2004-07-27 Sun Microsystems, Inc. Adder circuit with a regular structure

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101323444B1 (ko) 2011-02-08 2013-10-29 인텔 모바일 커뮤니케이션스 게엠베하 반복적 디코더 및 반복적 디코딩 방법

Also Published As

Publication number Publication date
AU5948101A (en) 2001-11-12
WO2001084720A9 (en) 2002-12-19
US20040237025A1 (en) 2004-11-25
JP2003533088A (ja) 2003-11-05
JP3854155B2 (ja) 2006-12-06
AU2001259481B2 (en) 2004-05-20
US20020021770A1 (en) 2002-02-21
US7197691B2 (en) 2007-03-27
KR20030005322A (ko) 2003-01-17
WO2001084720A1 (en) 2001-11-08

Similar Documents

Publication Publication Date Title
KR100566745B1 (ko) 레이턴시를 줄인 ｓｉｓｏ 모듈
AU2001259481A1 (en) Reduced-latency soft-in/soft-out module
Hashemi et al. A fast polar code list decoder architecture based on sphere decoding
Masera et al. VLSI architectures for turbo codes
Mandwale et al. Implementation of High Speed Viterbi Decoder using FPGA
Levine et al. Implementation of near Shannon limit error-correcting codes using reconfigurable hardware
US6591390B1 (en) CRC-based adaptive halting turbo decoder and method of use
US7020827B2 (en) Cascade map decoder and method
US7464316B2 (en) Modified branch metric calculator to reduce interleaver memory and improve performance in a fixed-point turbo decoder
US7266757B1 (en) Pipelined architecture implementing recursion processes for forward error correction
Sklar Fundamentals of turbo codes
US7178090B2 (en) Error correction code decoding device
Li et al. Unified convolutional/turbo decoder design using tile-based timing analysis of VA/MAP kernel
US20070113161A1 (en) Cascaded radix architecture for high-speed viterbi decoder
Muller et al. Spc05-3: On the parallelism of convolutional turbo decoding and interleaving interference
Beerel et al. A low latency SISO with application to broadband turbo decoding
Dong et al. Design and FPGA implementation of stochastic turbo decoder
US7698624B2 (en) Scheduling pipelined state update for high-speed trellis processing
Beerel et al. An/spl Oscr/(log/sub 2/N)-latency SISO with application to broadband turbo decoding
Martina et al. VLSI architectures for WiMAX channel decoders
Moncayo et al. Performance evaluation of a Turbo Codec with Log-MAP algorithm on FPGA and CPU
Scholl Hardware Implementations of Trellis based Decoders for Linear Block Codes
Leonardi Hardware implementations of trellis based decoders for linear block codes
Werling A Hardware Implementation of the Soft Output Viterbi Algorithm for Serially Concatenated Convolutional Codes
Liu MAP algorithms applied to linear block codes with sectionalized trellis diagrams

Legal Events

Date Code Title Description
PA0105 International application

St.27 status event code: A-0-1-A10-A15-nap-PA0105

PG1501 Laying open of application

St.27 status event code: A-1-1-Q10-Q12-nap-PG1501

A201 Request for examination
P11-X000 Amendment of application requested

St.27 status event code: A-2-2-P10-P11-nap-X000

P13-X000 Application amended

St.27 status event code: A-2-2-P10-P13-nap-X000

PA0201 Request for examination

St.27 status event code: A-1-2-D10-D11-exm-PA0201

R17-X000 Change to representative recorded

St.27 status event code: A-3-3-R10-R17-oth-X000

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

St.27 status event code: A-1-2-D10-D21-exm-PE0902

R17-X000 Change to representative recorded

St.27 status event code: A-3-3-R10-R17-oth-X000

T11-X000 Administrative time limit extension requested

St.27 status event code: U-3-3-T10-T11-oth-X000

T11-X000 Administrative time limit extension requested

St.27 status event code: U-3-3-T10-T11-oth-X000

T11-X000 Administrative time limit extension requested

St.27 status event code: U-3-3-T10-T11-oth-X000

P11-X000 Amendment of application requested

St.27 status event code: A-2-2-P10-P11-nap-X000

P13-X000 Application amended

St.27 status event code: A-2-2-P10-P13-nap-X000

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

St.27 status event code: A-1-2-D10-D22-exm-PE0701

GRNT Written decision to grant
PR0701 Registration of establishment

St.27 status event code: A-2-4-F10-F11-exm-PR0701

PR1002 Payment of registration fee

St.27 status event code: A-2-2-U10-U12-oth-PR1002

Fee payment year number: 1

PG1601 Publication of registration

St.27 status event code: A-4-4-Q10-Q13-nap-PG1601

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

FPAY Annual fee payment

Payment date: 20090324

Year of fee payment: 4

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 4

LAPS Lapse due to unpaid annual fee
PC1903 Unpaid annual fee

St.27 status event code: A-4-4-U10-U13-oth-PC1903

Not in force date: 20100328

Payment event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

PC1903 Unpaid annual fee

St.27 status event code: N-4-6-H10-H13-oth-PC1903

Ip right cessation event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

Not in force date: 20100328

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000