| 講演名 | 2015-03-02 離散無記憶通信路に対して許容できる相互情報量の条件下で出力記号数を削減するアルゴリズム 永原 拓実, 阪井 祐太, 岩田 賢一, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 通信路出力に対して量子化を行うことにより,符号化問題における計算量を減少できる場合がある.KurkoskiとYagiは,通信路の入出力間の相互情報量を精度の測度とし,2元入力離散無記憶通信路とその入力分布と量子化点数が与えられたとき,出力に対する最適な量子化器を設計する動的計画法によるアルゴリズムを考案した.また,入力アルファベットが有限の離散無記憶通信路に対して,Kurkoski,Yamaguchi,Kobayashiは,通信路の出力に対する準最適な量子化器設計アルゴリズムを貪欲法に基づいて提案した.本稿では,与えられた離散通信路に対して許容できる相互情報量の条件下で量子化点数を可能な限り削減する問題を考える.その結果,与えられた入力分布と2元入力通信路と許容できる相互情報量の条件における通信路の出力記号数を最小にする量子化問題に対して,ある種の最適なアルゴリズムを述べる.また,与えられた通信路と入力分布と許容できる相互情報量の条件における通信路の出力記号数を最小にする量子化問題に対して,貪欲法に基づくアルゴリズムを述べる. |
| 抄録(英) | Some quantization techniques are used in channel coding system to reduce the complexity of coding problem. Kurkoski and Yagi proposed an algorithm for finding the optimal quantizer design of channel output for any binary-input discrete memoryless channel in the sense of maximizing mutual information between the channel input and the quantizer output using dynamic programming for a given input distribution. Moreover, Kurkoski, Yamaguchi, and Kobayashi considered a channel input of a finite alphabet, and proposed a suboptimal quantizer design algorithm by using greedy algorithm. In this paper, we consider quantizer design algorithms to reduce the number of output symbols as small as possible on condition that discrete channel satisfies admissible mutual information. We describe one optimal algorithm of quantizer design for binary-input discrete channel, and one greedy algorithm of quantizer design for discrete channel with a finite input alphabet. |
| キーワード(和) | 離散通信路 / 相互情報量 / 量子化器設計アルゴリズム / SMAWKアルゴリズム / 貪欲アルゴリズム |
| キーワード(英) | discrete channel / mutual information / quantizer design algorithm / SMAWK algorithm / greedy algorithm |
| 資料番号 | IT2014-86,ISEC2014-99,WBS2014-78 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2015/2/23(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 離散無記憶通信路に対して許容できる相互情報量の条件下で出力記号数を削減するアルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Algorithms to reduce the number of output symbols on condition that discrete memoryless channel satisfies admissible mutual information |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 離散通信路 / discrete channel |
| キーワード(2)（和/英） | 相互情報量 / mutual information |
| キーワード(3)（和/英） | 量子化器設計アルゴリズム / quantizer design algorithm |
| キーワード(4)（和/英） | SMAWKアルゴリズム / SMAWK algorithm |
| キーワード(5)（和/英） | 貪欲アルゴリズム / greedy algorithm |
| 第 1 著者 氏名（和/英） | 永原 拓実 / Takumi NAGAHARA |
| 第 1 著者 所属（和/英） | 福井大学大学院工学研究科情報・メディア工学専攻 Graduate School of Engineering, University of Fukui |
| 第 2 著者 氏名（和/英） | 阪井 祐太 / Yuta SAKAI |
| 第 2 著者 所属（和/英） | 福井大学大学院工学研究科情報・メディア工学専攻 Graduate School of Engineering, University of Fukui |
| 第 3 著者 氏名（和/英） | 岩田 賢一 / Ken-ichi IWATA |
| 第 3 著者 所属（和/英） | 福井大学大学院工学研究科情報・メディア工学専攻 Graduate School of Engineering, University of Fukui |
| 発表年月日 | 2015-03-02 |
| 資料番号 | IT2014-86,ISEC2014-99,WBS2014-78 |
| 巻番号（vol） | vol.114 |
| 号番号（no） | 471 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |