| 講演名 | 2009-05-29 有限状態無雑音通信路に適した語頭符号の構成法 小山 拓哉, 岩田 賢一, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では,定常無記憶情報源と一定でない伝送コストを有する有限状態無雑音通信路が与えられたとき,語頭符号において平均伝送コストの期待値の最小値を達成する符号の構成方法について考える.すなわち,GolinとRoteが示した伝送コストの期待値を最小とする構成法に対して,通信路における状態遷移関数が既知である場合への拡張を示す.その結果,通信路の各状態においてその状態から通信する場合,one-shotの意味において伝送コストの期待値を最小とする語頭符号を情報源記号数に対して多項式時間オーダーを要する計算量とメモリ量で構成できる. |
| 抄録(英) | We consider a problem to build good prefix-free codes for stationary memoryless sources over finite-state noiseless channels with unequal symbol costs. The paper presents a shortest-path procedure in directed acyclic graphs to construct good prefix-free codes for the sources over the channels. The algorithm generalizes Golin and Rote's algorithm for constructing good prefix-free codes to the state dependent noiseless channel case by removing an assumption that codewords should begin and end at the same state. This algorithm runs in polynomial time for the size of the source alphabet when the costs are positive integers for each finite-state, and the state transition function is given. |
| キーワード(和) | 制約を有する語頭符号 / コスト付き閉路のない有向グラフ / コスト最小経路 / 高密度記録符号 / 情報源・通信路結合符号化 |
| キーワード(英) | constrained prefix-free codes / directed acyclic graphs with costs / shortest path / data storage systems / joint source-channel coding |
| 資料番号 | IT2009-1 |
| 発行日 |
| 研究会情報 | |
| 研究会 | IT |
|---|---|
| 開催期間 | 2009/5/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Theory (IT) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 有限状態無雑音通信路に適した語頭符号の構成法 |
| サブタイトル（和） | |
| タイトル（英） | Constructing prefix-free codes for finite-state noiseless channels |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 制約を有する語頭符号 / constrained prefix-free codes |
| キーワード(2)（和/英） | コスト付き閉路のない有向グラフ / directed acyclic graphs with costs |
| キーワード(3)（和/英） | コスト最小経路 / shortest path |
| キーワード(4)（和/英） | 高密度記録符号 / data storage systems |
| キーワード(5)（和/英） | 情報源・通信路結合符号化 / joint source-channel coding |
| 第 1 著者 氏名（和/英） | 小山 拓哉 / Takuya KOYAMA |
| 第 1 著者 所属（和/英） | 福井大学大学院工学研究科情報・メディア工学専攻 Graduate School of Engineering, University of Fukui |
| 第 2 著者 氏名（和/英） | 岩田 賢一 / Ken-ichi IWATA |
| 第 2 著者 所属（和/英） | 福井大学大学院工学研究科情報・メディア工学専攻 Graduate School of Engineering, University of Fukui |
| 発表年月日 | 2009-05-29 |
| 資料番号 | IT2009-1 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | 66 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |