JPH0722969A

JPH0722969A - 演算装置

Info

Publication number: JPH0722969A
Application number: JP14494893A
Authority: JP
Inventors: Nobuo Asano; 野延夫浅; Mitsuru Uesugi; 杉充上; Toshihiro Ishikawa; 川利広石; Minoru Okamoto; 本稔岡
Original assignee: Matsushita Electric Industrial Co Ltd
Current assignee: Panasonic Holdings Corp
Priority date: 1993-06-16
Filing date: 1993-06-16
Publication date: 1995-01-24

Abstract

(57)【要約】【目的】ディジタル信号プロセッサにおいて、少ない
ハードウェア追加でビタビ復号のＡＣＳ計算の演算量を
軽減できる演算装置を提供する。【構成】第１および第２のデータメモリ１、２から同
一のポインタで指す番地の内容をそれぞれ読み出してＡ
ＬＵ１０と加算器１１の一方の入力とし、対となる複数
のレジスタ１２〜１５の内容をそれぞれＡＬＵ１０と加
算器１１の他方の入力とし、ＡＬＵ１０と加算器１１で
加算し、それぞれの演算結果を大小比較器２１の比較結
果により選択される第１および第２のレジスタ１８、１
９に格納するとともに大小比較器２１にも入力し、その
比較結果をシフトレジスタ２３に格納する。ＡＬＵ１０
と加算器１１で同時に加算することにより、１ステップ
でＡＣＳ計算を行なえるので、従来と比べメモリを増や
さず演算量を大幅に軽減することができる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、誤り訂正用畳み込み符
号化データのビタビ復号を行なうディジタル信号処理プ
ロセッサ等に使用される演算装置に関する。

【０００２】

【従来の技術】近年、ディジタル信号処理プロセッサ
（以下、ＤＳＰと略称する。）は、移動通信分野におけ
るディジタル化の動きにあわせて、携帯電話等への機器
組み込み用途のプロセッサとして注目されている。移動
無線回線におけるデータ通信では、ビット誤りが頻繁に
発生し、誤り訂正処理を行なう必要がある。誤り訂正の
手法には、畳み込み符号にビタビ復号を用いるものがあ
り、この誤り訂正処理にＤＳＰを使用することがある。

【０００３】ビタビ復号は、ＡＣＳ計算と呼ばれる加
算、比較、選択という単純な処理の繰り返しと、最終的
にデータを復号するトレースバック操作で畳み込み符号
の最尤復号を実現するものである。このビタビ復号で
は、情報ビット１ビットに対応する復号化データ（受信
信号）を得るごとに、その時点での各状態のパスのメト
リックを計算し、生き残りパスを求める。

【０００４】図５は符号化率１／Ｎ、拘束長ｋの畳み込
み符号器において、ある時点における状態Ｓ［２ｉ］
（ｉ＝０〜２^k-1−１）に対し、一つ前の時点の状態Ｓ
［ｉ］と状態Ｓ［ｉ＋２^k-2］から状態遷移を表わす２
本のパスが延びている様子を示している。ここで状態Ｓ
の［］内の数が２^k-1以上となる場合は２^k-1の剰余
を取ることとする。生き残りパスを求めるとは、状態Ｓ
［２ｉ］に延びている２本のパスのそれぞれのパスメト
リックを求め、比較し、確からしい方のパスを選択する
ことである。一つ前の時点の状態Ｓ［ｉ］と状態Ｓ［ｉ
＋２^k-2］のそれぞれのパスメトリックをＰ＾［ｉ］，
Ｐ＾［ｉ＋２^k-2］とする。また一つ前の状態から現時
点の状態へ遷移するときの畳み込み符号器の本来の出力
と受信信号との距離をブランチメトリックと言い、それ
ぞれの状態から状態Ｓ［２ｉ］へ延びるパスのメトリッ
クであるブランチメトリックをａ，ｂとすると、状態Ｓ
［２ｉ］へ延びる２本のパスのパスメトリックは、Ｐ＾［ｉ］＋ａＰ＾［ｉ＋２^k-2］＋ｂと表わせる。次に２つのパスメトリックを比較し、確か
らしい方を選択する。一般的にはパスメトリックの値の
小さい方を選択することが多く、状態Ｓ［２ｉ］のパス
メトリックＰ［２ｉ］は、次のようになる。Ｐ［２ｉ］＝ｍｉｎ［（Ｐ＾［ｉ］＋ａ），（Ｐ＾［ｉ＋２^k-2］＋ｂ）］ここでｍｉｎ［Ａ，Ｂ］はＡ，Ｂのうち小さい方を選択
することを示す。このようにパスメトリックを求めるた
めの加算、パスメトリックの比較、パスの選択という処
理を各時点で２^k-1個の状態に対して行なう。

