文献

J-GLOBAL ID：201802254762623399   整理番号：18A1354293

Gilbert-Varshamov限界に近づく局所的に安定で局所的に修正可能な符号【JST・京大機械翻訳】

Locally Testable and Locally Correctable Codes approaching the Gilbert-Varshamov Bound

著者 (5件)： Gopi Sivakanth (Department of Computer Science, Princeton University, Princeton, NJ, USA) ,  Kopparty Swastik (Department of Mathematics, Rutgers University, Piscataway, NJ, USA) ,  Oliveira Rafael (Department of Computer Science, Princeton University, Princeton, NJ, USA) ,  Ron-Zewi Noga (Department of Computer Science, University of Haifa, Haifa, Israel) ,  Saraf Shubhangi (Department of Mathematics, Rutgers University, Piscataway, NJ, USA)
資料名： IEEE Transactions on Information Theory  (IEEE Transactions on Information Theory)
巻： 64  号： 8  ページ： 5813-5831  発行年： 2018年 
JST資料番号： C0231A  ISSN： 0018-9448  CODEN： IETTAW  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 誤り訂正符号の理論における最も重要なオープン問題の一つは,二値符号のレートRと最小距離δの間のトレードオフを決定することである。最も良く知られたトレードオフはGil-Varshamov束縛であり,すべてのδ∈(0,1/2)に対して,最小距離δと速度R=R_GV(δ)>0(ある種の単純関数R_GV(δ))を持つ符号がある。本論文では,Gil-Varshamov限界を,局所誤差検出と誤り訂正アルゴリズムをサポートする符号により達成できることを示した。特に,以下の結果を示した。1)局所試験:すべてのδ∈(0,1/2)およびすべてのR<R_GV(δ)に対して,長さn,速度Rおよび最小距離δを有する符号が存在し,それらは準ポリログ(n)質問複雑性により局所的に安定である。2)局所補正:すべてのε>0に対して,すべてのδ<1/2に対して十分大きく,すべてのR<(1-ε)R_GV(δ)に対して,(δ/2)-o(1)分率誤差からO(n~ε)クエリ複雑さにより局所的に補正可能な長さn,速度R,最小距離δが存在する。さらに,これらの符号は,効率的なランダム化構成を有し,局所試験と局所補正アルゴリズムを,質問複雑性において時間多項式で実行することができた。局所的に修正可能な符号に関する著者らの結果は,同じパラメータで局所的に復号可能な符号を直ちに与える。著者らの局所的試験結果は,Kopパーティらによって,Thommesenのランダム連結技術と最も良く知られた局所的に安定な符号を結合することによって得られる。著者らの局所補正結果は,より多くの関係があり,さらに多くのアイデアに沿ってランダム連結を使用する。すなわち,Guruswami-Sudan-Indykリスト復号化戦略を用いて,Reed-Muller符号の局所的リスト復号性,局所的リスト回復可能性および局所的な信頼性を示した。最後に,著者らの最終的な局所補正アルゴリズムは,局所的なリスト復号化と局所的テストアルゴリズムを経由している。これは,局所的な安定性が局所的に修正可能なコードの構築において使用されると思われる。Copyright 2018 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  多項式 ,  信頼性 ,  *復号化 ,  誤り検出 ,  Reed-Muller符号 ,  誤り訂正 ,  誤り訂正符号
準シソーラス用語： ランダム化 ,  複雑性 ,  クエリー ,  バイナリコード ,  最小距離 ,  リスト復号化 , 【Automatic Indexing@JST】

分類 (1件)： 符号理論  (ND02030R)

タイトルに関連する用語 (2件)： 限界 ,  符号