펄스 위치 변조 멀티-소스 시스템을 위한 최대 우도 디코더 document_id A220623056013

ML (Maximum Likelihood) 수신기들이라고도 알려진, 최대 우도의 기준을 사용하는 수신기들이, 전송 채널이 가우시안 (Gaussian)일 때 최적이라고 전기통신 분야에서 잘 알려져 있다. 이 수신기들에 대한 설명은, 예를 들어, J.G. Proakis의 "Digital communications"라는 제목의 연구서, 4번째 판, 242-247 페이지에서 찾아 볼 수 있다. 최대 우도 수신기들은 특히 모바일 통신 분야에서 심사숙고되어 왔다. MAI (multi access interference, 멀티 액세스 간섭)을 제거하기 위해, 전송 채널 상으로 서로 다른 사용자들에 의해 방출 (발산)된 심볼들을 동시에 디코딩할 수 있는 ML 수신기 (멀티-사용자 ML 수신기)가 사용될 수 있다. 최대 우도의 기준에 따라 이 사용자들에 의해 전송된 심볼들을 추정하는 것은 네트워크의 포인트들 가운데에서 MK (M은 K 명의 사용자들에 의해 사용된 변조의 차원) 차원 공간 내에서 수신된 신호를 대표하는 한 포인트에 어느 것이 가장 가까운지를 서치하는 것으로 귀착된다는 것을 보여줄 수 있다. 포인트들의 네트워크는 서로 다른 사용자들의 변조 컨스텔레이션 (constellation)에 의해 생성된다. 이러한 방법은 많은 K에 대해 복잡하다는 것이 빠르게 드러나므로, 보통은 가장 가까운 이웃에 대한 서치를, 수신(된) 포인트를 중심으로 하는 잡음 구 (noise sphere)에 속한 네트워크의 포인트들로 제한하는 "스피어 디코딩 (sphere decoding)"이라 알려진 디코딩에 의존한다. 스피어 디코더에 대한 설명은 1999년 7월 IEEE 정보 이론 분야의 회보 45권 1639-1642 페이지에 실린 E. Viterbo 등의 논문 제목 "A universal lattice code decoder for fading channels"에서 찾을 수 있다. 스피어 디코딩은 PAM이나 QAM 타입 변조 컨스텔레이션을 이용하는 시스템에 적용되어 왔다. 보다 최근에 들어서, 스피어 디코딩은 MIMO (Multiple Input Multiple Output) 시스템 수신기들을 구현하는데 제안되어 왔다. MIMO 시스템은, 적어도 한 방출기 (emitter)가 복수의 안테나를 사용해 정보 심볼들을 전송하는 통신 시스템을 의미하는 것으로 간주 된다. 수신기는 한 개의 안테나 (MISO (Multiple Input Single Output) 시스템이 더 명시적으로 사용됨)나 복수의 안테나를 가질 수 있으며, MIMO라는 용어는 여기서 그러한 두 가지 구성을 구별하지 않고 지칭하도록 선택되었다. MIMO 시스템의 경우, 포인트들의 네트워크는 서로 다른 안테나에 의해 심볼들을 전송하는데 사용되는 변조 컨스텔레이션들에 의해 생성된다. MIMO 시스템의 스피어 디코딩의 일 실시예를, 2003년 10월, IEEE 정보 이론 분야 회보, 제49권, 제10호, 2389-2402 페이지에 공개된 M.O. Damen 등의 "On Maximum-Likelihood detection and the search for the closest lattice point"라는 제목의 논문에서 찾을 수 있다. 이러한 스피어 디코더에서는 PAM 및 QAM 변조만이 고찰된다. 이하의 설명에서, 포괄적 용어인 멀티-소스는 멀티-사용자 구성을 MIMO 구성과 동등하게 지칭한다. 제1경우에서, 소스들은 서로 다른 사용자들로부터 혹은 그들에게로의 심볼들의 플로우를 나타내고, 제2경우에서, 그 소스들은 서로 다른 안테나들에 의해 방출된 심볼들의 플로우를 나타낸다는 것을 알게 될 것이다. 이러한 두 경우들은 사용자들의 단말들이 멀티-안테나 타입일 때 합쳐질 수 있다는 것이 자명하다. 또, 심볼들의 흐름은 동기식 (synchronous)이라고 전제될 것이다. 스피어 디코딩 ML 수신기는 K 명의 사용자들에 대한 경우를 통해 설명될 것이고, 각 사용자 는 ik 개의 안테나를 사용해 수신기로, 즉, 총 개수가 인 소스들을 전송한다. 수신된 신호를 벡터 식에 따라 표현할 수 있다: 여기서, 위에서, x 는 P' 차원의 결정 변수들로 된 벡터이고, P'는 수신기의 안테나 개수와, 수신 안테나당 관측된 결정 변수들의 수 (예를 들어, 안테나당 정해진 경로들의 수)를 곱한 것과 같다. a 는 벡터들 a (1) , a (2) ,.., a (P) 의 연결에 의해 구해진, PM 사이즈의 벡터로서, 각 벡터 a (P) ( )는 p 번째 소스에 의해 전송된 정보 심볼의 벡터 표현이고, 사용된 변조방식의 차원과 같은 M 차원으로 되어 있다. H 는 전송 채널을 나타내는 P'xPM 사이즈의 매트릭스로서, 그것은 특히 서로 다른 안테나로부터의 경로들간, 그리고 사용자들간 간섭을 나타낸다. n 은 P' 차원의 벡터이고, 그 성분들은 수신된 신호에 영향을 미치는 중앙집중 부가 가우시안 백색 잡음 (centered additive Gaussian white noise)의 샘플들이다. 최대 우도 수신기는 수신된 벡터를 가지고 이분 편차 (quadratic deviation) 를 최소화하는 벡터 를, 다음 식과 같이 추정한다. CP는 P 개의 소스들의 각 컨스텔레이션들로부터의 곱 컨스텔레이션 (product constellation)이다. 수학식 2는 아래의 수학식 3과 같은 방식으로 쓰여질 수 있다는 것을 알 수 있다. 여기서, z= Q T x 이고, Q 및 R 은 각각 사이즈 P'xP인 단위 매트릭스 및, 매트릭스 H의 QR 분해, 즉 R T R = H T H 에 의해 얻어지는 PxP 사이즈의 상위 삼각 (triangular) 매트릭스이다. PAM 또는 QAM 컨스텔레이션들에 있어서, 이후 경시될 기본 선형 연산 을 사용하여, 생성된 컨스텔레이션의 포인트들이 ZMP의 요소들인 경우로 되는 것이 여전히 가능하며, 이때 Z는 모든 상대 정수들이고, M은 변조 컨스텔레이션들의 차원이다. 벡터들 Ra 는 이제 매트릭스 R 을 생성하는 네트워크 의 포인트들로서 나타내어 질 수 있다. 스피어 디코딩은, 수신된 신호를 대표하는 포인트 z 를 중심으로 하는 (MP 차원의 공간의) 구 안에서 가장 가까운 이웃에 대한 서치를 수행하는 동작에 존재한다. 그 서치는 이 구 안에 포함된 의 포인트들 사이에서 수행된다. 후보들이 연속적으로 선택되는 (혹은 계수(열거)되는 (enumerated)) 방식이, 디코딩 알고리즘 성능을 위해 매우 중요하다. 본래 두 계수 (enumeration) 기술들이 알려져 있는데, 하나는 Pohst로 알려져 있고, 다른 하나는 Schnorr-Euchner로 알려져 있다. Pohst 계수를 이용하는 스피어 디코딩을 먼저 설명할 것이다. 예시의 필요성에 따라, 변조방식이 PAM 타입이라는 것, 달리 말해, 고려되는 공간이 P 차원이라는 것이 전제될 것이다. 그것은 QAM 변조방식에도 적용되고, 그때 공간의 차원은 2P이다. 차원별로, 혹은 일반적인 용어에 따르면, 계층별로, 각 계층 마다 의 한 후보 포인트의 좌표를 선택함으로써 서치가 수행된다. 이차 거리 (quadratic distance) (수학식 3)에 대한 계층 P의 기여분 (contribution)은 간단히 다음의 수학식 4와 같다. 같은 방식으로, 이러한 이차 거리에 대한 계층 P-1의 기여분은 수학식 5에 의해 표현된다. 일반적으로, 계층 i의 기여분은 수학식 6에 의해 표현된다. Ei는 으로 정의된다. Ti가 연속 계층들 i+1,...,P의 기여분을 지칭할 때, 그것은 하향 반복 (descending recurrence)에 의해 얻어질 수 있다. 여기서, Tp=0이다. 앞의 관례들을 통해, 이차 반경 d인 구 안에서의 서치는 결국, 계층들 각각에 대해 수학식 8을 입증하는 Z의 값들 ai를 결정하는 일이 된다: 또는, 그 서치가 등가적 방식으로서, 계층들 각각에 대해 수학식 9를 입증하는 Z의 값들 ai를 결정하는 일이 된다. 마지막으로, PAM 컨스텔레이션이 대략 2의 멱수인 M'이고, 상술한 선형 변환이 일 때 이면, 서치는 인터벌 에 속하는 홀수의 정수들로 감축될 수 있다. 는 x 보다 큰 최소 정수이고 는 x 보다 작은 최대 정수이다. 이러한 서치 인터벌의 감소는 사실 수학식 9에 정의된 것 같은 인터벌과, 당해 차원상으로의 컨스텔레이션의 프로젝션 (projection)과의 교차부 (intersection)에 해당한다. 따라서 각 계층마다 유효 인터벌이 규정된다. 그것은 상위 계층들에서 값들 ai에 대해 이미 이뤄진 선택을 고려하여, 이 계층의 최대 용인 가능 편위 (excursion)를 제공한다. 도 1은 P=2이고 M'=4인 간단한 경우의 스피어 (sphere) 디코더의 원리를 나타낸 것이다. 스피어 (구)는 십자표시로 나타낸 포인트 z 를 중심으로 한다. 생성된 컨스텔레이션 C2의 포인트들은 원들로 표현된다. 계층 2의 유효 인터벌 [A2, B2]은, 구의 프롤젝션과 컨스텔레이션의 프로젝션과의 교차에 다름 아니며, 여기서 그것은 [A2, B2]=[-3, 3]이다. 유효 인터벌 [A1, B1]은 이제 [A2, B2] 내 값 a2의 선택에 의해 정해진다. 따라서, 도시된 예에서는 a2=1에 대해, 유효 인터벌이 [A1, B1]=[-3, 1]이 된다는 것을 알 수 있다. 도 2는 Pohst 계수를 이용한 스피어 디코딩 방법의 흐름도를 도시한 것이다. 210 단계에서, 계층 인덱스, 중간 변수들 및 구의 서치 반경에 대한 초기화가 이뤄진다, 즉, i=P; TP=0; EP=0; d=D로 되고 D는 서치 구의 초기 이차 반경이다. D는 잡음 전력 추정 함수로서 선택된다. 220 단계에서, Ti003e#d인지, 즉 인터벌이 빈 어셈블리 (empty assembly)로 줄어들었는지를 테스트한다. 그렇게 되었으면, 223 단계에서 i=P인지를 테스트하고 그것에 대한 결과가 긍정이면 알고리즘이 225 단계에서 종료된다. 그에 대한 결과가 부정이면, i를 1만큼 증가시키고 230 단계로 이동한다. Ti ≤d이면, 230 단계에서 수학식 10에 따라 바운드들 Ai 및 Bi를 산출하고 ai를 ai=Ai-2로 초기화한다. 240 단계에서, ai를 2 만큼 증가시키고 250 단계에서 해당 포인트가 여전히 인터벌 안에 존재하는지, 즉 ai≤Bi인지를 테스트한다. 테스트 결과가 부정이면, 테스트 223 단계로 돌아가고 긍정적이면 260 단계에서 i=1인지를 테스트한다. i=1이 아니면, 263 단계로 가서 i는 1 만큼 감소 되고, 새 값들 Ei-1과 Ti-1이 산출된다. 한편, 최하위 계층 i=1에 도달하였을 때, 270 단계에서 이 나중 계층의 기여분을 더하여 포인트 z 에서 선택된 후보의 거리, 즉, 를 구하도록 한다. 280단계에서 그 거리를 현재의 이차 반경 d와 비교한다. 그 거리가 더 작으면, 구의 반경을 결과적으로 로 축소하고, 최선의 후보를 로 업데이트한다. 모든 경우들 다음에 240 단계로 리턴이 이뤄진다. 위에 상세히 설명한 알고리즘은 계층별로 하위 바운드들부터 상위 바운드들을 향해 유효 인터벌들을 스캐닝함으로써 서치를 수행하는 것으로, 최고속 스캐닝은 최상위 계층 (i=P)에서 수행되고, 최저속 스캐닝은 최하위 계층 (i=1)에서 수행된다. 한 계층 내 후보의 새 좌표에 대한 각 선택시, 상위 계층들의 유효 인터벌들의 바운드들이 재산출된다. 또한, 수신된 포인트까지의 거리가 개선되자마자, 구의 반경을 업데이트하여, 서치가 가속화될 수 있도록 한다. 마지막으로, 알고리즘의 출력 벡터는 수신된 포인트 z 에 대해 가장 가까운, 생성 컨스텔레이션의 포인트이다. Pohst 계수를 이용한 스피어 디코딩은, 이들의 하위 바운드들부터 유효 인터벌을 규칙적으로 스캐닝하기 때문에 매우 느리다. Schnorr-Euchner 계수를 이용한 스피어 디코딩이 실질적으로 상술한 디코딩 보다는 고속이다. 그것은 전송된 신호의 최초 추정에 해당하는 곱 컨스텔레이션의 포인트 부터 서치를 수행하는 것이 더 효과적이라는 원리에 기초하고 있다. 더 명확히 말해, 이 포인트는 ZF-DFE 타입 이퀄라이제이션 (equalisation)을 이용해 얻어진다. ZF-DFE 타입 이퀄라이제이션에서는, 다음 (하위) 계층들에서, 한 계층 (한 사용자)에서 기인한 간섭을 빼는데, 각 계층에서의 결정이 스피어 디코더에 의해 취하여 진다. 즉, 계층 P부터 시작함으로써 수학식 11이 얻어진다. , , i=P-1,...,1 round(y)는 (이전의 선형 변환 의 형식으로) y에 가장 가까운 홀수인 상대 정수를 나타낸다. 각 계층 i는 같이 네트워크의 포인트 a 부터 수신 포인트 z 까지의 이차 거리에 기여한다. 가장 가까운 이웃에 대한 서치는 각 계층 i마다 좌표들 , , , , 등 ( )을 계속해서 고려함으로써 수행된다. 그에 따라 부터 시작해서 이러한 추정의 어느 한 편으로 지그재그 형태로 진행하면서 동시에 유효 인터벌 안에 반드시 머물게 된다는 것을 알게 될 것이다. 도 3은 Schnorr-Euchner 계수를 이용하는 스피어 디코딩 방법의 흐름도를 보인 것이다. 310 단계에서, 계층 인덱스, 중간 변수들 및 구의 서치 반경이 초기화된다, 즉: i=P; ; TP=0; d=D (D는 서치 구의 초기 이차 반경이다). 320 단계에서, ZF-DFE 이퀄라이제이션: , ( )을 수행하고, 초기 좌표값 및 초기 서치 방향 을 정한다. 330 단계에서, 포인트가 구 안에 있는지를 테스트한다, 즉 인지를 테스트한다. 테스트 결과가 부정이면, 350 단계로 이동한다. 테스트 결과가 긍정이면 340 단계에서 그것이 실제로 컨스텔레이션 안에 있는지, 즉 를 확인한다. 그것이 컨스텔레이션 안에 없는 경우이면, 380 단계로 이동한다. 후보 ai가 유효 인터벌 (구와 컨스텔레이션 교차부의 프로젝션) 안에 있으면, 345 단계에서 최하위 계층, i=1에 도달했는가를 테스트한다. 도달하였으면, 360 단계로 진행한다. 도달하지 않았으면, 347 단계에서 중간 변수들을 업데이트하고: , i를 1만큼 감소시킨다. 이제 320 단계로 리턴한다. 350 단계에서 i=P인지를 테스트한다. 그것이 맞으면, 알고리즘은 355 단계에서 종료되고, 그렇지 않으면 370 단계로 이동하여 i를 1만큼 증가시킨다. 345 단계에서, i=1이면, 최하위 계층에 도달하였으므로 포인트 후보를 찾은 것이다. 이 계층의 기여분을 더하여, 포인트 z 까지의 선택된 후보의 거리를 구한다, 즉, . 360 단계에서 그 거리와 현재의 이차 반경 d를 비교한다. 그 거리가 d보다 적으면, 365 단계에서 거리를 로 업데이트하고 최인접 이웃을 로 업데이트한다. 모든 경우들에서, 370 단계로 가서 i를 1만큼 증가시킨다. 마지막으로 380 단계에서, ai를 로 업데이트 하고 ( ) 330 단계로 리턴한다. 도 4a 및 4b는 각각, Pohst 계수 및 Schnorr-Euchner에 따른 포인트 스캐닝을 개략적으로 나타낸 것이다. 컨스텔레이션은 4-PAM이었고 소스들의 개수 P는 3이라고 전제하였다. 서로 다른 라인들은 P=3 차원에 따른 프로젝션들에 해당한다. 십자표시로 z 의 성분들을 표시하였고 원으로 PAM 변조 컨스텔레이션들의 포인트들을 표시하였다. 두 경우들 모두, 알고리즘에 의해 연속적으로 커버 되는 브랜치들이 (1), (2) 등으로 표시되고 있다. 스피어 디코딩은 PAM 및 QAM 변조방식을 위해서는 수많은 연구의 주제가 되어 왔지만, 최근에 들어와서야 겨우 PPM (Pulse Position Modulation) 변조방식을 위한 것으로 고찰되고 있다. 이런 타입의 변조방식에 대한 스피어 디코딩은 개인, 실내 및 모바일 통신 (PIRMC'06) 분야 17차 연례 IEEE 국제 회의 절차 중 공개된 C. Abou-Rjeily 등의 "MIMO UWB communications using modified Hermite pulses"라는 제목의 논문에서 펄스 타입 UWB MIMO 시스템을 위해 제안되었다. 펄스형 UWB 시스템은 (몇몇 피코 초들 (picoseconds)의 열인) 매우 간결한 펄스 프레임들의 기저 대역 전송을 이용하는 시스템이라는 것을 상기해야 할 것이다. 전송된 심볼들은 변조 알파벳 M -PPM에 속하거나, 보다 일반적 방식으로서, 하이브리드 변조방식 M -PPM- M' -PAM에 속한다. 변조 알파벳의 카디널 (cardinal)은 MM'이다. M 개의 시간의 위치들 각각에 대해, M' 개의 변조 크기들이 가능하다. 이 알파벳의 심볼 a는 시퀀스 am으로 나타낼 수 있고 이때, m=0,...,M-1이고, 이며, 는 변조 M -PPM의 위치이고, 는 PAM 변조의 크기(진폭)이고, 는 Dirac 분포이다. 각각의 PPM 또는 PPM-PAM 심볼은 시간의 위치들을 변조하고, 필요하다면, 시간의 위치들과 프레임의 기본 펄스들의 진폭들을 변조한다. 심볼 M -PPM (및 M -PPM- M' -PAM)을 M 차원의 벡터라고 간주할 수 있고, 그 성분들 중 오직 하나만 1 (및 )이고 다른 것들은 0으로 되어 있다. QAM 변조와는 달리, PPM 또는 PPM-PAM 심볼의 성분들은 그러므로 독립적인 것이 못된다. P 개의 소스들이 PPM 심볼들을 전송한다고 가정할 때, 고려될 신호들의 공간은 MP 차원이다. 이 공간에서, 각각의 소스는 PPM이나 PPM-PAM 심볼의 M 개의 시간 위치들 (또는 서브-계층들)로 이뤄진 한 계층으로 표현된다. 상술한 논문에서 기술된 스피어 디코딩은 M개의 연속 계층들을 이들의 상호 종속성으로 인해 공유 방식 (joint manner)에 따라 다룰 것을 제안하고 있다. 수학식 8은 이제, 말하자면 p차 계층에 대해, M 개의 연속 서브-계층들을 연결하는 구속자 (constraint)로 대체된다: 여기서, z (p) 는 수신된 신호를 대표하는 z 의 서브 벡터이다, 즉 벡터 z 는 각각이 한 소스에 대응하는 P 개의 벡터들 z (1) ,.., z (P) 의 연결에 의해 형성되며, zm(p) 는 이 소스에 의해 방출된 PPM 또는 PPM-PAM 심볼의 m 번째 성분이다; 함수 f는 f(p,m)=(p-1)M+m으로 주어진다; Tp는 계층들 p+1,...,P의 이차 거리에 대한 기여분들의 합이다. 각각의 소스 p마다, 전송이 오직 한 위치 에 대해서만 일어난다고 할 때, 수학식 12는 다음과 같은 식으로 다시 재작성될 수 있다: 아니면 수학식 12는 더 간결한 형식으로서 다음과 같이 쓰여질 수 있다: 여기서, 벡터 a 는 벡터 z 처럼 P 개의 벡터들 a (1) , a (2) ,.., a (P) 연결로 형성되며, a (p) 는 성분들 로 되고, 이때 m=1,..,M이다; R (i,j) 는 m=(i-1)M+1,..,iM이고 m'=(j-1)M+1,..,jM일 때 요소들 rm,m'로 이뤄진 R 의 서브 매트릭스 M x M이다; 소정 매트릭스 에 있어서, 는 통상적으로 이 매트릭스의 k 번째 열 (column)을 가리킨다; 는 매트릭스 E 의 p번째 열로서 로 정의된다. 수학식 14로부터 소스 p에 대응하는 M개의 서브 계층들은 합동으로 다뤄짐을 알 수 있을 것이다. 특히, m=1,..,M인 성분들 am(p) 각각의 유효 인터벌들의 바운드들이 동시에 정해진다. 이러한 바운드들은 상위 계층들에 대해 이미 선택된 후보들 a (p+1) ,.., a (P) 에 좌우된다. 이러한 스피어 디코딩에 사용되는 계수 기술은 Pohst 계수의 확장이라고 간주 될 수 있다. 계층당 한 위치만을 선택하는 사전 조치를 취함으로써 각 계층의 시간의 위치들이 하위 바운드들부터 하나씩 스캐닝 된다. 따라서 디코딩의 수렴은 상대적으로 느려진다. 또, Schnorr-Euchner 타입 계수 기술의 직접적인 어플리케이션은 서브 계층들, 즉, 동일한 계층의 PPM 위치들이 독립적이지 않기 때문에 평범한 것과는 거리가 멀다.