【０００５】さらにパスの選択においてどちらを選択し
たかという履歴をパスセレクト信号ＰＳ［ｊ］，（ｊ＝
０〜２^k-1−１）として残しておく必要がある。選ばれ
たパスの一つ前の状態Ｓ［］の［］内の数が他方の
状態のそれよりも小さければＰＳ［ｊ］＝０、そうでな
ければＰＳ［ｊ］＝１とする。上記の場合、ｉ＜ｉ＋２
^k-2（ｍｏｄ２^k-1）とすれば、パスセレクト信号ＰＳ
［２ｉ］は、次のようになる。

【数１】

【０００６】パスの選択前では各状態に２本のパスが延
びているので、ある時点におけるブランチメトリックは
２・２^k-1個存在するが、畳み込み符号器の出力がＮビ
ットであることを考えれば、その時点でのブランチメト
リック計算は２・２^k-1回行なう必要はなく、受信信号
と２^N通りの出力パタンとで２^N回行なっておけばよい
ことが分かる。

【０００７】図６は従来の演算装置のブロック図を示す
ものである。以下、算術論理演算回路をＡＬＵと略す。
図６において、３１はパスメトリック、パスセレクト信
号などを記憶するデータメモリ、３２はデータメモリ３
１に接続されデータの供給や演算結果の格納等を行なう
ためのバス、３３はＡＬＵ３５の右側入力の値を一時記
憶するラッチ、３４はＡＬＵ３５の左側入力の値を一時
記憶するラッチ、３５は算術論理演算を行なうＡＬＵ、
３６、３７、３８、３９、４０、４１、４２は演算結果
を一時記憶するレジスタ、４３、４４はレジスタ出力を
選択するマルチプレクサ、４５、４６、４７、４８はデ
ータメモリ３１の読み出し番地または格納番地を示すポ
インタ、４９はポインタ出力を選択するマルチプレク
サ、５０はＡＬＵ３５の出力をシフトするバレルシフタ
である。

【０００８】以上のように構成された演算装置につい
て、ある時点の２^k-1個の状態におけるＡＣＳ計算の動
作について示す。簡単のためＮ＝２，ｋ＝３として説明
する。データメモリ３１には一つ前の時点の各状態のパ
スメトリックＰ＾［ｉ］，（ｉ＝０〜３）、現時点で得
られる各状態のパスメトリックＰ［ｉ］，（ｉ＝０〜
３）およびパスセレクト信号ＰＳ［ｉ］，（ｉ＝０〜
３）を格納する領域を設けておく。図４はデータメモリ
３１の領域割当の例を示す図である。ポインタ４５、４
６、４７、４８には初期値としてそれぞれＰ＾［０］の
読み出し番地、Ｐ＾［２］の読み出し番地、Ｐ［０］の
格納番地、パスセレクト信号格納番地を設定しておく。
図３は一つ前の状態から現時点の状態へ遷移する様子を
すべての状態について示している。図３において、一つ
前の状態から現時点の状態へ遷移するときパスそれぞれ
に畳み込み符号器の本来の出力シンボルの例を記してあ
る。受信信号とそれぞれの出力シンボルの距離を計算し
たものがブランチメトリックとなるが、出力シンボルが
同じであればブランチメトリックは等しくなるので、出
力シンボル００，０１，１０，１１の２²種類について
計算しておけばよく、レジスタ３６、３７、３８、３９
にすでに計算した２²種類のブランチメトリックを格納
しておく。

【０００９】次にある時点の２²個の状態におけるＡＣ
Ｓ計算の動作概要をステップに分けて説明する。

