JPH06204894A

JPH06204894A - 多数決回路及びビタビ復号器

Info

Publication number: JPH06204894A
Application number: JP34951792A
Authority: JP
Inventors: Hiroyuki Yoshida; 洋之吉田
Original assignee: Sony Corp
Current assignee: Sony Corp
Priority date: 1992-12-28
Filing date: 1992-12-28
Publication date: 1994-07-22

Abstract

(57)【要約】【構成】冗長２進表現を用いた加算処理を行うために
木構造状に配された複数の加算器１，２，３，４を相互
に接続し、これら加算器によって複数の入力符号を順次
加算することで多数決を行う。【効果】構成の大型化を防止し、高速動作を可能とす
る。ビタビ復号器に適用することで、誤りを少なくでき
る。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、畳み込み符号の最尤復
号法に使用されるいわゆるビタビ復号器に関し、特にパ
スメモリ出力の最尤判定（多数決）を行う多数決回路に
関するものである。

【０００２】

【従来の技術】ビタビ(Viterbi) 復号器は、畳み込み符
号の最尤復号法に使用されるものであり、既知の複数個
の符号系列のうち、入力符号系列に最も符号距離が近い
パスを最尤パスとして選択し、この選択されたパスに対
応して復号データを得るものであり、誤り訂正能力が高
いことから例えば衛星通信等の復号器として使用されて
いる。

【０００３】ここで、従来のビタビ復号器は、例えば図
９に示すように、符号分配器としてのブランチメトリッ
ク計算部１０１と、複数のＡＣＳ（Add Compare Selec
t) 回路からなるステートメトリック計算部１０２と、
パスメモリ回路１０３と、上記パスメモリ回路１０３の
出力に基づいて多数決を行って復号信号を得る多数決
（最尤判定、ＭＬＤ:Maximum Likelihood Decision) 回
路１０４とで構成されるものである。

【０００４】すなわち、この図９において、上記符号分
配器としてのブランチメトリック計算部１０１には、入
力端子１００_Iと１００_Qを介した直交変調の復号信号
Ｉ，Ｑが入力符号として供給されている。当該ブランチ
メトリック計算部１０１では、これら入力符号から各ノ
ード毎の４種類のブランチメトリック（ハミング距離）
ＢＭ00〜ＢＭ11を計算し、求めたブランチメトリックＢ
Ｍ00〜ＢＭ11を後段のステートメトリック計算部１０２
の各ＡＣＳ回路に送る。

【０００５】ステートメトリック計算部１０２では、拘
束長Ｋとすると、２^K-1状態分のステートメトリックが
計算されると共に、２^K-1本のパス選択信号が出力され
る。すなわち、ステートメトリック計算部１０２は例え
ば拘束長Ｋ＝４とすると７個のＡＣＳ回路により構成さ
れるものであり、各ＡＣＳ回路は、入力されたブランチ
メトリックＢＭ00〜ＢＭ11に１シンボル前のパスメトリ
ックを加算して２つのパスに対応する新たなパスメトリ
ックを計算し、これらのパスメトリック値を比較器で比
較して、パスメトリックの小さい方を生き残りパスとし
て選択し、その選択したパスを示すパス選択信号（後段
のパスメモリでのパス選択信号）ＳＥＬを出力すると共
に、上記選択したパスメトリック（ステートメトリック
ＳＭ）を他のＡＣＳ回路に送る。

【０００６】なお、上記ステートメトリック計算部の各
々のＡＣＳ回路は、図示は省略するが具体的には、例え
ば２つの加算器(Adder) と、１つの比較器(Comparator)
と、１つのセレクタ(Selector)とを主要構成要素とする
ものである。すなわち、各ＡＣＳ回路では、供給された
２つ１組のブランチメトリックＢＭと、他のＡＣＳ回路
からの上記選択された２つ１組のパスメトリック（ステ
ートメトリックＳＭ）とが、それぞれ対応する何れか一
方の加算器にて加算され、これら２つの加算器からの出
力（２つのパスに対応する新たなパスメトリック）が上
記比較器に送られる。当該比較器では上記生き残りパス
が選択され、そのパスがパス選択信号（バス選択信号）
ＳＥＬとして出力される。また、上記２つの加算器から
のパスメトリックは上記セレクタにも送られ、当該セレ
クタでは上記比較器からのパス選択信号ＳＥＬに基づい
て上記２つのパスメトリックを選択する。

【０００７】上記ステートメトリック計算部１０２から
のパス選択信号（各ＡＣＳ回路からのパス選択信号）Ｓ
ＥＬは、パスメモリ回路１０３に送られる。当該パスメ
モリ回路１０３は、上記ステートメトリック計算部１０
２からのパス選択信号ＳＥＬが加えられて、生き残りパ
スの経歴が記憶されるものである。具体的構成の図示は
省略するが、当該パスメモリ回路１０３は、複数段構成
の複数のパスメモリセルからなるものであり、上記各Ａ
ＣＳ回路からのパス選択信号ＳＥＬが、当該パスメモリ
回路１０３の対応する各パスメモリセルに送られる。こ
こで、各段のパスメモリセルでは、入力データ（初段の
パスメモリセルには初期値）が、クロックＣＬＫと上記
パス選択信号ＳＥＬに基づいて順次内部状態を遷移させ
るようにシフトされる。すなわち、復号サイクル毎にＡ
ＣＳ回路で生き残りパスと判定した側のパスメモリセル
の内容をパス選択信号を用いて後段のパスメモリセルに
転送する。なお、拘束長Ｋの場合には、パスメモリセル
が、状態数２^K-1×拘束長（Ｋ×５）個程度組み合わさ
れてパスメモリ回路全体が構成される。

【０００８】これらパスメモリセルからの出力が、上記
多数決回路（最尤判定回路）１０４に送られる。当該多
数決回路１０４で判定された上記ステートメトリックＳ
Ｍが最小となる経歴のパスメモリ回路１０３の内容が
“０”又は“１”の復号信号として出力端子１０５から
出力される。

