Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNew Upper Bounds on A(n,d)
58
0
0.0
(
0
)
Added by
Beniamin Mounits Mr
Publication date
2005
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Upper bounds on the maximum number of codewords in a binary code of a given length and minimum Hamming distance are considered. New bounds are derived by a combination of linear programming and counting arguments. Some of these bounds improve on the best known analytic bounds. Several new record bounds are obtained for codes with small lengths.
rate research
Read More
In this work we consider the communication of information in the presence of a causal adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codeword $(x_1,...,x_n)$ bit-by-bit over a communication channel. The sender and the receiver do not share common randomness. The adversarial jammer can view the transmitted bits $x_i$ one at a time, and can change up to a $p$-fraction of them. However, the decisions of the jammer must be made in a causal manner. Namely, for each bit $x_i$ the jammers decision on whether to corrupt it or not must depend only on $x_j$ for $j leq i$. This is in contrast to the classical adversarial jamming situations in which the jammer has no knowledge of $(x_1,...,x_n)$, or knows $(x_1,...,x_n)$ completely. In this work, we present upper bounds (that hold under both the average and maximal probability of error criteria) on the capacity which hold for both deterministic and stochastic encoding schemes.
Locally recoverable (LRC) codes have recently been a focus point of research in coding theory due to their theoretical appeal and applications in distributed storage systems. In an LRC code, any erased symbol of a codeword can be recovered by accessing only a small number of other symbols. For LRC codes over a small alphabet (such as binary), the optimal rate-distance trade-off is unknown. We present several new combinatorial bounds on LRC codes including the locality-aware sphere packing and Plotkin bounds. We also develop an approach to linear programming (LP) bounds on LRC codes. The resulting LP bound gives better estimates in examples than the other upper bounds known in the literature. Further, we provide the tightest known upper bound on the rate of linear LRC codes with a given relative distance, an improvement over the previous best known bounds.
The $l$-th stopping redundancy $rho_l(mathcal C)$ of the binary $[n, k, d]$ code $mathcal C$, $1 le l le d$, is defined as the minimum number of rows in the parity-check matrix of $mathcal C$, such that the smallest stopping set is of size at least $l$. The stopping redundancy $rho(mathcal C)$ is defined as $rho_d(mathcal C)$. In this work, we improve on the probabilistic analysis of stopping redundancy, proposed by Han, Siegel and Vardy, which yields the best bounds known today. In our approach, we judiciously select the first few rows in the parity-check matrix, and then continue with the probabilistic method. By using similar techniques, we improve also on the best known bounds on $rho_l(mathcal C)$, for $1 le l le d$. Our approach is compared to the existing methods by numerical computations.
In this work, novel upper and lower bounds for the capacity of channels with arbitrary constraints on the support of the channel input symbols are derived. As an immediate practical application, the case of multiple-input multiple-output channels with amplitude constraints is considered. The bounds are shown to be within a constant gap if the channel matrix is invertible and are tight in the high amplitude regime for arbitrary channel matrices. Moreover, in the high amplitude regime, it is shown that the capacity scales linearly with the minimum between the number of transmit and receive antennas, similarly to the case of average power-constrained inputs.
In this paper, we revisit the problem of finding the longest systematic-length $k$ for a linear minimum storage regenerating (MSR) code with optimal repair of only systematic part, for a given per-node storage capacity $l$ and an arbitrary number of parity nodes $r$. We study the problem by following a geometric analysis of linear subspaces and operators. First, a simple quadratic bound is given, which implies that $k=r+2$ is the largest number of systematic nodes in the emph{scalar} scenario. Second, an $r$-based-log bound is derived, which is superior to the upper bound on log-base $2$ in the prior work. Finally, an explicit upper bound depending on the value of $frac{r^2}{l}$ is introduced, which further extends the corresponding result in the literature.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