【００１０】状態Ｓ［０］のＡＣＳ計算（１）ポインタ４５が指すデータメモリ３１の番地から
パスメトリックＰ＾［０］を読み出し、ラッチ３３に格
納する。ＡＬＵ３５はラッチ３３の内容を素通りさせレ
ジスタ４０に格納する。（２）レジスタ３６の内容をラッチ３３に格納する。レ
ジスタ４０の内容をラッチ３４に格納する。ＡＬＵ３５
はラッチ３３の内容とラッチ３４の内容を加算し、その
結果をレジスタ４０に格納する。この状態は、「Ｐ＾
［０］と出力シンボル００に対するブランチメトリック
との和が求められた。」ということになる。（３）ポインタ４６が指すデータメモリ３１の番地から
パスメトリックＰ＾［２］を読み出し、ラッチ３３に格
納する。ＡＬＵ３５はラッチ３３の内容を素通りさせレ
ジスタ４１に格納する。（４）レジスタ３９の内容をラッチ３３に格納する。レ
ジスタ４１の内容をラッチ３４に格納する。ＡＬＵ３５
はラッチ３３の内容とラッチ３４の内容を加算し、その
結果をレジスタ４１に格納する。この状態は、「Ｐ＾
［２］と出力シンボル１１に対するブランチメトリック
との和が求められた。」ということになる。（５）レジスタ４０の内容をラッチ３３に格納する。レ
ジスタ４１の内容をラッチ３４に格納する。ＡＬＵ３５
はラッチ３３の内容とラッチ３４の内容を大小比較す
る。（６）（５）においてラッチ３３の内容の方が小さいか
等しければ、（７）（８）（９）を実行する。（５）に
おいてラッチ３４の内容の方が小さければ、（７）’
（８）’（９）’を実行する。（７）ポインタ４７が指すデータメモリ３１の番地にレ
ジスタ４０の内容を格納する。（８）ポインタ４２の内容をラッチ３３に格納する。Ａ
ＬＵ３５はラッチ３３の内容を素通りさせ、バレルシフ
タ５０で左１ビットのシフトを行ない、その結果をレジ
スタ４２に格納する。（９）固定値０をラッチ３３に格納する。レジスタ４２
の内容をラッチ３４に格納する。ＡＬＵ３５はラッチ３
３の内容とラッチ３４の内容を加算し、その結果をレジ
スタ４２に格納する。（７）’ポインタ４７が指すデータメモリ３１の番地に
レジスタ４１の内容を格納する。（８）’レジスタ４２の内容をラッチ３３に格納する。
ＡＬＵ３５はラッチ３３の内容を素通りさせ、バレルシ
フタ５０で左１ビットのシフトを行ない、その結果をレ
ジスタ４２に格納する。（９）’固定値１をラッチ３３に格納する。レジスタ４
２の内容をラッチ３４に格納する。ＡＬＵ３５はラッチ
３３の内容とラッチ３４の内容を加算し、その結果をレ
ジスタ４２に格納する。この状態は、「パスメトリック
の比較、選択およびパスセレクト信号の格納を行なっ
た。」ということになる。

【００１１】状態Ｓ［１］のＡＣＳ計算（１０）ポインタ４５が指すデータメモリ３１の番地か
らパスメトリックＰ＾［０］を読み出し、ラッチ３３に
格納する。ＡＬＵ３５はラッチ３３の内容を素通りさせ
レジスタ４０に格納する。（１１）レジスタ３９の内容をラッチ３３に格納する。
レジスタ４０の内容をラッチ３４に格納する。ＡＬＵ３
５はラッチ３３の内容とラッチ３４の内容を加算し、そ
の結果をレジスタ４０に格納する。この状態は、「Ｐ＾
［０］と出力シンボル１１に対するブランチメトリック
との和が求められた。」ということになる。（１２）ポインタ４６が指すデータメモリ３１の番地か
らパスメトリックＰ＾［２］を読み出し、ラッチ３３に
格納する。ＡＬＵ３５はラッチ３３の内容を素通りさせ
レジスタ４１に格納する。（１３）レジスタ３６の内容をラッチ３３に格納する。
レジスタ４１の内容をラッチ３４に格納する。ＡＬＵ３
５はラッチ３３の内容とラッチ３４の内容を加算し、そ
の結果をレジスタ４１に格納する。この状態は、「Ｐ＾
［２］と出力シンボル００に対するブランチメトリック
との和が求められた。」ということになる。（１４）レジスタ４０の内容をラッチ３３に格納する。
レジスタ４１の内容をラッチ３４に格納する。ＡＬＵ３
５はラッチ３３の内容とラッチ３４の内容を大小比較す
る。（１５）（１４）においてラッチ３３の内容の方が小さ
いか等しければ、（１６）（１７）（１８）を実行す
る。（１４）においてラッチ３４の内容の方が小さけれ
ば、（１６）’（１７）’（１８）’を実行する。（１６）ポインタ４７をインクリメントした後、ポイン
タ４７が指すデータメモリ３１の番地にレジスタ４０の
内容を格納する。（１７）レジスタ４２の内容をラッチ３３に格納する。
ＡＬＵ３５はラッチ３３の内容を素通りさせ、バレルシ
フタ５０で左１ビットのシフトを行ない、その結果をレ
ジスタ４２に格納する。（１８）固定値０をラッチ３３に格納する。レジスタ４
２の内容をラッチ３４に格納する。ＡＬＵ３５はラッチ
３３の内容とラッチ３４の内容を加算し、その結果をレ
ジスタ４２に格納する。（１６）’ポインタ４７をインクリメントした後、ポイ
ンタ４７が指すデータメモリ３１の番地にレジスタ４１
の内容を格納する。（１７）’レジスタ４２の内容をラッチ３３に格納す
る。ＡＬＵ３５はラッチ３３の内容を素通りさせ、バレ
ルシフタ５０で左１ビットのシフトを行ない、その結果
をレジスタ４２に格納する。（１８）’固定値１をラッチ３３に格納する。レジスタ
４２の内容をラッチ３４に格納する。ＡＬＵ３５はラッ
チ３３の内容とラッチ３４の内容を加算し、その結果を
レジスタ４２に格納する。この状態は、「パスメトリッ
クの比較、選択およびパスセレクト信号の格納を行なっ
た。」ということになる。

