論文の概要: Block Circulant Codes with Application to Decentralized Systems

• arxiv url: http://arxiv.org/abs/2406.12160v2
• Date: Mon, 16 Dec 2024 04:33:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-17 13:48:33.630302
• Title: Block Circulant Codes with Application to Decentralized Systems
• Title（参考訳）: ブロック循環符号と分散システムへの応用
• Authors: Birenjith Sasidharan, Emanuele Viterbo, Son Hoang Dau,
• Abstract要約: 我々は,分散消去復号化をサポートするブロック循環符号のファミリ[n,k,d]を開発する。 このコードは、ブロックチェーンネットワークのデータ可用性問題に対処するプロトコルで使用するのに理想的だ。
• 参考スコア（独自算出の注目度）: 12.014314088945968
• License:
• Abstract: In this paper, we design a family of $[n,k,d]$ block circulant codes that consist of many $[n_0 \ll n,k_0 \ll k,d_0]$ local codes and that satisfy three properties: (1) the code supports distributed erasure decoding, (2) $d$ can be scaled above $d_0$ by a given parameter, and (3) it is amenable to low complexity verification of code symbols using a cryptographic commitment scheme. These properties make the code ideal for use in protocols that address the data availability problem in blockchain networks. Moreover, the code outperforms the currently used 2D Reed-Solomon (RS) code with a larger relative minimum distance $(d/n)$, as desired in the protocol, for a given rate $(k/n)$ in the high-rate regime. The code is designed in two steps. First, we develop the topology, i.e., the structure of linear dependence relations among code symbols, and define it as the block circulant topology $T_{[\mu,\lambda,\omega]}(\rho)$. In this topology, there are $\mu$ local codes, each constrained by $\rho$ parity checks. The set of symbols of a local code intersects with another in a uniform pattern, determined by two parameters, namely the overlap factor $\lambda$ and the overlap width $\omega$. Next, we instantiate the topology, i.e., to specify the coefficients of linear dependence relations, to construct the block circulant codes ${\cal C}_{\text{BC}}[\mu,\lambda,\omega,\rho]$. Every local code is a $[\lambda\omega+\rho,\lambda\omega,\rho+1]$ generalized RS code. The block circulant code has $n=\mu(\rho+\omega)$, $k=\mu\omega$ and we show that $d=\lambda\rho+1$ under certain conditions. For $\lambda=2$, we prove that $d=2\rho+1$ always, and provide an efficient, parallelizable erasure-correcting decoder that fully recovers the codeword when there are $\leq 2\rho$ erasures. The decoder uses a novel decoding mechanism that iteratively recovers erasures from pairs of local codes.
• Abstract（参考訳）: 本稿では,多くの$[n_0 \ll n,k_0 \ll k,d_0]$ローカルコードからなるブロック循環コードのファミリーを設計し,(1)コードが分散消去デコーディングをサポートすること,(2)$d$を所定のパラメータで$d_0$以上スケール可能であること,(3)暗号コミットメントスキームを用いてコードシンボルの複雑さの検証を行うことができること,の3つの特性を満たす。 これらのプロパティは、ブロックチェーンネットワークのデータ可用性問題に対処するプロトコルで使用するのに理想的なコードである。 さらに、現在の2D Reed-Solomon (RS) コードは、プロトコルで望まれるような、より大きい相対的最小距離$(d/n)$で、ハイレートで与えられたレート$(k/n)$よりも優れている。 コードは2つのステップで設計されている。 まず、符号記号間の線形依存関係の構造であるトポロジーを開発し、それをブロック循環トポロジー $T_{[\mu,\lambda,\omega]}(\rho)$ と定義する。 このトポロジには$\mu$ローカルコードがあり、それぞれ$\rho$パリティチェックによって制約されている。 ローカルコードのシンボルのセットは、一様パターンで相互に交わり、オーバーラップ係数$\lambda$とオーバーラップ幅$\omega$という2つのパラメータによって決定される。 次に、トポロジー、すなわち線形依存関係の係数を定め、ブロック循環コードを構成するために、${\cal C}_{\text{BC}}[\mu,\lambda,\omega,\rho]$をインスタンス化する。 すべてのローカルコードは$[\lambda\omega+\rho,\lambda\omega,\rho+1]$ 一般化RSコードである。 ブロック循環コードは$n=\mu(\rho+\omega)$, $k=\mu\omega$であり、ある条件下では$d=\lambda\rho+1$を示す。 $\lambda=2$の場合、$d=2\rho+1$が常にあることを証明し、$\leq 2\rho$消去があるときにコードワードを完全に復元する、効率的で並列化可能な消去デコーダを提供する。 デコーダは、一対のローカルコードから消去を反復的に回収する新しい復号機構を使用する。

関連論文リスト

• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。