KR100459419B1 - Viterbi decoder - Google Patents
Viterbi decoder Download PDFInfo
- Publication number
- KR100459419B1 KR100459419B1 KR10-2001-0088532A KR20010088532A KR100459419B1 KR 100459419 B1 KR100459419 B1 KR 100459419B1 KR 20010088532 A KR20010088532 A KR 20010088532A KR 100459419 B1 KR100459419 B1 KR 100459419B1
- Authority
- KR
- South Korea
- Prior art keywords
- metric
- path
- input
- branch
- bit
- 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
Links
- 230000004083 survival effect Effects 0.000 claims abstract description 28
- 230000007704 transition Effects 0.000 claims description 4
- 238000010586 diagram Methods 0.000 description 7
- 239000000654 additive Substances 0.000 description 2
- 230000000996 additive effect Effects 0.000 description 2
- 238000004364 calculation method Methods 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 230000006870 function Effects 0.000 description 2
- 238000000034 method Methods 0.000 description 2
- 230000008901 benefit Effects 0.000 description 1
- 230000005540 biological transmission Effects 0.000 description 1
- 230000001186 cumulative effect Effects 0.000 description 1
- 125000004122 cyclic group Chemical group 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 230000008569 process Effects 0.000 description 1
- 230000000644 propagated effect Effects 0.000 description 1
- 238000010187 selection method Methods 0.000 description 1
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
- H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
- H03M13/41—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors
- H03M13/4107—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors implementing add, compare, select [ACS] operations
-
- 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/41—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors
- H03M13/4161—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors implementing path management
- H03M13/4169—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors implementing path management using traceback
-
- 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/6502—Reduction of hardware complexity or efficient processing
Landscapes
- Physics & Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Error Detection And Correction (AREA)
Abstract
본 발명은 복조된 입력 시퀀스에 따른 입력 코드워드의 가지 워드를 계산하여 상기 계산된 가지 워드의 오차를 연산하여 출력하고, 상기 입력 코드워드와 기대 코드워드값 사이의 거리값을 근거로 채널 잡음의 영향에 의해서 오류 발생의 확률적 빈도가 가장 높은 특정 입력 코드워드에 대해 이를 메트릭 판단 비트로 생성하여 출력하는 가지 메트릭 연산장치와; 새로운 가지 메트릭, 누적된 경로 메트릭 및 메트릭 판단 비트를 입력받아 두가지 경로에 대한 가지 메트릭과 누적된 경로 메트릭의 합의 차이가 오류를 발생하는 범위 내에 있는지를 판단하여, 상기 판단 결과에 따라 상기 입력된 메트릭 판단 비트를 사용하여 생존 경로를 결정하는 가산 비교 선택 연산장치와; 상기 가산 비교 선택 연산장치를 통해 출력된 생존 경로 및 메트릭을 저장하는 경로 메모리부와; 실제 전송된 시퀀스에 대응하는 출력 시퀀스를 복호해내는 복호기로 구성된 것을 특징으로 하는 비터비 디코더를 제공한다.The present invention calculates a branch word of an input codeword according to a demodulated input sequence, calculates and outputs an error of the calculated branch word, and calculates channel noise based on a distance value between the input codeword and an expected codeword value. A branch metric computing device that generates and outputs a metric decision bit for a specific input codeword having the highest probability of error occurrence by the influence; The new branch metric, the accumulated path metric, and the metric determination bit are input to determine whether the difference between the sum of the branch metric and the accumulated path metric for the two paths is within an error generating range, and according to the determination result, the input metric An addition comparison selection computing device for determining a survival path using the decision bit; A path memory unit for storing a survival path and a metric outputted through the addition comparison selection calculator; It provides a Viterbi decoder, characterized by consisting of a decoder for decoding the output sequence corresponding to the actually transmitted sequence.
따라서, 본 발명은 가산 비교 선택 연산장치에서 두 가지 경로에 대해 복호의 오류를 범할 수 있는 가지 메트릭 값과 누적된 경로 메트릭 값의 합의 차이를 정의하고 이 경우에 가지 워드 연산 장치에서 입력 코드워드의 최상위 비트가 잡음에 의해 영향을 받을 수 있는 확률적 빈도가 높다고 판단되는 특정 입력 코드워드에 대해 이를 메트릭 판단 비트로 사용함으로써 비터비 복호의 결과의 정밀도를 향상시킬 수 있다는 이점이 있다.Accordingly, the present invention defines the difference between the sum of the branch metric value and the accumulated path metric value that may cause a decoding error for two paths in the addition comparison selection operation unit, and in this case, the input codeword It is advantageous to improve the precision of the result of Viterbi decoding by using this as a metric determination bit for a specific input codeword that is determined that the most significant bit is affected by noise.
Description
본 발명은 가산 비교 선택 연산장치를 구비한 비터비 디코더에 관한 것으로, 특히 각 상태별로 두 가지 경로 중에서 최적의 경로를 찾는 비교 연산을 효과적으로 계산하기 위한 가산 비교 선택 연산장치를 구비한 비터비 디코더에 관한 것이다.The present invention relates to a Viterbi decoder having an addition comparison selection operation device, and more particularly, to a Viterbi decoder having an addition comparison selection operation device for effectively calculating a comparison operation for finding an optimal path among two paths for each state. It is about.
최근 디지털 통신 시스템에서 신뢰성있는 데이터의 전송을 위하여 에러 제어를 위한 코드의 사용은 필수 불가결한 요소가 되었고, 원래의 디지털 신호를 정확하게 복원하기 위해서 비터비 알고리즘 등의 최대 추정 수법을 이용한 복호가 널리 행해지고 있다.In recent years, the use of code for error control has become an indispensable element for reliable data transmission in digital communication systems, and decoding using a maximum estimation technique such as Viterbi algorithm is widely used to accurately recover the original digital signal. have.
도 1은 디지털 통신 시스템의 개략적인 구성도이다.1 is a schematic configuration diagram of a digital communication system.
도 1을 참조하면, 입력 시퀀스를 콘벌루션 인코드시켜 코드 워드 시퀀스로 변환하여 출력하는 인코더(10)와, 상기 출력된 코드 워드 시퀀스를 변조하여 출력하는 변조기(20)와, 상기 변조기(20)로부터 출력된 신호를 전송하는 통신 채널(30)과, 상기 채널(30)을 통해 전송된 정보를 수신하여 이산(양자화) 신호를 발생하여 출력하는 복조기(50)와, 원래의 디지털 신호를 비터비 알고리즘을 통해 정확하게 복원해내는 디코더(60)로 구성된다.Referring to FIG. 1, an encoder 10 for convolutionally encoding an input sequence, converting the code sequence into a code word sequence, a modulator 20 for modulating and outputting the output code word sequence, and the modulator 20 A communication channel 30 for transmitting the signal output from the demodulator, a demodulator 50 for generating and outputting a discrete (quantized) signal by receiving the information transmitted through the channel 30, and an original digital signal It is composed of a decoder 60 that accurately recovers through an algorithm.
상기 통신 채널(30)에서는 도 1에 도시된 부가 백색 가우시안 잡음(AWGA)과 같은 채널 잡음(40)에 영향을 받아 전송된 정보를 교란시킬 수 있다.The communication channel 30 may disturb the transmitted information under the influence of the channel noise 40 such as the additional white Gaussian noise (AWGA) shown in FIG. 1.
상기 복조기(50)는 경판정(hard decision)복조기와 연판정(soft decision)복조기가 있을 수 있는데, 상기 경판정 복조기는 전송된 것이 0인지 1인지를 확실하게 결정하고, 연판정(soft decision)복조기는 수신 정보를 복조하고, 또한 복조된 정보의 신뢰도에 관한 추가 정보를 제공하여, 디코더(60)의 성능을 개선시킨다.The demodulator 50 may include a hard decision demodulator and a soft decision demodulator. The hard decision demodulator reliably determines whether 0 or 1 is transmitted, and makes a soft decision. The demodulator demodulates the received information and also provides additional information regarding the reliability of the demodulated information, thereby improving the performance of the decoder 60.
디코더(60)에서 수행되는 비터비 알고리즘은 시간 ti에서 수신된 신호와 각 상태에 들어온 트렐리스(trellis) 경로 사이의 거리 또는 유사성 척도(measure of similarity)를 계산하여 최단 경로를 발견하며 각 노드는 주어진 이산 시간의 상태에 대응한다.The Viterbi algorithm performed at the decoder 60 finds the shortest path by calculating the distance or measure of similarity between the signal received at time t i and the trellis path entering each state and each The node corresponds to the state of a given discrete time.
트렐리스 노드에 접속하는 라인을 가지(branch)라 하는데, 이는 하나의 상태에서 또 다른 상태로의 천이(transition)에 대응한다.A line connecting a trellis node is called a branch, which corresponds to a transition from one state to another.
트렐리스 노드에 접속하는 가지는 메트릭에 할당되며 이러한 메트릭은에 근사한 부로그 우도 함수로 주어지는데, 여기에서은 측정된 출력을 나타내는 신호이고,는 상태간의 전위를 위한 실제 출력을 나타내는 신호이다.Branches connecting to trellis nodes are assigned to metrics, which are Is given by the approximate sublog likelihood function, where Is a signal representing the measured output, Is the signal representing the actual output for the potential between states.
특히 메트릭을 판정하는데 사용되는 로그 우도 함수는 해밍 거리(Hamming distance)와 같은 최소 거리 측도로 감소될 수 있다.In particular, the log likelihood function used to determine the metric can be reduced to a minimum distance measure, such as a Hamming distance.
주어진 입력 메시지에 후행하여, 해밍 거리는 알고리즘의 측정하는 심벌 및 인코더가 작성한 심벌간의 서로 다른 비트수를 측정한다.Following a given input message, the Hamming distance measures the number of different bits between the algorithm's measuring symbols and the encoder's written symbols.
하나의 상태에서 다른 상태로의 천이시에 두개의 경로가 같은 상태로 들어온다면 가장 좋은 메트릭을 가진 하나가 선택되고 이 경로를 생존 경로(surviving path)라 한다.When two paths enter the same state from one state to another, the one with the best metric is selected and this path is called the surviving path.
생존 경로의 선택은 모든 상태에 대하여 수행되어져야 하며, 최적 경로를 선택한다는 것은 최대 근사 메트릭 또는 최소 거리 메트릭을 가진 코드워드를 선택하는 것이다.The choice of survival path should be performed for all states, and selecting the optimal path is to select the codeword with the maximum approximation metric or the minimum distance metric.
도 2는 트렐리스의 일부 예시도이다.2 is a diagram illustrating some examples of trellis.
도 2를 참조하면, 왼쪽(상태 i, j)과 오른쪽(상태 ii, jj)의 각각 두개의 노드는 각각 시간 (t)와 시간 (t+1)에서의 두가지 상태를 나타내며, 시간 (t)에서 상태 ii(0)로 가는 2가지 경로는, 시간(t)에서 상태 i(0)에서 접속하는 경로(BM0)와 상태 j(1)에서 접속하는 경로(BM1)의 두가지이다.Referring to Figure 2, two nodes each on the left (state i, j) and the right (state ii, jj) represent two states at time t and time t + 1, respectively, and time t Are two paths from the state ii (0) to the path BM0 connected in state i (0) at time t and the path BM1 connected in state j (1).
마찬가지로, 시간(t+1)에서 상태 jj(1)로 가는 경로도 2가지이며, 시간 (t+1)에서 상태 i(0)에서 접속하는 경로(BM2)와 상태 j(1)에서 접속하는 경로(BM3)이다.Similarly, there are two paths from the time t + 1 to the state jj (1), and the path BM2 connected in the state i (0) and the state j (1) connected at the time t + 1. Route BM3.
비터비 알고리즘은 도 3을 참조하면, 가산 비교 선택 절차의 순환적 연산을 포함한다.The Viterbi algorithm, with reference to FIG. 3, includes a cyclic operation of an additive comparison selection procedure.
도 3은 종래 기술에 따른 가산 비교 선택 연산장치의 블록 구성도이다.3 is a block diagram of an addition comparison selection operation apparatus according to the prior art.
도 3을 참조하면, 가산 비교 선택 연산장치는 시간(t)에서의 상태와 관련되어 누적된 경로 메트릭(PM0)에 시간 (t)에서의 상태에서 시간 (t+1)에서의 상태로의 천이와 관련된 가지 메트릭(BM0)을 가산한 값을 출력하는 제 1 가산기(70)와, 시간(t)에서의 상태와 관련되어 누적된 경로 메트릭(PM1)에 시간 (t)에서의 상태에서 시간 (t+1)에서의 상태로의 천이와 관련된 가지 메트릭(BM1)을 가산한 값을 출력하는 제 2 가산기(80)와, 상기 제 1 및 제 2 가산기(70, 80)로부터 출력된 값의 크기를 비교하여 그 크기 정보를 출력하는 비교부(90)와, 상기 비교부(90)로부터 출력되는 크기 비교 정보로 최적의 경로를 선택하여 그에 해당하는 메트릭을 출력하는 선택부(100)로 구성된다.Referring to FIG. 3, the addition comparison selection operation unit transitions from the state at time t to the state at time t + 1 to the accumulated path metric PM0 in relation to the state at time t. A first adder 70 outputting a value obtained by adding the branch metric BM0 associated with and a time in a state at time t to a path metric PM1 accumulated in relation to the state at time t; a second adder 80 outputting a value obtained by adding the branch metric BM1 related to the transition to the state at t + 1), and the magnitude of the value output from the first and second adders 70 and 80; And a comparison unit 90 for comparing the size information and outputting the size information, and a selection unit 100 for selecting an optimal path using the size comparison information output from the comparison unit 90 and outputting a metric corresponding thereto. .
상기 가산 비교 선택 연산장치는 각각의 트렐리스 단계의 모든 상태에 대해서 반복 적용되고, 상기 선택부(100)로부터 출력된 신호는 다음 트렐리스 단계의 입력으로 사용된다.The addition comparison selection operation unit is repeatedly applied to all states of each trellis step, and the signal output from the selection unit 100 is used as an input of the next trellis step.
즉, 최적의 경로를 반복적으로 선택함으로써 비터비 알고리즘은 트렐리스를 통해 가장 적당한 경로를 재구성하는데, 이는 송신단에서 보낸 신호가 채널 잡음에 의해서 파괴되기 전에 실제 전송된 시퀀스에 대응할 수 있다.That is, by repeatedly selecting the optimal path, the Viterbi algorithm reconstructs the most suitable path through the trellis, which may correspond to the actual transmitted sequence before the signal sent from the transmitter is destroyed by channel noise.
그러나, 종래의 가산 비교 선택 연산장치는 비교 모듈에서 2가지 경로, 다시 말하면 새로운 가지 메트릭값과 누적된 경로 메트릭 값을 합하여 단순히 크고 작음만을 서로 비교한다.However, the conventional addition comparison selection operation unit compares only two large and small ones by adding two paths, that is, a new branch metric value and a accumulated path metric value, in the comparison module.
이는 2가지 경로의 가지 메트릭 값과 누적된 경로 메트릭 값의 합의 차이가 없거나 또는 무시할 수 있을 정도로 작은 경우에 최적의 생존 경로를 결정하는데 오류를 발생시킬 수 있다는 문제점이 있다.This may cause an error in determining an optimal survival path in the case where there is no difference between the sum of the branch metric values of the two paths and the accumulated path metric values or is small enough to be ignored.
따라서, 본 발명은 종래 기술의 문제점을 해결하기 위한 것으로, 채널 잡음의 효과가 크게 나타나는 입력 코드워드의 최상위 비트의 잡음 교란의 확률적 빈도가 높은 입력 코드워드를 생존 경로를 판단하는 기준으로 하는 비터비 디코더를 제공함에 그 목적이 있다.Accordingly, the present invention is to solve the problems of the prior art, the beater which uses the input codeword having a high probability of noise disturbance of the most significant bit of the input codeword that the effect of the channel noise is large as a criterion for determining the survival path The purpose is to provide a non-decoder.
상기의 목적을 달성하기 위한 본 발명의 일 실시 예는, 복조된 입력 시퀀스에 따른 입력 코드워드의 가지 워드를 계산하여 그 계산된 가지 워드의 오차를 연산하여 출력하고, 상기 입력 코드워드와 기대 코드워드값 사이의 거리값을 근거로 하여, 최상위 비트가 잡음에 의해 영햐을 받을 수 있는 확률적 빈도가 높다고 판단되는 특정 입력 코드워드를 검출하여 이를 메트릭 판단 비트로 생성하여 출력하는 가지 메트릭 연산장치와; 새로운 가지 메트릭, 누적된 경로 메트릭 및 메트릭 판단 비트를 입력받아 두가지 경로에 대한 가지 메트릭과 누적된 경로 메트릭의 합의 차이가 오류를 발생하는 범위 내에 있는지를 판단하여, 상기 판단 결과에 따라 상기 입력된 메트릭 판단 비트를 사용하여 생존 경로를 결정하는 가산 비교 선택 연산장치와; 상기 가산 비교 선택 연산장치를 통해 출력된 생존 경로 및 메트릭을 저장하는 경로 메모리부와; 실제 전송된 시퀀스에 대응하는 출력 시퀀스를 복호해내는 복호기로 구성된 것을 특징으로 한다.According to an embodiment of the present invention, a branch word of an input codeword according to a demodulated input sequence is calculated, an error of the calculated branch word is output, and the output codeword and an expected code are output. A branch metric computing device that detects a specific input codeword determined to have a high probability that the most significant bit can be received by noise based on the distance between word values, and generates and outputs it as a metric determination bit; The new branch metric, the accumulated path metric, and the metric determination bit are input to determine whether the difference between the sum of the branch metric and the accumulated path metric for the two paths is within an error generating range, and according to the determination result, the input metric An addition comparison selection computing device for determining a survival path using the decision bit; A path memory unit for storing a survival path and a metric outputted through the addition comparison selection calculator; The decoder may be configured to decode an output sequence corresponding to the actually transmitted sequence.
도 1은 디지털 통신 시스템의 개략적인 블록 구성도.1 is a schematic block diagram of a digital communication system.
도 2는 트렐리스의 일 실시예도.2 is an embodiment of a trellis.
도 3은 비터비 디코더의 가산 비교 선택 연산장치의 블록 구성도.Fig. 3 is a block diagram of an addition comparison selection arithmetic unit of a Viterbi decoder.
도 4는 4비트의 입력 코드워드와 기대 코드워드 값 사이의 거리값 테이블.4 is a distance value table between a 4-bit input codeword and an expected codeword value.
도 5는 본 발명에 따른 비터비 디코더의 전체 구성 블록도.5 is an overall block diagram of a Viterbi decoder according to the present invention;
도 6은 도 5의 가산 비교 선택 연산장치의 동작 설명을 위한 플로우차트.FIG. 6 is a flowchart for explaining an operation of the addition comparison selection calculator of FIG. 5; FIG.
***도면의 주요 부분에 대한 부호 설명****** Explanation of symbols for main parts of drawings ***
10 : 인코더 20 : 변조기10: encoder 20: modulator
30 : 채널 50 : 복조기30 channel 50 demodulator
60 : 디코더 110 : 가지 메트릭 연산 장치60: decoder 110: branch metric operation unit
120 : 가지 워드 연산부 130 : 가지 메트릭 연산부120: branch word operation unit 130: branch metric operation unit
140 : 최상위 비트 잡음 검출기 150 : 가산 비교 선택 연산장치140: most significant bit noise detector 150: addition comparison selection operation unit
160 : 경로 메모리 170 : 복호기160: path memory 170: decoder
이하, 본 발명에 따른 일 실시예를 첨부한 도면을 참조하여 상세히 설명하기로 한다.Hereinafter, with reference to the accompanying drawings an embodiment according to the present invention will be described in detail.
비터비 디코더에서 가지 메트릭은 해당 가지가 일어날 때, 예상되는 출력값, 가지 워드와 연판정에 의해 디코더가 받아들인 데이터 사이의 오차를 연산한다.In the Viterbi decoder, the branch metric computes the error between the expected output value, the branch word and the data accepted by the decoder when the branch occurs.
실제 비터비 디코딩을 구현할 때, 4비트 입력 코드워드로 구성된 소프트 입력값이 사용될 수 있으며, 이는 경판정 비터비 디코딩과 비교하여 4비트로 구현된 비터비 디코딩이 SNR(Signal-to-noise ratio)에서 2dB만큼 디코더의 성능을 개선시키기에 충분하기 때문이다.When implementing real Viterbi decoding, soft inputs consisting of 4-bit input codewords can be used, which means that 4-bit Viterbi decoding at SNR (Signal-to-noise ratio) compared to hard decision Viterbi decoding. This is enough to improve the decoder's performance by 2dB.
4비트로 구성된 입력 코드워드값에서 최상위 비트(예를 들어 1000이라 할 때, 1)는 부호 비트에 해당하며 하위 3비트는 각 입력값의 크기를 나타낸다.In the input codeword value composed of 4 bits, the most significant bit (for example, 1 when 1000) corresponds to a sign bit and the lower 3 bits represent the size of each input value.
이 4비트의 소프트 입력 워드가 채널 잡음 등으로 인해 영향을 받게 되는 경우, 최상위 비트는 입력값의 부호를 나타내는 비트이므로 다른 비트가 같은 확률로 채널 잡음으로 인한 교란된 경우에 비해 오차의 범위가 커지게 된다.If this 4-bit soft input word is affected by channel noise, etc., the most significant bit is the bit representing the sign of the input value, so the error range is larger than the case where the other bits are disturbed by the channel noise with the same probability. You lose.
즉, 같은 확률로 최상위 비트와 최하위비트가 잡음의 영향을 받을 때, 도 4에 보는 바와 같이 그 오차의 범위가 8배 커지게 된다.That is, when the most significant bit and the least significant bit are affected by noise with the same probability, the range of the error becomes 8 times larger as shown in FIG.
예를 들면, 입력으로 받은 4비트의 입력 코드워드가 "0111"이라 할 때, 최상위 비트가 잡음에 의해 "1111"을 나타내는 경우, 원래의 값에 비해 크기의 차이가 8이되며 최하위비트가 잡음에 의해 "0110"가 되는 경우는 원래의 값에 비해 1의 오차의 값을 갖는다.For example, when the 4-bit input codeword received as input is "0111", if the most significant bit represents "1111" due to noise, the difference in magnitude is 8 compared to the original value, and the least significant bit is noise. In the case of " 0110 ", a value of 1 is compared with the original value.
이를 이용하여, 즉 최상위 비트가 잡음으로 인해 교란되었는지를 판단하여 이를 메트릭 판단 비트로써 활용하여 가산 비교 선택 연산장치에서 메트릭의 두가지 경로의 차이가 없거나 무시할 수 있을 정도로 작은 경우에 최적의 생존 경로를 결정한다.This is used to determine whether the most significant bit is disturbed by noise and use it as a metric decision bit to determine the optimal survival path in case the difference between the two paths of the metric is small or negligible in the additive comparison selection operation. do.
도 5는 본 발명에 따른 비터비 디코더의 전체 블록 구성도이다.5 is an overall block diagram of a Viterbi decoder according to the present invention.
도 5를 참조하면, 본 발명에 따른 비터비 디코더는 복조된 입력 시퀀스에 따른 입력 코드워드의 가지 워드를 계산하여 상기 계산된 가지 워드의 오차를 연산하여 출력하고, 입력 코드워드의 최상위 비트가 채널 잡음에 의해 영향을 받을 수 있는 확률적 빈도가 높다고 판단되는 특정 입력 코드워드를 검출하여 이를 메트릭 판단 비트로 설정하고 출력하는 가지 메트릭 연산 장치(110)와, 새로운 가지 메트릭, 누적된 경로 메트릭 및 메트릭 판단 비트를 입력받아 두가지 경로에 대한 가지 메트릭과 누적된 경로 메트릭의 합의 차이가 오류를 발생하는 범위 내에 있는지를 판단하여, 상기 판단 결과에 따라 상기 입력된 메트릭 판단 비트를 사용하여 생존 경로를 결정하는 가산 비교 선택 연산장치(150)와, 상기 가산 비교 선택 연산장치(150)를 통해 출력된 생존 경로 및 메트릭을 저장하는 경로 메모리부(160)와, 실제 전송된 시퀀스에 대응하는 출력 시퀀스를 복호해내는 복호기(170)로 구성된다.Referring to FIG. 5, the Viterbi decoder according to the present invention calculates a branch word of an input codeword according to a demodulated input sequence, calculates and outputs an error of the calculated branch word, and the most significant bit of the input codeword is a channel. Branch metric calculation unit 110 that detects a specific input codeword determined to have a high probability of being affected by noise, sets it as a metric determination bit, and outputs it, a new branch metric, a cumulative path metric, and a metric determination It is determined whether the difference between the sum of the branch metric and the accumulated path metric for the two paths is within an error occurrence range by receiving a bit, and according to the determination result, the addition of determining the survival path using the input metric determination bit. Survival output through the comparison selection operation unit 150 and the addition comparison selection operation unit 150 The path memory unit 160 stores paths and metrics, and a decoder 170 that decodes an output sequence corresponding to an actually transmitted sequence.
상기 가산 비교 선택 연산장치(150)는 종래 기술과 알고리즘의 차이가 있으나, 도 3에 도시된 구조는 동일하므로, 도 3을 참조하여 설명하면, 상태 천이시 발생하는 누적된 경로 메트릭과 가지 메트릭을 합산하여 각각의 경로를 출력하는 두 개의 가산기(70, 80)와, 상기 두 개의 가산기(70, 80)로부터 출력되는 경로의 차이가 임계값 내에 위치하는지를 판단하여, 상기 판단 결과, 임계값내에 위치할 경우, 상기 가지 메트릭 연산 장치(110)로부터 출력된 메트릭 판단 비트에 따라 생존 경로를 판단하고, 두 가지 경로에 대한 가산기(70, 80)의 결과의 차이가 임계값 이상일 경우, 두 가지 경로 중 최소 거리를 가진 메트릭을 생존 경로로 출력하는 비교부(90)와, 상기 비교부(90)에서 출력된 최적의 누적된 메트릭 및 생존 경로를 입력 경로로 지시하는 선택부(100)로 구성된다.The addition comparison selection operation unit 150 has a difference between the prior art and the algorithm. However, since the structure shown in FIG. 3 is the same, referring to FIG. It is determined whether the difference between the two adders 70 and 80 that add up and output the respective paths and the paths output from the two adders 70 and 80 is within a threshold value. In this case, the survival path is determined according to the metric determination bits output from the branch metric calculation device 110, and when the difference between the results of the adders 70 and 80 for the two paths is greater than or equal to a threshold value, the two paths are determined. The comparator 90 outputs a metric having the minimum distance as a survival path, and the selector 100 instructs the optimal accumulated metric and survival path output from the comparator 90 as an input path. It is.
상술한 바와 같이 구성된 상태에서의 동작 설명은 다음과 같다.The description of the operation in the state configured as described above is as follows.
최상위 잡음 비트 검출기(140)는 연판정 복조된 입력 시퀀스가 4비트의 입력 코드워드라 할 때, 채널 잡음에 의해 오류의 경로 선택을 하도록 유도할 확률적 빈도가 높은 입력 코드워드 "1111"이나 "0000"을 포함하고 있는지 검색하고 이를 검출한다.The most significant noise bit detector 140 is an input codeword " 1111 " or " high probability " that leads to a path selection of an error by channel noise when the soft decision demodulated input sequence is a 4-bit input codeword. Search for "0000" and detect it.
이는 신뢰성 있는 0이나 1의 중간값에 해당하는 4비트로서 신뢰성있는 0이나 1에서 채널 잡음에 의하여 확률적으로 가장 큰 오차를 발생시킬 수 있는 발생 빈도가 높은 경우이다.This is a case where 4 bits corresponding to the median of 0 or 1 are reliable and the frequency of occurrence of the probability of generating the largest error due to channel noise at 0 or 1 is high.
즉, 실제적으로 신뢰성있는 0에서 "1111"이나 "0000"의 입력이 되기 위해서는 "1111"은 최상위비트가 잡음에 의해 교란되어 실제 발생한 잡음에 비해 크게 표현되는 경우이며, "0000"은 최상위 비트를 제외한 하위 3비트가 잡음에 의해 교란되어 나타나는 경우이다.In other words, in order to become a reliable 0 to "1111" or "0000" input, "1111" is a case where the most significant bit is disturbed by noise and is represented larger than the noise actually generated, and "0000" represents the most significant bit. This is the case where the lower 3 bits excepted appear disturbed by noise.
따라서, 확률적으로 최상위 비트가 잡음에 의해 교란되는 경우가 하위 3비트가 연속적으로 잡음에 의해 교란되는 경우보다 훨씬 발생 빈도가 크다고 할 수 있다.Accordingly, it can be said that the case where the most significant bit is disturbed by noise is more likely to occur than the case where the lower three bits are continuously disturbed by noise.
마찬가지로, 신뢰성있는 "1"의 경우, "1111" 이나 "0000"의 입력이 되기 위해서는 "0000"은 최상위 비트가 잡음에 의해 교란되어 실제 발생한 잡음에 비해 크게 표현되는 경우이며, "1111"은 최상위 비트를 제외한 하위 3비트가 잡음에 의해 교란되어 나타나는 경우이며, "0000"가 발생하는 빈도가 확률적으로 크다고 할 수 있다.Similarly, in the case of the reliable "1", in order to become an input of "1111" or "0000", "0000" is a case where the most significant bit is disturbed by noise and is represented larger than the actual noise. The lower 3 bits except for the bits appear to be disturbed by noise, and the frequency of occurrence of "0000" is stochastic.
따라서, 실제적으로 채널 잡음이 미치는 영향이 작음에도 불구하고 가장 크게 나타나는 경우를 최상위 비트 잠음 검출기(140)에서 검출하여 이를 가산 비교 선택 연산장치(150)에서 참조하는 메트릭 판단 비트(D0,D1)로 활용한다.Therefore, the metric determination bits (D 0 , D 1 ) that detect the most significant occurrence of the most significant bit lock detector 140 and refer to it in the addition comparison selection operation unit 150 despite the small influence of the channel noise. To be used.
메트릭 판단 비트는 모든 트렐리스에 대해서 각 상태동안 계산되고 매 심벌마다 갱신된다.The metric decision bit is calculated for each state for every trellis and updated every symbol.
메트릭 판단비트(D0,D1)는 초기 상태에서는 모두 "0"의 값을 가지며, 메트릭 판단비트(D0,D1)는 4비트의 입력 코드워드가 "0000"이나 "1111"의 값을 가지게 될 때 각 경로에 대해서 1이 되고, 그 값은 누적된 경로 메트릭을 따라 계속적으로 전파된다. 이는 앞서 기술한 바와 같이, 입력 코드워드가 "0000"이나 "1111"의 값을 가지는 경우에 최상의 비트가 잡음에 의해 교란되어 잘못된 경로를 선택할 확률적 빈도가 가장 크기 때문에 두 경로중에서 최적의 경로 선택이 애매한 경우에 그 판단근거로 사용할 수 있다. 더불어 최상위 비트 잡음 검출기(140)는 입력 코드워드가 "0000"이나 "1111"인 뿐만이 아니고 도4에 나타낸 입력 코드워드와 기대 코드워드값 사이의 거리값 테이블을 판단 근거로 하여 특정 입력의 코드워드로 확장을 하여 이에 해당하는 입력 코드워드에 대해 메트릭 판단 비트를 1로 설정할 수 있다.The metric decision bits (D 0 , D 1 ) have a value of "0" in the initial state, and the metric decision bits (D 0 , D 1 ) have a 4-bit input codeword of "0000" or "1111". When it has, it becomes 1 for each path, and the value is continuously propagated along the accumulated path metric. This is because, as described above, when the input codeword has a value of "0000" or "1111", the optimal path selection is the most likely because the best bit is disturbed by noise and the probability of selecting the wrong path is the highest. If it is ambiguous, it can be used as the basis for judgment. In addition, the most significant bit noise detector 140 not only has an input codeword of "0000" or "1111", but also codeword of a specific input based on the determination of the distance value table between the input codeword and the expected codeword value shown in FIG. The metric determination bit may be set to 1 for the corresponding input codeword by expanding to.
가지 메트릭 연산장치(110)는 현재 상태에서 최상위 비트 잡음 검출기(140)가 메트릭 판단 비트의 값을 변화시키지 않으면, 가장 큰 메트릭을 가진 경로의 그 전 상태의 메트릭 판단 비트를 따르게 된다.The branch metric arithmetic unit 110 follows the metric decision bit of the previous state of the path with the largest metric unless the highest bit noise detector 140 changes the value of the metric decision bit in the current state.
가지 워드 연산부(120)에서 계산된 가지 워드는 가지 메트릭 연산부(130)에서 디코더가 받아들인 입력 시퀀스에 따른 입력 코드워드와 오차를 연산하게 된다.The branch word calculated by the branch word operator 120 calculates an input codeword and an error according to an input sequence received by the decoder by the branch metric operator 130.
새로운 가지 메트릭 및 누적된 경로 메트릭은 최상위 비트 잡음 검출기(140)에서 검출된 한 비트의 메트릭 판단 비트는 가산 비교 선택 연산장치(150)의 입력으로 쓰여진다.The new branch metric and the accumulated path metric are written to the input of the add comparison select operation unit 150 with one bit of the metric decision bit detected by the most significant bit noise detector 140.
가산 비교 선택 연산장치(150)에서 가산 모듈은 두 가지 경로에 대해 가지 메트릭과 누적된 경로 메트릭의 합을 구한다.In the addition comparison selection operation unit 150, the addition module obtains the sum of the branch metric and the accumulated path metric for the two paths.
비교 모듈은 도 6에 도시된 최적의 생존 경로 선택을 위한 비교 장치의 플로우차트와 같은 연산을 수행한다.The comparison module performs the same operation as the flowchart of the comparison apparatus for selecting the optimal survival path shown in FIG. 6.
비교 모듈은 두가지 경로에 대한 가산기의 결과(P0, P1)와 메트릭 판단 비트(D0, D1)외에 추가적으로 최적의 생존 경로를 선택하기 어렵다고 정의된 두 경로의 차이(diff)의 범위, 임계값(TH)을 입력받는다.In addition to the results of the adders for the two paths (P 0 , P 1 ) and the metric decision bits (D 0 , D 1 ), the comparison module adds a range of differences between the two paths defined as difficult to select an optimal survival path, The threshold value TH is input.
비교 모듈은 두 가지 경로의 차이가 임계값 내에 위치하는지를 판단한다(S200).The comparison module determines whether the difference between the two paths is located within the threshold (S200).
즉, 최소 거리 메트릭을 가진 코드워드를 최적 경로라 할 때, 두가지 경로의 차이가 임계값 내에 위치하는지를 검색하는 것이다.That is, when a codeword having a minimum distance metric is called an optimal path, it is to search whether the difference between the two paths is within a threshold.
상기 S200의 판단 결과, 최소 거리 메트릭을 가진 코드워드를 최적 경로라 할 때, 두 가지 경로(P0-P1=diff)의 차이가 임계값 내에 위치하지 않는 경우, 즉 4비트의 입력 코드워드를 이용하여 충분히 생존 경로의 판단이 가능한 경우, 두 가지 경로 중에서 최소 거리를 가진 메트릭을 검출한다(S230).As a result of the determination of S200, when a codeword having a minimum distance metric is an optimal path, when a difference between two paths (P 0 -P 1 = diff) is not located within a threshold, that is, an input codeword of 4 bits If it is possible to sufficiently determine the survival path, the metric having the minimum distance among the two paths is detected (S230).
즉, P0-P1의 값이 음이 되는 경우, P0가 최소 거리를 가진 메트릭이므로 P0를 생존 경로로 결정하고(S240), P0-P1의 값이 양이 되는 경우, P1가 최소 거리를 가진 메트릭이므로 P1을 생존 경로로 결정한다(S220).That is, when P 0 -P 1 becomes negative, P 0 is determined as a survival path because P 0 is a metric having a minimum distance (S240), and when P 0 -P 1 becomes positive, P 0. Since 1 is a metric having a minimum distance, P 1 is determined as a survival path (S220).
그러나, 상기 S200의 판단 결과, 두가지 경로의 차이(P0-P1)가 임계값 내에 위치하는 경우 메트릭 판단 비트를 이용하여 최적 경로를 선택하게 된다(S210).However, as a result of the determination of S200, when the difference (P 0 -P 1 ) between the two paths is located within the threshold, the optimal path is selected using the metric determination bit (S210).
두 가지 경로 중에서 메트릭 판단 비트를 포함한 메트릭을 생존 경로로 선택하게 되는데, P0의 메트릭 판단 비트인 D0가 1일 경우, P1을 생존 경로로 결정한다(S220).A metric including a metric determination bit is selected as a survival path among two paths. When D 0, which is a metric determination bit of P 0 , is 1, P 1 is determined as a survival path (S220).
그러나,D0가 1이 아닐 경우, P0를 생존 경로로 결정한다(S240).However, if D 0 is not 1, P 0 is determined as a survival path (S240).
이는 메트릭 판단 비트를 포함하고 있는 경로가 채널 잡음이 실제로 미친 효과에 비해 크게 나타나는 경우이기 때문이다.This is because the path containing the metric decision bits is larger than the effect of the channel noise.
가산 비교 선택 연산장치(150)의 선택 모듈은 비교 모듈에서 최적의 누적된 메트릭 및 생존 경로를 산출하는 입력 경로 지시를 출력한다.The selection module of the addition comparison selection operation unit 150 outputs an input path instruction for calculating an optimal accumulated metric and a survival path in the comparison module.
가산 비교 선택 연산장치(150)를 통해 생성된 생존 경로 및 메트릭은 다음 트렐리스 단계를 위해 경로 메모리(160)에 저장되고, 복호기(170)에서 후에 트레이스백 과정을 거쳐 실제 전송된 시퀀스에 대응할 수 있는 시퀀스를 복호해낸다.Survival paths and metrics generated by the add comparison selection arithmetic unit 150 are stored in the path memory 160 for the next trellis step, and are decoded in the decoder 170 to correspond to the actual transmitted sequence after a traceback process. Decode a sequence that can be.
이상의 본 발명은 상기에 기술된 실시예들에 의해 한정되지 않고, 당업자들에 의해 다양한 변형 및 변경을 가져올 수 있으며, 이는 첨부된 청구항에서 정의되는 본 발명의 취지와 범위에 포함된다.The present invention is not limited to the embodiments described above, and various modifications and changes can be made by those skilled in the art, which are included in the spirit and scope of the present invention as defined in the appended claims.
상기에서 살펴본 본 발명은 가산 비교 선택 연산장치에서 두 가지 경로에 대해 복호의 오류를 범할 수 있는 가지 메트릭 값과 누적된 경로 메트릭 값의 합의 차이를 정의하고 이 경우에 가지 메트릭 연산장치에서 채널 잡음의 영향에 의해서 오류 발생의 확률적 빈도가 가장 높은 입력 코드워드, 특히 입력 코드워드의 최상위 비트가 잡음에 의해 영향을 받을 수 있는 확률적 빈도가 높다고 판단되는 특정 입력 코드워드에 대해 이를 메트릭 판단 비트로 사용함으로써 비터비 복호의 결과의 정밀도를 향상시킬 수 있다는 이점이 있다.The present invention as described above defines the difference between the sum of the branch metric value and the accumulated path metric value that may cause a decoding error for two paths in the addition comparison selection operation unit, and in this case, the channel noise Use it as a metric decision bit for an input codeword with the highest probability of error occurrence by its influence, especially for a particular input codeword where the most significant bit of the input codeword is likely to be affected by noise. This has the advantage that the accuracy of the result of Viterbi decoding can be improved.
Claims (2)
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
KR10-2001-0088532A KR100459419B1 (en) | 2001-12-29 | 2001-12-29 | Viterbi decoder |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
KR10-2001-0088532A KR100459419B1 (en) | 2001-12-29 | 2001-12-29 | Viterbi decoder |
Publications (2)
Publication Number | Publication Date |
---|---|
KR20030058145A KR20030058145A (en) | 2003-07-07 |
KR100459419B1 true KR100459419B1 (en) | 2004-12-03 |
Family
ID=32216072
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
KR10-2001-0088532A Expired - Fee Related KR100459419B1 (en) | 2001-12-29 | 2001-12-29 | Viterbi decoder |
Country Status (1)
Country | Link |
---|---|
KR (1) | KR100459419B1 (en) |
-
2001
- 2001-12-29 KR KR10-2001-0088532A patent/KR100459419B1/en not_active Expired - Fee Related
Also Published As
Publication number | Publication date |
---|---|
KR20030058145A (en) | 2003-07-07 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
US6061823A (en) | Error correcting/decoding apparatus and error correcting/decoding method | |
US6148431A (en) | Add compare select circuit and method implementing a viterbi algorithm | |
US5802116A (en) | Soft decision Viterbi decoding with large constraint lengths | |
EP0671817A1 (en) | Soft symbol decoding for use in an MLSE-equaliser or convolutional decoder | |
US8671335B2 (en) | Soft output Viterbi detector with error event output | |
KR970019196A (en) | Signal determining apparatus and receiving apparatus in a coded communication system, signal judging method, and communication path state estimating method | |
JPH09181619A (en) | Viterbi decoder and its decoding method | |
KR20020027535A (en) | ACS unit for a Viterbi decoder | |
JPH10133898A (en) | Method for detecting and correcting error of convolution encoding data | |
US8009773B1 (en) | Low complexity implementation of a Viterbi decoder with near optimal performance | |
JP2008118327A (en) | Viterbi decoding method | |
JPH09232971A (en) | Viterbi decoding method and viterbi decoding circuit | |
EP0748057B1 (en) | Bit error counting method and counter | |
KR100459419B1 (en) | Viterbi decoder | |
US7062000B1 (en) | Viterbi decoder | |
US7263653B2 (en) | Algorithm for a memory-based Viterbi decoder | |
JP2757473B2 (en) | Viterbi decoder | |
JP3987153B2 (en) | Signal decoding for Viterbi decoder based on Manhattan or Hamming metric scheme | |
JP2591332B2 (en) | Error correction decoding device | |
KR100431162B1 (en) | coderate detection circuit | |
JPH05110452A (en) | Convolution code viterbi decoding data discrimination system | |
KR0169681B1 (en) | Viterbi Decoder | |
JP3337950B2 (en) | Error correction decoding method and error correction decoding device | |
JP2757476B2 (en) | Viterbi decoder | |
KR20020048963A (en) | Viterbi decoder |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
A201 | Request for examination | ||
PA0109 | Patent application |
Patent event code: PA01091R01D Comment text: Patent Application Patent event date: 20011229 |
|
PA0201 | Request for examination | ||
N231 | Notification of change of applicant | ||
PN2301 | Change of applicant |
Patent event date: 20020614 Comment text: Notification of Change of Applicant Patent event code: PN23011R01D |
|
PG1501 | Laying open of application | ||
E902 | Notification of reason for refusal | ||
PE0902 | Notice of grounds for rejection |
Comment text: Notification of reason for refusal Patent event date: 20031213 Patent event code: PE09021S01D |
|
AMND | Amendment | ||
E601 | Decision to refuse application | ||
PE0601 | Decision on rejection of patent |
Patent event date: 20040721 Comment text: Decision to Refuse Application Patent event code: PE06012S01D Patent event date: 20031213 Comment text: Notification of reason for refusal Patent event code: PE06011S01I |
|
J201 | Request for trial against refusal decision | ||
PJ0201 | Trial against decision of rejection |
Patent event date: 20040820 Comment text: Request for Trial against Decision on Refusal Patent event code: PJ02012R01D Patent event date: 20040721 Comment text: Decision to Refuse Application Patent event code: PJ02011S01I Appeal kind category: Appeal against decision to decline refusal Decision date: 20041013 Appeal identifier: 2004101003727 Request date: 20040820 |
|
AMND | Amendment | ||
PB0901 | Examination by re-examination before a trial |
Comment text: Amendment to Specification, etc. Patent event date: 20040917 Patent event code: PB09011R02I Comment text: Request for Trial against Decision on Refusal Patent event date: 20040820 Patent event code: PB09011R01I Comment text: Amendment to Specification, etc. Patent event date: 20040212 Patent event code: PB09011R02I |
|
B701 | Decision to grant | ||
PB0701 | Decision of registration after re-examination before a trial |
Patent event date: 20041013 Comment text: Decision to Grant Registration Patent event code: PB07012S01D Patent event date: 20041004 Comment text: Transfer of Trial File for Re-examination before a Trial Patent event code: PB07011S01I |
|
GRNT | Written decision to grant | ||
PR0701 | Registration of establishment |
Comment text: Registration of Establishment Patent event date: 20041122 Patent event code: PR07011E01D |
|
PR1002 | Payment of registration fee |
Payment date: 20041123 End annual number: 3 Start annual number: 1 |
|
PG1601 | Publication of registration | ||
PR1001 | Payment of annual fee |
Payment date: 20070918 Start annual number: 4 End annual number: 4 |
|
FPAY | Annual fee payment |
Payment date: 20080926 Year of fee payment: 5 |
|
PR1001 | Payment of annual fee |
Payment date: 20080926 Start annual number: 5 End annual number: 5 |
|
LAPS | Lapse due to unpaid annual fee | ||
PC1903 | Unpaid annual fee |
Termination category: Default of registration fee Termination date: 20101009 |