【０００９】なお、従来のビタビ復号器については、特
開昭６１−１２８６３２号公報や、特開昭６１−６０１
２７号公報等に記載されているものを挙げることができ
る。

【００１０】

【発明が解決しようとする課題】ところで、例えば上述
したビタビ復号器に使用されるような一般的な多数決回
路は、具体的には、図１０に示すように構成されるもの
である。なお、この図１０には、６４ビットの多数決回
路を示す。この図１０に示す従来の６４ビットの多数決
回路は、３２個の１ビット全加算器４０２と、１６個の
２ビット全加算器４０３と、８個の３ビット全加算器４
０５と、４個の４ビット全加算器４０６と、２個の５ビ
ット全加算器４０７と、１個の６ビット全加算器４０８
とで構成されるものである。

【００１１】すなわち、この図１０において、６４ビッ
ト分の入力符号Ｍ０〜Ｍ６３が各入力端子に供給され
る。これら６４ビット入力符号Ｍ０〜Ｍ６３は、例えば
Ｍ０とＭ１、Ｍ２とＭ３、・・・のように、２ビットず
つそれぞれ１ビット全加算器４０２に送られ、各加算器
４０２で加算される。各１ビット加算器４０２の加算結
果は２ビットであり、２つの１ビット加算器４０２の出
力がそれぞれ次段の２ビット全加算器４０３に送られて
加算される。以下同様に、２ビット全加算器４０３から
の３ビット出力は２つ１組でそれぞれ３ビット全加算器
４０５に送られ、当該３ビット全加算器４０５の４ビッ
ト出力は２つ１組でそれぞれ４ビット全加算器４０６に
送られ、当該４ビット全加算器４０６の５ビット出力は
２つ１組でそれぞれ５ビット全加算器４０７に送られ、
当該５ビット全加算器４０７の６ビット出力は２つ１組
でそれぞれ６ビット全加算器４０８に送られる。当該６
ビット全加算器４０８の出力が多数決演算結果として出
力端子４０９から出力される。

【００１２】この図１０に示したような従来の多数決回
路においては、図示は省略しているが各段の全加算器
（各ｎビットの全加算器）内では下位ビットからの桁上
がり信号（キャリアウト）の伝搬があるため、演算に長
時間が必要となり、したがって、全体として高速動作が
困難となっている。

【００１３】また、例えば図１０に示したように、３２
個の１ビット全加算器４０２と、１６個の２ビット全加
算器４０３と、８個の３ビット全加算器４０５と、４個
の４ビット全加算器４０６と、２個の５ビット全加算器
４０７と、１個の６ビット全加算器４０８とで構成され
るものであるため、非常に回路規模が大きくなると言う
問題点がある。

【００１４】さらに、上述したような従来の多数決回路
を例えば拘束長Ｋのビタビ復号器に適用した場合、当該
ビタビ復号器では２^K-1ビット分のパスメモリ出力を多
数決判定（最尤判定）して“０”か“１”の復号出力と
することになる。この場合、例えば拘束長Ｋ＝７になる
と、上記図１０のように６４ビット分の多数決が必要と
なり、上述したように構成の大型化と動作の長時間化の
問題がある。このようなことから、通常は、６４ビット
の内の任意の８ビット程度だけを多数決することが多
い。しかし、この場合、伝送路のＳ／Ｎが低い時には、
誤りが多くなり、したがって全ビットの多数決が必要と
なってしまう。

【００１５】そこで、本発明は、上述のような実情に鑑
みて提案されたものであり、構成の大型化を防止すると
共に、高速動作を可能とし、さらに全ビットの多数決を
行うことができる多数決回路と、この多数決回路（最尤
判定回路）を有する誤りの少ないビタビ復号器を提供す
ることを目的とするものである。

【００１６】

【課題を解決するための手段】本発明の多数決回路は、
上述の目的を達成するために提案されたものであり、い
わゆる冗長２進表現（冗長数値表現，Wallace Tree) を
用いた加算処理を行うために木構造状に配された複数の
加算器からなり、これら加算器による加算処理によっ
て、複数の入力符号の多数決を行うものである。

【００１７】なお、この多数決回路においては、加算処
理中に加算結果が所定ビット数となる位置に多ビット全
加算器を設けるような構成としている。

【００１８】また、本発明のビタビ復号器は、入力符号
に基づいてブランチメトリックを計算するブランチメト
リック計算部と、ブランチメトリックに基づいてパス選
択信号を出力する複数のＡＣＳ回路からなるステートメ
トリック計算部と、上記パス選択信号が供給される複数
のパスメモリセルからなるパスメモリ回路と、上記パス
メモリ回路の出力に対して冗長２進数表現を用いた加算
処理を行って多数決を行う多数決回路とを有するもので
ある。

【００１９】すなわち、本発明のビタビ復号器は、拘束
長Ｋのパスメモリ出力２^K-1個の多数決を行う多数決回
路として、冗長２進法（冗長数値表現）を用いた半加算
器及び全加算器の組み合わせにより構成される２^K-1ビ
ットの多数決回路を有するものである。

【００２０】

【作用】本発明の多数決回路によれば、冗長２進表現を
用いた加算処理を行う構成とすることで、各段を構成す
る加算器間で桁上げ信号の伝搬なしの加算を行うことが
でき、高速演算が可能となる。

【００２１】

【実施例】以下、本発明の実施例を図面を参照しながら
説明する。

【００２２】本発明実施例の多数決回路は、いわゆる冗
長２進表現（冗長数値表現）を用いた加算処理を行い、
複数の入力符号の多数決を行うようものである。すなわ
ち、本実施例における多数決は、例えば図１に示すよう
な工程で実現される。

【００２３】この図１においては、本実施例の多数決の
原理を説明するため、例えば、入力符号ａ１，ａ０の２
ビットと、入力符号ｂ１，ｂ０の２ビットと、入力符号
ｃ１，ｃ０の２ビットの加算を例に挙げて説明する。な
お、図中○，△，□は、加算演算における加算器の入力
ペアと出力ペアに対応している。

