Advanced
Tap-length Optimization of Decision Feedback Equalizer Using Genetic Algorithm
Tap-length Optimization of Decision Feedback Equalizer Using Genetic Algorithm
Journal of the Korea Institute of Information and Communication Engineering. 2015. Aug, 19(8): 1765-1772
Copyright © 2015, The Korean Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : April 23, 2015
  • Accepted : May 29, 2015
  • Published : August 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
지홍 손
기만 김
kimkim@kmou.ac.kr

Abstract
수중음향통신 채널은 다중 경로 전달이 주요 장애 요인이 되며, 일반적으로 이러한 문제점을 극복하기 위해 등화기가 적용된다. 본 논문에서는 결정 궤환 등화기의 탭 길이를 유전자 알고리즘을 통해 최적화하는 방법을 제안하였다. 유전자 알고리즘의 유전 정보를 전방향 필터와 후방향 필터의 길이로 입력받은 후, 목적함수에 따라 훈련 신호 구간에서의 BER(bit error rate)을 계산하여 필터 길이를 최적화한다. 목적함수는 결정 궤환 등화기, BER 계산으로 설정되었다. 실험 결과, 수심 25 m에 배치된 수신기에 수신된 신호에 훈련 신호만을 이용하였을 때, BER이 0.0355로 나타났다. 모든 데이터를 목적함수 내의 BER계산에 이용하였을 때, BER이 0.0215로 나타났다.
Keywords
Ⅰ. 서 론
일반적으로 다중 경로 전달로 인한 심볼 간 간섭 현상이 매우 심각한 수중음향통신 채널과 같은 주파수 선택적 채널에서 신호의 복구를 위해 등화기가 사용된다. 등화기는 선형 등화기와 비선형 등화기 두 가지로 분류할 수 있는데 이 가운데 결정 궤환 등화기는 비선형 등화기로써 일반적으로 선형 등화기보다 성능이 뛰어나다. 하지만 등화기의 성능은 탭 길이에 영향을 많이 받는데, 결정 궤환 등화기가 올바르게 동작하기 위해서는 전방향 필터(feed forward filter)와 후방향 필터(feed back filter)의 탭 길이를 적절하게 설정해야 한다.
등화기의 탭 길이 최적화를 위해 초기 백색화기(prewhitener)를 등화기 앞에 두어 탭 길이를 최적화하는 연구가 진행되었다 [1] . 본 논문에서는 결정 궤환 등화기의 탭 길이를 최적화하기 위해서 유전자 알고리즘에 기반한 방법을 제안하였다. 전방향 필터와 후방향 필터의 길이는 유전자 알고리즘에서 유전 정보로 취급된다. 유전자 알고리즘은 전방향 필터와 후방향 필터의 길이를 사용하여 무작위 교배(random cross-over) 방법을 통해 동작한다. 목적함수는 RLS (recursive least square) 알고리즘으로 동작하는 결정 궤환 등화기와 BER(bit error rate) 계산으로 구성된다. 위와 같은 목적함수로 유전자 알고리즘을 시행하여 수중음향통신 채널에 적합한 결정 궤환 등화기의 최적의 탭 길이를 추정하였다.
실제 통신에서는 훈련 심볼만을 이용해야 되기 때문에, 본 논문에서는 목적함수에서 BER을 계산하는 데 사용되는 신호를 훈련 심볼과 전송된 데이터 모두 사용하는 경우와 훈련 심볼만 이용하는 경우, 두 가지로 최적화 성능을 비교 분석하였다.
Ⅱ. 결정 궤환 등화기의 탭 길이 최적화
- 2.1. 결정 궤환 등화기
일반적으로 비선형 등화기는 선형 등화기보다 더 좋은 성능을 갖는 것으로 알려져 있다 [2 , 3] . 결정 궤환 등화기는 전형적인 비선형 등화기로써, 과거의 심볼 출력을 현재의 심볼 계산에 사용한다. 그림 1 에서 등화기 입력은 전방향 필터 부분에 연결되어 있고, 출력은 후방향 필터에 연결되어있다 [4 , 5] .
PPT Slide
Lager Image
결정 궤환 등화기 Fig. 1 Decision Feedback Equalizer
등화기의 계수를 갱신하기 위해서 RLS 알고리즘과 같은 적응 알고리즘을 사용할 수 있다 [6] . 등화기 출력 심볼 y ( n )은 전방향 필터 출력 값에서 후방향 필터 출력 값의 차로 표현된다. 이 때 전방향 필터와 후방향 필터 탭 길이에 따라 성능이 불규칙적으로 나타난다 [7 - 9] . 따라서 전방향 필터와 후방향 필터 탭 길이의 조정은 매우 중요하다.
PPT Slide
Lager Image
목적 함수 Fig. 2 Object Function
- 2.2. 유전자 알고리즘을 통한 탭 길이 최적화
유전자 알고리즘은 함수의 상태를 최신화하기 위해 어떠한 계수나 값을 최적화하는 기술이다 [10 - 12] . 본 논문에서는 이 유전자 알고리즘을 결정 궤환 등화기의 탭길이 최적화에 적용하는 방법을 제안하였다. 제안한 유전자 알고리즘을 시행하기 위해서 다음과 같은 과정이 처리된다. 첫 번째, 한 세대가 시작될 때, 무작위로 유전정보를 지닌 여러 개체를 만들어야 한다. 여기서 세대는 개체들의 묶음을 의미한다. 이 때, 무작위로 생성된 유전 정보로 사용되는 정수 값은 전방향 필터와 후방향 필터 길이다. 두 번째, 목적함수를 구성한다. 목적함수는 결정 궤환 등화기와 BER 계산 과정으로 구성된다. 유전자 알고리즘에서 생성된 유전 정보를 결정 궤환 등화기의 전방향 필터와 후방향 필터의 길이로 사용하여 목적함수를 통해 BER을 계산한다.
목적함수 부분을 수식으로 표현하면 다음과 같다. r ( n )은 수신된 심볼, y ( n )은 등화기 출력,, wf ( k )는 전방향 필터, wb ( k )는 후방향 필터이고, d ( n )은 경판정후 심볼 값이라 할 때 y ( n )은 다음과 같다.
PPT Slide
Lager Image
여기서 Nf 는 전방향 필터 탭 길이, Nb 는 후방향 필터 탭 길이이다. 탭 길이는 각 세대마다 개체별로 교배 과정 후 나온 수를 이용하여 갱신한다. 식 (1)을 행렬로 표현하면 다음과 같이 나타낼 수 있다.
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
여기서 Wf Wb 는 각각 순방향 필터와 역방향 필터의 계수이다. Xn 는 수신신호 벡터 Rn 와 경판정 후 심볼 벡터 Dn 를 연접하여 만든 열벡터이다. N 은 전송된 심볼의 길이이다.
PPT Slide
Lager Image
PPT Slide
Lager Image
식 (9)의
PPT Slide
Lager Image
는 경판정 이후 심볼을 비트로 바꾼 값이다. 즉, 수신된 비트로 송신 비트 s ( n )와 비교하여 비트 오율을 측정한다. 한 세대의 각 개체마다 BER을 평가하여 성능이 좋은 순으로 정렬하여 성능이 좋지 않은 개체의 절반을 제거한다. 다음 세대로 넘어가기 전에 빈자리를 채우기 위해 무작위로 새로운 개체를 생성한다. 그리고 다음 세대를 위해 개체들을 교배시키게 되는데 이를 위해서 유전 정보를 이진수로 변형해야 한다. 본 논문에서는 무작위 지점 선정 교배 방법을 사용하였다. 예를 들어, 유전 정보가 최대 2 7 인 개체가 교배를 하는데 무작위 지점이 4가 나왔다고 가정하자. 아래 그림과 같은 교배 방법을 통해 다음 세대를 생성한다. 다음세대가 생성되고, 이진수를 다시 십진수로 변환하여 유전정보로 사용한다.
PPT Slide
Lager Image
지점 선택 후 교배 Fig. 3 Cross-over after Selecting Point
PPT Slide
Lager Image
지점 선택 후 교배와 역배치 Fig. 4 Cross-over and Reversal after Selecting Point
세대가 거치면서 진화하는 도중에 최적화 상태가 아닌 방향으로 진화하는 경우를 방지하기 위해 낮은 확률로 돌연변이가 발생하도록 설정한다. 이진수 유전 정보의 임의 지점에서 돌변연이가 발생하였을 때, 그 지점이 만약 ‘1’이라면 ‘0’으로 변화하고, 만약 ‘0’이라면 ‘1’로 보수 관계로 돌연변이가 발생하도록 둔다.
유전자 개체 다양성을 유지하기 위해서 동일한 성능을 지닌 유전 정보를 지는 개체를 삭제하는 중복성 검사를 시행한다. 다양한 유전 정보를 지닌 개체가 많을수록 최적화 상태에 빠르게 도달할 수 있다.
Ⅲ. 실험 결과
유전자 알고리즘을 적용한 결정 궤환 등화기를 포함하는 수중음향통신 시스템의 성능을 분석하였다. 본 실험에서 데이터는 QPSK(Quadrature Phase Shift Keying) 변조되었으며, 비트 전송률은 1 kbps로 하였다. 반송 주파수는 16 kHz로 하였으며, 샘플링 주파수는 192 kHz로 하였다. 패킷은 512개의 M 시퀀스가 사용된 훈련 구간과 2,000개의 비트로 구성된 데이터 구간으로 구성되었다. 실험은 2015년 3월 송신기 1개, 수신기 2개로 진행되었다. 호수의 수심은 약 40 m였으며, 송신기의 수심은 4 m, 수신기의 수심은 15 m와 25 m로 하였다. 송수신기 간의 거리는 약 340 m로 하였으나 고정되지는 않았다. 송신기는 ITC-1001 모델, 수신기는 B&K 8106 모델을 사용하였으며, 전력 증폭기는 B&K 2713 모델을 사용하였다.
PPT Slide
Lager Image
실험 구성도 Fig. 5 Experimental Setup
그림 6 7 은 선형 주파수 변조된 신호를 주기적으로 반복 전송하여 획득한 신호를 이용하여 추정된 채널 응답 특성이다. 그림 6 은 25 m 수신기(1 ch)의 채널응답 특성이고, 그림 7 은 15 m 수신기(2 ch)의 채널 응답 특성이다.
PPT Slide
Lager Image
채널 응답 특성 25 m (1ch) Fig. 6 Channel Impulse Response 25 m (1ch)
PPT Slide
Lager Image
채널 응답 특성 15 m (2ch) Fig. 7 Channel Impulse Response 15 m (2ch)
그림 6 은 가장 먼저 도달되는 직접파와 약 0.015초 후에 호수 바닥면에 의한 반사파와 약 0.023초 후에 호수 수면에 의한 반사파가 수신되는 것을 알 수 있다. 실험 당시 호수 수면에 얇은 조각난 얼음이 형성되어있어 수면 얼음에 의한 반사파는 산란되어 수신되는 것을 볼수 있다. 그리고 2ch의 경우, 수면에 의한 반사파는 수신되지 않고 바닥면에 의한 반사파만 수신되는 것을 알 수 있다.
수신된 QPSK 신호는 그림 8 과 같은 수신기 구조로 처리되었다. 수신기는 신호의 동기화와 도플러 주파수 추정 및 보상 [13 , 14] 과정 등으로 구성되었다. PLL(phase locked loop)은 위상 동기 루프이다.
PPT Slide
Lager Image
수신기 구조 Fig. 8 Receiver schemes
목적함수를 이용하여 BER 분석을 할 때, 훈련 신호만을 이용하여 목적함수 내에서 BER을 계산하여 제안한 유전자 알고리즘을 시행하였다. 훈련 신호 구간 동안의 최적화된 결정 궤환 등화기의 탭 길이를 적용하여, 데이터 신호를 복구하였다. 수신된 신호에 유전자 알고리즘을 적용하기 위해 알고리즘 시행 총 세대 수는 30세대, 세대 당 개체 수는 10개체, 유전 정보는 최대 2 6 으로 고정하였다. 1ch로 입력된 신호의 SNR(signal to noise ratio)은 약 7.2 dB, 2ch로 입력된 신호의 SNR은 약 10.3 dB로 1 ch이 2 ch에 비해 다중 경로 전달 신호와 잡음이 많이 첨가된 것으로 측정되었다.
그림 9 는 1ch 신호에 탭 길이를 최적화하지 않고, 임의의 값을 탭 길이로 선정하여 등화기의 출력 값을 성상도로 나타낸 것이며, 그림 10 은 1ch 신호에 유전자 알고리즘을 이용하여 탭 길이를 최적화된 등화기의 출력값을 성상도로 나타낸 것이다.
PPT Slide
Lager Image
최적화 되지 않은 등화기의 성상도 (1ch) Fig. 9 Constellation of the non-optimized equalizer
PPT Slide
Lager Image
최적화 된 등화기의 성상도 (1ch) Fig. 10 Constellation of the optimized equalizer
그림 9 그림 10 에 비해 성상도가 많이 퍼져 있는 것을 알 수 있고, 그림 10 그림 9 에 비해 성상도가 모여 있는 것을 알 수 있다. 그림 11 은 2ch 신호에 탭 길이를 최적화하지 않은 등화기 출력 값의 성상도이다. 그림 12 와 비교하였을 때, 그림 12 에 비해 성상도가 퍼져 있는 것을 알 수 있다.
PPT Slide
Lager Image
최적화 되지 않은 등화기의 성상도 (2ch) Fig. 11 Constellation of the non-optimized equalizer
PPT Slide
Lager Image
최적화 된 등화기의 성상도 (2ch) Fig. 12 Constellation of the optimized equalizer
그림 13 그림 14 는 1부터 2 6 까지 전방향 필터와 후방향 필터의 탭 길이를 두었을 때, BER 결과 그림이다. 흰색일수록 낮은 BER을 가지며, 검정색일수록 높은 BER을 지닌다. 그림 13 은 1ch의 신호의 BER그림이다. 1ch은 전방향필터는 3~10, 후방향필터는 30~40에서 낮은 BER을 갖는 것을 알 수 있다. 그림 14 는 2ch의 신호의 BER그림이다. 2ch 신호는 1ch 신호에 비해 낮은 BER 영역이 보다 광범위하게 분포되어 있는 것을 알수 있다. 전방향 필터는 거의 모든 부분에서 낮은 BER을 지닌 것을 알 수 있으나, 12~14구간에서는 후방향필터가 50이상이 되었을 때, 높은 BER이 나타나는 것을 알 수 있다. 그리고 전방향 필터가 30이상 일 때, 후방향 필터가 30이상이면 높은 BER이 나타나는 것을 알 수 있다.
PPT Slide
Lager Image
탭 길이에 따른 1ch BER Fig. 13 1ch BER in accordance with tap-length
PPT Slide
Lager Image
탭 길이에 따른 2ch BER Fig. 14 2ch BER in accordance with tap-length
그림 15 는 1ch의 신호를 유전자 알고리즘을 적용하여 출력된 전방향 필터와 후방향 필터의 탭 길이이다. 그림 15 -(a)는 목적함수에서 BER분석을 위해 훈련 심볼과 전송된 심볼을 모두 사용했을 경우이다. 12세대부터 수렴하여 27세대에서 전방향 필터의 탭 길이는 6, 후방향 필터의 탭 길이는 30으로 낮은 BER 영역으로 수렴된 것을 알 수 있다. 그림 15 -(b)는 목적함수에서 BER 분석을 위해 훈련 신호만을 사용했을 경우이다. 세대 초반에는 탭 길이 변동성이 크나, 22세대부터 수렴하여 전방향 필터의 탭 길이는 8, 후방향 필터의 탭 길이는 35로 낮은 BER 영역으로 수렴된 것을 알 수 있다.
PPT Slide
Lager Image
유전자 알고리즘 세대 당 1ch 탭 길이 Fig. 15 Tap-length per generation of GA (1ch)
그림 16 은 2ch 신호를 유전자 알고리즘을 적용하여 출력된 전방향 필터와 후방향 필터의 길이이다. 그림 16 -(a)는 목적함수에서 BER분석을 위해 훈련 심볼과 전송된 심볼을 모두 사용했을 경우이다. 첫 세대부터 수렴하여 전방향 필터의 탭 길이는 6, 후방향 필터의 탭길이는 41로 고정되었다. 그림 16 -(b)는 목적함수에서 BER분석을 위해 훈련 신호만을 사용했을 경우이다. 첫세대에 변동이 약간 있으나 2세대부터 수렴하여 전방향 필터의 탭 길이는 7, 후방향 필터의 탭 길이는 25로 낮은 BER영역으로 수렴되었다.
PPT Slide
Lager Image
유전자 알고리즘 세대 당 2ch 탭 길이 Fig. 16 Tap-length per generation of GA (2ch)
유전자 알고리즘을 적용하여 BER을 분석한 결과, 세대 별로 BER이 그림 17 과 같이 나타났다. 1ch 신호에 훈련 신호만 적용했을 때, BER이 0.0355로 수렴하였다. 1ch 신호에 모든 데이터를 적용했을 때, BER이 0.0215로 수렴하였다. 1ch의 경우 훈련 신호만 적용했을 때, 모든 데이터를 사용한 것에 비해 다소 부정확한 최적화 성능이 나타났다. 2ch의 경우 왜곡이 거의 없어 훈련 신호만 적용했을 때, BER이 10 -4 로 수렴하였다. 2ch 신호에 모든 데이터를 적용했을 때, 첫 세대부터 BER이 0으로 수렴하여 나타났다.
PPT Slide
Lager Image
BER 분석 Fig. 17 BER Analysis
위와 같은 사실로부터 훈련 심볼만을 이용하여 유전자 알고리즘에 적용했을 때, 훈련 심볼 구간만 이용하여 최적화한 것이기 때문에 모든 신호를 이용했을 때보다 부정확하다. 그러나 심볼 길이가 짧아 계산량이 적고, 모든 데이터를 적용하여 유전자 알고리즘을 시행했을 때와 유사한 최적화 성능이 나타난다.
Ⅳ. 결 론
수중음향통신 채널에서 결정 궤환 등화기의 전방향 필터와 후방향 필터의 길이를 결정하기 위한 유전자 알고리즘을 제안하였다. 유전자 알고리즘의 유전 정보를 등화기의 전방향 필터와 후방향 필터로 설정하고, 목적함수로는 등화기와 BER 계산 부분을 두었다. 목적함수에서 BER을 계산하기 위해 훈련 심볼과 전송된 심볼 모두 이용하는 경우와 훈련 심볼만을 이용하는 경우의 두 가지 최적화 성능을 분석하였다. 호수실험 결과, 훈련 심볼만 이용하여 유전자 알고리즘을 시행했을 때, 훈련 심볼와 전송된 심볼 모두 사용했을 때와 비슷한 성능이 나타났다.
향후 연구 내용으로 보다 정확한 최적화를 위해 채널에 따른 훈련 신호 길이를 결정하는 방법 등에 대한 연구가 필요하다. 아울러 해상 실험을 통한 성능 분석에 대한 연구도 진행되어야 할 것이다.
BIO
손지홍(Ji-hong Son)
2014년 한국해양대학교 전파공학과 (학사)
2014년 ~ 현재 한국해양대학교 전파공학과 (석사과정)
※관심분야 : 수중음향통신, 신호처리
김기만(Ki-man Kim)
1988년 연세대학교 전자공학과 (공학사)
1990년 연세대학교 전자공학과 (공학석사)
1995년 연세대학교 전자공학과 (공학박사)
1996년 ~ 현재 한국해양대학교 전파공학과 교수
1997년 ~ 현재 한국정보통신학회, 종신회원
2007년 ~ 현재 방위사업청 지정 수중통신탐지특화연구센터 실장
2013년 ~ 현재 TTA WG9031 수중음파통신 표준화 그룹 위원
※관심분야 : 수중음향통신, 소나 신호처리, 빔 형성
References
Gong Yu , Cowan Colin F.N. , Chen Jian “An Adaptive Linear Equalizer with Optimum Filter Length and Decision Delay,” 7th International Conference on Mathematics in Signal Processing Sept. 2006
Agarwal Amit , Sur S. N. , Bera R. “Linear vs Non Linear Equalizer In Different Channel Condition,” International Journal of Advanced Technology & Engineering Research (IJATER) E-ICETT 2014, 3rd International e-Conference 2014
Belfore C. , Park J. “Decision Feedback Equalization,” Proceeding of The IEEE Aug. 1979 vol. 67, no. 8 1143 - 1156
Agarwal Amit , Sur S. N. , Singh Arun Kumar , Gurung Hemanth , Gupta Abhishek Kumar , Bera R. “Performance Analysis of Linear and Non-Linear Equalizer in Rician Channel,” C3IT-2012 2012 vol. 4 687 - 691
Lee Inkyu , Cioffi John M. 1995 “A Fast Computation Algorithm for the Decision Feedback Equalizer,” IEEE Transactions on Communications 43 (11) 2742 - 2749    DOI : 10.1109/26.481225
Zhuang Weihua 1998 “RLS Algorithm with Variable Forgetting Factor for Decision Feedback Equalizer over Time-Variant Fading Channels,” Wireless Personal Communications 8 15 - 29    DOI : 10.1023/A:1008856607190
Gong Yu , Hong Xia , Abu-Salim Khalid F. “Adaptive MMSE Equalizer with Optimum Tap-length and Decision Delay,” IEEE Sensor Signal Processing for Defence Sept. 2010 1 - 5
Gong Yu , Cowan Colin F. N. 2004 “Optimum Decision Delay of the Finite-Length DFE,” IEEE Signal Processing Letters 11 (11) 858 - 861    DOI : 10.1109/LSP.2004.836943
Voois Paul A. , Lee Inkyu , Cioffi John M. 1996 “The Effect of Decision Delay in Finite-Length Decision Feedback Equalizer,” IEEE Transaction on Information Theory 42 (2)    DOI : 10.1109/18.485729
Srinivas M. , Patnaik L. M. 1994 “Adaptive Probabilities of Crossover,” IEEE Transactions on Systems, Man and Cybernetics 24 (4) 656 - 667    DOI : 10.1109/21.286385
Janikow Cezary Z. , Michalewicz Zbigniew “An Experimental Comparison of Binary and Floating Point Representations in Genetic Algorithms,” International Conference on Genetic Algorithms 1991 31 - 36
Eiban A. E. , Raue P-E. , Ruttkay Zs. “Genetic Algorithms with Multi-parent Recombination,” Proceedings of the 3rd Conference on Parallel Problem Solving from Nature 1994 78 - 87
Sharif Bayan S. , Neasham Jeff , Hinton Oliver R. , Adams Alan E. 2000 “A Computationally Efficient Doppler Compensation System for Underwater Acoustic Communications,” IEEE Journal of Oceanic Engineering 25 (1) 52 - 61    DOI : 10.1109/48.820736
Tao Shuai , Xu-wen Liang , Xiao-ting Chen “Decision- Directed Estimation of Carrier Frequency and Phase for Burst PSK Transmission,” IEEE Wireless Communications Networking and Mobile Computing International Conference Sept. 2009 1 - 4