コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

情報理論上の未解決問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』

この記事では、情報理論上の未解決問題(じょうほうりろんじょうのみかいけつもんだい)を列挙している。これらは、情報源符号化 (source coding)と通信路符号化(Channel Coding)に分かれる。哲学上の未解決問題[1]に関連する問題もある。

通信路符号化

[編集]
  • ネットワークの容量: 一般的なワイヤレス ネットワークの容量は不明である。AWGN チャネルやフェーディング チャネルなど、容量がわかっている特定のケースがある。[2]
  • 放送チャンネルの容量: ブロードキャストチャンネルの容量、または1つの送信機が多数の受信機に情報を送信している場合は、いくつかの特定のケースで知られているものの、一般的には不明である。[3][4]
  • 干渉チャネルの容量(2ユーザ):干渉チャネルの容量は、相互に干渉する2つの送信機と受信機のペアがある場合には、一般的には不明である。能力は特別なケースで知られている:強力な干渉体制、注射決定論。容量は、おおよその意味で、または、ブロック電力制約ごとの射出半決定論的な、添加用白色ガウスノイズの範囲内で知られている。
  • 双方向チャネルの容量: 双方向チャネル (情報が同時に送信されるチャネル) の容量は不明である。[5][6]
  • Alohaの容量: ALOHAnetは、容量がまだ不明である非常に単純なアクセス方式を使用している、いくつかの特別なケースで知られている。[7]
  • 量子容量: 量子チャネルの容量は一般に知られていない。[8]

より完全なリストについては、カバーとゴピナート[9]を参照。符号理論[10]と関連分野には多くの未解決の問題がある。[11][12]

情報源符号化

[編集]
  • 損失分散ソースコーディング: 相互に通信しないエンコーダーを使用して相関情報ソースを圧縮する最善の方法、各ソースを歪みメトリック内に保持する方法は不明である。

近年解決した問題

[編集]

脚注

[編集]
  1. ^ Adriaans, Pieter. “Open Problems in the Study of Information and Computation”. 21 June 2013閲覧。
  2. ^ Cover, Thomas (1991-08-26). Elements of Information Theory. Wiley-Interscience. ISBN 978-0471062592. https://archive.org/details/elementsofinform0000cove 
  3. ^ Cover, Thomas (Oct 1998). “Comments on Broadcast Channels”. IEEE Trans Inf Theory 44 (6): 2524. doi:10.1109/18.720547. http://pdfs.semanticscholar.org/a0e9/2a5716e0224562f4ade36828d99988b2f6d9.pdf. 
  4. ^ Broadcast Channels”. Notre Dame. 6 July 2014閲覧。
  5. ^ Shannon, Claude (1961). “Two-way communication channels”. Proc Fourth Berkeley Sump on Mathematical Statistics and Probability 1: 611. 
  6. ^ meeuwissen, Erik (16 Aug 1998). “The Origin of Two-Way Channels”. Proc ISIT I: 185. 
  7. ^ Médard, Muriel (March 2004). “Capacity of Time-Slotted ALOHA Packetized Multiple-Access Systems Over the AWGN Channel”. IEEE Transactions on Wireless Communications 3 (2): 486–499. doi:10.1109/TWC.2003.821175. オリジナルの2011-12-18時点におけるアーカイブ。. https://web.archive.org/web/20111218191542/http://colemant.ece.illinois.edu/pubs/capacityALOHAtwireless.pdf 11 July 2014閲覧。. 
  8. ^ Shor, Peter (2000). “Quantum Information Theory: Results and Open Problems”. In Alon N.; Bourgain J.; Connes A. et al.. Visions in Mathematics, GAFA 2000 Special Volume: Part II. Modern Birkhäuser Classics. Birkhäuser Basel. pp. 816–838. doi:10.1007/978-3-0346-0425-3_9. ISBN 978-3-0346-0425-3. http://www-math.mit.edu/~shor/papers/GAFA.pdf 
  9. ^ Cover, Thomas; Gopinath, B. (1987). Open Problems in Communication and Computation. Springer-Verlag. https://raganwald.com/assets/fractran/open-problems-in-communication-and-computation-1987.pdf 11 February 2021閲覧。 
  10. ^ David Joyner; Jon-Lark Kim (2010). Selected Unsolved Problems in Coding Theory. New York: Springer 
  11. ^ Longo, Giuseppe (1975). Information theory: new trends and open problems. ISBN 9783211813782. https://books.google.com/books?id=ddxfAAAAMAAJ 
  12. ^ Tse, David (1996). “It's Easier to Approximate”. Information Theory Society Newsletter. http://www.eecs.berkeley.edu/~dtse/isit09_plenary.pdf 26 June 2013閲覧。.