【００２４】先ず、第１の工程として、ａ１，ａ０とｂ
１，ｂ０とｃ１，ｃ０をそれぞれ例えば△，○とし、各
桁毎のビットを加算する。すなわち、最上位ビット（Ｍ
ＳＢ）のａ１，ｂ１，ｃ１を△と表し、最下位ビット
（ＬＳＢ）のａ０，ｂ０，ｃ０を○で表した場合、この
△で示される各桁のビット同士と○で示される各桁のビ
ット同士の加算を行う。

【００２５】次に、第２の工程として、上記第１の工程
による最上位ビットの加算結果の２ビットを△△と表
し、上記最下位ビットの加算結果を○○と表した場合、
当該△△を上位側２ビットに、当該○○を下位側２ビッ
トに並べ、中間ビットの○と△のみを加算する。また、
この第２の工程では、上記△△のうちの上位側ビット
と、上記○○のうちの下位側ビットを共に×で表し、こ
れらについてはそのままそのまま第３の工程に移行させ
る。

【００２６】第３の工程では、上記第２の工程における
上記中間ビットの○と△の加算結果を○○と表し、次に
上記第２の工程における最上位側の×のビットを○で表
した場合、この第２の工程における最上位側の×のビッ
トを表す○のビットと、上記第２の工程における加算結
果の○○のうちの上位側のビットとを加算する。また、
この第３の工程では、上記第２の工程における加算結果
の○○のうちの下位側のビットを×で表し、上記第２の
工程における下位側ビットの×と共に、そのまま第４の
工程に移行させる。

【００２７】最後の第４の工程では、上記第３の工程に
おける加算結果を表す○○を上位側のＤ３，Ｄ２ビット
とし、下位側の××のビットをＤ１，Ｄ０とし、これに
より、Ｄ３，Ｄ２，Ｄ１，Ｄ０の結果（○○××）を得
る。

【００２８】上記図１の工程を具体的回路構成で示す
と、図２に示すようになる。

【００２９】この図２において、全加算器１には上記図
１のａ１，ｂ１，ｃ１のビットが供給され、全加算器２
には上記図１のａ０，ｂ０，ｃ０のビットが供給され
る。すなわち、この全加算器１及び２は、上記図１で説
明した第１の工程の加算を行う。

【００３０】次に、半加算器３の２つの入力端子には、
上記全加算器１の加算信号と上記全加算器２のキャリア
ウト信号（桁上げ信号）が供給される。これにより、当
該半加算器３では、上記図１で説明した第２の工程での
加算が行われる。

【００３１】上記半加算器３のキャリアウト信号は一方
の入力端子に上記全加算器１のキャリアウト信号が供給
される半加算器４の他方の入力端子に供給される。した
がって、当該半加算器４では上記図２で説明した第３の
工程の加算が行われる。

【００３２】最後に、上記全加算器２の加算信号は上記
図１におけるＤ０のビットとして出力され、上記半加算
器３の加算信号は上記図１におけるＤ１のビットとして
出力され、上記半加算器４の加算信号は上記図１におけ
るＤ２のビットとして出力され、また当該半加算器４の
キャリアウト信号は上記図１におけるＤ３のビットとし
て出力される。すなわち、このＤ３，Ｄ２，Ｄ１，Ｄ０
のビットが、上記図１で説明した第４の工程の出力とな
る。

【００３３】ところで、上述の図１で説明したような冗
長２進表現を用いた加算処理の原理を、例えば６４ビッ
ト多数決判定に適用する場合の各工程は、図３〜図５に
示すようなものとなる。なお、この図３〜図５は一連の
連続する工程であるが、図示の都合により分割して表し
ている。

【００３４】先ず、６４ビット多数決判定における第１
の工程では、図３に示すように、６４ビットの入力符号
の第０ビット〜第６３ビットの各ビットの３つを１組と
してそれぞれを○○○，△△△，□□□で順に表すとす
る。ただし、第６０ビット及び第６１ビットは２つで□
□とし、第６２ビット及び第６３ビットは☆☆で表すと
する。また、この第１の工程では、上記○○○，△△
△，□□□及び□□，☆☆毎に加算を行う。

【００３５】次に、第２の工程では、上記第１の工程に
おける上記○○○の各ビットの加算により得られた加算
結果を更に○○で表し、△△△の各ビットの加算により
得られた加算結果をさらに△△で表し、□□□（及び□
□）の各ビットの加算により得られた加算結果をさらに
□□で表し、☆☆の各ビットはそのまま第３の工程に移
行する。また、この第２の工程では、入力符号の第０ビ
ット〜第８ビットの加算で得られた加算結果の上位側桁
の○△□を△△△で表し、下位側桁の○△□を○○○で
表す。以下同様に、入力符号の第９ビット〜第１７ビッ
トの加算で得られた加算結果の上位側桁の○△□を□□
□で表し下位側桁の○△□を☆☆☆で表し、入力符号の
第１８ビット〜第２６ビットの加算で得られた加算結果
の上位側桁の○△□を●●●で表し下位側桁の○△□を
◎◎◎で表し、入力符号の第２７ビット〜第３５ビット
の加算で得られた加算結果の上位側桁の○△□を△△△
で表し下位側桁の○△□を○○○で表し、入力符号の第
３６ビット〜第４４ビットの加算で得られた加算結果の
上位側桁の○△□を□□□で表し下位側桁の○△□を☆
☆☆で表し、入力符号の第４５ビット〜第５３ビットの
加算で得られた加算結果の上位側桁の○△□を●●●で
表し下位側桁の○△□を◎◎◎で表し、入力符号の第５
４ビット〜第６３ビットの加算で得られた加算結果の上
位側桁の○△□☆を△△△☆で表し下位側桁の○△□☆
を○○○☆で表す。この第２の工程では、これら△△
△、○○○、□□□、☆☆☆、●●●、◎◎◎、△△△
☆、○○○☆の加算を行う。

