図面 (/)

技術 符号化・復号化システム及び方法及び符号化プログラム及び復号化プログラム

出願人 日本電信電話株式会社国立大学法人東京大学
発明者 三宅茂樹村松純山本博資
出願日 2012年5月24日 (7年1ヶ月経過) 出願番号 2012-119002
公開日 2013年12月9日 (5年7ヶ月経過) 公開番号 2013-247474
状態 特許登録済
技術分野 圧縮、伸長・符号変換及びデコーダ 符号誤り検出・訂正
主要キーワード 条件付確率密度関数 エネルギー制約 エントロピー関数 歪み限界 歪情報 歪み関数 疎行列 歪み情報
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2013年12月9日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (11)

課題

連続アルファベット上の通信系において、符号化限界に近い性能を示しつつ効率的に符号化を実現する。

解決手段

本発明は、有歪み情報符号化装置では、連続情報源からの出力xNを、疎行列条件付確率密度関数を用いてスカラー量子化し、スカラー量子化された結果を用いて最適化処理を行うことでベクトル量子化を行い、φ(xN)を出力し、出力されたφ(xN)に、疎行列Bを掛けることで符号語mKを求める。有歪み情報源復号化装置では、符号化装置から入力された符号語mKを、疎行列A、B、L次元ベクトルcL用いて最適化処理を行うことで、情報符号化された連続アルファベットを復号化する。

概要

背景

従来では、符号化の理論限界への到達よりも符号化を効率的に処理できることの方が重視されてきた。ところが、1990年代通信路符号化の分野で効率的な符号化・復号化が可能でありながら、かつ符号化レートが理論限界に近づくまでに到達可能であるLDPC(Low Density Parity Check)符号やターボ符号出現した。それ以降、効率的な符号処理も符号化レートの理論限界への到達も同時に実現を目指すような符号の考案が大きな位置を占めるようになった。しかしながら、LDPC符号やそれに類する符号の適用先は殆どが離散アルファベット通信系であり、連続系への適用例としてよく知られているのは2入力(0−1入力)実数出力のAWGN(Additive White Noise Gaussian)通信路くらいである。典型的な連続通信路であるガウス型通信路に対してもシャノン限界を達成する符号語の配置は与えることができても、あるメッセージを効率的に符号化・復号化する手段は知られていない。連続アルファベットの有歪情報源符号化に関しても同様である。

以下では通信系を情報源符号化と通信路符号化に分けて従来技術を概説し、さらに近年効率的な符号化実現方式のひとつであるとして議論されている疎行列符号化について言及する。

1.有歪み情報源符号化
連続アルファベットを出力とする情報源としてガウス型情報源に関してはシャノン限界を達成する符号の存在が示されているが(例えば、非特許文献1参照)、効率的な符号に関する検討はあまりなされていない。有歪み情報源符号化の実現方式としてはスカラー量子化ベクトル量子化がある。

・スカラー量子化:容易に実現可能であるが(例えば、非特許文献2参照)、符号化の理論限界(レー歪み関数で示される)に近づき得ない。

・ベクトル量子化:現実的なアルゴリズムが数多く提案されているが(例えば、非特許文献2参照)、符号化処理を効率的に行わせるために理論限界への到達性犠牲にしている。

2.通信路符号化
・連続アルファベットを入出力とする通信路に関しては、理論的にはガウス型通信路の様な対称性を持つ通信路に関してはシャノン限界を達成する符号の存在が示されているが(例えば、非特許文献1参照)、効率的な符号に関する検討はあまりなされていない。LDPC符号の連続通信路への応用として、入力は2値,出力は連続であるAWGN通信路が知られている(例えば、非特許文献3参照)。

3.疎行列符号化
・離散アルファベット上の通信系に対しては,様々な符号化方式(例えば、非特許文献4,5参照)が提案されており、理論的には符号化限界に到達することが示されている。さらに、sum-product法やLP(Linear Programming)復号法などの適切な実現アルゴリズムによって効率的に実現可能であることが近年シミュレーション等で示されつつある。一方で、連続アルファベットに関しては未だ検討は行われていない。なお、多値アルファベットの符号の実現方式については例えば線形復号法(以下LP復号法)を使ったもの(例えば、非特許文献6参照)等がある。

概要

