-
Block Circulant Codes with Application to Decentralized Systems
Authors:
Birenjith Sasidharan,
Emanuele Viterbo,
Son Hoang Dau
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_{[μ,λ,ω]}(ρ)$ parameterized by integers $ρ\geq 2$, $ω\geq 1$,…
▽ More
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_{[μ,λ,ω]}(ρ)$ parameterized by integers $ρ\geq 2$, $ω\geq 1$, $λ\geq 2$, and $μ$ a multiple of $λ$. In this topology, the code has $μ$ local codes with $ρ$ parity-check (p-c) constraints and a total of $μρ$ p-c equations fully define the code. Next, we construct a class of block circulant (BC) codes ${\cal C}_{\text{BC}}[μ,λ,ω,ρ]$ with blocklength $n=μ(ρ+ω)$, dimension $k=μω$ that instantiate $T_{[μ,λ,ω]}(ρ)$. Every local code of ${\cal C}_{\text{BC}}[μ,λ,ω,ρ]$ is a $[ρ+λω,λω,ρ+1]$ generalized Reed-Solomon (RS) code. The overlap between supports of local codes helps to enhance the minimum distance $ρ+1$ to $2ρ+1$, without compromising much on the rate. We provide an efficient, parallelizable decoding algorithm to correct $2ρ$ erasures when $λ=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.
△ Less
Submitted 17 June, 2024;
originally announced June 2024.
-
Repairing Reed-Solomon Codes with Side Information
Authors:
Thi Xinh Dinh,
Ba Thong Le,
Son Hoang Dau,
Serdar Boztas,
Stanislav Kruglik,
Han Mao Kiah,
Emanuele Viterbo,
Tuvi Etzion,
Yeow Meng Chee
Abstract:
We generalize the problem of recovering a lost/erased symbol in a Reed-Solomon code to the scenario in which some side information about the lost symbol is known. The side information is represented as a set $S$ of linearly independent combinations of the sub-symbols of the lost symbol. When $S = \varnothing$, this reduces to the standard problem of repairing a single codeword symbol. When $S$ is…
▽ More
We generalize the problem of recovering a lost/erased symbol in a Reed-Solomon code to the scenario in which some side information about the lost symbol is known. The side information is represented as a set $S$ of linearly independent combinations of the sub-symbols of the lost symbol. When $S = \varnothing$, this reduces to the standard problem of repairing a single codeword symbol. When $S$ is a set of sub-symbols of the erased one, this becomes the repair problem with partially lost/erased symbol. We first establish that the minimum repair bandwidth depends on $|S|$ and not the content of $S$ and construct a lower bound on the repair bandwidth of a linear repair scheme with side information $S$. We then consider the well-known subspace-polynomial repair schemes and show that their repair bandwidths can be optimized by choosing the right subspaces. Finally, we demonstrate several parameter regimes where the optimal bandwidths can be achieved for full-length Reed-Solomon codes.
△ Less
Submitted 12 May, 2024;
originally announced May 2024.
-
Private Repair of a Single Erasure in Reed-Solomon Codes
Authors:
Stanislav Kruglik,
Han Mao Kiah,
Son Hoang Dau,
Eitan Yaakobi
Abstract:
We investigate the problem of privately recovering a single erasure for Reed-Solomon codes with low communication bandwidths. For an $[n,k]_{q^\ell}$ code with $n-k\geq q^{m}+t-1$, we construct a repair scheme that allows a client to recover an arbitrary codeword symbol without leaking its index to any set of $t$ colluding helper nodes at a repair bandwidth of $(n-1)(\ell-m)$ sub-symbols in…
▽ More
We investigate the problem of privately recovering a single erasure for Reed-Solomon codes with low communication bandwidths. For an $[n,k]_{q^\ell}$ code with $n-k\geq q^{m}+t-1$, we construct a repair scheme that allows a client to recover an arbitrary codeword symbol without leaking its index to any set of $t$ colluding helper nodes at a repair bandwidth of $(n-1)(\ell-m)$ sub-symbols in $\mathbb{F}_q$. When $t=1$, this reduces to the bandwidth of existing repair schemes based on subspace polynomials. We prove the optimality of the proposed scheme when $n=q^\ell$ under a reasonable assumption about the schemes being used. Our private repair scheme can also be transformed into a private retrieval scheme for data encoded by Reed-Solomon codes.
△ Less
Submitted 10 May, 2024;
originally announced May 2024.
-
Repairing with Zero Skip Cost
Authors:
Wenqin Zhang,
Yeow Meng Chee,
Son Hoang Dau,
Tuvi Etzion,
Han Mao Kiah,
Yuan Luo
Abstract:
To measure repair latency at helper nodes, we introduce a new metric called skip cost that quantifies the number of contiguous sections accessed on a disk. We provide explicit constructions of zigzag codes and fractional repetition codes that incur zero skip cost
To measure repair latency at helper nodes, we introduce a new metric called skip cost that quantifies the number of contiguous sections accessed on a disk. We provide explicit constructions of zigzag codes and fractional repetition codes that incur zero skip cost
△ Less
Submitted 6 May, 2024;
originally announced May 2024.
-
A Family of Low-Complexity Binary Codes with Constant Hamming Weights
Authors:
Birenjith Sasidharan,
Emanuele Viterbo,
Son Hoang Dau
Abstract:
In this paper, we focus on the design of binary constant weight codes that admit low-complexity encoding and decoding algorithms, and that have a size $M=2^k$. For every integer $\ell \geq 3$, we construct a $(n=2^\ell, M=2^{k_{\ell}}, d=2)$ constant weight code ${\cal C}[\ell]$ of weight $\ell$ by encoding information in the gaps between successive $1$'s. The code is associated with an integer se…
▽ More
In this paper, we focus on the design of binary constant weight codes that admit low-complexity encoding and decoding algorithms, and that have a size $M=2^k$. For every integer $\ell \geq 3$, we construct a $(n=2^\ell, M=2^{k_{\ell}}, d=2)$ constant weight code ${\cal C}[\ell]$ of weight $\ell$ by encoding information in the gaps between successive $1$'s. The code is associated with an integer sequence of length $\ell$ with a constraint defined as {\em anchor-decodability} that ensures low complexity for encoding and decoding. The complexity of the encoding is linear in the input size $k$, and that of the decoding is poly-logarithmic in the input size $n$, discounting the linear time spent on parsing the input. Both the algorithms do not require expensive computation of binomial coefficients, unlike the case in many existing schemes. Among codes generated by all anchor-decodable sequences, we show that ${\cal C}[\ell]$ has the maximum size with $k_{\ell} \geq \ell^2-\ell\log_2\ell + \log_2\ell - 0.279\ell - 0.721$. As $k$ is upper bounded by $\ell^2-\ell\log_2\ell +O(\ell)$ information-theoretically, the code ${\cal C}[\ell]$ is optimal in its size with respect to two higher order terms of $\ell$. In particular, $k_\ell$ meets the upper bound for $\ell=3$ and one-bit away for $\ell=4$. On the other hand, we show that ${\cal C}[\ell]$ is not unique in attaining $k_{\ell}$ by constructing an alternate code ${\cal \hat{C}}[\ell]$ again parameterized by an integer $\ell \geq 3$ with a different low-complexity decoder, yet having the same size $2^{k_{\ell}}$ when $3 \leq \ell \leq 7$. Finally, we also derive new codes by modifying ${\cal C}[\ell]$ that offer a wider range on blocklength and weight while retaining low complexity for encoding and decoding. For certain selected values of parameters, these modified codes too have an optimal $k$.
△ Less
Submitted 30 June, 2024; v1 submitted 29 January, 2024;
originally announced January 2024.
-
New results on Erasure Combinatorial Batch Codes
Authors:
Phuc-Lu Le,
Son Hoang Dau,
Hy Dinh Ngo,
Thuc D. Nguyen
Abstract:
We investigate in this work the problem of Erasure Combinatorial Batch Codes, in which $n$ files are stored on $m$ servers so that every set of $n-r$ servers allows a client to retrieve at most $k$ distinct files by downloading at most $t$ files from each server. Previous studies have solved this problem for the special case of $t=1$ using Combinatorial Batch Codes. We tackle the general case…
▽ More
We investigate in this work the problem of Erasure Combinatorial Batch Codes, in which $n$ files are stored on $m$ servers so that every set of $n-r$ servers allows a client to retrieve at most $k$ distinct files by downloading at most $t$ files from each server. Previous studies have solved this problem for the special case of $t=1$ using Combinatorial Batch Codes. We tackle the general case $t \geq 1$ using a generalization of Hall's theorem. Additionally, we address a realistic scenario in which the retrieved files are consecutive according to some order and provide a simple and optimal solution for this case.
△ Less
Submitted 30 September, 2023;
originally announced October 2023.
-
From Programming Bugs to Multimillion-Dollar Scams: An Analysis of Trapdoor Tokens on Decentralized Exchanges
Authors:
Phuong Duy Huynh,
Thisal De Silva,
Son Hoang Dau,
Xiaodong Li,
Iqbal Gondal,
Emanuele Viterbo
Abstract:
We investigate in this work a recently emerging type of scam token called Trapdoor, which has caused the investors hundreds of millions of dollars in the period of 2020-2023. In a nutshell, by embedding logical bugs and/or owner-only features to the smart contract codes, a Trapdoor token allows users to buy but prevent them from selling. We develop the first systematic classification of Trapdoor t…
▽ More
We investigate in this work a recently emerging type of scam token called Trapdoor, which has caused the investors hundreds of millions of dollars in the period of 2020-2023. In a nutshell, by embedding logical bugs and/or owner-only features to the smart contract codes, a Trapdoor token allows users to buy but prevent them from selling. We develop the first systematic classification of Trapdoor tokens and a comprehensive list of their programming techniques, accompanied by a detailed analysis on representative scam contracts. We also construct the very first dataset of 1859 manually verified Trapdoor tokens on Uniswap and build effective opcode-based detection tools using popular machine learning classifiers such as Random Forest, XGBoost, and LightGBM, which achieve at least 0.98% accuracies, precisions, recalls, and F1-scores.
△ Less
Submitted 21 September, 2023; v1 submitted 9 September, 2023;
originally announced September 2023.
-
Improving Robustness and Accuracy of Ponzi Scheme Detection on Ethereum Using Time-Dependent Features
Authors:
Phuong Duy Huynh,
Son Hoang Dau,
Xiaodong Li,
Phuc Luong,
Emanuele Viterbo
Abstract:
The rapid development of blockchain has led to more and more funding pouring into the cryptocurrency market, which also attracted cybercriminals' interest in recent years. The Ponzi scheme, an old-fashioned fraud, is now popular on the blockchain, causing considerable financial losses to many crypto-investors. A few Ponzi detection methods have been proposed in the literature, most of which detect…
▽ More
The rapid development of blockchain has led to more and more funding pouring into the cryptocurrency market, which also attracted cybercriminals' interest in recent years. The Ponzi scheme, an old-fashioned fraud, is now popular on the blockchain, causing considerable financial losses to many crypto-investors. A few Ponzi detection methods have been proposed in the literature, most of which detect a Ponzi scheme based on its smart contract source code or opcode. The contract-code-based approach, while achieving very high accuracy, is not robust: first, the source codes of a majority of contracts on Ethereum are not available, and second, a Ponzi developer can fool a contract-code-based detection model by obfuscating the opcode or inventing a new profit distribution logic that cannot be detected (since these models were trained on existing Ponzi logics only). A transaction-based approach could improve the robustness of detection because transactions, unlike smart contracts, are harder to be manipulated. However, the current transaction-based detection models achieve fairly low accuracy. We address this gap in the literature by developing new detection models that rely only on the transactions, hence guaranteeing the robustness, and moreover, achieve considerably higher Accuracy, Precision, Recall, and F1-score than existing transaction-based models. This is made possible thanks to the introduction of novel time-dependent features that capture Ponzi behaviours characteristics derived from our comprehensive data analyses on Ponzi and non-Ponzi data from the XBlock-ETH repository
△ Less
Submitted 30 August, 2023;
originally announced August 2023.
-
Designing Compact Repair Groups for Reed-Solomon Codes
Authors:
Thi Xinh Dinh,
Serdar Boztas,
Son Hoang Dau,
Emanuele Viterbo
Abstract:
Motivated by the application of Reed-Solomon codes to recently emerging decentralized storage systems such as Storj and Filebase/Sia, we study the problem of designing compact repair groups for recovering multiple failures in a decentralized manner. Here, compactness means that the corresponding trace repair schemes of these groups of helpers can be generated from a single or a few seed repair sch…
▽ More
Motivated by the application of Reed-Solomon codes to recently emerging decentralized storage systems such as Storj and Filebase/Sia, we study the problem of designing compact repair groups for recovering multiple failures in a decentralized manner. Here, compactness means that the corresponding trace repair schemes of these groups of helpers can be generated from a single or a few seed repair schemes, thus saving the time and space required for finding and storing them. The goal is to design compact repair groups that can tolerate as many failures as possible. It turns out that the maximum number of failures a collection of repair groups can tolerate equals the size of a minimum hitting set of a collection of subsets of the finite field {\mathbb{F}_{q^{\ell}}} minus one. When the repair groups for each symbol are generated from a single subspace, we establish a pair of asymptotically tight lower bound and upper bound on the size of such a minimum hitting set. Using Burnside's Lemma and the Möbius inversion formula, we determine a number of subspaces that together attain the upper bound on the minimum hitting set size when the repair groups are generated from multiple subspaces.
△ Less
Submitted 11 May, 2023;
originally announced May 2023.
-
$k$-server Byzantine-Resistant PIR Scheme with Optimal Download Rate and Optimal File Size
Authors:
Stanislav Kruglik,
Son Hoang Dau,
Han Mao Kiah,
Huaxiong Wang
Abstract:
We consider the problem of designing a Private Information Retrieval (PIR) scheme on $m$ files replicated on $k$ servers that can collude or, even worse, can return incorrect answers. Our goal is to correctly retrieve a specific message while keeping its identity private from the database servers. We consider the asymptotic information-theoretic capacity of this problem defined as the maximum rati…
▽ More
We consider the problem of designing a Private Information Retrieval (PIR) scheme on $m$ files replicated on $k$ servers that can collude or, even worse, can return incorrect answers. Our goal is to correctly retrieve a specific message while keeping its identity private from the database servers. We consider the asymptotic information-theoretic capacity of this problem defined as the maximum ratio of the number of correctly retrieved symbols to the downloaded one for a large enough number of stored files. We propose an achievable scheme with a small file size and prove that such a file size is minimal for the fixed number of retrieved symbols, solving the problem pointed out by Banawan and Ulukus.
△ Less
Submitted 5 May, 2023; v1 submitted 4 February, 2023;
originally announced February 2023.
-
Committed Private Information Retrieval
Authors:
Quang Cao,
Hong Yen Tran,
Son Hoang Dau,
Xun Yi,
Emanuele Viterbo,
Chen Feng,
Yu-Chih Huang,
Jingge Zhu,
Stanislav Kruglik,
Han Mao Kiah
Abstract:
A private information retrieval (PIR) scheme allows a client to retrieve a data item $x_i$ among $n$ items $x_1,x_2,\ldots,x_n$ from $k$ servers, without revealing what $i$ is even when $t < k$ servers collude and try to learn $i$. Such a PIR scheme is said to be $t$-private. A PIR scheme is $v$-verifiable if the client can verify the correctness of the retrieved $x_i$ even when $v \leq k$ servers…
▽ More
A private information retrieval (PIR) scheme allows a client to retrieve a data item $x_i$ among $n$ items $x_1,x_2,\ldots,x_n$ from $k$ servers, without revealing what $i$ is even when $t < k$ servers collude and try to learn $i$. Such a PIR scheme is said to be $t$-private. A PIR scheme is $v$-verifiable if the client can verify the correctness of the retrieved $x_i$ even when $v \leq k$ servers collude and try to fool the client by sending manipulated data. Most of the previous works in the literature on PIR assumed that $v < k$, leaving the case of all-colluding servers open. We propose a generic construction that combines a linear map commitment (LMC) and an arbitrary linear PIR scheme to produce a $k$-verifiable PIR scheme, termed a committed PIR scheme. Such a scheme guarantees that even in the worst scenario, when all servers are under the control of an attacker, although the privacy is unavoidably lost, the client won't be fooled into accepting an incorrect $x_i$. We demonstrate the practicality of our proposal by implementing the committed PIR schemes based on the Lai-Malavolta LMC and three well-known PIR schemes using the GMP library and blst, the current fastest C library for elliptic curve pairings.
△ Less
Submitted 25 September, 2023; v1 submitted 3 February, 2023;
originally announced February 2023.
-
Two-Server Private Information Retrieval with Optimized Download Rate and Result Verification
Authors:
Stanislav Kruglik,
Son Hoang Dau,
Han Mao Kiah,
Huaxiong Wang
Abstract:
Private Information Retrieval (PIR) schemes allow a client to retrieve any file of interest, while hiding the file identity from the database servers. In contrast to most existing PIR schemes that assume honest-but-curious servers, we study the case of dishonest servers. The latter provide incorrect answers and try to persuade the client to output the wrong result. We introduce several PIR schemes…
▽ More
Private Information Retrieval (PIR) schemes allow a client to retrieve any file of interest, while hiding the file identity from the database servers. In contrast to most existing PIR schemes that assume honest-but-curious servers, we study the case of dishonest servers. The latter provide incorrect answers and try to persuade the client to output the wrong result. We introduce several PIR schemes with information-theoretic privacy and result verification for the case of two servers. Security guarantees can be information-theoretical or computational, and the verification keys can be public or private. In this work, our main performance metric is the download rate.
△ Less
Submitted 8 June, 2023; v1 submitted 27 January, 2023;
originally announced January 2023.
-
Efficient Hamiltonian Reduction for Quantum Annealing on SatCom Beam Placement Problem
Authors:
Thinh Q. Dinh,
Son Hoang Dau,
Eva Lagunas,
Symeon Chatzinotas
Abstract:
Beam Placement (BP) is a well-known problem in Low-Earth Orbit (LEO) satellite communication (SatCom) systems, which can be modelled as an NP-hard clique cover problem. Recently, quantum computing has emerged as a novel technology which revolutionizes how to solve challenging optimization problems by formulating Quadratic Unconstrained Binary Optimization (QUBO), then preparing Hamiltonians as inp…
▽ More
Beam Placement (BP) is a well-known problem in Low-Earth Orbit (LEO) satellite communication (SatCom) systems, which can be modelled as an NP-hard clique cover problem. Recently, quantum computing has emerged as a novel technology which revolutionizes how to solve challenging optimization problems by formulating Quadratic Unconstrained Binary Optimization (QUBO), then preparing Hamiltonians as inputs for quantum computers. In this paper, we study how to use quantum computing to solve BP problems. However, due to limited hardware resources, existing quantum computers are unable to tackle large optimization spaces. Therefore, we propose an efficient Hamiltonian Reduction method that allows quantum processors to solve large BP instances encountered in LEO systems. We conduct our simulations on real quantum computers (D-Wave Advantage) using a real dataset of vessel locations in the US. Numerical results show that our algorithm outperforms commercialized solutions of D-Wave by allowing existing quantum annealers to solve 17.5 times larger BP instances while maintaining high solution quality. Although quantum computing cannot theoretically overcome the hardness of BP problems, this work contributes early efforts to applying quantum computing in satellite optimization problems, especially applications formulated as clique cover/graph coloring problems.
△ Less
Submitted 12 October, 2022;
originally announced October 2022.
-
Practical Considerations in Repairing Reed-Solomon Codes
Authors:
Thi Xinh Dinh,
Luu Y Nhi Nguyen,
Lakshmi J. Mohan,
Serdar Boztas,
Tran Thi Luong,
Son Hoang Dau
Abstract:
The issue of repairing Reed-Solomon codes currently employed in industry has been sporadically discussed in the literature. In this work we carry out a systematic study of these codes and investigate important aspects of repairing them under the trace repair framework, including which evaluation points to select and how to implement a trace repair scheme efficiently. In particular, we employ diffe…
▽ More
The issue of repairing Reed-Solomon codes currently employed in industry has been sporadically discussed in the literature. In this work we carry out a systematic study of these codes and investigate important aspects of repairing them under the trace repair framework, including which evaluation points to select and how to implement a trace repair scheme efficiently. In particular, we employ different heuristic algorithms to search for low-bandwidth repair schemes for codes of short lengths with typical redundancies and establish three tables of current best repair schemes for $[n, k]$ Reed-Solomon codes over GF(256) with $4 \leq n \leq 16$ and $r = n - k \in \{2,3,4\}$. The tables cover most known codes currently used in the distributed storage industry.
△ Less
Submitted 22 May, 2022;
originally announced May 2022.
-
TreePIR: Efficient Private Retrieval of Merkle Proofs via Tree Colorings with Fast Indexing and Zero Storage Overhead
Authors:
Son Hoang Dau,
Quang Cao,
Rinaldo Gagiano,
Duy Huynh,
Xun Yi,
Phuc Lu Le,
Quang-Hung Luu,
Emanuele Viterbo,
Yu-Chih Huang,
Jingge Zhu,
Mohammad M. Jalalzai,
Chen Feng
Abstract:
A Batch Private Information Retrieval (batch-PIR) scheme allows a client to retrieve multiple data items from a database without revealing them to the storage server(s). Most existing approaches for batch-PIR are based on batch codes, in particular, probabilistic batch codes (PBC) (Angel et al. S&P'18), which incur large storage overheads. In this work, we show that \textit{zero} storage overhead…
▽ More
A Batch Private Information Retrieval (batch-PIR) scheme allows a client to retrieve multiple data items from a database without revealing them to the storage server(s). Most existing approaches for batch-PIR are based on batch codes, in particular, probabilistic batch codes (PBC) (Angel et al. S&P'18), which incur large storage overheads. In this work, we show that \textit{zero} storage overhead is achievable for tree-shaped databases. In particular, we develop TreePIR, a novel approach tailored made for private retrieval of the set of nodes along an arbitrary root-to-leaf path in a Merkle tree with no storage redundancy. This type of trees has been widely implemented in many real-world systems such as Amazon DynamoDB, Google's Certificate Transparency, and blockchains. Tree nodes along a root-to-leaf path forms the well-known Merkle proof. TreePIR, which employs a novel tree coloring, outperforms PBC, a fundamental component in state-of-the-art batch-PIR schemes (Angel et al. S&P'18, Mughees-Ren S&P'23, Liu et al. S&P'24), in all metrics, achieving $3\times$ lower total storage and $1.5$-$2\times$ lower computation and communication costs. Most notably, TreePIR has $8$-$160\times$ lower setup time and its polylog-complexity indexing algorithm is $19$-$160\times$ faster than PBC for trees of $2^{10}$-$2^{24}$ leaves.
△ Less
Submitted 4 June, 2024; v1 submitted 10 May, 2022;
originally announced May 2022.
-
On the Formation of Min-weight Codewords of Polar/PAC Codes and Its Applications
Authors:
Mohammad Rowshan,
Son Hoang Dau,
Emanuele Viterbo
Abstract:
Minimum weight codewords play a crucial role in the error correction performance of a linear block code. In this work, we establish an explicit construction for these codewords of polar codes as a sum of the generator matrix rows, which can then be used as a foundation for two applications. In the first application, we obtain a lower bound for the number of minimum-weight codewords (a.k.a. the err…
▽ More
Minimum weight codewords play a crucial role in the error correction performance of a linear block code. In this work, we establish an explicit construction for these codewords of polar codes as a sum of the generator matrix rows, which can then be used as a foundation for two applications. In the first application, we obtain a lower bound for the number of minimum-weight codewords (a.k.a. the error coefficient), which matches the exact number established previously in the literature. In the second application, we derive a novel method that modifies the information set (a.k.a. rate profile) of polar codes and PAC codes in order to reduce the error coefficient, hence improving their performance. More specifically, by analyzing the structure of minimum-weight codewords of polar codes (as special sums of the rows in the polar transform matrix), we can identify rows (corresponding to \textit{information} bits) that contribute the most to the formation of such codewords and then replace them with other rows (corresponding to \textit{frozen} bits) that bring in few minimum-weight codewords. A similar process can also be applied to PAC codes. Our approach deviates from the traditional constructions of polar codes, which mostly focus on the reliability of the sub-channels, by taking into account another important factor - the weight distribution. Extensive numerical results show that the modified codes outperform PAC codes and CRC-Polar codes at the practical block error rate of $10^{-2}$-$10^{-3}$.
△ Less
Submitted 20 September, 2023; v1 submitted 16 November, 2021;
originally announced November 2021.
-
Local Codes with Addition Based Repair
Authors:
Han Mao Kiah,
Son Hoang Dau,
Wentu Song,
Chau Yuen
Abstract:
We consider the complexities of repair algorithms for locally repairable codes and propose a class of codes that repair single node failures using addition operations only, or codes with addition based repair. We construct two families of codes with addition based repair. The first family attains distance one less than the Singleton-like upper bound, while the second family attains the Singleton-l…
▽ More
We consider the complexities of repair algorithms for locally repairable codes and propose a class of codes that repair single node failures using addition operations only, or codes with addition based repair. We construct two families of codes with addition based repair. The first family attains distance one less than the Singleton-like upper bound, while the second family attains the Singleton-like upper bound.
△ Less
Submitted 8 June, 2015;
originally announced June 2015.
-
Weakly Secure MDS Codes for Simple Multiple Access Networks
Authors:
Son Hoang Dau,
Wentu Song,
Chau Yuen
Abstract:
We consider a simple multiple access network (SMAN), where $k$ sources of unit rates transmit their data to a common sink via $n$ relays. Each relay is connected to the sink and to certain sources. A coding scheme (for the relays) is weakly secure if a passive adversary who eavesdrops on less than $k$ relay-sink links cannot reconstruct the data from each source. We show that there exists a weakly…
▽ More
We consider a simple multiple access network (SMAN), where $k$ sources of unit rates transmit their data to a common sink via $n$ relays. Each relay is connected to the sink and to certain sources. A coding scheme (for the relays) is weakly secure if a passive adversary who eavesdrops on less than $k$ relay-sink links cannot reconstruct the data from each source. We show that there exists a weakly secure maximum distance separable (MDS) coding scheme for the relays if and only if every subset of $\ell$ relays must be collectively connected to at least $\ell+1$ sources, for all $0 < \ell < k$. Moreover, we prove that this condition can be verified in polynomial time in $n$ and $k$. Finally, given a SMAN satisfying the aforementioned condition, we provide another polynomial time algorithm to trim the network until it has a sparsest set of source-relay links that still supports a weakly secure MDS coding scheme.
△ Less
Submitted 22 April, 2015;
originally announced April 2015.
-
Locally Encodable and Decodable Codes for Distributed Storage Systems
Authors:
Son Hoang Dau,
Han Mao Kiah,
Wentu Song,
Chau Yuen
Abstract:
We consider the locality of encoding and decoding operations in distributed storage systems (DSS), and propose a new class of codes, called locally encodable and decodable codes (LEDC), that provides a higher degree of operational locality compared to currently known codes. For a given locality structure, we derive an upper bound on the global distance and demonstrate the existence of an optimal L…
▽ More
We consider the locality of encoding and decoding operations in distributed storage systems (DSS), and propose a new class of codes, called locally encodable and decodable codes (LEDC), that provides a higher degree of operational locality compared to currently known codes. For a given locality structure, we derive an upper bound on the global distance and demonstrate the existence of an optimal LEDC for sufficiently large field size. In addition, we also construct two families of optimal LEDC for fields with size linear in code length.
△ Less
Submitted 19 April, 2015;
originally announced April 2015.
-
Erasure codes with symbol locality and group decodability for distributed storage
Authors:
Wentu Song,
Son Hoang Dau,
Chau Yuen
Abstract:
We introduce a new family of erasure codes, called group decodable code (GDC), for distributed storage system. Given a set of design parameters {α; β; k; t}, where k is the number of information symbols, each codeword of an (α; β; k; t)-group decodable code is a t-tuple of strings, called buckets, such that each bucket is a string of βsymbols that is a codeword of a [β; α] MDS code (which is encod…
▽ More
We introduce a new family of erasure codes, called group decodable code (GDC), for distributed storage system. Given a set of design parameters {α; β; k; t}, where k is the number of information symbols, each codeword of an (α; β; k; t)-group decodable code is a t-tuple of strings, called buckets, such that each bucket is a string of βsymbols that is a codeword of a [β; α] MDS code (which is encoded from αinformation symbols). Such codes have the following two properties: (P1) Locally Repairable: Each code symbol has locality (α; β-α+ 1). (P2) Group decodable: From each bucket we can decode αinformation symbols. We establish an upper bound of the minimum distance of (α; β; k; t)-group decodable code for any given set of {α; β; k; t}; We also prove that the bound is achievable when the coding field F has size |F| > n-1 \choose k-1.
△ Less
Submitted 28 July, 2015; v1 submitted 3 February, 2015;
originally announced February 2015.
-
Secure Erasure Codes With Partial Decodability
Authors:
Son Hoang Dau,
Wentu Song,
Chau Yuen
Abstract:
The MDS property (aka the $k$-out-of-$n$ property) requires that if a file is split into several symbols and subsequently encoded into $n$ coded symbols, each being stored in one storage node of a distributed storage system (DSS), then an user can recover the file by accessing any $k$ nodes. We study the so-called $p$-decodable $μ$-secure erasure coding scheme…
▽ More
The MDS property (aka the $k$-out-of-$n$ property) requires that if a file is split into several symbols and subsequently encoded into $n$ coded symbols, each being stored in one storage node of a distributed storage system (DSS), then an user can recover the file by accessing any $k$ nodes. We study the so-called $p$-decodable $μ$-secure erasure coding scheme $(1 \leq p \leq k - μ, 0 \leq μ< k, p | (k-μ))$, which satisfies the MDS property and the following additional properties:
(P1) strongly secure up to a threshold: an adversary which eavesdrops at most $μ$ storage nodes gains no information (in Shannon's sense) about the stored file,
(P2) partially decodable: a legitimate user can recover a subset of $p$ file symbols by accessing some $μ+ p$ storage nodes.
The scheme is perfectly $p$-decodable $μ$-secure if it satisfies the following additional property:
(P3) weakly secure up to a threshold: an adversary which eavesdrops more than $μ$ but less than $μ+p$ storage nodes cannot reconstruct any part of the file.
Most of the related work in the literature only focused on the case $p = k - μ$. In other words, no partial decodability is provided: an user cannot retrieve any part of the file by accessing less than $k$ nodes.
We provide an explicit construction of $p$-decodable $μ$-secure coding schemes over small fields for all $μ$ and $p$. That construction also produces perfectly $p$-decodable $μ$-secure schemes over small fields when $p = 1$ (for every $μ$), and when $μ= 0, 1$ (for every $p$). We establish that perfect schemes exist over \emph{sufficiently large} fields for almost all $μ$ and $p$.
△ Less
Submitted 13 October, 2014;
originally announced October 2014.
-
On the Existence of MDS Codes Over Small Fields With Constrained Generator Matrices
Authors:
Son Hoang Dau,
Wentu Song,
Chau Yuen
Abstract:
We study the existence over small fields of Maximum Distance Separable (MDS) codes with generator matrices having specified supports (i.e. having specified locations of zero entries). This problem unifies and simplifies the problems posed in recent works of Yan and Sprintson (NetCod'13) on weakly secure cooperative data exchange, of Halbawi et al. (arxiv'13) on distributed Reed-Solomon codes for s…
▽ More
We study the existence over small fields of Maximum Distance Separable (MDS) codes with generator matrices having specified supports (i.e. having specified locations of zero entries). This problem unifies and simplifies the problems posed in recent works of Yan and Sprintson (NetCod'13) on weakly secure cooperative data exchange, of Halbawi et al. (arxiv'13) on distributed Reed-Solomon codes for simple multiple access networks, and of Dau et al. (ISIT'13) on MDS codes with balanced and sparse generator matrices. We conjecture that there exist such $[n,k]_q$ MDS codes as long as $q \geq n + k - 1$, if the specified supports of the generator matrices satisfy the so-called MDS condition, which can be verified in polynomial time. We propose a combinatorial approach to tackle the conjecture, and prove that the conjecture holds for a special case when the sets of zero coordinates of rows of the generator matrix share with each other (pairwise) at most one common element. Based on our numerical result, the conjecture is also verified for all $k \leq 7$. Our approach is based on a novel generalization of the well-known Hall's marriage theorem, which allows (overlapping) multiple representatives instead of a single representative for each subset.
△ Less
Submitted 15 January, 2014;
originally announced January 2014.
-
On Block Security of Regenerating Codes at the MBR Point for Distributed Storage Systems
Authors:
Son Hoang Dau,
Wentu Song,
Chau Yuen
Abstract:
A passive adversary can eavesdrop stored content or downloaded content of some storage nodes, in order to learn illegally about the file stored across a distributed storage system (DSS). Previous work in the literature focuses on code constructions that trade storage capacity for perfect security. In other words, by decreasing the amount of original data that it can store, the system can guarantee…
▽ More
A passive adversary can eavesdrop stored content or downloaded content of some storage nodes, in order to learn illegally about the file stored across a distributed storage system (DSS). Previous work in the literature focuses on code constructions that trade storage capacity for perfect security. In other words, by decreasing the amount of original data that it can store, the system can guarantee that the adversary, which eavesdrops up to a certain number of storage nodes, obtains no information (in Shannon's sense) about the original data. In this work we introduce the concept of block security for DSS and investigate minimum bandwidth regenerating (MBR) codes that are block secure against adversaries of varied eavesdropping strengths. Such MBR codes guarantee that no information about any group of original data units up to a certain size is revealed, without sacrificing the storage capacity of the system. The size of such secure groups varies according to the number of nodes that the adversary can eavesdrop. We show that code constructions based on Cauchy matrices provide block security. The opposite conclusion is drawn for codes based on Vandermonde matrices.
△ Less
Submitted 18 February, 2014; v1 submitted 10 September, 2013;
originally announced September 2013.
-
Optimal Locally Repairable Linear Codes
Authors:
Wentu Song,
Son Hoang Dau,
Chau Yuen,
Tiffany Jing Li
Abstract:
Linear erasure codes with local repairability are desirable for distributed data storage systems. An [n, k, d] code having all-symbol (r, δ})-locality, denoted as (r, δ)a, is considered optimal if it also meets the minimum Hamming distance bound. The existing results on the existence and the construction of optimal (r, δ)a codes are limited to only the special case of δ = 2, and to only two small…
▽ More
Linear erasure codes with local repairability are desirable for distributed data storage systems. An [n, k, d] code having all-symbol (r, δ})-locality, denoted as (r, δ)a, is considered optimal if it also meets the minimum Hamming distance bound. The existing results on the existence and the construction of optimal (r, δ)a codes are limited to only the special case of δ = 2, and to only two small regions within this special case, namely, m = 0 or m >= (v+δ-1) > (δ-1), where m = n mod (r+δ-1) and v = k mod r. This paper investigates the existence conditions and presents deterministic constructive algorithms for optimal (r, δ)a codes with general r and δ. First, a structure theorem is derived for general optimal (r, δ)a codes which helps illuminate some of their structure properties. Next, the entire problem space with arbitrary n, k, r and δ is divided into eight different cases (regions) with regard to the specific relations of these parameters. For two cases, it is rigorously proved that no optimal (r, δ)a could exist. For four other cases the optimal (r, δ)a codes are shown to exist, deterministic constructions are proposed and the lower bound on the required field size for these algorithms to work is provided. Our new constructive algorithms not only cover more cases, but for the same cases where previous algorithms exist, the new constructions require a considerably smaller field, which translates to potentially lower computational complexity. Our findings substantially enriches the knowledge on (r, δ)a codes, leaving only two cases in which the existence of optimal codes are yet to be determined.
△ Less
Submitted 8 July, 2013;
originally announced July 2013.
-
Polynomial Time Algorithm for Min-Ranks of Graphs with Simple Tree Structures
Authors:
Son Hoang Dau,
Yeow Meng Chee
Abstract:
The min-rank of a graph was introduced by Haemers (1978) to bound the Shannon capacity of a graph. This parameter of a graph has recently gained much more attention from the research community after the work of Bar-Yossef et al. (2006). In their paper, it was shown that the min-rank of a graph G characterizes the optimal scalar linear solution of an instance of the Index Coding with Side Informati…
▽ More
The min-rank of a graph was introduced by Haemers (1978) to bound the Shannon capacity of a graph. This parameter of a graph has recently gained much more attention from the research community after the work of Bar-Yossef et al. (2006). In their paper, it was shown that the min-rank of a graph G characterizes the optimal scalar linear solution of an instance of the Index Coding with Side Information (ICSI) problem described by the graph G. It was shown by Peeters (1996) that computing the min-rank of a general graph is an NP-hard problem. There are very few known families of graphs whose min-ranks can be found in polynomial time. In this work, we introduce a new family of graphs with efficiently computed min-ranks. Specifically, we establish a polynomial time dynamic programming algorithm to compute the min-ranks of graphs having simple tree structures. Intuitively, such graphs are obtained by gluing together, in a tree-like structure, any set of graphs for which the min-ranks can be determined in polynomial time. A polynomial time algorithm to recognize such graphs is also proposed.
△ Less
Submitted 25 April, 2013;
originally announced April 2013.
-
Delay Minimization in Varying-Bandwidth Direct Multicast with Side Information
Authors:
Son Hoang Dau,
Zheng Dong,
Chau Yuen,
Terence H. Chan
Abstract:
We study the delay minimization in a direct multicast communication scheme where a base station wishes to transmit a set of original packets to a group of clients. Each of the clients already has in its cache a subset of the original packets, and requests for all the remaining packets. The base station communicates directly with the clients by broadcasting information to them. Assume that bandwidt…
▽ More
We study the delay minimization in a direct multicast communication scheme where a base station wishes to transmit a set of original packets to a group of clients. Each of the clients already has in its cache a subset of the original packets, and requests for all the remaining packets. The base station communicates directly with the clients by broadcasting information to them. Assume that bandwidths vary between the station and different clients. We propose a method to minimize the total delay required for the base station to satisfy requests from all clients.
△ Less
Submitted 27 January, 2013;
originally announced January 2013.
-
Balanced Sparsest Generator Matrices for MDS Codes
Authors:
Son Hoang Dau,
Wentu Song,
Zheng Dong,
Chau Yuen
Abstract:
We show that given $n$ and $k$, for $q$ sufficiently large, there always exists an $[n, k]_q$ MDS code that has a generator matrix $G$ satisfying the following two conditions: (C1) Sparsest: each row of $G$ has Hamming weight $n - k + 1$; (C2) Balanced: Hamming weights of the columns of $G$ differ from each other by at most one.
We show that given $n$ and $k$, for $q$ sufficiently large, there always exists an $[n, k]_q$ MDS code that has a generator matrix $G$ satisfying the following two conditions: (C1) Sparsest: each row of $G$ has Hamming weight $n - k + 1$; (C2) Balanced: Hamming weights of the columns of $G$ differ from each other by at most one.
△ Less
Submitted 22 January, 2013;
originally announced January 2013.
-
Parity Declustering for Fault-Tolerant Storage Systems via $t$-designs
Authors:
Son Hoang Dau,
Yan Jia,
Chao Jin,
Weiya Xi,
Kheong Sann Chan
Abstract:
Parity declustering allows faster reconstruction of a disk array when some disk fails. Moreover, it guarantees uniform reconstruction workload on all surviving disks. It has been shown that parity declustering for one-failure tolerant array codes can be obtained via Balanced Incomplete Block Designs. We extend this technique for array codes that can tolerate an arbitrary number of disk failures vi…
▽ More
Parity declustering allows faster reconstruction of a disk array when some disk fails. Moreover, it guarantees uniform reconstruction workload on all surviving disks. It has been shown that parity declustering for one-failure tolerant array codes can be obtained via Balanced Incomplete Block Designs. We extend this technique for array codes that can tolerate an arbitrary number of disk failures via $t$-designs.
△ Less
Submitted 15 March, 2013; v1 submitted 27 September, 2012;
originally announced September 2012.
-
Optimal Index Codes with Near-Extreme Rates
Authors:
Son Hoang Dau,
Vitaly Skachek,
Yeow Meng Chee
Abstract:
The min-rank of a digraph was shown by Bar-Yossef et al. (2006) to represent the length of an optimal scalar linear solution of the corresponding instance of the Index Coding with Side Information (ICSI) problem. In this work, the graphs and digraphs of near-extreme min-ranks are characterized. Those graphs and digraphs correspond to the ICSI instances having near-extreme transmission rates when u…
▽ More
The min-rank of a digraph was shown by Bar-Yossef et al. (2006) to represent the length of an optimal scalar linear solution of the corresponding instance of the Index Coding with Side Information (ICSI) problem. In this work, the graphs and digraphs of near-extreme min-ranks are characterized. Those graphs and digraphs correspond to the ICSI instances having near-extreme transmission rates when using optimal scalar linear index codes. In particular, it is shown that the decision problem whether a digraph has min-rank two is NP-complete. By contrast, the same question for graphs can be answered in polynomial time.
Additionally, a new upper bound on the min-rank of a digraph, the circuit-packing bound, is presented. This bound is often tighter than the previously known bounds. By employing this new bound, we present several families of digraphs whose min-ranks can be found in polynomial time.
△ Less
Submitted 18 March, 2013; v1 submitted 6 February, 2012;
originally announced February 2012.
-
Error Correction for Index Coding with Side Information
Authors:
Son Hoang Dau,
Vitaly Skachek,
Yeow Meng Chee
Abstract:
A problem of index coding with side information was first considered by Y. Birk and T. Kol (IEEE INFOCOM, 1998). In the present work, a generalization of index coding scheme, where transmitted symbols are subject to errors, is studied. Error-correcting methods for such a scheme, and their parameters, are investigated. In particular, the following question is discussed: given the side information h…
▽ More
A problem of index coding with side information was first considered by Y. Birk and T. Kol (IEEE INFOCOM, 1998). In the present work, a generalization of index coding scheme, where transmitted symbols are subject to errors, is studied. Error-correcting methods for such a scheme, and their parameters, are investigated. In particular, the following question is discussed: given the side information hypergraph of index coding scheme and the maximal number of erroneous symbols $δ$, what is the shortest length of a linear index code, such that every receiver is able to recover the required information? This question turns out to be a generalization of the problem of finding a shortest-length error-correcting code with a prescribed error-correcting capability in the classical coding theory.
The Singleton bound and two other bounds, referred to as the $α$-bound and the $κ$-bound, for the optimal length of a linear error-correcting index code (ECIC) are established. For large alphabets, a construction based on concatenation of an optimal index code with an MDS classical code, is shown to attain the Singleton bound. For smaller alphabets, however, this construction may not be optimal. A random construction is also analyzed. It yields another implicit bound on the length of an optimal linear ECIC.
Further, the problem of error-correcting decoding by a linear ECIC is studied. It is shown that in order to decode correctly the desired symbol, the decoder is required to find one of the vectors, belonging to an affine space containing the actual error vector. The syndrome decoding is shown to produce the correct output if the weight of the error pattern is less or equal to the error-correcting capability of the corresponding ECIC.
Finally, the notion of static ECIC, which is suitable for use with a family of instances of an index coding problem, is introduced.
△ Less
Submitted 14 May, 2011;
originally announced May 2011.
-
On the Security of Index Coding with Side Information
Authors:
Son Hoang Dau,
Vitaly Skachek,
Yeow Meng Chee
Abstract:
Security aspects of the Index Coding with Side Information (ICSI) problem are investigated. Building on the results of Bar-Yossef et al. (2006), the properties of linear index codes are further explored. The notion of weak security, considered by Bhattad and Narayanan (2005) in the context of network coding, is generalized to block security. It is shown that the linear index code based on a matrix…
▽ More
Security aspects of the Index Coding with Side Information (ICSI) problem are investigated. Building on the results of Bar-Yossef et al. (2006), the properties of linear index codes are further explored. The notion of weak security, considered by Bhattad and Narayanan (2005) in the context of network coding, is generalized to block security. It is shown that the linear index code based on a matrix $L$, whose column space code $C(L)$ has length $n$, minimum distance $d$ and dual distance $d^\perp$, is $(d-1-t)$-block secure (and hence also weakly secure) if the adversary knows in advance $t \leq d-2$ messages, and is completely insecure if the adversary knows in advance more than $n - d$ messages. Strong security is examined under the conditions that the adversary: (i) possesses $t$ messages in advance; (ii) eavesdrops at most $μ$ transmissions; (iii) corrupts at most $δ$ transmissions. We prove that for sufficiently large $q$, an optimal linear index code which is strongly secure against such an adversary has length $κ_q+μ+2δ$. Here $κ_q$ is a generalization of the min-rank over $F_q$ of the side information graph for the ICSI problem in its original formulation in the work of Bar- Yossef et al.
△ Less
Submitted 14 February, 2011;
originally announced February 2011.
-
Index Coding and Error Correction
Authors:
Son Hoang Dau,
Vitaly Skachek,
Yeow Meng Chee
Abstract:
A problem of index coding with side information was first considered by Y. Birk and T. Kol (IEEE INFOCOM, 1998). In the present work, a generalization of index coding scheme, where transmitted symbols are subject to errors, is studied. Error-correcting methods for such a scheme, and their parameters, are investigated. In particular, the following question is discussed: given the side information h…
▽ More
A problem of index coding with side information was first considered by Y. Birk and T. Kol (IEEE INFOCOM, 1998). In the present work, a generalization of index coding scheme, where transmitted symbols are subject to errors, is studied. Error-correcting methods for such a scheme, and their parameters, are investigated. In particular, the following question is discussed: given the side information hypergraph of index coding scheme and the maximal number of erroneous symbols $δ$, what is the shortest length of a linear index code, such that every receiver is able to recover the required information? This question turns out to be a generalization of the problem of finding a shortest-length error-correcting code with a prescribed error-correcting capability in the classical coding theory. The Singleton bound and two other bounds, referred to as the $α$-bound and the $κ$-bound, for the optimal length of a linear error-correcting index code (ECIC) are established. For large alphabets, a construction based on concatenation of an optimal index code with an MDS classical code, is shown to attain the Singleton bound. For smaller alphabets, however, this construction may not be optimal. A random construction is also analyzed. It yields another inexplicit bound on the length of an optimal linear ECIC. Finally, the decoding of linear ECIC's is discussed. The syndrome decoding is shown to output the exact message if the weight of the error vector is less or equal to the error-correcting capability of the corresponding ECIC.
△ Less
Submitted 14 January, 2011;
originally announced January 2011.
-
Secure Index Coding with Side Information
Authors:
Son Hoang Dau,
Vitaly Skachek,
Yeow Meng Chee
Abstract:
Security aspects of the Index Coding with Side Information (ICSI) problem are investigated. Building on the results of Bar-Yossef et al. (2006), the properties of linear coding schemes for the ICSI problem are further explored. The notion of weak security, considered by Bhattad and Narayanan (2005) in the context of network coding, is generalized to block security. It is shown that the coding sche…
▽ More
Security aspects of the Index Coding with Side Information (ICSI) problem are investigated. Building on the results of Bar-Yossef et al. (2006), the properties of linear coding schemes for the ICSI problem are further explored. The notion of weak security, considered by Bhattad and Narayanan (2005) in the context of network coding, is generalized to block security. It is shown that the coding scheme for the ICSI problem based on a linear code C of length n, minimum distance d and dual distance d^\perp, is (d-1-t)-block secure (and hence also weakly secure) if the adversary knows in advance t \le d - 2 messages, and is completely insecure if the adversary knows in advance more than n - d^\perp messages.
△ Less
Submitted 25 November, 2010;
originally announced November 2010.
-
Linear Size Optimal q-ary Constant-Weight Codes and Constant-Composition Codes
Authors:
Yeow Meng Chee,
Son Hoang Dau,
Alan C. H. Ling,
San Ling
Abstract:
An optimal constant-composition or constant-weight code of weight $w$ has linear size if and only if its distance $d$ is at least $2w-1$. When $d\geq 2w$, the determination of the exact size of such a constant-composition or constant-weight code is trivial, but the case of $d=2w-1$ has been solved previously only for binary and ternary constant-composition and constant-weight codes, and for some s…
▽ More
An optimal constant-composition or constant-weight code of weight $w$ has linear size if and only if its distance $d$ is at least $2w-1$. When $d\geq 2w$, the determination of the exact size of such a constant-composition or constant-weight code is trivial, but the case of $d=2w-1$ has been solved previously only for binary and ternary constant-composition and constant-weight codes, and for some sporadic instances.
This paper provides a construction for quasicyclic optimal constant-composition and constant-weight codes of weight $w$ and distance $2w-1$ based on a new generalization of difference triangle sets. As a result, the sizes of optimal constant-composition codes and optimal constant-weight codes of weight $w$ and distance $2w-1$ are determined for all such codes of sufficiently large lengths. This solves an open problem of Etzion.
The sizes of optimal constant-composition codes of weight $w$ and distance $2w-1$ are also determined for all $w\leq 6$, except in two cases.
△ Less
Submitted 9 August, 2010;
originally announced August 2010.
-
The Sizes of Optimal q-Ary Codes of Weight Three and Distance Four: A Complete Solution
Authors:
Yeow Meng Chee,
Son Hoang Dau,
Alan C. H. Ling,
San Ling
Abstract:
This correspondence introduces two new constructive techniques to complete the determination of the sizes of optimal q-ary codes of constant weight three and distance four.
This correspondence introduces two new constructive techniques to complete the determination of the sizes of optimal q-ary codes of constant weight three and distance four.
△ Less
Submitted 25 March, 2008;
originally announced March 2008.
