論文の概要: Block Circulant Codes with Application to Decentralized Systems
- arxiv url: http://arxiv.org/abs/2406.12160v1
- Date: Tue, 18 Jun 2024 00:22:20 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-19 23:28:06.615853
- Title: Block Circulant Codes with Application to Decentralized Systems
- Title(参考訳): ブロック循環符号と分散システムへの応用
- Authors: Birenjith Sasidharan, Emanuele Viterbo, Son Hoang Dau,
- Abstract要約: C_textBC[mu,lambda,omega,rho]$ with blocklength $n=mu(rho+omega)$ and dimension $k=muomega$。
ローカルコードはすべて$cal C_textBC[mu,lambda,omega,rho]$は$[rho+lambdaomega,lambdaomega,rho+1]$ generalized Reed-Solomon (RS)である。
- 参考スコア(独自算出の注目度): 12.014314088945968
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The structure of linear dependence relations between coded symbols of a linear code, irrespective of specific coefficients involved, is referred to as the {\em topology} of the code. The specification of coefficients is referred to as an {\em instantiation} of the topology. In this paper, we propose a new block circulant topology $T_{[\mu,\lambda,\omega]}(\rho)$ parameterized by integers $\rho \geq 2$, $\omega \geq 1$, $\lambda \geq 2$, and $\mu$ a multiple of $\lambda$. In this topology, the code has $\mu$ local codes with $\rho$ parity-check (p-c) constraints and a total of $\mu\rho$ p-c equations fully define the code. Next, we construct a class of block circulant (BC) codes ${\cal C}_{\text{BC}}[\mu,\lambda,\omega,\rho]$ with blocklength $n=\mu(\rho+\omega)$, dimension $k=\mu\omega$ that instantiate $T_{[\mu,\lambda,\omega]}(\rho)$. Every local code of ${\cal C}_{\text{BC}}[\mu,\lambda,\omega,\rho]$ is a $[\rho+\lambda\omega,\lambda\omega,\rho+1]$ generalized Reed-Solomon (RS) code. The overlap between supports of local codes helps to enhance the minimum distance $\rho+1$ to $2\rho+1$, without compromising much on the rate. We provide an efficient, parallelizable decoding algorithm to correct $2\rho$ erasures when $\lambda=2$. Finally, we illustrate that the BC codes serve as a viable alternative to 2D RS codes in protocols designed to tackle blockchain networks' data availability (DA) problem. In these protocols, every node in a network of light nodes randomly queries symbols from a codeword stored in full nodes and verifies them using a cryptographic commitment scheme. For the same performance in tackling the DA problem, the BC code requires querying a smaller number of symbols than a comparable 2D RS code for a fixed high rate. Furthermore, the number of local codes in the BC code is typically smaller, yielding a reduction in the complexity of realizing the commitment scheme.
- Abstract(参考訳): 線形符号の符号付き記号間の線形依存関係の構造は、関係する特定の係数に関係なく、符号の {\em topology} と呼ばれる。
係数の仕様はトポロジーの {\em instantiation} と呼ばれる。
本稿では,新しいブロック循環トポロジーである$T_{[\mu,\lambda,\omega]}(\rho)$を整数でパラメータ化し,$\rho \geq 2$,$\omega \geq 1$,$\lambda \geq 2$,$\mu$ a multiple of $\lambda$を提案する。
このトポロジーにおいて、コードは$\mu$ローカルコードを持ち、$\rho$ parity-check (p-c) 制約を持ち、合計$\mu\rho$ p-c 方程式はコードを完全に定義している。
次に、ブロックサーキュラント(BC)コードのクラスを構成する。 ${\cal C}_{\text{BC}}[\mu,\lambda,\omega,\rho]$ with blocklength $n=\mu(\rho+\omega)$, dimension $k=\mu\omega$ that instantiate $T_{[\mu,\lambda,\omega]}(\rho)$。
ローカルコードはすべて${\cal C}_{\text{BC}}[\mu,\lambda,\omega,\rho]$は$[\rho+\lambda\omega,\lambda\omega,\rho+1]$ Generalized Reed-Solomon (RS)コードです。
ローカルコードのサポート間のオーバーラップは、レートに多くの妥協を加えることなく、最小距離$\rho+1$から$2\rho+1$に拡張するのに役立ちます。
効率よく並列化可能なデコードアルゴリズムを提供し、$\lambda=2$のときに2$\rho$消去を補正する。
最後に、BCコードはブロックチェーンネットワークのデータ可用性(DA)問題に対処するために設計されたプロトコルにおいて、2D RSコードに代わる実行可能な代替手段として機能することを示す。
これらのプロトコルでは、光ノードのネットワーク内の各ノードは、全ノードに格納されたコードワードからランダムにシンボルをクエリし、暗号的なコミットメントスキームを用いて検証する。
DA問題に対処するのと同じパフォーマンスのために、BCコードは固定レートで同等の2D RSコードよりも少ない数のシンボルをクエリする必要がある。
さらに、BCコード内のローカルコードの数は典型的には小さく、コミットメントスキームを実現する複雑さが減少する。
関連論文リスト
- Quantum $(r,δ)$-locally recoverable codes [41.08639347877682]
古典的な$(r,delta)$-locally recoveryable codeはエラー訂正コードであり、コードワードの各座標$c_i$に対して、$c_i$を含む少なくとも$r+デルタ-1$座標のセットが存在する。
これらのコードは、大規模分散およびクラウドストレージシステムにおける情報の損失を避けるのに有用である。
論文 参考訳(メタデータ) (2024-12-21T11:45:32Z) - Characterizing Quantum Codes via the Coefficients in Knill-Laflamme Conditions [3.980076328494117]
量子誤り訂正(QEC)は、ノイズに対する量子情報の保護に不可欠である。
我々は, Knill-Laflamme (KL) 係数 $lambda_ij$ の構造を条件 $PE_idagger E_j P = lambda_ij P$ から検討する。
論文 参考訳(メタデータ) (2024-10-10T14:38:15Z) - A shortcut to an optimal quantum linear system solver [55.2480439325792]
複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。
ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。
あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
論文 参考訳(メタデータ) (2024-06-17T20:54:11Z) - A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring [55.17220687298207]
閾値秘密共有方式により、ディーラーは、秘密が一定量の株式から正しく回収されたことをすべての参加者に分配することができる。
我々は、リング上の$ell$-bitシークレットのための、進化する$k$-thresholdシークレット共有スキームを、正確性と完全なセキュリティで新たに構築することを提案する。
論文 参考訳(メタデータ) (2024-02-02T05:04:01Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳(メタデータ) (2023-07-11T08:51:53Z) - Performance Analysis of Quantum CSS Error-Correcting Codes via
MacWilliams Identities [9.69910104594168]
実用実装において最も重要なクラスの1つである安定化器符号の性能を解析する。
WEの知識と論理演算子解析を組み合わせた新しい手法を提案する。
大きなコードについては、$rho_mathrmL approx 1215 rho4$および$rho_mathrmL approx 663 rho5$ for the $[85,1,7]$および$[181,1,10]$Surface codesを提供します。
論文 参考訳(メタデータ) (2023-05-02T10:19:02Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳(メタデータ) (2022-10-15T09:22:22Z) - Divisible Codes for Quantum Computation [0.6445605125467572]
可分符号は、符号語重みが1より大きい共通の因子を共有する性質によって定義される。
本稿では、論理ゲートによって変換される量子情報を保護するために、それらがどのように使用できるかを検討する。
論文 参考訳(メタデータ) (2022-04-27T20:18:51Z) - Distance bounds for generalized bicycle codes [0.7513100214864644]
一般化自転車符号(英: Generalized bike codes, GB codes)は、二項循環行列からなる量子誤り訂正符号のクラスである。
我々は,行重4,6,8の2ビット符号化符号群において,ある素循環サイズのGB符号を網羅的に列挙した。
観測された距離スケーリングは、$A(w)n1/2+B(w)$と一致しており、$n$はコード長であり、$A(w)$は$w$で増加している。
論文 参考訳(メタデータ) (2022-03-31T17:43:34Z) - Optimal Combination of Linear and Spectral Estimators for Generalized
Linear Models [59.015960528781115]
最適に $hatboldsymbol xrm L$ と $hatboldsymbol xrm s$ を組み合わせる方法を示す。
我々は,$(boldsymbol x, hatboldsymbol xrm L, hatboldsymbol xrm s)$の制限分布を確立するために,Adroximate Message Passing (AMP)アルゴリズムの設計と解析を行う。
論文 参考訳(メタデータ) (2020-08-07T18:20:05Z) - On the Modularity of Hypernetworks [103.1147622394852]
構造化対象関数の場合、ハイパーネットワークにおけるトレーニング可能なパラメータの総数は、標準ニューラルネットワークのトレーニング可能なパラメータの数や埋め込み法よりも桁違いに小さいことを示す。
論文 参考訳(メタデータ) (2020-02-23T22:51:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。