連続アルファベット上の通信系において、符号化限界に近い性能を示しつつ効率的に符号化を実現する。 本発明は、有歪み情報源符号化装置では、連続情報源からの出力xNを、疎行列、条件付確率密度関数を用いてスカラー量子化し、スカラー量子化された結果を用いて最適化処理を行うことでベクトル量子化を行い、φ(xN)を出力し、出力されたφ(xN)に、疎行列Bを掛けることで符号語mKを求める。有歪み情報源復号化装置では、符号化装置から入力された符号語mKを、疎行列A、B、L次元ベクトルcL用いて最適化処理を行うことで、情報符号化された連続アルファベットを復号化する。

目的

本発明は、上記の点に鑑みなされたもので、上記の条件を満たし、連続アルファベット上の通信系において、符号化限界に近い性能を示しつつ、効率的な実現も可能とするような符号化・復号化システム及び方法及び符号化プログラム及び復号化プログラムを提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

連続アルファベットを符号化・復号化する符号化・復号化システムであって、予め、疎行列A、B、及びL次元ベクトルcL、条件付確率密度関数w(y|x)が格納された記憶手段と、連続情報源からの出力xNを、前記疎行列、前記条件付確率密度関数を用いてスカラー量子化し、スカラー量子化された結果を用いて最適化処理を行うことでベクトル量子化を行い、φ(xN)を出力するベクトル量子化手段と、前記ベクトル量子化手段の出力φ(xN)に、前記疎行列Bを掛けることで符号語mKを求める符号化手段と、を具備した情報符号化装置を有することを特徴とする符号化・復号化システム。

請求項2

前記ベクトル量子化手段は、歪み限界への到達性保証するための条件を、(但し、pは連続情報源、Δは正の実数、wは条件付確率密度関数)とする請求項1記載の符号化・復号化システム。

請求項3

予め、疎行列A、B、及びL次元横ベクトルcL、条件付確率密度関数w(y|x)が格納された記憶手段と、前記符号化装置から入力された符号語mKを、前記疎行列A、B、前記をL次元横ベクトルcL用いて最適化処理を行うことで復号化を行う復号化手段を具備した、情報符号化された連続アルファベットを復号化する情報復号化装置を更に有する請求項1記載の符号化・復号化システム。

請求項4

連続アルファベットを入出力とする通信路を対象とする符号化・復号化システムであって、予め、疎行列A、B、及びL次元横ベクトルcL、確率密度関数p(x)が格納された記憶手段と、前記確率密度関数p(x)をスカラー量子化し、スカラー量子化したものをとし、請求項1記載の情報符号化装置の出力を、前記疎行列A、B、前記L次元横ベクトルcL、及び量子化されたを用いて最適化を行うことにより符号化を行う符号化手段と、具備した通信路符号化装置を有することを特徴とする符号化・復号化システム。

請求項5

前記符号化手段は、レー限界への到達性を保証するための条件を、(但し、pは連続情報源、Δは正の実数、wは条件付確率密度関数)とする請求項4記載の符号化・復号化システム。

請求項6

予め、疎行列A、B、及びL次元横ベクトルcLが格納された記憶手段と、連続通信路から出力されたyNを、前記疎行列A、及びL次元横ベクトルcLを用いて最適化処理を行う最適化手段と、前記最適化手段の出力に前記疎行列Bを掛けることでを求めるメッセージ推定手段と、を具備した通信路復号化装置を更に有する請求項4記載の符号化・復号化システム。

請求項7

連続アルファベットを符号化・復号化する符号化・復号化方法であって、符号化装置において、予め、疎行列A、B、及びL次元横ベクトルcL、条件付確率密度関数w(y|x)を記憶手段記憶格納しておき、ベクトル量子化手段が、連続情報源からの出力xNを、前記疎行列、前記条件付確率密度関数を用いてスカラー量子化し、量子化された結果を用いて最適化処理を行うことでベクトル量子化を行い、φ(xN)を出力するベクトル量子化ステップと、符号化手段が、前記ベクトル量子化ステップにより出力されたφ(xN)に、前記疎行列Bを掛けることで符号語mKを求める符号化ステップと、を行うことを特徴とする符号化・復号化方法。

請求項8

復号化装置において、予め、疎行列A、B、及びL次元横ベクトルcL、条件付確率密度関数w(y|x)を記憶手段に格納しておき、復号化手段が、前記符号化装置から入力された符号語mKを、前記疎行列A、B、前記をL次元横ベクトルcL用いて最適化処理を行うことで、情報符号化された連続アルファベットを復号化する情報復号化ステップをさらに行う請求項7記載の符号化・復号化方法。

