講演名 | 2002/3/11 因数分解を用いた正整数のユニバーサル符号化 柴田 英明, 山本 博資, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 従来提案されていた正整数のユニバーサル符号は,十分大きな全ての正整数nに対して,その符号語長L(n)がL(n)≧log^*_2n-(log^2_2e)ω^*(n)となるものであった.ここで,log^*_2n=log_2n+log^2_2n+...+log^<ω^*(n)>_2(n)であり,ω^*(n)はlog^s_2n≧0となる最大のsである.本論文では任意に与えられた符号C(n)の符号語長がL(n)のとき,nの因数分解を利用して,新しい符号C^^~(n)を作り,その符号語長L^^~(n)が,任意のnでL^^~(n)≦L(n)+2L(1)を満たし,かつ加算無限個のnでL^^~(n) |
抄録(英) | It is known that any universal code of the positive integers must satisfy L(n)≧log^*_2n - (log^2_2e)ω(n) for infinite many positive integers n, where L(n) stands for the codeword length, ω^*(n) is the largest integer s such that log^s_2 n≧0, and log^*_2 n = log_2 n + log^2_2 n + ... + log^<ω^*(n)>_2(n). On the other hand, any known universal codes satisfy this ineqeality of L(n) for all large integers. But this fact does not deny that some code has L(n) shorter than the lower bound for infinite many integers. In this paper, for any given code C(n), we construct a new code C(n) based on factorization of n, and we show that the codeword length of C^^~(n), L^^~(n), satisfies that L^^~(n) ≦ L(n) + 2L(1) for all n, and L^^~(n) |
キーワード(和) | Eliasのω符号 / 対数スター関数 / 正整数のユニバーサル符号化 |
キーワード(英) | Elias ω code / log-star function / universal code of positive integers |
資料番号 | ISEC2001-110 |
発行日 |
研究会情報 | |
研究会 | ISEC |
---|---|
開催期間 | 2002/3/11(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | Information Security (ISEC) |
---|---|
本文の言語 | JPN |
タイトル(和) | 因数分解を用いた正整数のユニバーサル符号化 |
サブタイトル(和) | |
タイトル(英) | Universal Code of the Positive Integers Based on Factorization |
サブタイトル(和) | |
キーワード(1)(和/英) | Eliasのω符号 / Elias ω code |
キーワード(2)(和/英) | 対数スター関数 / log-star function |
キーワード(3)(和/英) | 正整数のユニバーサル符号化 / universal code of positive integers |
第 1 著者 氏名(和/英) | 柴田 英明 / Hideaki SHIBATA |
第 1 著者 所属(和/英) | 東京大学大学院情報理工学系研究科数理情報学専攻 Department of Mathematical Informatics, Graduate School of Information Science and Technology, the University of Tokyo |
第 2 著者 氏名(和/英) | 山本 博資 / Hirosuke YAMAMOTO |
第 2 著者 所属(和/英) | 東京大学大学院情報理工学系研究科数理情報学専攻 Department of Mathematical Informatics, Graduate School of Information Science and Technology, the University of Tokyo |
発表年月日 | 2002/3/11 |
資料番号 | ISEC2001-110 |
巻番号(vol) | vol.101 |
号番号(no) | 727 |
ページ範囲 | pp.- |
ページ数 | 6 |
発行日 |