【００３６】第３の工程では、上記第２の工程における
入力符号の第０ビット〜第８ビット及び第２７ビット〜
第３５ビットに対応する○○○で示した桁の各ビットの
加算結果を○○と表し、△△△で示した桁の各ビットの
加算結果を△△と表す。以下同様に、入力符号の第９ビ
ット〜第１７ビット及び第３６ビット〜第４４ビットに
対応する☆☆☆の加算結果を☆☆と表し□□□の加算結
果を□□と表し、入力符号の第１８ビット〜第２６ビッ
ト及び第４５ビット〜第５３ビットに対応する●●●の
加算結果を●●と表し◎◎◎の加算結果を◎◎と表し、
入力符号の第５４ビット〜第６３ビットに対応する○○
○☆のうちの○○○の加算結果を○○と表し△△△☆の
うちの△△△の加算結果を△△と表し☆☆はそのまま表
す。また、この第３の工程では、上記第２の工程に上位
側桁の加算結果を上位側２ビット分に並べ、上記第２の
工程の下位側桁の加算結果を下位側２ビット分に並べる
と共に、入力符号の第０ビット〜第５３ビットに対応す
る最下位側桁の○☆●を○○○と表し、２ｔｈ桁の○△
☆□●◎を△☆△☆△☆と表し、最上位側桁の△☆◎を
□□□と表す。さらに、入力符号の第５４ビット〜第６
３ビットに対応する最下位側桁の○☆を○○に、２ｔｈ
桁の○△☆を△△△に、最上位側桁の△を☆に変換して
表す。この第３の工程では、上述同様にこれらの加算を
行う。

【００３７】以下、上述の工程に準じて、図３及び図４
に示す第４の工程では、第３の工程における○○○及び
○○の加算結果を○○と表し、第３の工程での△△△の
加算結果を△△と表し、第３の工程での☆☆☆の加算結
果を☆☆と表し、第３の工程での□□□の加算結果を□
□と表し、☆は☆で表してそれぞれ図３に示すように並
べる。次に、図４に示すように、これら並べた各桁のう
ち下位側桁から順に○○○の桁を○○○で、○△☆○△
☆○△の桁を△□☆△□☆△□で、△☆□△☆□△☆の
桁を●◎★●◎★●◎で、□□の桁を▲で表して、それ
ぞれの加算を行う。

【００３８】第５の工程では、第４の工程における○同
士の加算結果を○○で、△同士の加算結果を△△で、□
同士の加算結果を□□で、☆同士の加算結果を☆☆で、
●同士の加算結果を●●で、◎同士の加算結果を◎◎
で、★同士の加算結果を★で、▲同士の加算結果を▲▲
で表してこれらを図４のように並べる。また、これら並
べた各桁のうち下位側桁から順に、○の桁を×で、○△
□☆の桁を○○○×で、△□☆●◎★の桁を△△△□□
□で、●◎★▲の桁を☆☆☆×で、▲の桁を×で表し、
それぞれ加算する。なお、×のビットはそのまま次の第
６の工程に移行させる。

【００３９】図４及び図５に示す第６の工程では、第５
の工程における○同士の加算結果を○○で、△同士の加
算結果を△△で、□同士の加算結果を□□で、☆同士の
加算結果を☆☆で表して並べる。また、これら並べた各
桁のうち下位側桁から順に、×の桁は×で、○×の桁を
○○で、○△□の桁を△△△で、△□☆×の桁を□□□
×で、☆×の桁を☆☆で表し、それぞれ加算する。な
お、×のビットはそのまま次の第７の工程に移行させ
る。

【００４０】図５の第７の工程では、第６の工程におけ
る○同士の加算結果を○○で、△同士の加算結果を△△
で、□同士の加算結果を□□で、☆同士の加算結果を☆
☆で表して並べる。また、これら並べた各桁のうち○の
桁を×で、○△の桁を○○で、△□の桁を△△で、□×
の桁を□□で表し、それぞれ加算する。なお、×のビッ
トはそのまま次の第８の工程に移行させる。

【００４１】第８の工程では、第７の工程における○同
士の加算結果を○○で、△同士の加算結果を△△で、□
同士の加算結果を□□で表す。次に、○○、△△、□□
を同一桁で並べて加算する。なお、×のビットはそのま
ま次の第９の工程に送る。

【００４２】第９の工程では、第８の工程の加算結果の
☆☆☆☆とそのまま移行された×××からなる☆☆☆☆
×××を多数決の結果として得る。

【００４３】上記図３〜図５の工程を具体的回路構成で
示すと、図６〜図８に示すようになる。なお、これら図
６〜図８は一体となっている回路構成を分割して示し、
図６には入力符号Ｍ０〜Ｍ６３の６４ビットのうちのＭ
０〜Ｍ２６までに、また図７はＭ２７〜Ｍ６３までに対
応している。

【００４４】先ず、図６及び図７において、端子３０１
にはＭ０〜Ｍ６３の各ビットが供給される。ここで、１
ビット全加算器３０２₀の入力端子Ａ２にはＭ０のビッ
トが、入力端子Ａ１にはＭ１のビットが、キャリイン端
子ＣＩにはＭ３のビットが供給される。以下同様に、１
ビット全加算器３０２₁〜３０２₁₉までは、対応するＭ
３〜Ｍ５９のビットがそれぞれ対応する入力端子Ａ１，
Ａ２及びキャリイン端子ＣＩに供給される。また、１ビ
ット半加算器３０２₂₀の入力端子Ａ２にはＭ６０のビッ
トが、入力端子Ａ１にはＭ６１のビットが供給され、１
ビット半加算器３０２₂₁の入力端子Ａ２にはＭ６２のビ
ットが、入力端子Ａ１にはＭ６３のビットが供給され
る。これら１ビット全加算器３０２₀〜３０２₁₉及び１
ビット半加算器３０２₂₀，３０２₂₁への入力符号の供給
及び加算が、上記図３で説明した第１の工程となる。

