(57)【要約】デコーダ104及び700は、ノイズのある通信チャンネル103を伝送してきたデータを復号するように動作可能である。デコーダ104または700は、通信チャンネル103を介して受信された符号化データyのビットを記憶するメモリ703を備える。デコーダ104または700は、受信したビットyから送信された符号語を推定するプロセッサ701も備える。プロセッサ701は、受信したデータyを復号するための線形計画法(LP)を決定するように動作可能であり、線形計画法は費用関数を含む。LPの解は、費用関数に関連する複数の変数を一回の繰り返しで変更する座標上昇法を用いて計算される。送信された符号語は、LPの解を用いて受信した符号化データyから推定される。【選択図】図６
2010535459.tif 000002
【特許請求の範囲】
【請求項１】
通信システムにおいて受信されたデータを表す符号を復号する方法であって、
前記通信システムにおいて通信チャンネル１０３上を伝送された符号語ｘを表す符号化されたデータｙを受信するステップと、
前記受信したデータを復号するための線形計画法（ＬＰ）を決定するステップであって、該線形計画法は、特定の符号語が前記通信チャンネル１０３を介して送信されたときに特定の語（ワード）が受信される確率に関連する費用関数を含む、ステップと、
一回の繰り返しで前記費用関数に関連する複数の変数を変更する座標上昇法を用いて前記ＬＰの解を計算するステップと、
前記ＬＰの解を用いて、送信された符号語
【数１２２】
2010535459.tif 000126
を、前記受信した符号化されたデータｙから推定するステップ
を含む方法。
【請求項２】
線形計画法を決定する前記ステップが、
前記ＬＰから双対ＬＰを決定するステップであって、前記ＬＰは主ＬＰであり、前記双対ＬＰは、双対費用関数、前記費用関数から得られた制約、及び、前記主ＬＰにおける制約を含む、ステップを含み、
前記ＬＰの解を計算する前記ステップが、
前記双対ＬＰの解を計算するときに前記双対費用関数を最適化することによって前記双対ＬＰを解くステップを含む
ことからなる、請求項１の方法。
【請求項３】
前記双対費用関数を最適化する前記ステップが、前記双対費用関数が前記制約に関して最大化されるように前記双対ＬＰの解を決定するステップを含むことからなる、請求項２の方法。
【請求項４】
前記双対費用関数が、被加数である局所関数を表す、前記双対費用関数の関数ノードＡ’ｉまたはＢ’ｊ、及び、前記それぞれの関数の変数を表すそれぞれの関数ノードに接続されたエッジを有するフォーニー型ファクターグラフ５００によって表現可能であり、
前記双対ＬＰを解くステップが、前記複数の変数を選択するステップを含み、該複数の変数が、前記関数ノードの特定の関数ノードに付随するエッジによって表される変数を含むことからなる、請求項２の方法。
【請求項５】
前記特定の関数ノードが、関数Ａ’ｉまたはＢ’ｊを表し、前記双対ＬＰ中のＡ’ｉが前記主ＬＰ中の一致関数ノードＡｉの双対関数であり、前記双対ＬＰ中のＢ’ｊが、前記主ＬＰ中のパリティ検査ノードＢｊの双対関数である、請求項４の方法。
【請求項６】
前記複数の変数を選択するステップが、
Ａ’ｉ関数ノードまたはＢ’ｊ関数ノードをランダムに選択するステップと、
前記ランダムに選択された関数ノードの付随するエッジに関連する変数を更新するステップ
を含むことからなる、請求項５の方法。
【請求項７】
前記双対費用関数の一部が、
【数１２３】
2010535459.tif 000127
によって表現可能であり、ここで、
【数１２４】
2010535459.tif 000128
が費用関数中の変数であり、
【数１２５】
2010535459.tif 000129
が前記複数の変数を表し、
前記双対ＬＰを解くステップが解を決定するステップを含み、該解において、
【数１２６】
2010535459.tif 000130
が最大になることからなる、請求項２の方法。
【請求項８】
前記双対費用関数の一部が、
【数１２７】
2010535459.tif 000131
によって表現可能であり、
前記双対ＬＰを解くステップが解を決定するステップを含み、該解において、
【数１２８】
2010535459.tif 000132
が最大になることからなる、請求項２の方法。
【請求項９】
ノイズのある通信チャンネル１０３上を伝送して受信されたデータｙを復号するように動作可能なデコーダ（１０４または７００）であって、
該デコーダ（１０４または７００）が、
前記通信チャンネル１０３を介して受信した符号化されたデータｙのビットを格納するメモリ７０３と、
送信された符号語
【数１２９】
2010535459.tif 000133
を、前記受信したビットｙから推定するプロセッサ７０１
を備え、
該プロセッサ７０１は、決定するステップと、計算するステップと、推定するステップとによって、前記送信された符号語を推定するように動作可能であり、
前記決定するステップが、前記受信したデータｙを復号するための線形計画法（ＬＰ）を決定するステップであり、該線形計画法は、特定の符号語が前記通信チャンネル１０３を介して送信されたときに特定の語（ワード）が受信される確率に関連する費用関数を含み、
前記計算するステップが、前記費用関数に関連する複数の変数を一回の繰り返しで変更する座標上昇法を用いて前記ＬＰの解を計算するステップであり、
前記推定するステップが、前記ＬＰの解を用いて、前記受信した符号化されたデータｙから送信された符号語
【数１３０】
2010535459.tif 000134
を推定するステップであることからなる、デコーダ。
【請求項１０】
前記プロセッサ７０１が、前記ＬＰを双対費用関数を含む双対ＬＰとして定式化し、及び、該双対ＬＰの解を求めることからなる、請求項９のデコーダ（１０４または７００）。
【発明の詳細な説明】
【背景技術】
【０００１】
典型的な現代の通信システムは、通信チャンネル上を受信機へと伝送させるためのデータを符号化（エンコード）するためのエンコーダ（符号化器）を具備する送信機を備える。圧縮するためにデータを符号化して、伝送エラーを訂正するための冗長性を付加することができる。たとえば、冗長シンボルを符号化された情報シンボルに付加することができ、これによって、伝送される可能性のあるシンボルのシーケンスの集合を可能性のある全てのシーケンスの一部に効果的に限定することができる。エンコーダは、チャンネル符号化技術にしたがってメッセージを符号化することによって冗長シンボルを付加する。たとえば、低密度パリティ検査符号（low-density parity-check code：LDPC code）がデータを符号化するためによく使用される。
【０００２】
受信機側では、たとえばノイズのあるチャンネルのために伝送中に導入されるエラーがデコーダ（復号器）によって訂正される。デコーダは、受信機におけるデータの完全性を確保するので、信頼性のある符号化通信システムの重要な部分である。
【０００３】
スループットが高いことは、多くの現代の通信システムにおいて非常の望ましい特徴である。これらのシステム内のデコーダは、伝送中に導入されたエラーを迅速に訂正することを試みる。デコード（復号化）における遅れは、システムのスループットを低くしうる。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
近年、データの復号（デコード）を表す線形計画法（linear program：ＬＰ。または、線形プログラム）を定式化し、次に、従来の線形計画法アルゴリズムを用いてそのＬＰを解いてデータを復号することにより、デコーダにおける符号の復号を実行できることが提案されている。しかしながら、これらの、ＬＰを解くために従来の線形計画法アルゴリズムを用いる「ＬＰデコーダ」は、多くの復号化用途に実装するにはあまりにも遅くかつ効率が悪い可能性が高い。たとえば、ＬＰを解くのに時間がかかるために、デコーダの復号速度が従来のデコーダよりも遅くなる場合がある。また、ＬＰを解くためのデータを記憶するのに必要なメモリ量が、従来のデコーダよりもはるかに多くなりえ、これによって、デコーダのサイズ及びコストが増大しうる。
【課題を解決するための手段】
【０００５】
デコーダは、ノイズのある通信チャンネルを伝送するデータを復号するように動作可能である。デコーダは、通信チャンネルを介して受信された符号化されたデータのビットを記憶するメモリを備える。デコーダはまた、受信したビットから送信された符号語（またはコードワード）を推定（または評価）するプロセッサを備える。プロセッサは、受信したデータを復号するための線形計画法（ＬＰ）を決定するように動作することができ、この場合、線形計画法は費用関数を含む。ＬＰの解は、１回の繰り返しで費用関数に関連する複数の変数を変更する（または変化させる）座標上昇（coordinate-ascent）法を用いて計算される。送信された符号語は、ＬＰの解（または解法）を用いて、受信された符号化データから推定される。
【０００６】
いくつかの実施形態についての以下の詳細な説明を添付の図面と併せて参照することによってそれらの実施形態の種々の特徴がより良く理解されるので、それらの特徴をより十分に理解することができる。
【図面の簡単な説明】
【０００７】
【図１】１実施形態による通信システムを示す。
【図２】１実施形態による、データを復号するための線形計画法の解を表す多面体（ポリトープ）を示す。
【図３】１実施形態による、図２に示す多面体の弛緩したバージョンを示す。
【図４】１実施形態による、データをデコーダするための主線形計画法を表すフォーニー型ファクターグラフ（Forney-style factor graph：ＦＦＧ）を示す。
【図５】１実施形態による、データを復号するための双対線形計画法を表すＦＦＧを示す。
【図６】１実施形態による、データを復号するための１方法の流れ図を示す。
【図７】１実施形態によるデコーダを示す。
【発明を実施するための形態】
【０００８】
簡潔にすると共に説明のために、いくつの実施形態の原理を、該実施形態の例を主として参照することによって説明する。以下の説明では、それらの実施形態を完全に理解できるようにするために、多くの特定の細部が説明される。しかしながら、当業者には、それらの特定の細部に限定することなくそれらの実施形態を実施できることが明らかであろう。いくつかの例では、実施形態を不必要に不明瞭にしないようにするために、周知の方法及び構成について詳しくは説明されていない。
【０００９】
１実施形態によれば、データを復号するための方法は、復号問題をＬＰとして定式化するステップを含む。データは、低密度パリティ検査（low-density parity check：LDPC）符号、または、他の任意の線形または非線形符号を用いて符号化されている場合がある。１実施形態によれば、主ＬＰ（または一次ＬＰ）が定式化され、対応する双対ＬＰが該主ＬＰから決定される。双対ＬＰは、受信されたデータをより速い速度（またはレート）で復号するための改良された座標上昇（coordinate-ascent）法を用いて解かれる。
【００１０】
改良された座標上昇法は、１回の反復で複数の変数を更新する。これらの複数の変数は、複数のいわゆる局所関数の和として表すことができる費用関数の変数の一部である。費用関数を、関数ノードが局所関数を表し、エッジが変数を表すフォーニー型ファクターグラフ（ＦＦＧ）として表すことができ、この場合、エッジは、該エッジに関連する変数が関数ノードに関連する局所関数に対する引数（または独立変数）である場合にのみ、該関数ノードに付随する。複数の変数は、ＦＦＧ内の関数ノードに付随するエッジによって表される全ての変数を含むことができる。複数の変数は、関数ノードによって表される特定の関数に対する引数である。１実施形態によれば、関数ノードに付随するＦＦＧ内のエッジに関連する全ての変数は、改良された座標上昇法を用いて１回の反復で更新される。これによって、データを復号するのに必要な反復の数が少なくなり、それゆえ、復号速度が速くなる。１実施形態では、ＬＰは、ＦＦＧによって表される双対ＬＰとして定式化される。複数の変数は、双対ＬＰ内の費用関数を表すＦＦＧ内の関数ノードに付随するエッジによって表される全ての変数を含む。
【００１１】
図１は、１実施形態による、エンコード／デコードシステム（符号化／復号化システム）１００を示す。システム１００は、メッセージソース１００からのメッセージを受け取って、ＬＤＰＣ符号などの線形符号とすることができる符号を用いて該メッセージをエンコード（符号化）するエンコーダ１０２を備える。他の任意の線形符号または非線形符号を使用することもできる。たとえば、メッセージソース１０１は、「ｓ」として示されるメッセージを生成する。このメッセージｓは、エンコーダ１０２によってエンコード（符号化）される。エンコーダ１０２の出力は符号語である。従来のエンコード法を用いてメッセージｓをエンコードする。１つの例では、ＬＤＰＣ符号を用いてメッセージｓをエンコードする。メッセージソース１０１及びエンコーダ１０２を、送信機に含めることができ、または、エンコーダ１０２だけを、エンコードされたメッセージＳをシステム１００に送信する送信機に含めることができる。
【００１２】
符号語ｘはメッセージｓを表す。メッセージｓ及び符号語ｘを次のように表すことができる。
【数１】
2010535459.tif 000003
ｓ１、…、ｓｋはメッセージ内のビットである。ｘ１、…、ｘｎは、メッセージを表すために使用できる符号Ｃからの符号語のビットまたはシンボルである。ｎは、符号語内のビットまたはシンボルの数である。
【００１３】
符号語ｘは、通信チャンネル１０３上をデコーダ１０４を含む受信機へと送信される。デコーダ１０４は、この送信された符号語ｘを受信するが、それはｙとして示されている。たとえば、チャンネル１０３は、送信された符号語ｘとは異なる場合がある受信された語（ワード）ｙをもたらすノイズを含む。このノイズのあるチャンネル１０３はｘにエラーを導入する場合がある。ｙを、
【数２】
2010535459.tif 000004
と表すことができる。通信チャンネル１０３は、エンコードされたデータを記憶するための媒体に対するエンコードされたデータの書き込み及び読み出しという全ての処理を表すこともできることに留意されたい。たとえば、エンコードされたデータを、ハードディスクなどのコンピュータ読み取り可能媒体に格納することができる。データは、コンピュータ読み取り可能媒体から読み出されて、デコーダ１０４によって復号される。コンピュータ読み取り可能媒体に格納されたデータのいくつかは、時間の経過と共に破損する場合がある。デコーダ１０４は、本明細書に記載されているステップを用いて、格納されているデータを復号するときにそのデータを不正確に推定（または評価）するという誤り（エラー）を最小にする。
【００１４】
デコーダ１０４は、ｙを復号して、送信された符号語ｘと、該符号語ｘによって表されるメッセージｓを推定（または評価）する。推定（または評価）された送信済みの符号語は、
【数３】
2010535459.tif 000005
として示されており、推定（または評価）されたメッセージは、
【数４】
2010535459.tif 000006
として示されている。
【数５】
2010535459.tif 000007
及び、
【数６】
2010535459.tif 000008
は、受信したメッセージに対して更なる処理を実行することができる回路１０５に送られる。
【００１５】
復号ルールを選択する一般的なアプローチは、誤りのある
【数７】
2010535459.tif 000009
に対する復号の確率を最小化する、すなわち、
【数８】
2010535459.tif 000010
を最小にする復号ルールを選択することである。選択されたルールは、ブロック毎の最大事後確率（maximum a posteriori:ＭＡＰ）復号ルールとして知られており、
【数９】
2010535459.tif 000011
と書くことができる。この定義に基づいて、受信された所与のｙに対するｘの事後確率（または経験的確率）を最大にする符号語ｘが選択される。全ての符号語が同程度の確からしさ（または同じ確率）で送信されると想定すると（これは、ごく一般的な想定である）、決定ルールは、ブロック毎の最尤（ＭＬ）復号ルール（または、尤度最大化復号ルール）として知られているものになり、これは、
【数１０】
2010535459.tif 000012
として定義される。この定義に基づいて、ｘが送信された場合にｙが観測される確率を最大にするコードワードｘが選択される。ＭＬ復号に対するこの式を次の式１のように書くことができることが、Feldman他による「Using Linear Programming toDecode Binary Linear Codes」、IEEE Transactions onInformation Theory, March 2005, pp. 954-972（以下、「Feldman他」として参照する）に記載されている。
【００１６】
【数１１】
2010535459.tif 000013
【００１７】
式１は、費用関数
【数１２】
2010535459.tif 000014
を最小にする符号語ｘを見出すようにＭＬ復号を定式化できることを示している。デコーダ１０４は、費用関数を最小にする符号語ｘを選択する。ここで、
【数１３】
2010535459.tif 000015
である。λｉは、ｉ番目のビットの対数尤度比(Log-likelihood ratio；ＬＬＲ）である。このＬＬＲλｉの符号は、送信されたビットｘｉが０と１のどちらである可能性が高いかを示す。ｘｉが１である可能性が高い場合にはλｉは負である。ｘｉが０である可能性が高い場合にはλｉは正である。Feldman他に記載されているように、費用ベクトル（cost vector）λを、ＬＰ復号問題の解に影響を与えることなく正のスカラーによって均一にリスケール（大きさを調整する）できることに留意されたい。たとえば、２元対称通信路（binary symmetric channel）の場合、ｙｉ＝１であればλｉ＝−１であり、ｙｉ＝０であればλｉ＝＋１であると想定することができる。
【００１８】
費用関数
【数１４】
2010535459.tif 000016
がｘに関して線形であり、かつ、費用関数が最小化される集合が離散的であるので、この最適化問題は整数ＬＰ（integer LP）として既知ものである。
【００１９】
式１は、２元線形符号（binary linear code）を復号するために、費用関数
【数１５】
2010535459.tif 000017
を最小にする符号語が見出されることを示している。式１の解は、次の式２によって表される最適化問題の解でもあることが理解される。
【００２０】
【数１６】
2010535459.tif 000018
【００２１】
式２において、conv(C)は、Ｃの凸閉包（convex hull。または凸包）を意味する。費用関数がｘに関して線形であり、かつ、conv(C)が多面体である（したがって、一致及び不一致を利用して表すことができる）ので、式２に関する最適化問題はＬＰと呼ばれる。式２は、最小値がＣについてだけでなくconv(C)について取得されるときにも、式１の解が費用関数
【数１７】
2010535459.tif 000019
を最小にするということを示している。費用関数
【数１８】
2010535459.tif 000020
を最小にするconv(C)中のポイントの集合は、conv(C)の少なくとも１つの頂点−これは定義により符号語である−を常に含むことに留意されたい。したがって、実用上の見地からは、式１と式２の解は等価である。
【００２２】
式１及び２を解くことは、よい符号 (good code)のブロック長ｎに関して指数関数的に複雑になり、したがって、実用上有意なブロック長について解くことはできない。そこで、最適化理論における標準的なアプローチは、多面体（この例ではconv(C)）を記述の複雑さ (description complexity：記述複雑さ)がはるかに少ない弛緩（または緩和。以下同じ）された多面体に弛緩することである。こうして、新たなＬＰをより簡単に解くことができ、その上、この新たなＬＰの解が、通常は、以前のＬＰの解に近いか、または、それと同じになるように、弛緩された多面体が定式化される。式２を次のように書くこともできる。
【００２３】
【数１９】
2010535459.tif 000021
【００２４】
式３において、ωは多面体Ω内の点であり、ωｉはベクトルω＝（ω１、ω２、・・・、ωｎ）内の成分（または要素）である。図２は、式１及び２の解を表す２次元多面体２００の一例を示す。多面体２００の頂点がＬＰの解である。頂点のいくつかがω（１）〜ω（５）として示されている。式４は、弛緩された多面体に関するＬＰを表す。
【００２５】
【数２０】
2010535459.tif 000022
【００２６】
式４において、Ω’は弛緩された多面体である。多面体２００の弛緩の一例が図３に弛緩３００として示されている。式４においてＬＰをより簡単に解くことができ、その上、その解が、式３におけるＬＰの解に近いかまたはそれと同じであるように、弛緩３００は選択される。
【００２７】
デコードに関しては、弛緩された多面体は基本多面体 (fundamental polytope)と呼ばれる。かかる基本多面体を以下のようにＬＤＰＣ符号について定義することができる。ＬＤＰＣ符号は、本技術分野において知られているように、パリティ検査行列を用いて定義される。パリティ検査行列はランダムに生成されることができる。さらに重要なことには、ＬＤＰＣ符号は、行列とベクトルの積（行列ベクトル積）ＨｘＴが０に等しい場合（Ｈは、符号Ｃに対するパリティ検査行列である）に、符号語ｘがＬＤＰＣ符号Ｃ内にあるように定義される。
【００２８】
たとえば、パリティ検査行列Ｈは、
【００２９】
【数２１】
2010535459.tif 000023
である。
【００３０】
符号語ｘは、ｘ１＋ｘ２＋ｘ３＝０（ｍｏｄ２）、ｘ２＋ｘ４＋ｘ５＝０（ｍｏｄ２）、及び、ｘ３＋ｘ４＋ｘ５＝０（ｍｏｄ２）という３つの条件を満たさなければならない。したがって、これらの条件を満たす全てのｘの集合であるＣは、Ｃ１∩Ｃ２∩Ｃ３という論理積である。ここで、
【数２２】
2010535459.tif 000024
である。
【００３１】
基本多面体Ｐ(Ｈ)は、この場合、式５に示すように定義される。
【００３２】
【数２３】
2010535459.tif 000025
【００３３】
Ｐ(Ｈ)が、実際に、conv(C)の弛緩、すなわち、Ｐ(Ｈ)がconv(C)のスーパーセット（または上位集合）であることがわかる。この場合、ＬＰデコーダは式６に示すように定義される。
【００３４】
【数２４】
2010535459.tif 000026
【００３５】
本明細書及びFeldman他では、基本多面体内の点（ポイント）を疑似符号語と呼んでいる。当業者には、基本多面体を別様に定義できること、及び、非ＬＰＤＣ符号及び非線形符号についても定義できることが明らかであろう。パリティ検査行列及び符号Ｃ１〜Ｃ３は、ＬＰデコーダを定義するのに適した基本多面体の生成を例示するための１例として提示されている。
【００３６】
本明細書における例及び式の多くは、ｍ×ｎの大きさのパリティ検査行列Ｈによって定義される２元線形符号（binary linear code）Ｃを含んでいる。Ｈに基づいて、集合は次のように定義される。
【数２５】
2010535459.tif 000027
さらに、各
【数２６】
2010535459.tif 000028
について、符号は、
【数２７】
2010535459.tif 000029
である。ここで、ｈｊは、Ｈのｊ番目の行である。Ｃｊは、Ｉｊにない全ての位置が制約されていないところの長さｎの符号であることに留意されたい。
【００３７】
１実施形態によれば、式６に記述されているＬＰは主ＬＰと呼ばれ、対応する双対ＬＰ（dual LP）を主ＬＰから決定して該ＬＰの解が求められる。一般的に、任意の（主）線形計画問題の場合、いわゆる双対ＬＰを定式化することができる。双対ＬＰを決定する理由の１つは、双対ＬＰを用いて主ＬＰの解を導出できることにある。したがって、式６中の主ＬＰを直接に解かなくてもよい。代わりに双対ＬＰを解いて、その解から主ＬＰの解を導出するための１つの方法を以下で説明する。式６に記述されているＬＰに関しては、対応する主ＬＰと該主ＬＰから定式化された双対ＬＰが、Vontobel他による「TowardsLow Complexity Linear-Programming Decoding」（２００６年２月２６日）に記載されている（以下、この文献を「Vontobel他」という）。主ＬＰは次のように式７で示される。
【００３８】
式７：
【数２８】
2010535459.tif 000030
という制約の下に、
【数２９】
2010535459.tif 000031
を最小にする。
【００３９】
符号
【数３０】
2010535459.tif 000032
は、全ての要素が０のベクトルと、全ての要素が１である、長さが
【数３１】
2010535459.tif 000033
のベクトルを含む集合である。
【数３２】
2010535459.tif 000034
は、位置
【数３３】
2010535459.tif 000035
における短縮された符号Ｃｊである。
【数３４】
2010535459.tif 000036
についてはベクトルｕｉが用いられ、この場合、エントリは、
【数３５】
2010535459.tif 000037
によって索引付けされ、
【数３６】
2010535459.tif 000038
によって示される。
【数３７】
2010535459.tif 000039
についてはベクトルνｊが用いられ、この場合、エントリはＩｊによって索引付けされ、
【数３８】
2010535459.tif 000040
によって示される。その後、エントリａｉ、ｂｊについて、類似の表記である、
【数３９】
2010535459.tif 000041
がそれぞれ使用される。
【００４０】
上記の最適化問題は、図４に示されかつ後述するＦＦＧによってすっきりと表される。ＦＦＧにおいてＬＰそのものを表現するために、制約は、追加の費用項（cost term）として表される。これは、ＬＰ制約を満たさない変数の任意の構成に費用＋∞を割り当て、ＬＰ制約を満たす変数の構成に費用０を割り当てることによって達成される。上記の最小化問題は、この場合、次のようにな拡張された費用関数の（制約のない）最小化と等価である。
【数４０】
2010535459.tif 000042
全ての
【数４１】
2010535459.tif 000043
及び、全ての
【数４２】
2010535459.tif 000044
について、それぞれ、
【数４３】
2010535459.tif 000045
である。
【数４４】
2010535459.tif 000046
という表記は、ステートメントＳが真の場合は、
【数４５】
2010535459.tif 000047
であることを、偽の場合は、
【数４６】
2010535459.tif 000048
であることを意味する。
【００４１】
ＦＦＧを用いて、式７において示されるＬＰの拡張された費用関数を表すことができる。図４は、式７で示されるＬＰの拡張された費用関数の一部のＦＦＧ４００を示す。ここで説明されるＦＦＧは加法関数（additive function）を表し、該関数の値は、局所関数（localfunction）ノードの値の和に等しく、さらに、式７中のＬＰの拡張された費用関数の値にも等しい。ＦＦＧ４００は、左側にある局所関数ノードλｉｘｉ、及び、右側にある制約関数ノードを示す。主ＬＰの完全なＦＦＧは、局所関数λｉｘｉ（ｉ＝１〜ｎ）の各々の関数ノードを対応するエッジと共に含む。関数ノード４０１は、変数ｘｉ（ｉ＝１〜ｎ）である引数（または独立変数）を有する関数を表すことに留意されたい。変数ｘｉ及びｕｉ，０に対応するエッジは、「＝」関数ノードによって接続され、該関数ノードは、値が、
【数４７】
2010535459.tif 000049
である一致関数（equalityfunction。または、等値関数）ノードである。関数Ａｉ及びＢｊの関数ノード４０２及び４０３が図示されている。Ａｉ及びＢｊは、該ＬＰの一致及び不一致に関連するペナルティー関数（または損失関数）を表す。これらの関数ノードは、対応する一致及び不一致が満たされているか否かに応じて、０と無限大のいずれかとして推定（または評価）される。また、エッジ４０５と４０６は、値が、
【数４８】
2010535459.tif 000050
の一致関数ノードである「＝」によって接続されていることにも留意されたい。
【００４２】
いわゆる双対ＬＰを、式６に示されている主ＬＰに関連付けることができる。主ＬＰと双対ＬＰとは異なるＬＰであるが、一方の解を他方の解を求めるのに使用できる場合がしばしばある。詳細に後述するように、ＦＦＧを用いて双対ＬＰを表すことができる。
【００４３】
双対ＬＰは次のように式８によって定義される。
【００４４】
式８：
【数４９】
2010535459.tif 000051
とう制約下で、
【数５０】
2010535459.tif 000052
を最大にする。
【００４５】
本明細書では、<ベクトル１、ベクトル２>という表現は、ベクトル１とベクトル２という２つのベクトルの内積を意味する。制約を追加の費用項（cost term）として表すと、上記の最大化問題は、拡張された費用関数、すなわち、
【数５１】
2010535459.tif 000053
の（制約のない）最大化と等価である。各ｉ
【数５２】
2010535459.tif 000054
について、変数
【数５３】
2010535459.tif 000055
は、１つの不一致に関与する（または、１つの不等式に含まれる）だけであるので、ＤＬＰＤ２内の一致符号を対応する不一致符号に置き換えても最適解は変わらない。同じことが全ての
【数５４】
2010535459.tif 000056
にも当てはまる。
【００４６】
式８において、
【数５５】
2010535459.tif 000057
は費用関数を表す。
【数５６】
2010535459.tif 000058
は、双対ＬＰ内の変数である。ｎは、符号語内のシンボルの数である。λｉは、式１に関連して述べたように、各変数ノードにおけるＬＬＲである。双対ＬＰの任意の解は、
【数５７】
2010535459.tif 000059
を満たさなければならないので、時間及びメモリ空間を節約するためには、双対ＬＰを解くときに、
【数５８】
2010535459.tif 000060
のうちのいずれか１つの変数の集合だけを考慮すればよい。
【００４７】
図５は、式８において示される双対ＬＰの拡張された費用関数の一部のＦＦＧ５００を示す。関数ノード５０１は関数
【数５９】
2010535459.tif 000061
を表す。関数ノード５０２及び５０３は、上述したように、関数
【数６０】
2010535459.tif 000062
を表す。エッジ５０５と５０６は、「〜」関数ノードによって接続されていることに留意されたい。双対ＬＰでは、「〜」関数ノードは、そのような関数ノードがエッジｕとｖに接続されている場合には、関数値が、
【数６１】
2010535459.tif 000063
であるということを意味する。
【００４８】
ＦＦＧの代わりに、他のタイプのグラフを用いて式７の主ＬＰ及び式８の双対ＬＰを表すことができる。ファクターグラフ（factor graph。または、因子グラフ）やタナーグラフ（Tanner graph）などのグラフを用いて、ＬＰを図に表すことができる。
【００４９】
座標上昇法（座標上昇アルゴリズムとも呼ばれる）を用いて、双対ＬＰを解くことができる。なぜなら、双対ＬＰは、式８で示されている制約下で、
【数６２】
2010535459.tif 000064
の最大値を決定することによって求められるからである。Vontobel他のセクション６には、座標上昇型アルゴリズムを用いて式８に示されている双対ＬＰを解くことが開示されている。Vontobel他の開示によれば、座標上昇型アルゴリズムを用いて双対ＬＰを解くことの主なアイデアは、更新スケジュールにしたがってエッジ
【数６３】
2010535459.tif 000065
を選択することである。選択された各エッジについて、双対費用関数が増加するか、少なくとも減少しないように、
【数６４】
2010535459.tif 000066
の前の（古い）値を新しい値で置き換える。たとえば、図５を参照すると、関数ノード５０２は、３つの出エッジ（outgoing edge）５０５、５０７、及び５０８を有する。一回の繰り返しで、変数
【数６５】
2010535459.tif 000067
の１つを表すエッジ５０５などのエッジの１つが選択される。エッジ５０７及び５０８によって表される変数を含む、他の全ての変数は（たとえば一定値に）固定される。次に、双対費用関数
【数６６】
2010535459.tif 000068
が減少しないように、エッジ５０５によって表される変数
【数６７】
2010535459.tif 000069
の値が選択される。次に、別の繰り返しにおいて、別のエッジが選択されて、他の全ての変数が一定値に維持される。次に、双対費用関数が減少しないようにその変数の値が選択される。以下、残りの変数についても同様である。これは、かなり時間のかかる処理となりえ、特に、数百または数千ものビットを有する大きな符号語の場合にはそうである。
【００５０】
１実施形態によれば、複数の変数を１つの繰り返しにおいて変化させて双対ＬＰの解を求めることができるように座標上昇法を用いて双対ＬＰを解く。複数の変数が各繰り返しにおいて変更されるので、復号時間を短くすることができる。また、一般的に、双対ＬＰの費用関数が減少しないことを保証するためには計算が複雑になるので、座標上昇関数の一回の繰り返しで複数の変数を変えることは簡単に理解されることではないかもしれない。しかしながら、研究及び試験を通じて、座標上昇法の一回の繰り返しで変化する特定の変数を選択することによって双対ＬＰの解法を簡単にする後述の定式化が決定された。複数の変数は、双対ＬＰを表すＦＦＧ中の関数ノードに付随する（または入射する）エッジによって表される全ての変数を含みうる。たとえば、ＦＦＧ５００では、双対費用関数が減少しないように、出エッジ５０５、５０７及び５０８によって表される全ての変数が単一の繰り返しで変更される。ｕ'ｉ,０＝−ｘ'ｉであるので、エッジｕ'ｉ,０は変更されない場合があることに留意されたい。したがって、ｕ'ｉ,０に対して１つの値のみがあり、該値は、ｕ'ｉ,０（この場合、ｕ'ｉ,０＝−ｘ'ｉ）に割り当てられている値である。所与の
【数６８】
2010535459.tif 000070
について、ベクトル
【数６９】
2010535459.tif 000071
が、全ての変数
【数７０】
2010535459.tif 000072
を含む長さ
【数７１】
2010535459.tif 000073
のベクトルを示すものとする。
【数７２】
2010535459.tif 000074
は、Ａ’を表す任意の関数ノードに対する座標上昇法における一回の繰り返しで更新される全ての変数を含むベクトルである。双対ＬＰにおいて示される費用関数が減少しないように、関数
【数７３】
2010535459.tif 000075
を用いて、ベクトル
【数７４】
2010535459.tif 000076
内の全ての変数の値を決定することができる。式９は、
【数７５】
2010535459.tif 000077
を次のように定義する。
【００５１】
【数７６】
2010535459.tif 000078
【数７７】
2010535459.tif 000079
は、ベクトル
【数７８】
2010535459.tif 000080
中の変数を変更することによって影響を受ける双対費用関数の部分を表す。
【数７９】
2010535459.tif 000081
の解は、
【数８０】
2010535459.tif 000082
が最大になるポイントである。具体的には、
【数８１】
2010535459.tif 000083
は、次の（ｄｉ＋１）のポイント（点）の任意のポイントで最大になり、したがって、それらの凸包で最大になる。
【数８２】
2010535459.tif 000084
【００５２】
ｃは、長さｄｉで、かつ、ｋ番目の成分が、
【数８３】
2010535459.tif 000085
に等しいベクトルである。j(k)は、
【数８４】
2010535459.tif 000086
におけるｋ番目の要素であり、
【数１５０】
2010535459.tif 000087
である。また、
【数８５】
2010535459.tif 000088
である。ベクトル
【数８６】
2010535459.tif 000089
は、それぞれ、ベクトル
【数８７】
2010535459.tif 000090
であり、この場合、ｉ番目の位置は省かれている。
【数８８】
2010535459.tif 000091
は、上記のポイント（ｄｉ＋１）のうちの任意のポイントで最大になり、したがって、それらの凸包の任意のポイントで最大になる。したがって、それらのポイントのうちの任意のポイントを、双対費用関数の解として選択することができる。
【数８９】
2010535459.tif 000092
の最大値を迅速かつ効率的に計算することができ、これによって、より速い復号処理が提供されることに留意されたい。一般に、
【数９０】
2010535459.tif 000093
が最大になるポイントということに加えて、
【数９１】
2010535459.tif 000094
がその現在値に対して減少しない任意の
【数９２】
2010535459.tif 000095
を、解として使用できることに留意されたい。
【００５３】
上述したように、座標上昇法は、各々の繰り返しにおいて１つの変数を変化させる代わりに、各々の繰り返しにおいて複数の変数を同時に変化させる。複数の変数は、ＦＦＧ５００中の関数ノードに関連付けられている。１実施形態では、関数ノードの１つに関連付けられている複数の変数の集合は、座標上昇法の各繰り返しに対してランダムに選択され、これによって、復号時間を改善する（短くする）ことができる。
【００５４】
式９において、
【数９３】
2010535459.tif 000096
は、Ａ'ｉを表す任意の関数ノードについて座標上昇法における単一の繰り返しで更新される全ての変数を含むベクトルである。Ｂ'ｊを表すＦＦＧ５００中のノード（たとえば、ノード５０３）に対する一回の繰り返しで、複数の変数を変更することができる。これらの変数は、ノード５０３の出エッジを含む。以下に示す式１０は、双対ＬＰにおいて示される費用関数が減少しないように、ベクトル
【数９４】
2010535459.tif 000097
中の全ての変数の値を決定するための関数
【数９５】
2010535459.tif 000098
を定義し、ここで、
【数９６】
2010535459.tif 000099
は、Ｂ'ｊを表す任意の関数ノードについて座標上昇法における単一の繰り返しで更新される全ての変数を含むベクトルである。式１０は、
【数９７】
2010535459.tif 000100
を次のように定義する。
【００５５】
【数９８】
2010535459.tif 000101
【００５６】
式１０は、関数ノードＢ'ｊの出エッジに対応する全ての変数を更新するために使用される。関数ノードＢ'ｊが次数ｋを有し、
【数９９】
2010535459.tif 000102
であると仮定する。
【数１００】
2010535459.tif 000103
を最大にする
【数１０１】
2010535459.tif 000104
の集合は凸集合であるが、この集合は、式９を最大にするために得られたポイントの集合とは対照的に（説明するには）かなり複雑であることが容易に理解されよう。したがって、以下では、
【数１０２】
2010535459.tif 000105
を最大にする集合中の１つのポイント（このポイントは、一般的には集合の中間にある）ついて説明する。次の表記を使用する。｜λ｜は、λの絶対値を表す。
【数１０３】
2010535459.tif 000106
は、
【数１０４】
2010535459.tif 000107
の符号、及び、
【数１５１】
2010535459.tif 000108
を表す。さらに、
【数１０５】
2010535459.tif 000109
は、
【数１０６】
2010535459.tif 000110
となるように順序付けられる。この場合、中間のポイントは、
【数１０７】
2010535459.tif 000111
によって与えられる。
【数１０８】
2010535459.tif 000112
の定式化（または表現）はほぼ同じであるであることに留意されたい。また、上述の、
【数１０９】
2010535459.tif 000113
を最大にする集合中の１つのポイントに代えて、関数
【数１１０】
2010535459.tif 000114
が減少しないように、一般に、任意の
【数１１１】
2010535459.tif 000115
を選択できることに留意されたい。
【００５７】
式８中の双対ＬＰの解を用いて、式７中の主ＬＰの解を得ることができる。以下の式１１にしたがって、符号語の推定値
【数１１２】
2010535459.tif 000116
が設定される。
【００５８】
【数１１３】
2010535459.tif 000117
【００５９】
式１１に示されているように、
【数１１４】
2010535459.tif 000118
の場合には、
【数１１５】
2010535459.tif 000119
は０に等しく、
【数１１６】
2010535459.tif 000120
の場合には、
【数１１７】
2010535459.tif 000121
は１に等しい。また（他の場合には）、
【数１１８】
2010535459.tif 000122
である。「？」は、ビット
【数１１９】
2010535459.tif 000123
が０か１かをデコーダが決定できないことを意味する。この場合、再送または再読み込みを実行することができる。
【００６０】
図６は、１実施形態による、データを復号（デコード）するための方法６００のフローチャートを示す。図６を、限定ではなく例示として、図１〜５に関して説明することができる。
【００６１】
ステップ６０１では、符号化されたデータが受信される。たとえば、図１に示す符号化されたデータｙがデコーダ１０４によって受信される。
【００６２】
ステップ６０２では、受信したデータを復号するためにＬＰが決定される。このＬＰは式６及び７に記述されている。このＬＰは、特定の符号語が通信チャンネルを介して送信された場合に特定の語（ワード）が受信される確率に関連する費用関数を含む。このＬＰは、式８において示される双対ＬＰとして定式化され、ステップ６０２におけるＬＰはこの双対ＬＰを含むことができる。
【００６３】
ステップ６０３では、一回の繰り返しで費用関数に関連する複数の変数を変更する座標上昇法を用いて、ステップ６０２からのＬＰの解を求める。たとえば、任意のＡ'ｉについて、式９を解いて双対ＬＰの解を改善する。任意のＢ'ｊについて、式１０を解いて双対ＬＰの解を改善する。
【数１２０】
2010535459.tif 000124
及び、それぞれの
【数１２１】
2010535459.tif 000125
を最大にする解を選択することができる。
【００６４】
ステップ６０４では、送信された符号語を、ステップ６０３からの解を用いて、受信した符号化されたデータから推定する。式１１は、この解を送信された符号語の推定値に変換することを記述している。
【００６５】
図７は、１実施形態による、デコーダ７００の例示的なブロック図を示す。デコーダ７００は、ソフトウエアを実行するための実行プラットホームを提供するプロセッサ７０１などの１つ以上のプロセッサを備える。デコーダ７００は、また、図１に示すデータｙなどの通信チャンネルを介して受信されたデータを格納するためのデータ記憶装置７０２を備える。プロセッサ７０１は、上述の方法６００及び他の処理ステップに関して説明したように、受信したデータを復号するように動作可能である。デコーダ７００はメモリ７０３を備え、ソフトウエアは実行中はこのメモリに常駐することができる。このソフトウエアは、データを復号するために上述のステップを具現化（して実行）することができる。
【００６６】
具体的には、本明細書に記載した方法６００及び他の処理ステップを、メモリ７０３などのコンピュータ読み取り可能媒体に組み込まれて、プロセッサ７０１などのプロセッサによって実行されるソフトウエアとして実施することができる。これらのステップを、アクティブ及び非アクティブの種々の形態で存在することができるコンピュータプログラムによって具現化することができる。たとえば、それらのプログラムは、ソースコード、オブジェクトコード、実行可能コード、または、上記ステップのいくつかを実行するための他のフォーマットの形態のプログラム命令からなるソフトウエアプログラムとして存在しうる。これらのうちの任意のものを、記憶装置を備え、及び圧縮された形態または非圧縮形態の信号を含むコンピュータ読み取り可能媒体に組み込むことができる。好適なコンピュータ読み取り可能記憶装置の例には、従来のコンピュータシステムＲＡＭ（ランダムアクセスメモリ）、ＲＯＭ（読出し専用メモリ）、ＥＰＲＯＭ（消去可能なプログラマブルＲＯＭ）、ＥＥＰＲＯＭ（電気的に消去可能なプログラマブルＲＯＭ）及び、磁気ディスク、光ディスク、（磁気）テープが含まれる。コンピュータ読み取り可能信号の例には、キャリヤを用いて変調されるか否かにかかわらず、その信号をアクセスするように、コンピュータプログラムをホストしまたは実行するコンピュータシステムを構成することができるところの信号があり、これには、インターネットまたは他のネットワークを介してダウンロードされる信号が含まれる。これらの具体的な例には、ＣＤ−ＲＯＭで配布されるプログラムやインターネットからダウンロードされる配信プログラムが含まれる。ある意味では、抽象的な実体としてのインターネットそのものが、１つのコンピュータ読み取り可能媒体である。このことは、一般にコンピュータネットワークにも言える。
【００６７】
当業者には、デコーダ７００が一般的なデコーダを例示しており、デコーダ７００において使用できる多くの従来のコンポーネントが示されていないことが明らかであろう。
【００６８】
いくつかの実施形態をいくつかの例を参照して説明したが、当業者は、特許請求の範囲に含まれる実施形態の範囲から逸脱することなく、説明した実施形態に種々の変更を施すことができるであろう。
【図１】
2010535459.tif 000135
【図２】
2010535459.tif 000136
【図３】
2010535459.tif 000137
【図４】
2010535459.tif 000138
【図５】
2010535459.tif 000139
【図６】
2010535459.tif 000140
【図７】
2010535459.tif 000141
【国際調査報告】
2010535459.tif 000142
2010535459.tif 000143