【００１２】状態Ｓ［２］のＡＣＳ計算（１９）ポインタ４５をインクリメントした後、ポイン
タ４５が指すデータメモリ３１の番地からパスメトリッ
クＰ＾［１］を読み出し、ラッチ３３に格納する。ＡＬ
Ｕ３５はラッチ３３の内容を素通りさせレジスタ４０に
格納する。（２０）レジスタ３７の内容をラッチ３３に格納する。
レジスタ４０の内容をラッチ３４に格納する。ＡＬＵ３
５はラッチ３３の内容とラッチ３４の内容を加算し、そ
の結果をレジスタ４０に格納する。この状態は、「Ｐ＾
［１］と出力シンボル０１に対するブランチメトリック
との和が求められた。」ということになる。（２１）ポインタ４６をインクリメントした後、ポイン
タ４６が指すデータメモリ３１の番地からパスメトリッ
クＰ＾［３］を読み出し、ラッチ３３に格納する。ＡＬ
Ｕ３５はラッチ３３の内容を素通りさせレジスタ４１に
格納する。（２２）レジスタ３８の内容をラッチ３３に格納する。
レジスタ４１の内容をラッチ３４に格納する。ＡＬＵ３
５はラッチ３３の内容とラッチ３４の内容を加算し、そ
の結果をレジスタ４１に格納する。この状態は、「Ｐ＾
［３］と出力シンボル１０に対するブランチメトリック
との和が求められた。」ということになる。（２３）レジスタ４０の内容をラッチ３３に格納する。
レジスタ４１の内容をラッチ３４に格納する。ＡＬＵ３
５はラッチ３３の内容とラッチ３４の内容を大小比較す
る。（２４）（２３）においてラッチ３３の内容の方が小さ
いか等しければ、（２５）（２６）（２７）を実行す
る。（２３）においてラッチ３４の内容の方が小さけれ
ば、（２５）’（２６）’（２７）’を実行する。（２５）ポインタ４７をインクリメントした後、ポイン
タ４７が指すデータメモリ３１の番地にレジスタ４０の
内容を格納する。（２６）レジスタ４２の内容をラッチ３３に格納する。
ＡＬＵ３５はラッチ３３の内容を素通りさせ、バレルシ
フタ５０で左１ビットのシフトを行ない、その結果をレ
ジスタ４２に格納する。（２７）固定値０をラッチ３３に格納する。レジスタ４
２の内容をラッチ３４に格納する。ＡＬＵ３５はラッチ
３３の内容とラッチ３４の内容を加算し、その結果をレ
ジスタ４２に格納する。（２５）’ポインタ４７をインクリメントした後、ポイ
ンタ４７が指すデータメモリ３１の番地にレジスタ４１
の内容を格納する。（２６）’レジスタ４２の内容をラッチ３３に格納す
る。ＡＬＵ３５はラッチ３３の内容を素通りさせ、バレ
ルシフタ５０で左１ビットのシフトを行ない、その結果
をレジスタ４２に格納する。（２７）’固定値１をラッチ３３に格納する。レジスタ
４２の内容をラッチ３４に格納する。ＡＬＵ３５はラッ
チ３３の内容とラッチ３４の内容を加算し、その結果を
レジスタ４２に格納する。この状態は、「パスメトリッ
クの比較、選択およびパスセレクト信号の格納を行なっ
た。」ということになる。