請求項9

連続アルファベットを入出力とする通信路を対象とする符号化方法であって、符号化装置において、予め、疎行列A、B、及びL次元横ベクトルcL、確率密度関数p(x)を記憶手段に格納しておき、符号化手段が、前記確率密度関数p(x)をスカラー量子化し、スカラー量子化したものをとし、請求項1記載の情報符号化装置の出力を、前記疎行列A、B、、前記L次元横ベクトルcL、及びスカラー量子化されたを用いて最適化を行うことにより符号化を行う符号化ステップを行うことを特徴とする符号化・復号化方法。

請求項10

復号化装置において、予め、疎行列A、B、及びL次元横ベクトルcLを記憶手段に格納しておき、最適化手段が、連続通信路から出力されたyNを、前記疎行列A、及びL次元横ベクトルcLを用いて最適化処理を行う最適化ステップと、メッセージ推定手段が、前記最適化手段の出力に前記疎行列Bを掛けることでを求めるメッセージ推定ステップと、を行う請求項9記載の符号化・復号化方法。

請求項11

コンピュータを、請求項1または2に記載の符号化・復号化システムの符号化装置の各手段として機能させるための符号化プログラム

請求項12

コンピュータを、請求項3に記載の符号化・復号化システムの復号化装置の各手段として機能させるための復号化プログラム

請求項13

コンピュータを、請求項4または5に記載の符号化・復号化システムの符号化装置の各手段として機能させるための符号化プログラム。

請求項14

コンピュータを、請求項6に記載の符号化・復号化システムの復号化装置の各手段として機能させるための復号化プログラム。

技術分野

0001

本発明は、符号化・復号化システム及び方法及び符号化プログラム及び復号化プログラム係り、特に、連続アルファベット上の通信系において、理論で示される符号化限界にいくらでも近づき得るような疎行列符号化を実現するための符号化・復号化システム及び方法及び符号化プログラム及び復号化プログラムに関する。

背景技術

0002

従来では、符号化の理論限界への到達よりも符号化を効率的に処理できることの方が重視されてきた。ところが、1990年代通信路符号化の分野で効率的な符号化・復号化が可能でありながら、かつ符号化レートが理論限界に近づくまでに到達可能であるLDPC(Low Density Parity Check)符号やターボ符号出現した。それ以降、効率的な符号処理も符号化レートの理論限界への到達も同時に実現を目指すような符号の考案が大きな位置を占めるようになった。しかしながら、LDPC符号やそれに類する符号の適用先は殆どが離散アルファベットの通信系であり、連続系への適用例としてよく知られているのは2入力(0−1入力)実数出力のAWGN(Additive White Noise Gaussian)通信路くらいである。典型的な連続通信路であるガウス型通信路に対してもシャノン限界を達成する符号語の配置は与えることができても、あるメッセージを効率的に符号化・復号化する手段は知られていない。連続アルファベットの有歪情報源符号化に関しても同様である。

0003

以下では通信系を情報源符号化と通信路符号化に分けて従来技術を概説し、さらに近年効率的な符号化実現方式のひとつであるとして議論されている疎行列符号化について言及する。

0004

1.有歪み情報源符号化
連続アルファベットを出力とする情報源としてガウス型情報源に関してはシャノン限界を達成する符号の存在が示されているが(例えば、非特許文献1参照)、効率的な符号に関する検討はあまりなされていない。有歪み情報源符号化の実現方式としてはスカラー量子化ベクトル量子化がある。

0005

・スカラー量子化:容易に実現可能であるが(例えば、非特許文献2参照)、符号化の理論限界(レー歪み関数で示される)に近づき得ない。

0006

・ベクトル量子化:現実的なアルゴリズムが数多く提案されているが(例えば、非特許文献2参照)、符号化処理を効率的に行わせるために理論限界への到達性犠牲にしている。

0007

2.通信路符号化
・連続アルファベットを入出力とする通信路に関しては、理論的にはガウス型通信路の様な対称性を持つ通信路に関してはシャノン限界を達成する符号の存在が示されているが(例えば、非特許文献1参照)、効率的な符号に関する検討はあまりなされていない。LDPC符号の連続通信路への応用として、入力は2値,出力は連続であるAWGN通信路が知られている(例えば、非特許文献3参照)。