【００４５】次に、上記全加算器３０２₀〜３０２₁₉及
び１ビット半加算器３０２₂₀，３０２₂₁のキャリアウト
信号と加算信号は、後段の各加算器に送られるが、これ
ら全加算器３０２₀〜３０２₁₉及び１ビット半加算器３
０２₂₀，３０２₂₁と、後段の各加算器との間の接続は以
下のようになされている。

【００４６】先ず、全加算器３０２₀のキャリアウト端
子ＣＯは次段の１ビット全加算器３０３₀の入力端子Ａ
２と接続され、加算出力端子Ｓは１ビット全加算器３０
３₁の入力端子Ａ２と接続されている。以下同様に、全
加算器３０２₁のキャリアウト端子ＣＯは全加算器３０
３₀の入力端子Ａ１と接続され、加算出力端子Ｓは全加
算器３０３₁の入力端子Ａ１と接続されている。全加算
器３０２₂のキャリアウト端子ＣＯは全加算器３０３₀
のキャリイン端子ＣＩと接続され、加算出力端子Ｓは全
加算器３０３₁のキャリイン端子ＣＩと接続されてい
る。全加算器３０２₃のキャリアウト端子ＣＯは全加算
器３０３₂の入力端子Ａ２と接続され、加算出力端子Ｓ
は全加算器３０３₃の入力端子Ａ２と接続されている。
全加算器３０２₄のキャリアウト端子ＣＯは全加算器３
０３₂の入力端子Ａ１と接続され、加算出力端子Ｓは全
加算器３０３₃の入力端子Ａ１と接続されている。全加
算器３０２₅のキャリアウト端子ＣＯは全加算器３０３
₂のキャリイン端子ＣＩと接続され、加算出力端子Ｓは
全加算器３０３₃のキャリイン端子ＣＩと接続されてい
る。全加算器３０２₆のキャリアウト端子ＣＯは全加算
器３０３₄の入力端子Ａ２と接続され、加算出力端子Ｓ
は全加算器３０３₅の入力端子Ａ２と接続されている。
全加算器３０２₇のキャリアウト端子ＣＯは全加算器３
０３₄の入力端子Ａ１と接続され、加算出力端子Ｓは全
加算器３０３₅の入力端子Ａ１と接続されている。全加
算器３０２₈のキャリアウト端子ＣＯは全加算器３０３
₄のキャリイン端子ＣＩと接続され、加算出力端子Ｓは
全加算器３０３₅のキャリイン端子ＣＩと接続されてい
る。全加算器３０２₉のキャリアウト端子ＣＯは全加算
器３０３₆の入力端子Ａ２と接続され、加算出力端子Ｓ
は全加算器３０３₇の入力端子Ａ２と接続されている。
全加算器３０２₁₀のキャリアウト端子ＣＯは全加算器３
０３₆の入力端子Ａ１と接続され、加算出力端子Ｓは全
加算器３０３₇の入力端子Ａ１と接続されている。全加
算器３０２₁₁のキャリアウト端子ＣＯは全加算器３０３
₆のキャリイン端子ＣＩと接続され、加算出力端子Ｓは
全加算器３０３₇のキャリイン端子ＣＩと接続されてい
る。全加算器３０２₁₂のキャリアウト端子ＣＯは全加算
器３０３₈の入力端子Ａ２と接続され、加算出力端子Ｓ
は全加算器３０３₉の入力端子Ａ２と接続されている。
全加算器３０２₁₃のキャリアウト端子ＣＯは全加算器３
０３₈の入力端子Ａ１と接続され、加算出力端子Ｓは全
加算器３０３₉の入力端子Ａ１と接続されている。全加
算器３０２₁₄のキャリアウト端子ＣＯは全加算器３０３
₈のキャリイン端子ＣＩと接続され、加算出力端子Ｓは
全加算器３０３₉のキャリイン端子ＣＩと接続されてい
る。全加算器３０２₁₅のキャリアウト端子ＣＯは全加算
器３０３₁₀の入力端子Ａ２と接続され、加算出力端子Ｓ
は全加算器３０３₁₁の入力端子Ａ２と接続されている。
全加算器３０２₁₆のキャリアウト端子ＣＯは全加算器３
０３₁₀の入力端子Ａ１と接続され、加算出力端子Ｓは全
加算器３０３₁₁の入力端子Ａ１と接続されている。全加
算器３０２₁₇のキャリアウト端子ＣＯは全加算器３０３
₁₀のキャリイン端子ＣＩと接続され、加算出力端子Ｓは
全加算器３０３₁₁のキャリイン端子ＣＩと接続されてい
る。全加算器３０２₁₈のキャリアウト端子ＣＯは全加算
器３０３₁₂の入力端子Ａ２と接続され、加算出力端子Ｓ
は全加算器３０３₁₃の入力端子Ａ２と接続されている。
全加算器３０２₁₉のキャリアウト端子ＣＯは全加算器３
０３₁₂の入力端子Ａ１と接続され、加算出力端子Ｓは全
加算器３０３₁₃の入力端子Ａ１と接続されている。半加
算器３０２₂₀のキャリアウト端子ＣＯは全加算器３０３
₁₂のキャリイン端子ＣＩと接続され、加算出力端子Ｓは
全加算器３０３₁₃のキャリイン端子ＣＩと接続されてい
る。最後の半加算器３０２₂₁のキャリアウト端子ＣＯは
更に次の段の１ビット全加算器３０４₈のキャリイン端
子ＣＩに接続され、加算出力端子Ｓは１ビット半加算器
３０４₉の入力端子Ａ１に接続されている。

【００４７】これら全加算器３０３₀〜３０３₁₃で加算
が行われる。すなわち、これら全加算器３０２₀〜３０
２₁₉及び１ビット半加算器３０２₂₀，３０２₂₁と後段の
各加算器との間の接続及び、上記全加算器３０３₀〜３
０３₁₃における加算により、上記図３で説明した第２の
工程が実行される。

【００４８】上記全加算器３０３₀〜３０３₁₃のキャリ
アウト信号と加算信号は、さらに次段の各加算器に送ら
れるが、これら全加算器３０３₀〜３０３₁₃と、後段の
各加算器との間の接続は以下のようになされている。