【００１３】状態Ｓ［３］のＡＣＳ計算（２８）ポインタ４５が指すデータメモリ３１の番地か
らパスメトリックＰ＾［１］を読み出し、ラッチ３３に
格納する。ＡＬＵ３５はラッチ３３の内容を素通りさせ
レジスタ４０に格納する。（２９）レジスタ３８の内容をラッチ３３に格納する。
レジスタ４０の内容をラッチ３４に格納する。ＡＬＵ３
５はラッチ３３の内容とラッチ３４の内容を加算し、そ
の結果をレジスタ４０に格納する。この状態は、「Ｐ＾
［１］と出力シンボル１０に対するブランチメトリック
との和が求められた。」ということになる。（３０）ポインタ４６が指すデータメモリ３１の番地か
らパスメトリックＰ＾［３］を読み出し、ラッチ３３に
格納する。ＡＬＵ３５はラッチ３３の内容を素通りさせ
レジスタ４１に格納する。（３１）レジスタ３７の内容をラッチ３３に格納する。
レジスタ４１の内容をラッチ３４に格納する。ＡＬＵ３
５はラッチ３３の内容とラッチ３４の内容を加算し、そ
の結果をレジスタ４１に格納する。この状態は、「Ｐ＾
［３］と出力シンボル０１に対するブランチメトリック
との和が求められた。」ということになる。（３２）レジスタ４０の内容をラッチ３３に格納する。
レジスタ４１の内容をラッチ３４に格納する。ＡＬＵ３
５はラッチ３３の内容とラッチ３４の内容を大小比較す
る。（３３）（３２）においてラッチ３３の内容の方が小さ
いか等しければ、（３４）（３５）（３６）を実行す
る。（３２）においてラッチ３４の内容の方が小さけれ
ば、（３４）’（３５）’（３６）’を実行する。（３４）ポインタ４７をインクリメントした後、ポイン
タ４７が指すデータメモリ３１の番地にレジスタ４０の
内容を格納する。（３５）レジスタ４２の内容をラッチ３３に格納する。
ＡＬＵ３５はラッチ３３の内容を素通りさせ、バレルシ
フタ５０で左１ビットのシフトを行ない、その結果をレ
ジスタ４２に格納する。（３６）固定値０をラッチ３３に格納する。レジスタ４
２の内容をラッチ３４に格納する。ＡＬＵ３５はラッチ
３３の内容とラッチ３４の内容を加算し、その結果をレ
ジスタ４２に格納する。（３４）’ポインタ４７をインクリメントした後、ポイ
ンタ４７が指すデータメモリ３１の番地にレジスタ４１
の内容を格納する。（３５）’レジスタ４２の内容をラッチ３３に格納す
る。ＡＬＵ３５はラッチ３３の内容を素通りさせ、バレ
ルシフタ５０で左１ビットのシフトを行ない、その結果
をレジスタ４２に格納する。（３６）’固定値１をラッチ３３に格納する。レジスタ
４２の内容をラッチ３４に格納する。ＡＬＵ３５はラッ
チ３３の内容とラッチ３４の内容を加算し、その結果を
レジスタ４２に格納する。この状態は、「パスメトリッ
クの比較、選択およびパスセレクト信号の格納を行なっ
た。」ということになる。（３７）ポインタ４８が指すデータメモリ３１の番地に
レジスタ４２の内容を格納する。この状態は、「１つの
時点の各状態のパスセレクト信号を１ワードに詰めて格
納した。」ということになる。

【００１４】このように、上記従来の演算装置では、Ｎ
＝２、ｋ＝３の場合にある時点の２ ²個の状態における
ＡＣＳ計算を行なうのに、３７ステップ程度で行なうこ
とができる。また、一般にＮ＝Ｎ、ｋ＝ｋの場合にある
時点の２^k-1個の状態におけるＡＣＳ計算を行なうの
に、（９＊２^k-1＋１）ステップ程度で行なうことがで
きる。ただしＮが大きかったり、レジスタの本数の制限
等があるときは、多少のステップ増加を見込む必要があ
る。

【００１５】

【発明が解決しようとする課題】しかしながら、上記従
来の演算装置では、移動通信分野などでは１フレーム数
百ビットに対して畳み込み符号化されている場合が多
く、また移動通信においては回線のビット誤りが劣悪な
ため、畳み込み符号の拘束長ｋは５以上のものが使用さ
れることが多いので、各時点で各状態について行なうＡ
ＣＳ計算の演算量が多くなるという問題があった。

【００１６】本発明は、このような従来の問題を解決す
るものであり、ＡＣＳ計算を行なう演算ステップ数を大
幅に軽減することができる優れた演算装置を提供するこ
とを目的とするものである。

【００１７】

【課題を解決するための手段】本発明は、上記目的を達
成するために、同一のポインタで番地指定ができ、同時
に読み書き可能な第１および第２のデータメモリと、算
術論理演算回路と、算術論理演算回路と並行して加算を
行なう加算器と、算術論理演算回路と加算器を同時に実
行するときに対で使用する複数のレジスタと、算術論理
演算回路出力と加算器出力の大小比較を行なう大小比較
器と、大小比較器の比較結果を格納するシフトレジスタ
と、算術論理演算回路および加算器の演算結果を一時記
憶するとともに大小比較器の比較結果により選択される
第１および第２のレジスタとを備え、第１および第２の
データメモリから同一のポインタで指す番地の内容をそ
れぞれ読み出して算術論理演算回路および加算器の一方
の入力とし、対となる複数のレジスタの内容をそれぞれ
算術演算回路および加算器の他方の入力とし、算術演算
回路および加算器で同時に加算を行ない、それぞれの演
算結果をそれぞれ第１および第２のレジスタに格納する
とともに大小比較器にも入力し、その比較結果をシフト
レジスタに格納することを特徴とする。