0008

3.疎行列符号化
・離散アルファベット上の通信系に対しては,様々な符号化方式(例えば、非特許文献4,5参照)が提案されており、理論的には符号化限界に到達することが示されている。さらに、sum-product法やLP(Linear Programming)復号法などの適切な実現アルゴリズムによって効率的に実現可能であることが近年シミュレーション等で示されつつある。一方で、連続アルファベットに関しては未だ検討は行われていない。なお、多値アルファベットの符号の実現方式については例えば線形復号法(以下LP復号法)を使ったもの(例えば、非特許文献6参照)等がある。

先行技術

0009

T. M. Cover and J. A. Thomas, Elements of Information Theory 2ndEd., Wiley, 2006.
Gersho and R. M. Gray, Vector Quantization and Signal Compression, Kluwer Academic, 1992.
和田山正,低密度検査符号とその復号法,トリケップス, 2002.
S. Miyake and J. Muramatsu, "A construction of lossy source code using LDPC matrices,"IEICE Trans. Fundamentals, vol. E91-A, no. 6, pp. 1488-1501, 2008.
Muramatsu and S. Miyake, "Hash property and coding theorems for sparse matrices and maximum-likelihood coding, "IEEE Trans. Inform. Theory, vol. 56, no. 5, pp. 2143-2162, 2010.
本多淳也, 山本博資, "拡大体上のLDPC符号の線形計画法による復号法, "第33回情報理論とその応用シンポジウム(SITA2010)予稿集, pp. 121-126, 2010.

発明が解決しようとする課題

0010

スカラー量子化を用いて連続アルファベットを適切に離散化し、そこで疎行列符号化を適用するアルゴリズムを考える。その際に、
・通常は通信系の統計的な性質は明らかでない。従って通信系の統計的な性質に依存しない符号(ユニバーサル符号)となるよう構成する:
量子化幅Δを小さくする際の条件を明確にする。特に量子化幅Δが小さくなった極限で、相互情報量などの符号化レートに関連する量が連続系における対応する量に近づかなければならない:
という点に注意する必要がある。

0011

本発明は、上記の点に鑑みなされたもので、上記の条件を満たし、連続アルファベット上の通信系において、符号化限界に近い性能を示しつつ、効率的な実現も可能とするような符号化・復号化システム及び方法及び符号化プログラム及び復号化プログラムを提供することを目的とする。

課題を解決するための手段

0012

上記の課題を解決するため、本発明(請求項1)は、連続アルファベットを符号化・復号化する符号化・復号化システムであって、
予め、疎行列A、B、及びL次元ベクトルcL、条件付確率密度関数w(y|x)が格納された記憶手段と、
連続情報源からの出力xNを、前記疎行列、前記条件付確率密度関数を用いて量子化し、量子化された結果

0013

を用いて最適化処理を行うことでベクトル量子化を行い、φ(xN)を出力するベクトル量子化手段と、
前記ベクトル量子化手段の出力φ(xN)に、前記疎行列Bを掛けることで符号語mKを求める符号化手段と、を具備する情報符号化装置を有する。

0014

また、本発明(請求項2)は、前記ベクトル量子化手段において、
歪み限界への到達性を保証するための条件を、

0015

