JPH0312495B2 - - Google Patents
Info
- Publication number
- JPH0312495B2 JPH0312495B2 JP60253764A JP25376485A JPH0312495B2 JP H0312495 B2 JPH0312495 B2 JP H0312495B2 JP 60253764 A JP60253764 A JP 60253764A JP 25376485 A JP25376485 A JP 25376485A JP H0312495 B2 JPH0312495 B2 JP H0312495B2
- Authority
- JP
- Japan
- Prior art keywords
- path
- memory
- history
- threshold
- shift register
- 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 - Lifetime
Links
Landscapes
- Error Detection And Correction (AREA)
Description
【発明の詳細な説明】
〔概要〕
畳み込み符号をフアノ・アルゴリズムにより復
号するシーケンシヤル復号器に於いて、加算器と
シフトレジスタとによつて内部符号器を構成し、
シフトレジスタにより、パスメモリとの間のパス
の経歴の転送を高速化したものである。[Detailed Description of the Invention] [Summary] In a sequential decoder that decodes convolutional codes using the Juano algorithm, an internal encoder is configured by an adder and a shift register,
A shift register speeds up the transfer of path history to and from the path memory.
本発明は、畳み込み符号（convolutional
code）をフアノ・アルゴリズム（Fano
algorithm）で復号するシーケンシヤル復号器に
関するものである。 The present invention uses convolutional codes (convolutional codes).
code) to the Fano algorithm (Fano
This is related to a sequential decoder that decodes using a sequential algorithm.
畳み込み符号を復号する復号方法として、閾値
復号法（threshold decoding）、最尤復号法
（maxmum likelihood decoding）及びシーケン
シヤル復号器（逐次復号法）（sequential
decoding）に大別される。フアノ・アルゴリズ
ムは、シーケンシヤル復号法の復号アルゴリズム
の中心的なアルゴリズムであり、樹枝状符号の中
の一つのパスと受信系列とのパス値を計算し、そ
のパス値が或る閾値以下の場合に情報ビツトを復
号し、パス値が或る値を超えた場合は、謝りのパ
スに入つたものとして、正しいパスを探索し、正
しい情報ビツトを復号するアルゴリズムである。 Decoding methods for decoding convolutional codes include threshold decoding, maximum likelihood decoding, and sequential decoding.
decoding). The Juano algorithm is the main decoding algorithm of the sequential decoding method. It calculates the path value between one path in the dendritic code and the received sequence, and if the path value is less than a certain threshold, This algorithm decodes information bits, and if the path value exceeds a certain value, it is assumed that the path has entered the apology path, searches for the correct path, and decodes the correct information bits.
シーケンシヤル復号器は、パスメモリ、内部符
号器、パスメトリツクの判定、選択手段等からな
るものであり、第２図は従来例のシーケンシヤル
復号器の要部ブロツク図である。同図に於いて、
１１はパスメモリ、１２，１３，１４は内部符号
器を構成するメモリ及び法２の加算器、１５は受
信復調部、１６，１７はフアノ計量部、１８は処
理判定部である。拘束長は４、符号化率（符号の
情報率）は1/2の場合を示し、メモリ１２は拘束
長分のビツト長を有するものである。又加算器１
３，１４は、例えば、排他的論理和回路で構成す
ることができる。
The sequential decoder consists of a path memory, an internal encoder, path metric determination and selection means, etc. FIG. 2 is a block diagram of the main parts of a conventional sequential decoder. In the same figure,
11 is a path memory; 12, 13, and 14 are memories and modulo-2 adders constituting an internal encoder; 15 is a reception demodulation section; 16 and 17 are Fano measurement sections; and 18 is a processing determination section. The case is shown in which the constraint length is 4 and the coding rate (code information rate) is 1/2, and the memory 12 has a bit length equal to the constraint length. Adder 1
3 and 14 can be configured with exclusive OR circuits, for example.
受信信号は受信復調部１５により復調され、軟
判定により２系列の復調符号が出力され、又内部
符号器を構成するメモリ１２と加算器１３，１４
とにより、メモリ１２の内容を基に畳み込み符号
が形成され、それぞれフアノ計量部１６，１７に
加えられてシンボルメトリツクが求められる。フ
アノ計量部１６，１７の出力シンボルメトリツク
は処理判定部１８に加えられる。 The received signal is demodulated by the reception demodulation section 15, and two series of demodulation codes are outputted by soft decision.
As a result, convolutional codes are formed based on the contents of the memory 12, and are applied to the Fano measurement units 16 and 17, respectively, to obtain symbol metrics. The output symbol metrics of the Fano measurement units 16 and 17 are applied to a processing determination unit 18.
復号過程に於いては、メモリ１２に仮に“１”
又は“０”の復号出力を加えることにより、仮の
畳み込み符号を出力し、フアノ計量部１６，１７
に於いて復調信号と仮の畳み込みとの演算により
シンボルメトリツクを求めて処理判定部に加える
ことになり、処理判定部１８では、シンボルメト
リツクを加算したブランチメトリツクについて
“１”の場合と“０”の場合とについて大きい方
を選択し、一つ前に求めたパスメトリツクと加算
し、閾値と比較する。この閾値を超えない場合に
正しいパスとし、その時のメモリ１２の内容をパ
スの経歴としてパスメモリ１１に転送して、次の
処理に移行する。又パスメモリ１１の内容が復号
出力となる。 In the decoding process, "1" is temporarily stored in the memory 12.
Alternatively, by adding the decoded output of "0", a temporary convolutional code is output, and the Fano measurement unit 16, 17
In this step, a symbol metric is obtained by calculating the demodulated signal and the temporary convolution and is added to the processing judgment unit. For the case of "0", the larger one is selected, added to the previously obtained path metric, and compared with the threshold value. If this threshold value is not exceeded, the path is determined to be correct, the contents of the memory 12 at that time are transferred to the path memory 11 as the history of the path, and the process moves on to the next process. Also, the contents of the path memory 11 become the decoded output.
又閾値を超えた場合は、謝りがあるとして、一
つ前のパスの経歴を含む拘束長分のパスの経歴を
パスメモリ１１から読出してメモリ１２に転送
し、前述と同様な処理を行うことになる。その場
合も閾値を超えることになると、更に前のパスの
経歴を含む拘束長分のパスの経歴をパスメモリ１
１から読出してメモリ１２に転送し、前述と同様
な処理を行うことになる。このようにして正しい
パスを探索することになる。 If the threshold is exceeded, the path history corresponding to the constraint length, including the history of the previous path, is read out from the path memory 11 and transferred to the memory 12, and the same process as described above is performed as an apology. become. In that case, if the threshold is exceeded, the path history corresponding to the constraint length, including the history of the previous path, is stored in the path memory 1.
1 and transferred to the memory 12, and the same processing as described above is performed. In this way, the correct path will be searched.
第３図はフアノ・アルゴリズムの説明図であつ
て、処理判定部１８に於いてパス値（パスメトリ
ツク）と閾値D0とを比較し、この閾値D0を超え
ないパスを正しいパスして選択するものである。
そして、メモリ１２からパスメモリ１１にパスの
経歴として転送される。(1)点では閾値D0とパス
値が比較され、(2)、(3)点では閾値2D0とパス値が
比較され、(4)点では閾値3D0とパス値が比較さ
れ、(5)、(6)、(7)点で閾値4D0とパス値が比較され
る。 FIG. 3 is an explanatory diagram of the Juano algorithm, in which the processing judgment unit 18 compares the path value (path metric) with a threshold value D0 , and selects the path that does not exceed this threshold value D0 as the correct path. It is something.
Then, it is transferred from the memory 12 to the path memory 11 as a path history. At point (1), the threshold D 0 and the pass value are compared, at points (2) and (3), the threshold 2D 0 and the pass value are compared, at the (4) point, the threshold 3D 0 and the pass value are compared, and ( The threshold value 4D 0 and the path value are compared at points 5), (6), and (7).
(1)〜(7)点では何れもパス値が閾値を超えない場
合であるから、これまでのパスは正しいと判定さ
れることになり、メモリ１２の内容がパスの経歴
としてパスメモリ１１に転送される。このような
状態に於いて、(8)点では、パス値が閾値4D0を超
えることになるから、パスメモリ１１からメモリ
１２に一つ前の(7)点のパスの経歴を含む拘束長分
のパスの経歴を転送させ、閾値4D0を超えない他
のパスが存在するか否か判定する。他のパスが存
在しないことを判定すると、(7)点までのパスは誤
りと判定し、更に前の(6)点のパスの経歴を含む拘
束長分のパスの経歴をパスメモリ１１からメモリ
１２に転送し、他のパスの探索を行う。この時、
(11)点が閾値4D0を超えない他のパスとなる場合
は、それを正しいパスとして、後退によるパスの
探索から前進によるパスの探索に移行し、次の(12)
点に於ける判定処理が行われる。 Points (1) to (7) are cases in which the path value does not exceed the threshold value, so the path so far is determined to be correct, and the contents of the memory 12 are stored in the path memory 11 as the history of the path. be transferred. In this situation, at point (8), the path value exceeds the threshold 4D0 , so the constraint length containing the path history of the previous point (7) is stored from path memory 11 to memory 12. The path history for minutes is transferred, and it is determined whether there is another path that does not exceed the threshold 4D 0 . If it is determined that no other path exists, the path up to point (7) is determined to be an error, and the path history corresponding to the constraint length including the path history of the previous point (6) is stored from the path memory 11. 12 and searches for other paths. At this time,
(11) If the point is another path that does not exceed the threshold 4D 0 , consider it the correct path and move from searching for a backward path to searching for a forward path, and proceed as follows (12)
Judgment processing is performed at the point.
又(11)点のような閾値4D0を超えない他のパスが
存在しない場合、或いは次の（13）点が閾値4D0
を超える場合は、更に前の(5)点のパスの経歴を含
む拘束長分のパスの経歴がパスメモリ１１からメ
モリ１２に転送され、他のパスが探索される。こ
のように後退により正しいパスを探索するもの
で、（14）点も閾値4D0を超える場合、(5)点から
のパスが総て閾値4D0を超えるので、閾値を3D0
に下げてパスの探索を行うことなる。この場合、
（14）点は閾値3D0を超えないが、次の（15）点
は閾値3D0を超えるので、正しいパスでないと判
定される。 Also, if there is no other path that does not exceed the threshold 4D 0 , such as point (11), or the next point (13) is the threshold 4D 0.
If it exceeds, the path history corresponding to the constraint length including the path history of the previous point (5) is transferred from the path memory 11 to the memory 12, and another path is searched. In this way, the correct path is searched by regression, and if point (14) also exceeds the threshold 4D 0 , all paths from point (5) exceed the threshold 4D 0 , so the threshold is set to 3D 0.
The path search will be performed by lowering the in this case,
Point (14) does not exceed the threshold 3D 0 , but the next point (15) does exceed the threshold 3D 0 , so it is determined that it is not a correct path.
従つて、(7)点から(8)点のパスは、閾値3D0を超
えないので、正しいパスとされ、(9)点では閾値
3D0を超えることになり、誤りのパスと判定され
て、前述の後退による他のパスの探索が行われ、
閾値3D0を超えないようになるパスが存在しない
と、閾値を更に下げて2D0とする。それによつ
て、(9)点までのパスも正しいの判定され、前進に
よるパスの探索により(10)点も閾値2D0を超えない
ので、正しいパスと判定される。 Therefore, since the path from point (7) to point (8) does not exceed the threshold 3D 0 , it is considered a correct path, and the path from point (9)
3D exceeds 0 , the path is determined to be an error, and a search for another path is performed by regressing as described above.
If there is no path that does not exceed the threshold 3D 0 , the threshold is further lowered to 2D 0 . As a result, the path up to point (9) is also determined to be correct, and since point (10) also does not exceed the threshold value 2D 0 due to the forward path search, it is determined to be the correct path.
パスメモリ１１の内部符号器の一部を構成する
メモリ１２との間では、拘束長分のパスの経歴が
転送されるもので、例えば後退によるパスの探索
時には、一つ前のパスの経歴が書込まれているパ
スメモリ１１のアドレスから符号の拘束長分の長
さにわたるアドレスまでのパスの経歴を逐次読出
して、内部符号器の一部を構成するメモリ１２に
転送して書込むものであるから、符号の拘束長が
長くなると、パスメモリ１１とメモリ１２との間
のパスの経歴の転送時間が長くなり、処理速度が
低下する欠点があつた。
The path history corresponding to the constraint length is transferred between the path memory 11 and the memory 12 that forms part of the internal encoder. For example, when searching for a path by backwards, the history of the previous path is transferred. This is because the history of the path from the written address in the path memory 11 to the address corresponding to the length of the code constraint is sequentially read out, transferred to the memory 12 that forms part of the internal encoder, and written. As the code constraint length becomes longer, it takes longer to transfer the path history between the path memory 11 and the memory 12, resulting in a reduction in processing speed.
本発明は、パスの経歴を高速化し、処理速度を
向上することを目的とするものである。 The present invention aims to speed up path history and improve processing speed.
本発明のシーケンシヤル復号器は、内部符号器
の一部をシフトレジスタにより構成したものであ
り、第１図を参照して説明すると、シフトレジス
タ２と加算器３，４とにより内部符号器を構成し
て、パスの経歴を記憶するパスメモリ１のシフト
レジスタ２との間でパスの経歴を転送するもので
ある。
In the sequential decoder of the present invention, a part of the internal encoder is composed of a shift register.To explain with reference to FIG. 1, the internal encoder is composed of a shift register 2 and adders 3 and 4. The path history is then transferred to and from the shift register 2 of the path memory 1 which stores the path history.
前進でパスの探索を行う場合は、正しいパスと
判定された時に、パスメモリ１の所定のアドレス
へシフトレジスタ２からシフト出力したパスの経
歴が書込まれ、又後退でパスの探索を行う場合
は、パスメモリ１と所定のアドレスからパスの経
歴が読出されてシフトレジスタ２に加えられてシ
フトされ、それぞれパスメモリ１に対しては１回
の書込み又は読出しで済むことになり、処理の高
速を図ることができる。
When searching for a path in forward motion, when the path is determined to be correct, the history of the path shifted out from shift register 2 is written to a predetermined address in path memory 1, and when searching for a path in backward motion The path history is read from the path memory 1 and a predetermined address, added to the shift register 2, and shifted, and only one write or read is required for each path memory 1, which speeds up the processing. can be achieved.
以下図面を参照して本発明の実施例について詳
細に説明する。
Embodiments of the present invention will be described in detail below with reference to the drawings.
第１図は本発明の実施例の要部ブロツク図であ
り、パスメモリ１と内部符号器の部分のみを示す
ものである。その内部符号器を、シフトレジスタ
２と法２の加算器３，４とにより構成する。この
シフトレジスタ２は、左右方向のシフトが可能で
且つ符号の拘束長分の長さを有するものである。
このシフトレジスタ２の左方向へのシフト出力を
パスの経歴としてパスメモリ１へ転送して書込
み、又パスメモリ１からのパスの経歴をシフトレ
ジスタ２に転送して右方向へのシフトを行うもの
である。又加算器３，４の出力と畳み込み符号
は、図示を省略したフアノ計量部へ軟判定による
復調信号と共に加えられることになる。 FIG. 1 is a block diagram of the main parts of an embodiment of the present invention, showing only the path memory 1 and internal encoder. The internal encoder is composed of a shift register 2 and modulo-2 adders 3 and 4. This shift register 2 is capable of shifting in the left-right direction and has a length corresponding to the code constraint length.
The leftward shift output of the shift register 2 is transferred to the path memory 1 and written as the path history, and the path history from the path memory 1 is transferred to the shift register 2 and shifted to the right. It is. Further, the outputs of the adders 3 and 4 and the convolutional code are added together with a demodulated signal based on a soft decision to a Fano measurement section (not shown).
前進によるパスの探索時は、シフトレジスタ２
の左方向シフトによりパスの経歴がパスメモリ１
の所定のアドレスに書込まれる。そして、右端の
空いた領域に“１”又は“０”を加えて仮の符号
を加算器３，４から出力させ、前述のように、パ
ス値が閾値を超えない場合は正しいパスの判定す
るから、その時の“１”又は“０”がシフトレジ
スタ２の右端に残り、次のパスの探索時に、シフ
トレジスタ２の左方向へのシフトによりシフト出
力されるパスの経歴がパスメモリ１の前述のアド
レスの次のアドレスへ書込まれる。そして、シフ
トレジスタ２の右端に“１”又は“０”が加えら
れて仮の符号が出力される。 When searching for a path by moving forward, shift register 2
By shifting to the left, the path history is moved to path memory 1.
is written to a predetermined address. Then, "1" or "0" is added to the empty area at the right end to output a temporary code from adders 3 and 4, and as mentioned above, if the path value does not exceed the threshold, it is determined that the path is correct. , the "1" or "0" at that time remains at the right end of the shift register 2, and when searching for the next path, the path history that is shifted and output by shifting the shift register 2 to the left is the same as the above in the path memory 1. is written to the next address. Then, "1" or "0" is added to the right end of the shift register 2, and a temporary code is output.
又後退によるパスの探索時は、前回のパス探索
後にパスの経歴が書込まれたパスメモリ１のアド
レスから、そのパスの経歴が読出されてシフトレ
ジスタ２の左端に加えられ、右方向シフトが行わ
れる。それによつて、シフトレジスタ２には前回
のパスの経歴を含む符号の拘束長分のパスの経歴
がセツトされ、再度右端に“１”又は“０”が加
えられて、仮の符号が出力され、パス値が閾値を
超えないパスの探索が行われる。更に後退による
パスの探索を行う場合は、前前回のパスの探索時
にパスの経歴が書込まれたパスメモリ１のアドレ
スから、そのパスの経歴が読出されてシフトレジ
スタ２の左端に加えられ、右方向シフトが行われ
る。 Also, when searching for a path by backwards, the path history is read from the address in path memory 1 where the path history was written after the previous path search and added to the left end of shift register 2, and a rightward shift is performed. It will be done. As a result, the path history corresponding to the constraint length of the code including the history of the previous pass is set in the shift register 2, "1" or "0" is added to the right end again, and a temporary code is output. , a search is performed for a path whose path value does not exceed a threshold. When searching for a path further by backwards, the path history is read from the address in the path memory 1 where the path history was written during the previous path search and added to the left end of the shift register 2. A rightward shift is performed.
シフトレジスタ２は、前進によるパスの探索時
は、左方向へのシフト制御を行い、後退によるパ
スの探索時は、右方向へのシフト制御を行うこと
になり、このような制御手段は既に知られている
種々の手段を採用することができる。又パスメモ
リ１へのパスの経歴の書込み、或いはパスの経歴
の読出しの為のアドレス制御は、前進によるパス
の探索時か後退によるパスの探索時かに対応して
行われることになり、容易に実現することができ
る。 The shift register 2 performs shift control to the left when searching for a forward path, and performs shift control to the right when searching for a backward path. Such control means are already known. Various means can be adopted. In addition, address control for writing path history into path memory 1 or reading path history is easily performed depending on whether the path is being searched forward or backward. can be realized.
以上説明したように、本発明は、シーケンシヤ
ル復号器の内部符号器を、シフトレジスタ２と加
算器３，４とにより構成したもので、パスメモリ
１へのパスの経歴の書込み、及びパスメモリ１か
らのパスの経歴の読出しは、符号の拘束長に依存
することなく、１回で済むことになり、従来例に
比較して著しく高速化が可能となる利点がある。
As explained above, in the present invention, the internal encoder of a sequential decoder is configured by a shift register 2 and adders 3 and 4, and the path history is written in the path memory 1 and the path memory 1 The path history can be read only once without depending on the code constraint length, which has the advantage of being significantly faster than the conventional example.
第１図は本発明の実施例の要部ブロツク図、第
２図は従来例の要部ブロツク図、第３図はフア
ノ・アルゴリズムの説明図である。
１はパスメモリ、２はシフトレジスタ、３，４
は加算器である。
FIG. 1 is a block diagram of a main part of an embodiment of the present invention, FIG. 2 is a block diagram of a main part of a conventional example, and FIG. 3 is an explanatory diagram of the Fano algorithm. 1 is path memory, 2 is shift register, 3, 4
is an adder.
Claims (1)
復号器に於いて、 パスの経歴を記憶するパスメモリ１との間で前
記パスの経歴を相互に転送可能で、且つ符号の拘
束長の長さを有し、前記パスの経歴を一時的に蓄
積し、加算器３，４と共に内部符号器を構成する
シフトレジスタ２を備えた ことを特徴とするシーケンシヤル復号器。[Claims] 1. In a sequential decoder based on the Juano algorithm, the history of the path can be mutually transferred with the path memory 1 that stores the history of the path, and the length of the code constraint length is 1. A sequential decoder comprising: a shift register 2 which temporarily stores the path history and forms an internal encoder together with adders 3 and 4.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP25376485A JPS62114334A (en) | 1985-11-14 | 1985-11-14 | Sequential decoder |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP25376485A JPS62114334A (en) | 1985-11-14 | 1985-11-14 | Sequential decoder |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS62114334A JPS62114334A (en) | 1987-05-26 |
| JPH0312495B2 true JPH0312495B2 (en) | 1991-02-20 |
Family
ID=17255813
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP25376485A Granted JPS62114334A (en) | 1985-11-14 | 1985-11-14 | Sequential decoder |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS62114334A (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS63203019A (en) * | 1987-02-19 | 1988-08-22 | Fujitsu Ltd | Sequential decoder |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS59190751A (en) * | 1983-04-13 | 1984-10-29 | Nec Corp | Storage device updating circuit of viterbi decoder |
| GB8315363D0 (en) * | 1983-06-03 | 1983-07-06 | Gordon J A | Decoding errorcorrecting codes |
-
1985
- 1985-11-14 JP JP25376485A patent/JPS62114334A/en active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS62114334A (en) | 1987-05-26 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| KR970072838A (en) | Method and circuit for soft decision Viterbi decoding with large constraint length | |
| CA1260142A (en) | Sequential decoding device for decoding systematic code | |
| JP2531533B2 (en) | Iterative decoder | |
| JPWO2000052833A1 (en) | Maximum a posteriori probability decoding method and apparatus | |
| KR0135796B1 (en) | Traceback processing apparatus in viterbi decorder | |
| US7035356B1 (en) | Efficient method for traceback decoding of trellis (Viterbi) codes | |
| JP2005109771A (en) | Maximum posterior probability decoding method and apparatus | |
| JPS63161731A (en) | Sequential error correction decoding device | |
| US7173985B1 (en) | Method and apparatus for implementing a Viterbi decoder | |
| JPH0312495B2 (en) | ||
| JP4580927B2 (en) | Viterbi decoding apparatus and Viterbi decoding method | |
| US20040190651A1 (en) | Decoding a signal encoded with a convolutional code | |
| JP3235333B2 (en) | Viterbi decoding method and Viterbi decoding device | |
| JPS62164320A (en) | Sequential decoder | |
| JPH05335973A (en) | Viterbi decoder and convolutional code decoder | |
| JP3120342B2 (en) | Viterbi decoder | |
| Mansour et al. | Efficient decoding of watermarking schemes in the presence of false alarms | |
| JP2904271B2 (en) | Path memory unit for Viterbi decoder and decoding method | |
| JPH01158829A (en) | Sequential decoder | |
| KR950005860B1 (en) | Viterbi decoding method | |
| JPH01206729A (en) | Sequential decoder | |
| US7564930B1 (en) | Method and apparatus for implementing a traceback processor for trellis decoding in a Viterbi decoder | |
| JP2571384B2 (en) | Sequential decoder | |
| JP2671581B2 (en) | Successive decoding device | |
| JPH0740670B2 (en) | Stack algorithm type sequential decoding method |