【００１８】

【作用】したがって、本発明によれば、ＡＬＵおよび加
算器で同時に加算が行なえ、それぞれの演算結果を大小
比較することができるので、１ステップでＡＣＳ計算の
加算、比較を行なうことができ、データメモリのサイズ
の増加なしに演算ステップ数を減らすことができるとい
う効果を有する。

【００１９】

【実施例】図１は本発明の一実施例における演算装置の
構成を示すブロック図である。図１において、１、２は
パスメトリック、パスセレクト信号などを記憶する第１
および第２のデータメモリ、３、４はそれぞれデータメ
モリ１、２に接続されデータの供給や演算結果の格納等
を行なうためのバス、５はバス４からの入力と後述する
レジスタからの入力とを選択するマルチプレクサ、６は
ＡＬＵ１０の右側入力の値を一時記憶するラッチ、７は
ＡＬＵ１０の左側入力の値を一時記憶するラッチ、８は
加算器１１の右側入力の値を一時記憶するラッチ、９は
加算器１１の左側入力の値を一時記憶するラッチ、１０
はラッチ６および７の内容について算術論理演算を行な
うＡＬＵ、１１はラッチ８および９の内容を加算する加
算器、１２、１３、１４、１５はＡＬＵ１０および加算
器１１の演算結果を一時記憶する対となる複数のレジス
タ、１６、１７はレジスタ１２〜１５の出力を選択する
マルチプレクサ、１８はＡＬＵ１０の演算結果を一時記
憶する第１のレジスタ、１９は加算器１１の演算結果を
一時記憶する第２のレジスタ、２０はレジスタ１８、１
９の出力を選択するマルチプレクサ、２１はＡＬＵ１０
の出力と加算器１１の出力を大小比較を行ない、ＡＬＵ
１０の出力が小さいかまたは等しいとき比較結果０を出
力し、加算器１１の出力が小さいとき比較結果１を出力
する大小比較器、２２は大小比較器２１の比較結果であ
るパスセレクト信号、２３はパスセレクト信号２２をシ
フト入力とするシフトレジスタ、２４、２５、２６はデ
ータメモリ１、２の読み出し番地または格納番地を示す
ポインタ、２７はポインタ出力を選択するマルチプレク
サ、２８はパスセレクト信号２２を１ステップ遅延させ
る遅延器である。

【００２０】以上のように構成された演算装置につい
て、ある時点の２^k-1個の状態におけるＡＣＳ計算の動
作について説明する。簡単のためＮ＝２，ｋ＝３とす
る。データメモリ１、２には、一つ前の時点の各状態の
パスメトリックＰ＾［ｉ］，（ｉ＝０〜３）、現時点で
得られる各状態のパスメトリックＰ［ｉ］，（ｉ＝０〜
３）およびパスセレクト信号ＰＳ［ｉ］，（ｉ＝０〜
３）を格納する領域を設けておく。図２はデータメモリ
１、２の領域割当の例を示す図である。ポインタ２４、
２５、２６には初期値としてそれぞれ（Ｐ＾［０］，Ｐ
＾［２］）の読み出し番地、（Ｐ［０］，Ｐ［２］）の
格納番地、パスセレクト信号格納番地を設定しておく。
図３は一つ前の状態から現時点の状態へ遷移する様子を
すべての状態について示している。図３において、一つ
前の状態から現時点の状態へ遷移するときパスそれぞれ
に畳み込み符号器の本来の出力シンボルの例を記してあ
る。受信信号とそれぞれの出力シンボルの距離を計算し
たものがブランチメトリックとなるが、出力シンボルが
同じであればブランチメトリックは等しくなるので、出
力シンボル００，０１，１０，１１の２²種類について
計算しておけばよく、レジスタ１２、１３、１４、１５
にすでに計算した２²種類のブランチメトリックを格納
しておく。

【００２１】以下、ある時点の２²個の状態におけるＡ
ＣＳ計算の動作概要をステップに分けて説明する。