【００４９】全加算器３０３₀のキャリアウト端子ＣＯ
は次段の１ビット全加算器３０４₀の入力端子Ａ２と接
続され、加算出力端子Ｓは１ビット全加算器３０４₁の
入力端子Ａ２と接続されている。以下同様に、全加算器
３０３₁のキャリアウト端子ＣＯは全加算器３０４₂の
入力端子Ａ２と接続され、加算出力端子Ｓは全加算器３
０４₃の入力端子Ａ２と接続されている。全加算器３０
３₂のキャリアウト端子ＣＯは全加算器３０４₀の入力
端子Ａ１と接続され、加算出力端子Ｓは全加算器３０４
₁の入力端子Ａ１と接続されている。全加算器３０３₃
のキャリアウト端子ＣＯは全加算器３０４₂の入力端子
Ａ１と接続され、加算出力端子Ｓは全加算器３０４₃の
入力端子Ａ１と接続されている。全加算器３０３₄のキ
ャリアウト端子ＣＯは全加算器３０４₀のキャリイン端
子ＣＩと接続され、加算出力端子Ｓは全加算器３０４₁
のキャリイン端子ＣＩと接続されている。全加算器３０
３ ₅のキャリアウト端子ＣＯは全加算器３０４₂のキャ
リイン端子ＣＩと接続され、加算出力端子Ｓは全加算器
３０４₃のキャリイン端子ＣＩと接続されている。全加
算器３０３₆のキャリアウト端子ＣＯは全加算器３０４
₄の入力端子Ａ２と接続され、加算出力端子Ｓは全加算
器３０４₅の入力端子Ａ２と接続されている。全加算器
３０３₇のキャリアウト端子ＣＯは全加算器３０４₆の
入力端子Ａ２と接続され、加算出力端子Ｓは全加算器３
０４₇の入力端子Ａ２と接続されている。全加算器３０
３₈のキャリアウト端子ＣＯは全加算器３０４₄の入力
端子Ａ１と接続され、加算出力端子Ｓは全加算器３０４
₅の入力端子Ａ１と接続されている。全加算器３０３₉
のキャリアウト端子ＣＯは全加算器３０４₆の入力端子
Ａ１と接続され、加算出力端子Ｓは全加算器３０４₇の
入力端子Ａ１と接続されている。全加算器３０３₁₀のキ
ャリアウト端子ＣＯは全加算器３０４₄のキャリイン端
子ＣＩと接続され、加算出力端子Ｓは全加算器３０４₅
のキャリイン端子ＣＩと接続されている。全加算器３０
３₁₁のキャリアウト端子ＣＯは全加算器３０４₆のキャ
リイン端子ＣＩと接続され、加算出力端子Ｓは全加算器
３０４₇のキャリイン端子ＣＩと接続されている。全加
算器３０３₁₂のキャリアウト端子ＣＯは更に次段の１ビ
ット全加算器３０５₂のキャリイン端子ＣＩと接続さ
れ、加算出力端子Ｓは全加算器３０４₈の入力端子Ａ２
と接続されている。全加算器３０３₁₃のキャリアウト端
子ＣＯは全加算器３０４₈の入力端子Ａ１と接続され、
加算出力端子Ｓは半加算器３０４₉の入力端子Ａ２と接
続されている。

【００５０】これら全加算器３０４₀〜３０４₈及び半
加算器３０４₉で加算が行われる。すなわち、上記全加
算器３０３₀〜３０３₁₃と後段の各加算器との間の接続
及び、上記全加算器３０４₀〜３０４₈及び半加算器３
０４₉における加算により、上記図３で説明した第３の
工程が実行される。

【００５１】上記全加算器３０４₀〜３０４₈及び半加
算器３０４₉のキャリアウト信号と加算信号は、図６及
び図７と図８に示すように、さらに次段の１ビット半加
算器３０５₀，３０５₁と１ビット全加算器３０５₂，
３０５₃と半加算器３０５₄，全加算器３０５₅〜３０
５₇とに送られるが、これら各加算器間の接続は以下の
ようになされている。

【００５２】全加算器３０４₀のキャリアウト端子ＣＯ
は次段の１ビット半加算器３０５₀の入力端子Ａ２と接
続され、加算出力端子Ｓは１ビット半加算器３０５₁の
入力端子Ａ２と接続されている。以下同様に、全加算器
３０４₁のキャリアウト端子ＣＯは全加算器３０５₂の
入力端子Ａ２と接続され、加算出力端子Ｓは半加算器３
０５₄の入力端子Ａ２と接続されている。全加算器３０
４₂のキャリアウト端子ＣＯは全加算器３０５₃の入力
端子Ａ２と接続され、加算出力端子Ｓは全加算器３０５
₅の入力端子Ａ２と接続されている。全加算器３０４₃
のキャリアウト端子ＣＯは全加算器３０５₆の入力端子
Ａ２と接続され、加算出力端子Ｓは全加算器３０５₇の
入力端子Ａ２と接続されている。全加算器３０４₄のキ
ャリアウト端子ＣＯは半加算器３０５₀の入力端子Ａ１
と接続され、加算出力端子Ｓは半加算器３０５₁の入力
端子Ａ１と接続されている。全加算器３０４₅のキャリ
アウト端子ＣＯは全加算器３０５₂の入力端子Ａ１と接
続され、加算出力端子Ｓは半加算器３０５₄の入力端子
Ａ１と接続されている。全加算器３０４₆のキャリアウ
ト端子ＣＯは全加算器３０５₃の入力端子Ａ１と接続さ
れ、加算出力端子Ｓは全加算器３０５₅の入力端子Ａ１
と接続されている。全加算器３０４₇のキャリアウト端
子ＣＯは全加算器３０５₆の入力端子Ａ１と接続され、
加算出力端子Ｓは全加算器３０５₇の入力端子Ａ１と接
続されている。全加算器３０４₈のキャリアウト端子Ｃ
Ｏは全加算器３０５₃のキャリイン端子ＣＩと接続さ
れ、加算出力端子Ｓは全加算器３０５₅のキャリイン端
子ＣＩと接続されている。半加算器３０４₉のキャリア
ウト端子ＣＯは全加算器３０５₆のキャリイン端子ＣＩ
と接続され、加算出力端子Ｓは全加算器３０５₇のキャ
リイン端子ＣＩと接続されている。