(但し、pは連続情報源、Δは正の実数、wは条件付確率密度関数、P、Wはそれぞれスカラー量子化後のp及びwに対応する確率分布関数
とする。

0016

また、本発明(請求項3)は、予め、疎行列A、B、及びL次元横ベクトルcL、条件付確率密度関数w(y|x)が格納された記憶手段と、
前記符号化装置から入力された符号語mKを、前記疎行列A、B、前記をL次元横ベクトルcL用いて最適化処理を行うことで復号化を行う復号化手段を具備した情報符号化された連続アルファベットを復号化する情報復号化装置を更に有する。

0017

本発明(請求項4)は、連続アルファベットを入出力とする通信路を対象とする符号化・復号化システムであって、
予め、疎行列A、B、及びL次元横ベクトルcL、確率密度関数p(x)が格納された記憶手段と、
前記確率密度関数p(x)を量子化し、量子化したものを

0018

とし、請求項1記載の情報符号化装置の出力を、前記疎行列A、B、前記L次元横ベクトルcL、及び量子化された

0019

を用いて最適化を行うことにより符号化を行う符号化手段と、具備する通信路符号化装置を有する。

0020

また、本発明(請求項5)は、前記符号化手段において、
レート限界への到達性を保証するための条件を、

0021

(但し、pは連続情報源、Δは正の実数、wは条件付確率密度関数、P、Wはそれぞれスカラー量子化後のp及びwに対応する確率分布関数)
とする。

0022

また、本発明(請求項6)は、予め、疎行列A、B、及びL次元横ベクトルcLが格納された記憶手段と、
連続通信路から出力されたyNを、前記疎行列A、及びL次元横ベクトルcLを用いて最適化処理を行う最適化手段と、
前記最適化手段の出力

0023

に前記疎行列Bを掛けることで

0024

を求めるメッセージ推定手段と、を具備する通信路復号化装置を更に有する。

発明の効果

0025

通常の連続系におけるデータ圧縮(有歪み情報源符号化)に関しては、サンプリングスカラー(量子化)の後、量子化された量をさらに2値化した後、符号化を行うが、本発明によれば、スカラー量子化後の2値化の処理は不要となるので、従来よりも効率的な処理が可能となる。

0026

一方、誤り訂正(通信路符号化)に関しては、AWGN通信路に限ることなく、連続アルファベットを持つ一般の通信路に対しても、本発明で示した疎行列符号化を適用することでシャノン限界に迫る伝送レートを持ち、かつ、効率的に実現可能となる。

図面の簡単な説明

0027

本発明の一実施の形態における符号化・復号化システムの構成図である。
本発明の一実施の形態における有歪み符号化器の構成図である。
本発明の一実施の形態における有歪み符号化器の動作のフローチャートである。
本発明の一実施の形態における有歪み復号化器の構成図である。
本発明の一実施の形態における有歪み復号化器の動作のフローチャートである。
本発明の一実施の形態における通信路符号化器の構成図である。
本発明の一実施の形態における通信路符号化器の動作のフローチャートである。
本発明の一実施の形態における通信路復号化器の構成図である。
本発明の一実施の形態における通信路復号化器の動作のフローチャートである。
本発明の一実施の形態における実数の量子化を示す図である。

実施例

0028

以下、図面と共に本発明の実施の形態を説明する。

0029

図1は、本発明の一実施の形態における符号化・復号化システム構成図である。

0030

本発明の符号化・復号化システムは、情報源及び通信路に適用する符号化器と復号化器を有する。同図に示すように、情報源に適用され、連続アルファベットを符号化する有歪み符号化器100と、情報符号化された連続アルファベットを復号化する有歪み符号化器200と、通信路に適用される、連続アルファベットを入出力とし、符号化を行う通信路符号化器300、復号化を行う通信路復号化器400、から構成される。

0031

以下に動作の概要を示す。

0032

<有歪み符号化器100>
データ圧縮のための有歪み符号化器100は、図2に示すように、ベクトル量子化部110と符号化部120を有する。ベクトル量子化部110は、疎行列A及び最適化のためのベクトルcL、条件付確率密度関数(w(y|x))をメモリ(図示せず)に保持し、符号化部120は、疎行列Bをメモリ(図示せず)に保持するものとする。

0033

図3は、本発明の一実施の形態における有歪み符号化器の動作のフローチャートである。

0034

ベクトル量子化部110では、連続情報源からの出力[連続アルファベット]xNを取得すると(ステップ101)、メモリ(図示せず)に格納された行列A、ベクトルcL、条件付確率密度関数(w(y|x))を用いてスカラー量子化し(ステップ102)、その結果

0035

を用いて最適化処理を行うことでベクトル量子化を行い、φ(xN)を出力する(ステップ103)。符号化部120は、ベクトル量子化部110の出力φ(xN)に疎行列Bを掛けることで、符号語信号mKを求める(ステップ104)。

0036

当該有歪み符号化器100の詳細な動作については後述する。

0037

<有歪み復号化器200>
有歪み情報源符号化されたデータを復号する有歪み復号化器200は、図4に示すように、復号化部210を有する。復号化部210は、疎行列A、BとベクトルcLをメモリ(図示せず)保持する。

0038

図5は、本発明の一実施の形態における有歪み復号化器の動作のフローチャートである。

0039

復号化部210は、符号語mKを取得し(ステップ201)、入力された符号語mKについて、疎行列A、B、及びベクトルcLを用いて最適化処理を行うことで復号化を行う(ステップ202)。

0040

<通信路符号化器300>
次に、通信路符号化器300は、図6に示すように符号化部310を有する。符号化部310は、疎行列A、B、及び最適化のためのベクトルcLをメモリ(図示せず)に保持するものとする。

0041

図7は、本発明の一実施の形態における通信路符号化器の動作のフローチャートである。

0042

符号化部310は、相手に伝えるメッセージmKを取得し(ステップ301)、保持している疎行列A、B及びベクトルcL及び、取得したmKを用いて最適化を行うことで符号化を行う(ステップ302)。なお、通信路符号化器300の詳細な動作については後述する。

0043

<通信路復号化器400>
次に、通信路復号化器400は、図8に示すように、復号化部410とメッセージ推定部420を有する。なお、復号化部410は、疎行列A及びベクトルcLをメモリ(図示せず)に保持しているものとする。また、メッセージ推定部420は、疎行列Bをメモリ(図示せず)に保持しているものとする。

0044

図9は、本発明の一実施の形態における通信路復号化器の動作のフローチャートである。

0045

復号化部410は、連続通信路からの出力yNを取得し(ステップ401)、保持している疎行列A及びベクトルをcL用いて、最適化処理を行うことで復号化を行う(ステップ402)。メッセージ推定部420は、復号化部410の出力

0046

に疎行列Bを掛けることで符号語信号

0047

を求める(ステップ403)。なお、当該通信路復号化器400の詳細な動作について後述する。

0048

以下に、上記の各構成の動作の詳細を説明する。

0049

以下では、まず、連続情報源pが与えられたときの有歪み情報源符号について述べた後、連続通信路wが与えられたときの通信路符号について説明する。

0050

<有歪み符号化装置100>
図2に沿って、有歪み符号化器100の処理について説明する。

0051

ベクトル量子化部110で用いられる量子化アルゴリズムを説明する。

0052

符号化部120は、ベクトル量子化110の出力φ(xN)に疎行列Bを掛けることで符号語信号mkを求める。

0053

以下に具体的に説明する。

0054

まず、有歪み情報源符号の構成を示す。

0055

q元体Fqを、

0056

とする。また、N×L疎行列A、N×K疎行列B、およびL次元横ベクトルcL、および条件付き確率密度関数w(y|x)は、予め与えられメモリ(図示せず)に格納されているものとし、w(y|x)は次式で表される歪条件を満足するものとする。

0057

ベクトル量子化部110において条件付き確率密度関数w(y|x)を量子化したものを

0058

とする。すなわち、

0059

に対して、

0060

とする。但し、

0061

は、

0062

によって与えられる(図10参照)。但し、qを奇素数、Δを正の実数とする。

0063

も同様である。

0064

xN を連続情報源pNからの出力とすると、xNのベクトル量子化は、

0065

として与えられる。関数argは最適化(今の場合はmax)における最適値を与える引数を出力するものである。ベクトル量子化

0066

の符号語をmKとすると、符号化部120では、疎行列Bを用いて、

0067

とし、mKを出力する。符号器について、情報源pの統計的性質とは無関係に構成できることに注意しておく。

0068

<有歪み復号化器200>
次に、有歪み復号化器200について説明する。

0069

図4に沿って、有歪み復号化器200について説明する。

0070

有歪み復号化器200の復号化部210は、入力された符号語信号mK用いて最適化を行うことで復号化を行う。

0071

以下に詳細に説明する。

0072

符号語mKが復号化部210に与えられたものとすると、復号化器

0073

は、

0074

として与えられる。但し、上式中の関数H(エントロピー関数)は、

0075

のタイプ(すなわち系列上のアルファベットの経験分布)を

0076

とするとき、

0077

である。

0078

また、最適化の実行には多値の場合のLP復号を用いる。これは、エントロピー関数がタイプの関数であるのでタイプを固定して、固定されたタイプに関する実現可能性を判定する問題に帰着できる事実を用いる。復号化部210についても連続情報源pの統計的性質とは無関係に構成できることに注意しておく。

0079

<シャノン限界への到達性>
次に、連続アルファベットを出力とする有歪み符号化問題について、シャノン限界への到達性について説明する。

0080

とする。有歪み符号化問題において圧縮レートR=K/Nが与えられたときに達成可能な歪みの限界は、

0081

で与えられる(非特許文献1)。歪み限界への到達性を保証するためには、

0082

が成り立たなければならない。上式が成立するためには、新たにパラメータnを導入して

0083

となるように、有歪み符号化器100のベクトル量子化部110において量子化を行えばよい。

0084

<通信路符号化器300>
通信路符号化器300について、図6に沿って説明する。

0085

q元体Fqを、

0086

とする。また、N×L疎行列A,N×K疎行列B,およびL次元横ベクトルcLは予め与えられているものとする。符号化部310において符号語のエネルギー制約

0087

を満足する確率密度関数p(x)を量子化したものを、

0088

とする。すなわち、

0089

に対して、

0090

とする。但し、

0091

はxのスカラー量子化である。このとき、送りたいメッセージを、

0092

とすると、符号化部310

0093

は、

0094

として与えられる。関数argは最適化(今の場合はmax)における最適値を与える引数を出力するものである。なお、上の符号化には通信路Wは含まれていないことに注意しておく。

0095

<通信路復号化器400>
図8に沿って、通信路復号化器400について説明する。

0096

まず、復号化部410の処理を説明する。

0097

yNを通信路からの出力、yNの各要素をスカラー量子化したものを、

0098

とすると、復号部410

0099

は、

0100

として与えられる。ただし、上式中の関数(エントロピー関数)Hは、

0101

のタイプ(すなわち、各系列上のアルファベットの経験分布)を、

0102

とするとき、

0103

である。また、メッセージ推定部420で求められるメッセージmKの推定値

0104

とすると、

0105

となる。また、最適化の実行には多値の場合のLP復号を用いる。これは、エントロピー関数がタイプの関数であるのでタイプを固定して、固定されたタイプに関する実現可能性を判定する問題に帰着できる事実を用いる。復号化器についても通信路wの統計的性質とは無関係に構成できることに注意しておく。

0106

<シャノン限界への到達性>

0107

とする。通信路符号化問題において復号誤り漸近的に0となるためには伝送レートR=K/Nについて、

0108

でなければならない(非特許文献1)。レート限界への到達性を保証するためには、

0109

が成り立たなければならない。上式が成立するためには、新たにパラメータnを導入して、

0110

となるように、符号化部310においてスカラー量子化を行えばよい。

0111

上記のように、本発明は、従来からあるスカラー量子化と疎行列とを組み合わせることにより、連続アルファベット上の通信系(情報源及び通信路)において、符号化限界に近い性能を示しつつ効率的な実現も可能とする符号化・復号化システムを構成した。さらに、符号化器、復号化器のアルゴリズムは通信系の統計的な性質を知ることなく、実行可能なユニバーサル性を持つ。

0112

なお、上記の符号化器及び復号化器の各構成要素の動作(アルゴリズム)をプログラムとして構築し、符号化器、復号化器として利用されるコンピュータインストールして実行させる、または、ネットワークを介して流通させることが可能である。

0113

本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。

0114

100 有歪み符号化器
110ベクトル量子化部
120 符号化部
200 有歪み復号化器
210復号化部
300通信路符号化器
310 符号化部
400通信路復号化器
410 復号化部
420 メッセージ推定部

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • 日本放送協会の「 送信装置、受信装置、及びチップ」が 公開されました。( 2019/05/09)

    【課題】LDPC符号にビットインターリーブ処理を組み合わせて従来よりも誤り訂正能力を向上させる。【解決手段】送信装置30は、LDPC符号を生成するLDPC符号化部324a,324bと、LDPC符号に対... 詳細

  • 日本放送協会の「 送信装置、受信装置及びチップ」が 公開されました。( 2019/05/09)

    【課題】次世代の地上デジタル放送伝送方式においてQAMが適用された場合の適切なビットインターリーブ処理を規定する。【解決手段】本発明に係る送信装置1は、入力されたLDPC符号のLDPCパリティのみに対... 詳細

  • 日本放送協会の「 符号化器、復号器、送信装置及び受信装置」が 公開されました。( 2019/05/09)

    【課題】符号長69120ビットについてはLDPC符号化率12/16と、13/16の各々に関して、符号長17280ビットについてはLDPC符号化率7/16、8/16、9/16、10/16、11/16、1... 詳細

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