【００２２】状態Ｓ［０］のＡＣＳ計算（１）ポインタ２４が指すデータメモリ１、２の番地か
らパスメトリックＰ＾［０］，Ｐ＾［２］を読み出し、
それぞれラッチ６、ラッチ９に格納する。レジスタ１２
の内容をラッチ７に、これと対になるレジスタ１５の内
容をラッチ８に格納する。ＡＬＵ１０は、ラッチ６の内
容とラッチ７の内容を加算し、その結果をレジスタ１８
に格納するとともに大小比較器２１の片方の入力とす
る。一方加算器１１は、ラッチ８の内容とラッチ９の内
容を加算し、その結果をレジスタ１９に格納するととも
に大小比較器２１の他方の入力とする。大小比較器２１
は、ＡＬＵ１０の出力と加算器１１の出力との大小比較
を行ない、パスセレクト信号２２を発生する。パスセレ
クト信号２２は、シフトレジスタ２３および遅延器２８
にラッチされる。この状態は、「Ｐ＾［０］と出力シン
ボル００に対するブランチメトリックとの和が求めら
れ、Ｐ＾［２］と出力シンボル１１に対するブランチメ
トリックとの和が求められ、パスメトリックの比較、選
択およびパスセレクト信号の格納を行なった。」という
ことになる。（２）ポインタ２５が指すデータメモリ１の番地に遅延
器２８の出力で選択されたレジスタ１８またはレジスタ
１９の内容を格納する。

【００２３】状態Ｓ［１］のＡＣＳ計算（３）レジスタ１５の内容をラッチ７に、これと対にな
るレジスタ１２の内容をラッチ８に格納する。ＡＬＵ１
０は、ステップ（１）でラッチ６にすでに格納されてい
る内容とラッチ７の内容を加算し、その結果をレジスタ
１８に格納するとともに大小比較器２１の片方の入力と
する。一方加算器１１は、ステップ（１）でラッチ９に
すでに格納されている内容とラッチ８の内容を加算し、
その結果をレジスタ１９に格納するとともに大小比較器
２１の他方の入力とする。大小比較器２１は、ＡＬＵ１
０の出力と加算器１１の出力との大小比較を行ない、パ
スセレクト信号２２を発生する。パスセレクト信号２２
は、シフトレジスタ２３および遅延器２８にラッチされ
る。この状態は、「Ｐ＾［０］と出力シンボル１１に対
するブランチメトリックとの和が求められ、Ｐ＾［２］
と出力シンボル００に対するブランチメトリックとの和
が求められ、パスメトリックの比較、選択およびパスセ
レクト信号の格納を行なった。」ということになる。（４）ポインタ２５をインクリメントした後、ポインタ
２５が指すデータメモリ１の番地に遅延器２８の出力で
選択されたレジスタ１８またはレジスタ１９の内容を格
納する。（５）ポインタ２５の内容を（Ｐ［０］，Ｐ［２］）の
格納番地に戻す。

【００２４】状態Ｓ［２］のＡＣＳ計算（６）ポインタ２４をインクリメントした後、ポインタ
２４が指すデータメモリ１、２の番地からパスメトリッ
クＰ＾［１］，Ｐ＾［３］を読み出し、それぞれラッチ
６、ラッチ９に格納する。レジスタ１３の内容をラッチ
７に、これと対になるレジスタ１４の内容をラッチ８に
格納する。ＡＬＵ１０は、ラッチ６の内容とラッチ７の
内容を加算し、その結果をレジスタ１８に格納するとと
もに大小比較器２１の片方の入力とする。一方加算器１
１は、ラッチ８の内容とラッチ９の内容を加算し、その
結果をレジスタ１９に格納するとともに大小比較器２１
の他方の入力とする。大小比較器２１は、ＡＬＵ１０の
出力と加算器１１の出力との大小比較を行ない、パスセ
レクト信号２２を発生する。パスセレクト信号２２は、
シフトレジスタ２３および遅延器２８にラッチされる。
この状態は、「Ｐ＾［１］と出力シンボル０１に対する
ブランチメトリックとの和が求められ、Ｐ＾［３］と出
力シンボル０１に対するブランチメトリックとの和が求
められ、パスメトリックの比較、選択およびパスセレク
ト信号の格納を行なった。」ということになる。（７）ポインタ２５が指すデータメモリ２の番地に遅延
器２８の出力で選択されたレジスタ１８またはレジスタ
１９の内容を格納する。