【００５３】これら全加算器及び半加算器で加算が行わ
れる。すなわち、上記全加算器３０４₀〜３０４₈及び
半加算器３０４₉と次段の全加算器及び半加算器との間
の接続及び、これら次段の全加算器及び半加算器におけ
る加算により、上記図３及び図４で説明した第４の工程
が実行される。

【００５４】上記半加算器３０５₀，３０５₁と全加算
器３０５₂，３０５₃と半加算器３０５₄，全加算器３
０５₅〜３０５₇のキャリアウト信号と加算信号は、さ
らに後段の各加算器に送られるが、これら各加算器間の
接続は以下のようになされている。

【００５５】半加算器３０５₀のキャリアウト端子ＣＯ
は後段の１ビット半加算器３０７₀の入力端子Ａ２と接
続され、加算出力端子Ｓは１ビット全加算器３０８₁の
入力端子Ａ２と接続されている。半加算器３０５₁のキ
ャリアウト端子ＣＯは全加算器３０６₀の入力端子Ａ２
と接続され、加算出力端子Ｓは全加算器３０６₁の入力
端子Ａ２と接続されている。全加算器３０５₂のキャリ
アウト端子ＣＯは全加算器３０６₀の入力端子Ａ１と接
続され、加算出力端子Ｓは全加算器３０６₁の入力端子
Ａ１と接続されている。全加算器３０５₃のキャリアウ
ト端子ＣＯは全加算器３０６₀のキャリイン端子ＣＩと
接続され、加算出力端子Ｓは全加算器３０６₁のキャリ
イン端子ＣＩと接続されている。半加算器３０５₄のキ
ャリアウト端子ＣＯは全加算器３０６₂の入力端子Ａ２
と接続され、加算出力端子Ｓは後段の半加算器３０７₃
の入力端子Ａ２と接続されている。全加算器３０５₅の
キャリアウト端子ＣＯは全加算器３０６₂の入力端子Ａ
１と接続され、加算出力端子Ｓは全加算器３０６₃の入
力端子Ａ２と接続されている。全加算器３０６₆のキャ
リアウト端子ＣＯは全加算器３０６₂のキャリイン端子
ＣＩと接続され、加算出力端子Ｓは全加算器３０６₃の
入力端子Ａ１と接続されている。半加算器３０５₇のキ
ャリアウト端子ＣＯは全加算器３０６₃のキャリイン端
子ＣＩと接続されている。

【００５６】これら全加算器及び半加算器で加算が行わ
れる。すなわち、上記全加算器及び半加算器と後段の全
加算器及び半加算器との間の接続と、これら加算器にお
ける加算により、上記図４で説明した第５の工程が実行
される。

【００５７】上記全加算器３０６₀〜３０６₃のキャリ
アウト信号と加算信号は、さらに後段の各加算器に送ら
れるが、これらの間の接続は以下のようになされてい
る。

【００５８】全加算器３０６₀のキャリアウト端子ＣＯ
は半加算器３０７₀の入力端子Ａ１と接続され、加算出
力端子Ｓは全加算器３０７₁の入力端子Ａ２と接続され
ている。全加算器３０６₁のキャリアウト端子ＣＯは全
加算器３０７₁の入力端子Ａ１と接続され、加算出力端
子Ｓは全加算器３０７₂の入力端子Ａ２と接続されてい
る。全加算器３０６₂のキャリアウト端子ＣＯは全加算
器３０７₁のキャリイン端子ＣＩと接続され、加算出力
端子Ｓは全加算器３０７₂の入力端子Ａ１と接続されて
いる。全加算器３０６₃のキャリアウト端子ＣＯは全加
算器３０７₂のキャリイン端子ＣＩと接続され、加算出
力端子Ｓは半加算器３０７₃の入力端子Ａ１と接続され
ている。

【００５９】これら半加算器３０７₀，３０７₃及び全
加算器３０７₁，３０７₂で加算が行われる。すなわ
ち、これらの間の接続と、これら加算器における加算に
より、上記図４及び図５で説明した第６の工程が実行さ
れる。

【００６０】上記半加算器３０７₀，３０７₃及び全加
算器３０７₁，３０７₂のキャリアウト信号と加算信号
は、さらに後段の各加算器に送られるが、これら全加算
器及び半加算器と、後段の各加算器との間の接続は以下
のようになされている。

【００６１】全加算器３０７₀のキャリアウト端子ＣＯ
は全加算器３０９₀の入力端子Ａ２と接続され、加算出
力端子Ｓは半加算器３０８₀の入力端子Ａ２と接続され
ている。全加算器３０７₁のキャリアウト端子ＣＯは半
加算器３０８₀の入力端子Ａ１と接続され、加算出力端
子Ｓは全加算器３０８₁の入力端子Ａ１と接続されてい
る。全加算器３０７₂のキャリアウト端子ＣＯは全加算
器３０８₁のキャリイン端子ＣＩと接続され、加算出力
端子Ｓは半加算器３０８₂の入力端子Ａ２と接続されて
いる。半加算器３０７₃のキャリアウト端子ＣＯは半加
算器３０８₂の入力端子Ａ１と接続されている。

【００６２】これら接続及び加算により、上記図５で説
明した第７の工程が実行される。

【００６３】次に、半加算器３０８₀のキャリアウト端
子ＣＯは全加算器３０９₀の入力端子Ａ１と接続され、
加算出力端子Ｓは全加算器３０９₁の入力端子Ａ２と接
続されている。全加算器３０８₁のキャリアウト端子Ｃ
Ｏは全加算器３０９₁の入力端子Ａ１と接続され、加算
出力端子Ｓは半加算器３０９₂の入力端子Ａ２と接続さ
れている。半加算器３０８₂のキャリアウト端子ＣＯは
半加算器３０９₂の入力端子Ａ１と接続されている。

【００６４】これら接続及び加算により、上記図５で説
明した第８の工程が実行される。

【００６５】次に、半加算器３０９₂のキャリアウト端
子ＣＯは全加算器３０９₁のキャリインＣＩ端子と接続
され、全加算器３０９₁のキャリアウト端子ＣＯは全加
算器３０９₀のキャリインＣＩ端子と接続されている。
これら接続及び加算により、上記図５で説明した第９の
工程が実行される。

【００６６】なお、この図６〜図８の多数決回路は、例
えば拘束長Ｋ＝７のビタビ復号器に適用することができ
るものである。すなわち、本実施例のビタビ復号器は、
前述したような、入力符号に基づいてブランチメトリッ
クを計算するブランチメトリック計算部と、ブランチメ
トリックに基づいてパス選択信号を出力する複数のＡＣ
Ｓ回路からなるステートメトリック計算部と、上記パス
選択信号が供給される複数のパスメモリセルからなるパ
スメモリ回路とを有し、このパスメモリ回路の出力に対
して上述した図６〜図８に示したような冗長２進数表現
を用いた加算処理を行って多数決を行う多数決回路を有
してなるものである。したがって、図６の端子３０１に
供給される入力符号Ｍ０〜Ｍ６３は、パスメモリ回路か
らの６４ビット出力となる。

【００６７】また、図８の上記全加算器３０９₁の２つ
の出力は、２入力のＯＲ（論理和）ゲート３１０に送ら
れ、当該ゲート３０１で論理和が取られることで多数決
判定による“０”又は“１”が得られるようになる。す
なわち、加算処理の加算結果が所定ビットとなった場合
である図８の最終段３ビット分の全加算器の上位２ビッ
ト分を論理和ゲート３１０によって論理和を取ることに
より、上記入力符号Ｍ０〜Ｍ６３のうち、“１”の数が
３２以上の場合には“１”が出力され、それ以外は
“０”が出力される。これにより、６４ビット多数決が
なされたこととなる。この出力がビタビ復号器に適用さ
れる多数決回路の出力端子３１１から出力される。

【００６８】本実施例の多数決回路においては、上述し
た図６〜図８に示したように、最終段以外の全ての加算
器のキャリアウト（桁上げ信号線）は、同じ段の加算器
に桁上げ信号として送られていないため、高速動作が可
能となる。また、従来よりも、回路規模は、１ビット半
加算器で換算すると、約４０％分構成を少なくすること
が可能となる。

【００６９】さらに、本実施例においては、上記多数決
回路を用いることで、拘束長Ｋの長いビタビ復号器の場
合でも、小規模でかつ高速動作で、パスメモリ全ビット
出力を多数決判定でき、さらにＩＣ化も容易となる。ま
た、全ビット多数決を行えるので、ビタビ復号器の性能
を十分に引き出すことができる。

【００７０】

【発明の効果】上述のように、本発明においては、多数
決回路において冗長２進表現を用いた加算を行うこと
で、高速動作が可能となり、ＩＣ化が非常に容易とな
る。また、この多数決回路をビタビ復号器の最尤判定回
路に適用することで、拘束長Ｋの長いビタビ復号器であ
っても、小規模でかつ高速動作でパスメモリの全ビット
出力を多数決判定でき、さらに全ビット多数決を行える
ので、ビタビ復号器の性能を十分に引き出すことができ
る。

【図面の簡単な説明】

【図１】本発明の冗長２進表現の原理を説明するための
図である。

【図２】本実施例の冗長２進表現を用いた多数決回路の
具体例を示すブロック回路図である。

【図３】冗長２進表現を用いて６４ビット多数決を行う
場合の第１の工程から第４の工程の一部までを説明する
ための図である。

【図４】冗長２進表現を用いて６４ビット多数決を行う
場合の第４の工程の一部から第６の工程の一部までを説
明するための図である。

【図５】冗長２進表現を用いて６４ビット多数決を行う
場合の第６の工程の一部から第９の工程までを説明する
ための図である。

【図６】冗長２進表現を用いて６４ビット多数決を行う
多数決回路の具体的構成のうち入力符号Ｍ０〜Ｍ２６ま
でに対応する一部の構成を示すブロック回路図である。

【図７】冗長２進表現を用いて６４ビット多数決を行う
多数決回路の具体的構成のうち入力符号Ｍ２７〜Ｍ６３
までに対応する一部の構成を示すブロック回路図であ
る。

【図８】冗長２進表現を用いて６４ビット多数決を行う
多数決回路の具体的構成の後半部分の構成を示すブロッ
ク回路図である。

【図９】従来の多数決回路を説明するためのブロック回
路図である。

【図１０】ビタビ復号器の全体構成を示すブロック回路
図である。

【符号の説明】

１，２・・・・全加算器３，４・・・・半加算器１０１・・・・ブランチメトリック計算部１０２・・・・ステートメトリック計算部１０３・・・・パスメモリ回路１０４・・・・多数決回路（最尤判定回路）

Claims

【特許請求の範囲】

【請求項１】冗長２進表現を用いた加算処理を行い、
複数の入力符号の多数決を行うことを特徴とする多数決
回路。
【請求項２】入力符号に基づいてブランチメトリック
を計算するブランチメトリック計算部と、ブランチメトリックに基づいてパス選択信号を出力する
複数のＡＣＳ回路からなるステートメトリック計算部
と、上記パス選択信号が供給される複数のパスメモリセルか
らなるパスメモリ回路と、上記パスメモリ回路の出力に対して冗長２進数表現を用
いた加算処理を行って多数決を行う多数決回路とを有す
ることを特徴とするビタビ復号器。
【請求項３】加算処理中に加算結果が所定ビット数と
なる位置に多ビット全加算器を設けることを特徴とする
請求項１記載の多数決回路。