【００２５】状態Ｓ［３］のＡＣＳ計算（８）レジスタ１４の内容をラッチ７に、これと対にな
るレジスタ１３の内容をラッチ８に格納する。ＡＬＵ１
０は、ステップ（６）でラッチ６にすでに格納されてい
る内容とラッチ７の内容を加算し、その結果をレジスタ
１８に格納するとともに大小比較器２１の片方の入力と
する。一方加算器１１は、ステップ（６）でラッチ８に
すでに格納されている内容とラッチ９の内容を加算し、
その結果をレジスタ１９に格納するとともに大小比較器
２１の他方の入力とする。大小比較器２１は、ＡＬＵ１
０の出力と加算器１１の出力との大小比較を行ない、パ
スセレクト信号２２を発生する。パスセレクト信号２２
は、シフトレジスタ２３および遅延器２８にラッチされ
る。この状態は、「Ｐ＾［１］と出力シンボル１０に対
するブランチメトリックとの和が求められ、Ｐ＾［３］
と出力シンボル０１に対するブランチメトリックとの和
が求められ、パスメトリックの比較、選択およびパスセ
レクト信号の格納を行なった。」ということになる。（９）ポインタ２５をインクリメントした後、ポインタ
２５が指すデータメモリ２の番地に遅延器２８の出力で
選択されたレジスタ１８またはレジスタ１９の内容を格
納する。（１０）ポインタ２６が指すデータメモリ１の番地に、
シフトレジスタ２３の内容を格納する。この状態は、
「１つの時点の各状態のパスセレクト信号を１ワードに
詰めて格納した。」ということになる。

【００２６】このように、上記実施例の演算装置では、
Ｎ＝２、ｋ＝３の場合にある時点の２²個の状態におけ
るＡＣＳ計算を行なうのに、従来の３７ステップ程度に
対し１０ステップ程度で行なうことができる。また、一
般にＮ＝Ｎ、ｋ＝ｋの場合にある時点の２^k-1個の状態
におけるＡＣＳ計算を行なうのに、従来の（９＊２^k- ¹
＋１）ステップ程度に対し（２＊２^k-1＋１）ステップ
程度で行なうことができる。ただしＮが大きかったり、
レジスタの本数の制限等があるときは、多少のステップ
増加を見込む必要がある。

【００２７】

【発明の効果】本発明は、上記実施例から明らかなよう
に、ＡＬＵおよび加算器で同時に加算を行ない、それぞ
れの演算結果を大小比較するので、１ステップでＡＣＳ
計算の加算、比較を行なうことができ、データメモリを
２つに分割するもののサイズの合計では増加はなく、Ａ
ＣＳ計算の演算ステップ数を大幅に減らすことができる
という利点を有する。

【図面の簡単な説明】

【図１】本発明の一実施例における演算装置の構成を示
すブロック図

【図２】演算装置の動作説明のためのデータメモリの領
域割当例を示す模式図

【図３】演算装置の動作説明のための一つ前の状態から
現時点の状態へ遷移する様子をすべての状態について示
した状態遷移図

【図４】演算装置の動作説明のためのデータメモリの領
域割当例を示す模式図

【図５】演算装置の動作説明のためのビタビ復合におけ
る畳み込み符号器の状態遷移のパスの様子を示す状態遷
移図

【図６】従来の演算装置の概略構成を示すブロック図

【符号の説明】

１第１のデータメモリ２第２のデータメモリ３バス４バス５マルチプレクサ６ラッチ７ラッチ８ラッチ９ラッチ１０ＡＬＵ（算術論理演算回路）１１加算器１２レジスタ１３レジスタ１４レジスタ１５レジスタ１６マルチプレクサ１７マルチプレクサ１８第１のレジスタ１９第２のレジスタ２０マルチプレクサ２１大小比較器２２パスセレクト信号２３シフトレジスタ２４ポインタ２５ポインタ２６ポインタ２７マルチプレクサ２８遅延器

───────────────────────────────────────────────────── フロントページの続き (72)発明者岡本稔大阪府門真市大字門真1006番地松下電器産業株式会社内

Claims

【特許請求の範囲】

【請求項１】同一のポインタで番地指定ができ、同時
に読み書き可能な第１および第２のデータメモリと、算
術論理演算回路と、算術論理演算回路と並行して加算を
行なう加算器と、算術論理演算回路と加算器を同時に実
行するときに対で使用する複数のレジスタと、算術論理
演算回路出力と加算器出力の大小比較を行なう大小比較
器と、大小比較器の比較結果を格納するシフトレジスタ
と、算術論理演算回路および加算器の演算結果を一時記
憶するとともに大小比較器の比較結果により選択される
第１および第２のレジスタとを備え、第１および第２の
データメモリから同一のポインタで指す番地の内容をそ
れぞれ読み出して算術論理演算回路および加算器の一方
の入力とし、対となる複数のレジスタの内容をそれぞれ
算術演算回路および加算器の他方の入力とし、算術演算
回路および加算器で同時に加算を行ない、それぞれの演
算結果をそれぞれ第１および第２のレジスタに格納する
とともに大小比較器にも入力し、その比較結果をシフト
レジスタに格納することを特徴とする演算装置。