Based on a recently proposed fast Fourier transform by Lin, Chung, and Han, this paper presents two fast erasure decoding algorithms for Reed–Solomon (RS) codes over binary extension fields of lengthNand dimensionK. The first algorithm applies to low-rate RS codes (i.e.,K/N≤ 0:5) and achieves a complexity ofO(N log K). The second algorithm applies to high-rate RS codes (i.e.,K/N≥ 0:5) and achieves a complexity ofO(N log(N–K)). Compared to recent state-of-the-art algorithms, both proposed algorithms achieve the best complexity, resulting in significant throughput improvements in Single Instruction Multiple Data (SIMD) based simulations. Besides yielding new fast algorithms for RS codes, this paper also presents a new interpolation formula, as well as related results, which may be of independent interest.

Range coding is a type of entropy coding widely used in modern data compressors. However, its compression and decompression processes involve multiple range adjustments, and the bitstream can only be read sequentially during decoding, resulting in quite high latency. In addition, existing input-interleaved fast implementations demand additional computational and memory overhead for the post-compression byte-swizzling step, which leads to increased compression time. In this paper, we propose a parallel range coding method that employs multiple encoders and decoders without the need for the swizzling step. It is achieved by designing a sliding window mechanism to interleave the outputs of multiple encoders, so that the positions of each encoder's outputs in the bitstream follow a predictable and ordered pattern. This design reduces encoding latency and enables each decoder to pre-locate the data it needs to read during decoding, thereby improving both compression and decompression performance. The simulation results indicate that compared to the traditional range coding and existing multi-way input-interleaved implementations (which require a large amount of memory overhead during encoding), our proposal achieves an average throughput increase of 48.03%/81.08% and 74.01%/9.14% during encoding/decoding, respectively, with almost the same compression ratios.

In this paper, we present a fast Chinese remaindering transform (FCRT) over finite fields by exploring Lin-Chung-Han (LCH)-FFT. We take a new approach to LCHFFT by formulating it as a procedure to compute a remainder tree. It is demonstrated that by adopting the Cantor basis for the underlying field$\mathbb{F}_{2} Q$of LCH-FFT, a special set of moduli$\left\{M_{i}(x): 0 \leq i \leq n-1\right\}$, termed “FFT-moduli”, can be picked from the remainder tree, satisfying that they reside in a subfield$\mathbb{F}_{2^{q}}$, specifically$M_{i}(x) \in \mathbb{F}_{2^{q}}[x]$, and that their degrees sum up to$N=\sum_{i=0}^{n-1} \operatorname{deg} M_{i}(x)=2^{Q}$. The FCRT is defined as taking a polynomial$f(x) \in \mathbb{F}_{2^{q}}[x]$of degree less than$N$as input and computing the remainders$\left\{f(x) \bmod M_{i}(x): 0 \leq i \leq n-1\right\}$as output. Since the FCRT realizes a subfield subtree within LCH-FFT, it requires$O(N \log N)$operations over$\mathbb{F}_{2 q}$. Potential applications in coding and secret sharing are also discussed.

In this paper, we construct a new fast transform built on a similar structure with Fast Fourier Transform (FFT), which accelerates calculating polynomials modulo a specific group of moduli. The new transform can be expanded into polynomial remainder codes with lower time complexities. Besides, applying the fast transform in weighted threshold secret sharing with threshold t among N participants requires$O(Nt)$field operations, that improves the prior result$O(Nt\log ^{2} t\log \log t)$. In addition, the decoding algorithm requires$O(t\log ^{2}\log \log t)$field operations, that improves the prior result$O(Nt\log ^{2} t\log \log t)$.

Inversion encoding is an encoding technique used to encode bus transmissions in low-power systems. It is typically utilized to save energy by decreasing the number of transitions on the bus. When the data is transmitted into the bus, the conventional method adds an INV signal to indicate whether the data is inverted. The method reduces the average and the maximal number of transitions and results in the reduction of average and peak power dissipation. However, the method still has room for improvement. We propose an efficient inversion encoding method by adding$k$INV signals on bus transmission to achieve a smaller average number of transitions, which is supported by the results of the numerical calculations.

Distributed systems' applications employ distributed hashing for minimal dispersal, load balancing, and efficient lookups. One such scheme is Ring Consistent Hashing (RCH), which was initially proposed to tackle the issue of web hotspots. Later, it gained popularity in numerous practical ap-plications due to its structured node placement and$O(\log(N))$asymptotic complexity. Despite its popularity, RCH's uniformity is usually worse than other hashing schemes, such as the Highest Random Weight (HRW) and Anchor Hash (AH). For this reason, virtual nodes are introduced in RCH, which increases the memory footprint of the original scheme and restricts its scalability. In this paper, we propose a modification to the existing mapping rule between nodes and keys in the RCH scheme. We develop theoretical arguments and conduct several simulations on the conventional RCH algorithm using modified rule. The results show that the modified rule utilizes only half the number of virtual nodes compared to the original R CH for the same performance, resulting in significantly improved uniformity. Moreover, the memory footprint of the modified RCH is nearly halved compared to the original RCH, owing to the reduced number of virtual nodes. Additionally, the simulation results demonstrate that the modified scheme surpasses HRW and AH in lookup rate and memory usage, making it a superior choice for large-scale distributed systems.

This paper proposes a class of rateless Reed-Solomon (RLRS) codes with near-linear encoding/decoding complexities. Like fountain codes, the RLRS codes can generate a reasonably large number of encoded packets in packet-level transmissions. Furthermore, the RLRS codes are maximum distance separable (MDS) codes that always maintain zero reception overhead. In the proposed RLRS codes, the preservative field extensions are realized through Cantor’s field tower, which avoids searching some quadratic irreducible polynomials as in the prior RLRS codes based on Cauchy generator matrices. Additionally, the proposed RLRS codes are based on Vandermonde generator matrices, whereby the LCH transforms, a variant of fast Fourier transforms (FFTs) over binary extension fields, can be employed to reduce the encoding/decoding complexity. To further improve computational efficiency, this paper also proposes a scheduling scheme for the LCH transforms to generate encoded packets on demand, instead of generating packets whose number must be a power of two. Analysis shows that compared to the prior approach, the used field tower leads to a lower speed of computational complexity growth caused by field extensions. In addition, with the total number of source packets to be transmitted beingk, analysis shows that the proposed RLRS codes have the encoding/decoding complexityO(log2k) per source packet, superior toO(k) in the prior approach.

Reversible data hiding (RDH) has been extensively studied in the field of multimedia security. Embedding capacity is an important metric for RDH performance evaluation. However, the embedding capacity of existing methods for independent and identically distributed (i.i.d.) gray-scale signals is still not good enough. In this paper, we propose a high-capacity RDH code construction method that employs asymmetric numeral systems (ANS) coding as the underlying coding framework. Based on the proposed framework, two RDH methods are presented. First, we propose a static RDH method that takes the constant host probability mass function (PMF) as input parameters and offers high embedding performance. Then, we give a dynamic RDH method that can eliminate the need for transmitting the host PMF in advance by designing a reversible dynamic probability calculator. The simulation results on discrete normally distributed signals demonstrate that the performance of the proposed static method is very close to the expected rate-distortion bound, and the proposed dynamic method can achieve satisfactory embedding capacity without prior knowledge of host PMF at the cost of slightly sacrificing steganographic data quality. Moreover, the experimental results on gray-scale images show that the proposed static method provides higher peak signal-to-noise ratio (PSNR) values and larger embedding capacities than some state-of-the-art methods, e.g., the embedding capacity of image Lena is as high as 3.571 bits per pixel.

Canonical binary AIFV coding [1] contains two trees T0and T1. We show the method to compress T0, and the method to compress T1is with a similar way. We provide a new method to store the number of leaves, master nodes and complete internal nodes in each layer and compactly encode the string of numbers according to the specific property between the nodes.

The Asymmetrical Numeral Systems (ANS) coding has received significant attention in well-integrated compression systems. One particularly insightful technique that has emerged is the interleaved ANS coder (IAC), which substantially enhances the throughput by using multiple encoders and decoders. However, IAC has a limitation that even a single bit error in the compressed bitstream may diffuse across multiple decoders, resulting in many symbols to be incorrectly decoded. In this paper, we propose a parallel method to mitigate the diffusion for a class of error patterns, by limiting the errors to affect only a single decoder. The simulation results show that compared with IAC, our proposal can reduce the average number of incorrectly decoded symbols by about 50% while maintaining comparable encoding and decoding throughput.

This paper presents an early-termination method for the Welch-Berlekamp algorithm. Specifically, if e ≤ t (where e is the number of errors and t is the error correction capability), the Welch–Berlekamp algorithm can be terminated at latest at the completion of the (t + e)-th iteration. Based on the early-termination mechanism, a new variant of the Welch–Berlekamp algorithm called eFDMA is presented, and a systolic architecture is designed for the eFDMA algorithm. This provides an efficient implementation for the key equation solver for a new class of Reed–Solomon codes recently proposed by Lin et al. [9].

This paper presents a new erasure decoding algorithm for low-rate Reed–Solomon codes (rate ≤ 0.5) based on a recently proposed FFT known as LCH-FFT. The algorithm requires O(n log k) finite field operations, where n and k are the code’s length and dimension, respectively. Experiments based on the Intel AVX2 Instructions show that notable improvements in the throughput are achieved compared with the best-known algorithm with complexity O(n log n) (also based on LCH-FFT), and new speed records are created.

The nascent field of Rate-Distortion-Perception (RDP) theory is seeing a surge of research interest due to the application of machine learning techniques in the area of lossy compression. The information RDP function characterizes the three-way trade-off between description rate, average distortion, and perceptual quality measured by discrepancy between probability distributions. However, computing RDP functions has been a challenge due to the introduction of the perceptual constraint, and existing research often resorts to data-driven methods. In this paper, we show that the information RDP function can be transformed into a Wasserstein Barycenter problem. The non-strictly convexity brought by the perceptual constraint can be regularized by an entropy regularization term. We prove that the entropy regularized model converges to the original problem. Furthermore, we propose an alternating iteration method based on the Sinkhorn algorithm to numerically solve the regularized optimization problem. Experimental results demonstrate the efficiency and accuracy of the proposed algorithm.

In this paper, we investigate the properties of the novel polynomial basis proposed by Lin, Chung, and Han over Cantor-constructed binary extension finite fields and propose an improved truncated LCH transform for discrete intervals. Incorporating these results leads us to the development of efficient encoding/decoding algorithms of (n,k) Reed-Solomon erasure codes with time complexity O(nlog(T)) and O (1) space complexity, where T < n. We also propose its performance-tuned variation of the decoding algorithm when only recovery of message symbols is concerned. Our experiment in the production environment indicates a performance gain of ×1 on average and ×2 at most towards the original decoder algorithm.

Based on the Reed-Muller (RM) transform, this paper proposes a Reed-Solomon (RS) encoding/erasure decoding algorithm for any number of parities. Specifically, we first generalize the previous RM-based syndrome calculation, which allows only up to seven parities, to support any number of parities. Then we propose a general encoding/erasure decoding algorithm. The proposed encoding algorithm eliminates the operations in solving linear equations, and this improves the computational efficiency of existing RM-based RS algorithms. In terms of erasure decoding, this paper employs the generalized RM-based syndrome calculation and lower–upper (LU) decomposition to accelerate the computational efficiency. Analysis shows that the proposed encoding/erasure decoding algorithm approaches the complexity of$\lfloor \lg T \rfloor + 1$XORs per data bit with$N$increasing, where$T$and$N$denote the number of parities and codeword length respectively. To highlight the advantage of the proposed RM-based algorithms, the implementations with Single Instruction Multiple Data (SIMD) technology are provided. Simulation results show that the proposed algorithms are competitive, as compared with other cutting-edge implementations.

Ternary AIFV codes are almost instantaneous fixed-to-variable length codes, and are constructed based on two code trees. It is known that the redundancy of ternary AIFV codes is no more than one. In this paper, we provide a tighter upper bound on the redundancy of the ternary Huffman codes when the greatest probability of the source$p_{max}$is known. As a result, the redundancy of the optimal ternary AIFV codes is bounded by Huffman codes, since the ternary Huffman codes can be seen as the special AIFV codes. To achieve lower redundancy than Huffman codes, we also propose a method to construct a class of ternary AIFV codes with time complexity$O(n)$for$n$source symbols. In addition, the redundancy of the proposed AIFV codes is analyzed and compared with Huffman codes. Analyzing the ternary AIFV codes constructed by the algorithm, we derive a tighter redundancy upper bounds under some conditions, which are superior to Huffman codes.

Evolving secret sharing schemes do not require prior knowledge of the number of parties$n$, which may be infinitely countable. It is known that the evolving 2-threshold secret sharing scheme and prefix coding of integers have a one-to-one correspondence. However, it is unknown what prefix coding of integers should be used to construct a better secret sharing scheme. In this paper, we introduce a metric$K_{\Sigma }$to evaluate evolving 2-threshold secret sharing schemes$\Sigma $such that a smaller$K_{\Sigma }$of a scheme is better. The metric$K_{\Sigma }$is related to the ratio of the sum of the share sizes for the first$n$parties in scheme$\Sigma $and the sum of the share sizes for the optimal$(2,n)$-threshold secret sharing scheme. Then we prove that the metric$K_{\Sigma }\geq 1.5$and construct a new prefix coding of integers, termed$\lambda $code, to achieve the metric$K_{\Lambda }=1.59375$. Thus, this shows that the range of the metric$K_{\Sigma }$for the optimal$(2,\infty)$-threshold secret sharing scheme is$1.5\leq K_{\Sigma }\leq 1.59375$. In addition, an achievable lower bound on the sum of share sizes for$(2,n)$-threshold secret sharing schemes is also provided.

Entropy coding is a widely used technique for lossless data compression. The entropy coding schemes supporting the direct access capability on the encoded stream have been investigated in recent years. However, all prior schemes require auxiliary space to support the direct access ability. This paper proposes a rearranging method for prefix codes to support a certain level of direct access to the encoded stream without requiring additional data space. Then, an efficient decoding algorithm is proposed based on lookup tables. The simulation results show that when the encoded stream does not allow additional space, the number of bits per access read of the proposed method is above two orders of magnitude less than the conventional method. In contrast, the alternative solution consumes at least one more bit per symbol on average than the proposed method to support direct access. This indicates that the proposed scheme can achieve a good trade-off between space usage and access performance. In addition, if a small amount of additional storage space is allowed (it is approximately 0.057% in the simulation), the number of bits per access read in our proposal can be significantly reduced by 90%.

A universal scheme is proposed for the lossless compression of two-dimensional tables and matrices. Instead of standard row- or column-based compression, we propose to sort each column first and record both the sorted table and the corresponding permutation table of the sorting permutations. These two tables are then separately compressed. In this new scheme, both intra- and inter-column correlations can be efficiently captured, giving rise to improved compression ratio in particular when both column-wise and row-wise dependencies cooccur. This scheme reduces the problem of the compression of an arbitrary two-dimensional table to that of a ‘permutation table’ together with a ‘sorted table’, where the former is only dependent on the table dimension and the latter can be effectively compressed column-by-column using predictive methods. Based on this scheme, a new algorithm is proposed, SortComp (sort-and-compress). For correlated columns, we give an estimation of the asymptotic bit rate of the algorithm and compare it to column-oriented compression schemes. Numerical experiments on real-life csv datasets validate the advantages of SortComp compared to existing row- and column-oriented compression algorithms.

The codebook is important for canonical Huffman coding, which needs to contain the number of leaves in each layer of the canonical Huffman tree and the corresponding symbols. Specifically, as two conventional methods in [1], [2], only the number of leaves in each level of the canonical Huffman tree is needed to store. However, we provide a new method to store the number of internal nodes in each layer and compactly encode the string of numbers according to the specific property between the internal nodes.

In the conventional range asymmetric numeral systems (rANS), state$x$becomes larger after encoding a symbol$s$. In contrast, the proposed scheme directly outputs an$n$-bit digit$cdf_{s}+x\ (\text{mod}\ f_{s})$for symbol$s$, and decrease$x$via$x\leftarrow\lfloor x/f_{s}\rfloor$, where$2^{n}$denotes the denominator of the quantized frequency distribution,$f_{s}$and$cdf_{s}= \sum\nolimits_{i=0}^{s-1}f_{i}$represent the frequency of symbol$s$and the cumulative frequency counts, respectively. Therefore,$x$will become too small after encoding several symbols. To solve this issue, our proposal forces the state$x$always at a specific interval$I= [2^{T-vn}, 2^{T})$, and$I_{s}:=\left[f_{s}\times 2^{T-vn}, 2^{T}\right)$indicates the interval corresponding to symbol$s$, where$T, v\in \mathbb{N}$. The specific algorithm can be implemented based on the deque. Precisely, for a symbol$s$to be encoded, if the current$x$is within$I_{s}$, we encode it to an$n$-bit digit$cdf_{s}+x\ (\text{mod}\ f_{s})$and push the digit to deque. Otherwise, we first pop data from the deque to enlarge$x$before encoding. Finally, the remaining data in the deque is the desired encoded bit sequence.

In this paper, we study the straggler mitigation via coded computing in distributed computations. In particular, we consider the coded matrix-vector multiplication where the matrix is sparse and coding may break the sparsity of the matrix. We construct a class of sparse universal decodable matrices (UDMs) for coded computing. In simulations, it shows that the proposed code possesses better sparsity than other schemes with randomly generated sparse matrices. Besides, the proposed code performs well in numerical stability.

In this paper, we propose a method of checking data integrity in distributed storage systems. Compare with conventionally used cyclic redundancy check (CRC) method, the proposed method may usually achieve a 99% reduction of bandwidth with the expense of losing only a little detection capacity. We also provide an analysis of performance and a suggestion of auxiliary matrix used in the proposed framework. Besides, a theoretical upper bound of CRC method’s detection capacity is given.

In entropy coding, universal coding of integers (UCI) is a binary universal prefix code, such that the ratio of the expected codeword length to$\max \{1, H(P)\}$is less than or equal to a constant expansion factor$K_{\mathcal {C}}$for any probability distribution$P$, where$H(P)$is the Shannon entropy of$P$.$K_{\mathcal {C}}^{*}$is the infimum of the set of expansion factors. The optimal UCI is defined as a class of UCI possessing the smallest$K_{\mathcal {C}}^{*}$. Based on prior research, the range of$K_{\mathcal {C}}^{*}$for the optimal UCI is$2\leq K_{\mathcal {C}}^{*}\leq 2.75$. Currently, the code constructions achieve$K_{\mathcal {C}}=2.75$for UCI and$K_{\mathcal {C}}=3.5$for asymptotically optimal UCI. In this paper, we construct a class of UCI, termed$\iota $code, to achieve$K_{\mathcal {C}}=2.5$. This further narrows the range of$K_{\mathcal {C}}^{*}$to$2\leq K_{\mathcal {C}}^{*}\leq 2.5$. Next, a family of asymptotically optimal UCIs is presented, where their expansion factor infinitely approaches 2.5. Then, tighter upper bounds of the expansion factors are derived for several classic UCIs. Finally, we prove that the length of the first codeword of optimal UCI is one.

The almost instantaneous variable-to-fixed (AIVF) code is a class of non-prefix codes that parses data sequences into some fixed-length codewords. Recently, the dictionary construction of optimal AIVF code is proposed via a dynamic programming algorithm. However, the algorithm has time complexity$O(AM^{2})$in both single- and multiple-tree modes, where$A$denotes the alphabet size, and$M$denotes the dictionary size. In this paper, we present a greedy-like algorithm to construct the codebook. In particular, the proposed algorithm has time complexity$O(M)$in single-tree mode and$O(AM)$in multiple-tree mode.

Universal coding of integers (UCI) is a class of variable-length code, such that the ratio of the expected codeword length to $\max\{1, H( P)\}$ is within a constant factor, where H(P) is the Shannon entropy of the decreasing probability distribution P. However, if we consider the ratio of the expected codeword length to H(P), the ratio tends to infinity by using UCI, when H(P) tends to zero. To solve this issue, this paper introduces a class of codes, termed generalized UCI, such that the ratio of the expected codeword length to H(P) is within a constant factor K. The definition of generalized UCI is proposed, and then the coding structure of generalized UCI is introduced. Finally, the asymptotically optimal generalized UCI is presented.

The Fletcher checksum (FC) is a means of error detection that is analogous to cyclic redundancy checking but easier to implement in software. Now FC actually has two versions, one is Fletcher's original paper version termed as FC and the other is RFC1146 version termed as FC-RFC. This paper shows that the FC is a cyclic code. This is done by introducing a cyclic code known as the cyclic Fletcher code (CFC) and then showing that the CFC is equivalent to the FC. The clear algebraic structure of cyclic codes is used to analyze the code block length and code distance, and then the single error correction, double error detection, and burst error detection of the CFC are analyzed. Also given is the mathematical relationship between the CFC and a modified FC. Finally, the issue of implementation is considered, and a new scheduling for the CFC is proposed to prevent data hazards. A simulation shows that the proposed scheduling offers improvements of at least 46% in throughput for the CFC and FC-RFC.

Universal coding of integers (UCI) is a prefix coding suitable for probability distributions without prior knowledge. UCI has the property that the expected codeword length is no more than constant$K_{C}$times$\max \{1,H(P)\}$, where$K_{C}$is called the expansion factor and$H(P)$is the entropy of source$P$. A class of UCI$C$with a smaller$K_{C}$is preferred, but the minimum value of$K_{C}$(as well as its code construction) is still unknown. Thus, this paper provides a range of the minimum values of$K_{C}$. First, we show that$K_{C}\geq 2$for each UCI$C$. Then, for the upper bound, we provide a class of UCIs, termed$\eta $code, to achieve$K_{C}=2.75$. This approach improves the prior result$K_{C}=3$achieved by Elias$\gamma $coding. Next, we propose an asymptotically optimal UCI, termed$\theta $code, to achieve$K_{C}=3.5$. Finally, we compare the range of the minimum value of$K_{C}$of$\eta $code,$\theta $code and some other UCIs.

In this paper, we consider the update bandwidth in distributed storage systems (DSSs). The update bandwidth, which measures the transmission efficiency of the update process in DSSs, is defined as the average amount of data symbols transferred in the network when the data symbols stored in a node are updated. This paper contains the following contributions. First, we establish the closed-form expression of the minimum update bandwidth attainable by irregular array codes. Second, after defining a class of irregular array codes, called Minimum Update Bandwidth (MUB) codes, which achieve the minimum update bandwidth of irregular array codes, we determine the smallest code redundancy attainable by MUB codes. Third, the code parameters, with which the minimum code redundancy of irregular array codes and the smallest code redundancy of MUB codes can be equal, are identified, which allows us to define MR-MUB codes as a class of irregular array codes that simultaneously achieve the minimum code redundancy and the minimum update bandwidth. Fourth, we introduce explicit code constructions of MR-MUB codes and MUB codes with the smallest code redundancy. Fifth, we establish a lower bound of the update complexity of MR-MUB codes, which can be used to prove that the minimum update complexity of irregular array codes may not be achieved by MR-MUB codes. Last, we construct a class of$(n = k + 2, k)$vertical maximum-distance separable (MDS) array codes that can achieve all of the minimum code redundancy, the minimum update bandwidth and the optimal repair bandwidth of irregular array codes.

In this paper, we investigate the encoding circuit size of Hamming codes and Hadamard codes. To begin with, we prove lower bounds of encoding circuit size required in the encoding of (punctured) Hadamard codes and (extended) Hamming codes. Then the encoding algorithms for (extended) Hamming codes are presented to achieve the derived lower bounds.

This article describes a fast Reed-Solomon encoding algorithm with four and seven parity symbols in between. First, we show that the syndrome of Reed-Solomon codes can be computed via the Reed-Muller transform. Based on this result, the fast encoding algorithm is then derived. Analysis shows that the proposed approach asymptotically requires 3 XORs per data bit, representing an improvement over previous algorithms. The simulation demonstrates that the performance of the proposed approach improves with the increase of code length and is superior to other methods. In particular, when the parity number is 5, the proposed approach is about two times faster than other cutting-edge methods.

Golomb coding is a type of entropy encoding scheme for geometric distributions. It consists of two parts, and both parts are coded with variable-length coding, which requires a higher computational effort than fixed-length coding schemes. To solve this issue, the first part of this article presents a variant of Golomb coding that uses fixed-length coding to code the first part. The simulations show that the proposed coding scheme has a higher throughput than Golomb coding, due to the reduction of arithmetic complexity. In the second part, we discuss the n-ary versions of Golomb coding and the proposed coding scheme.

In this paper, a variant of the Reed-Muller code, termed symmetric Reed-Muller (SRM) code, is proposed. We show that the bivariate version of SRM code forms the best-known locally-correctable codes in certain parameter regimes. Then, the minimum distance of SRM codes is provided in certain cases. Finally, the multivariate version of SRM codes is introduced.

In this paper, we consider the update bandwidth in distributed storage systems. The update bandwidth is defined as the bandwidth when the data storage in a node is updated. The minimum update bandwidth for irregular array codes is provided. Further, we minimize the code redundancy when the update bandwidth is minimal. Finally, we introduce a class of vertical MDS codes that minimizes both update bandwidth and code redundancy.

Secret sharing is the method to share secrets among a group of shares, and the secret can be reconstructed if one obtains a predefined number of shares. The polynomial secret sharing is usually constructed over a field. In this letter, a novel polynomial secret sharing over a ring is proposed. In particular, by choosing a certain ring, the fast Fourier transform can be applied on the encoding of secret sharing. The analysis shows that the proposed secret sharing scheme requires O(N log2N) Boolean operations per secret bit, which improves the prior result O(8log* NN log2N) Boolean operations per secret bit. The simulation shows that the proposed scheme is in average four times faster than the conventional approach.

Locally decodable codes and locally correctable codes (LCCs) have several important applications, such as private information retrieval, secure multiparty computation, and circuit lower bounds. Three major parameters are considered in LCCs: query complexity, message length, and codeword length. The most familiar LCCs in the regime of low query complexity are the generalized Reed-Muller (GRM) codes. However, it has not previously been determined whether there exist codes that have shorter codeword lengths than GRM codes with the same query complexity and message length. In this paper, we show that the projective Reed-Muller (PRM) codes are such LCCs for some parameters. The GRM code is specified by the alphabet size q, the number of variables m, and the degree d, where d ≤ q - 2. When d = q - 2 and q - 1 is a power of a prime, we prove that there exists a PRM code with shorter codeword length than the GRM code with the same query complexity and message length. We also present for these PRM codes a perfectly smooth local decoder to recover a symbol in a codeword by accessing not more than q symbols at the coordinates of the codeword.

Different from all the previous reversible data hiding schemes, a completely novel one for the color image is proposed, which reversibly embeds messages into the color host image without modifying its corresponding gray version. The property of grayscale invariance is valuable, because many applications and image processing algorithms for color images are based on the corresponding gray versions, such as black and white printing, producing reading materials for color blind people, single-channel image processing, and so on. Thus, in terms of these applications and image processing algorithms, the presented scheme will make the generated color marked image be free for its further uses. In this paper, the unchanged gray version is utilized efficiently in both the embedding processes and the extracting processes. Messages are embedded into the red and blue channels of color image, and then the green channel is adjusted adaptively to remove the offsets from the gray version caused by modifying its red and blue channels. To return the adjusted green channel, error correcting bits guaranteeing the reversibility are regarded as one part of payloads to be recursively embedded. Therefore, the reversibility and the property of grayscale invariance are both achieved.

In this paper, we devise a fast encoding algorithm for triply extended Reed-Solomon codes. The proposed approach requires approximately two XORs per bit, which improves the prior result of three XORs per bit established by certain maximum distance separable (MDS) array codes. We also prove that, for MDS codes with two and three parities, the scheduling algorithms require at least two XORs per bit. To the best of our knowledge, this is the first provable scheduling algorithm for the triple-parity MDS codes to approach the theoretical lower bounds. The implementation with SIMD instructions is provided. The simulations show that the proposed approach is competitive, as compared with other cutting edge implementations.

In this paper, we discuss the principal pivot transforms (PPT) on a family of matrices, called the radix-2 DFT-type matrices. Given a transformation matrix, the PPT of the matrix is a transformation matrix with exchanging some entries between the input array and the output array. The radix-2 DFT-type matrices form a classification of matrices such that the transformations by the matrices can be calculated via radix-2 butterflies. A number of well-known matrices, such as radix-2 DFT matrices and Hadamard matrices, belong to this classification. In this paper, the sufficient conditions for the PPTs on radix-2 DFT-type matrices are given, such that their transformations can also be computed in O{n lg n). Then based on the results above, an encoding algorithm for systematic Reed-Solomon (RS) codes in O{n lg n) field operations is presented.

In computer storage, RAID 6 is a level of RAID that can tolerate two failed drives. When RAID-6 is implemented by Reed-Solomon (RS) codes, the penalty of the writing performance is on the field multiplications in the second parity. In this paper, we present a configuration of the factors of the second-parity formula, such that the arithmetic complexity can reach the optimal complexity bound when the code length approaches infinity. In the proposed approach, the intermediate data used for the first parity is also utilized to calculate the second parity. To the best of our knowledge, this is the first approach supporting the RAID-6 RS codes to approach the optimal arithmetic complexity.

Recently, a new polynomial basis over binary extension fields was proposed, such that the fast Fourier transform (FFT) over such fields can be computed in the complexity of order O(n lg(n)), where n is the number of points evaluated in FFT. In this paper, we reformulate this FFT algorithm, such that it can be easier understood and be extended to develop frequencydomain decoding algorithms for (n = 2m, k) systematic Reed-Solomon (RS) codes over F2m, m ∈ Z+, with n- k a power of two. First, the basis of syndrome polynomials is reformulated in the decoding procedure so that the new transforms can be applied to the decoding procedure. A fast extended Euclidean algorithm is developed to determine the error locator polynomial. The computational complexity of the proposed decoding algorithm is O(n lg(n-k)+(n-k) lg2(n-k)), improving upon the best currently available decoding complexity O(n lg2(n) lglg(n)), and reaching the best known complexity bound that was established by Justesen in 1976. However, Justesen's approach is only for the codes over some specific fields, which can apply Cooley-Tukey FFTs. As revealed by the computer simulations, the proposed decoding algorithm is 50 times faster than the conventional one for the (216, 215) RS code over F216.

In this paper, we present a fast Fourier transform algorithm over extension binary fields, where the polynomial is represented in a non-standard basis. The proposed Fourier-like transform requires O(h lg(h)) field operations, where h is the number of evaluation points. Based on the proposed Fourier-like algorithm, we then develop the encoding/decoding algorithms for (n = 2m, k) Reed-Solomon erasure codes. The proposed encoding/erasure decoding algorithm requires O(n lg(n)), in both additive and multiplicative complexities. As the complexity leading factor is small, the proposed algorithms are advantageous in practical applications. Finally, the approaches to convert the basis between the monomial basis and the new basis are proposed.

In this paper, we consider the network coding (NC) enabled three-phase protocol for information exchange between two users in a wireless two-way (bidirectional) relay network. Modulo-based (nonbinary) and XOR-based (binary) NC schemes are considered as information mixture schemes at the relay while all transmissions adopt pulse amplitude modulation (PAM). We first obtain the optimal constellation mapping at the relay that maximizes the decoding performance at the users for each NC scheme. Then, we compare the two NC schemes, each in conjunction with the optimal constellation mapping at the relay, in different conditions. Our results demonstrate that, in the low SNR regime, binary NC outperforms nonbinary NC with 4-PAM, while they have mixed performance with 8-PAM. This observation applies to quadrature amplitude modulation (QAM) composed of two parallel PAMs.

Regenerating codes represent a class of block codes applicable for distributed storage systems. The [n, k, d] regenerating code has data recovery capability while possessing arbitrary k out of n code fragments, and supports the capability for code fragment regeneration through the use of other arbitrary d fragments, for k ≤ d ≤ n - 1. Minimum storage regenerating (MSR) codes are a subset of regenerating codes containing the minimal size of each code fragment. The first explicit construction of MSR codes that can perform exact regeneration (named exact-MSR codes) for d ≥ 2k - 2 has been presented via a product-matrix framework. This paper addresses some of the practical issues on the construction of exact-MSR codes. The major contributions of this paper include as follows. A new product-matrix framework is proposed to directly include all feasible exact-MSR codes for d ≥ 2k - 2. The mechanism for a systematic version of exact-MSR code is proposed to minimize the computational complexities for the process of message-symbol remapping. Two practical forms of encoding matrices are presented to reduce the size of the finite field.

In this paper, we present a new basis of polynomial over finite fields of characteristic two and then apply it to the encoding/decoding of Reed-Solomon erasure codes. The proposed polynomial basis allows that h-point polynomial evaluation can be computed in O(hlog2(h)) finite field operations with small leading constant. As compared with the canonical polynomial basis, the proposed basis improves the arithmetic complexity of addition, multiplication, and the determination of polynomial degree from O(hlog2(h)log2log2(h)) to O(hlog2(h)). Based on this basis, we then develop the encoding and erasure decoding algorithms for the (n=2r, k) Reed-Solomon codes. Thanks to the efficiency of transform based on the polynomial basis, the encoding can be completed in O(nlog2(k)) finite field operations, and the erasure decoding in O(nlog2(n)) finite field operations. To the best of our knowledge, this is the first approach supporting Reed-Solomon erasure codes over characteristic-2 finite fields while achieving a complexity of O(nlog2(n)), in both additive and multiplicative complexities. As the complexity leading factor is small, the algorithms are advantageous in practical applications.

This paper considers a multi-way relay network in which multiple users intend to achieve full information exchange with one another with the aid of a single relay. A general method for designing the transmission protocol with binary physical- layer network coding (PNC) is developed based on a tree representation. Different transmission schemes are analytically and numerically examined in terms of the decoding strategy, throughput performance, and energy consumption. It is shown that distributing the load of transmissions unevenly among users may achieve a better network throughput performance although some users will consume remarkably more energy than others. A systematic approach to designing the transmission scheme such that minimum error probability is achieved while some specified energy constraint is satisfied is also proposed.

The$(n,k,d)$regenerating code is a class of$(n,k)$erasure codes with the capability to recover a lost code fragment from other$d$existing code fragments. In this paper, we focus on the design of exact regenerating codes at minimum bandwidth regenerating (MBR) points. For$d=n-1$, a class of$(n,k,d=n-1)$exact-MBR codes, termed as repair-by-transfer codes, have been developed in prior work to avoid arithmetic operations in node repairing process. The first result of this paper presents a new class of repair-by-transfer codes via congruent transformations. As compared with prior works, the advantages of proposed codes include: i) the minimum of field size is significantly reduced from$n \atopwithdelims ()2$to$n$; ii) the encoding complexity is decreased from$n^4$to$n^3$. Our simulation results show that the proposed code achieves faster operations than the prior approach does under large$n$. The second result of this paper presents a new form of coding matrix for product-matrix exact-MBR codes. The proposed coding matrix includes the following advantages: i) the minimum of finite field size is reduced from$n-k+d$to$n$; ii) the fast Reed-Solomon erasure coding algorithms can be applied on the proposed exact-MBR codes to reduce the time complexities.

Regenerating code represents a class of erasure codes applicable to distributed storage systems. An [n, k, d] regenerating code admits the recovery of the message from any k out of the n encoded fragments, and the recovery of an erasure fragment from other arbitrary d valid fragments, for k ≤ d ≤ n - 1. Minimum Storage Regenerating (MSR) code is the regenerating code attaining the minimal storage requirement. By product-matrix framework, the [n, k, d ≥ 2k-2] exact-MSR code is presented by Rashmi et al. This paper presents a novel version of exact-MSR codes for the same set of parameters. As compared with previous works, the major contributions of work include: i). An approach is proposed to directly include the d > 2k - 2 Exact-MSR codes in the product-matrix representation; ii). The required size of the finite field is reduced to n from n(d - k +1). The proposed coding techniques further improve the practicability of Exact-MSR codes.

The (n,k) information dispersal algorithm (IDA) is a coding technique converting a digital source file into n small digital files (shadows), and the receipt of any k out of the n shadows can losslessly reconstruct the source file. This paper presents an encoding and two decoding algorithms of (n,k) IDA via the fast Fermat number transform (FNT). The proposed encoding algorithm requires O(nlog k) arithmetic operations, and the two decoding algorithms have complexities O(nlog k) and O(klog2k) for a reasonably large file. As compared with existing work, the proposed algorithms generate significant improvement in the throughput in the low code rate k/n ≤ 1/2 settings.

In this paper, we consider a two-way relay network in which two users exchange messages through a single relay using a physical-layer network coding (PNC) based protocol. The protocol comprises two phases of communication. In the multiple access (MA) phase, two users transmit their modulated signals concurrently to the relay, and in the broadcast (BC) phase, the relay broadcasts a network-coded (denoised) signal to both users. Nonbinary and binary network codes are considered for uniform and nonuniform pulse amplitude modulation (PAM) adopted in the MA phase, respectively. We examine the effect of different choices of symbol mapping (i.e., mapping from the denoised signal to the modulation symbols at the relay) and bit mapping (i.e., mapping from the modulation symbols to the source bits at the user) on the system error-rate performance. A general optimization framework is proposed to determine the optimal symbol/bit mappings with joint consideration of noisy transmissions in both communication phases. Complexity-reduction techniques are developed for solving the optimization problems. It is shown that the optimal symbol/bit mappings depend on the signal-to-noise ratio (SNR) of the channel and the modulation scheme. A general strategy for choosing good symbol/bit mappings is also presented based on a high-SNR analysis, which suggests using a symbol mapping that aligns the error patterns in both communication phases and Gray and binary bit mappings for uniform and nonuniform PAM, respectively.

The detection problem of the space shift keying (SSK) signaling and its generalized form (namely, generalized SSK or GSSK) in the emerging large-scale multiple-input multiple-output (MIMO) systems is discussed in this paper. First, we explicitly formulate the tree search and column search detection schemes achieving optimal maximum likelihood (ML) performance, and discuss their pros and cons in the context of large MIMO systems where the size of the GSSK modulation alphabet increases significantly. Secondly, we propose two useful suboptimal detection methods for large MIMO systems and large-alphabet GSSK signaling based on convex relaxation, which induce an approximately 2-4 dB performance penalty as shown through experimental results.

Energy-efficient communication using a class of spatial modulation (SM) that encodes the source information entirely in the antenna indices is considered in this paper. The energy-efficient modulation design is formulated as a convex optimization problem, where minimum achievable average symbol power consumption is derived with rate, performance, and hardware constraints. The theoretical result bounds any modulation scheme of this class, and encompasses the existing space shift keying (SSK), generalized SSK (GSSK), and Hamming code-aided SSK (HSSK) schemes as special cases. The theoretical optimum is achieved by the proposed practical energy-efficient HSSK (EE-HSSK) scheme that incorporates a novel use of the Hamming code and Huffman code techniques in the alphabet and bit-mapping designs. Experimental studies demonstrate that EE-HSSK significantly outperforms existing schemes in achieving near-optimal energy efficiency. An analytical exposition of key properties of the existing GSSK (including SSK) modulation that motivates a fundamental consideration for the proposed energy-efficient modulation design is also provided.

The (t, n) visual cryptography (VC) is a secret sharing scheme where a secret image is encoded into n transparencies, and the stacking of any t out of n transparencies reveals the secret image. The stacking of t - 1 or fewer transparencies is unable to extract any information about the secret. We discuss the additions and deletions of users in a dynamic user group. To reduce the overhead of generating and distributing transparencies in user changes, this paper proposes a (t, n) VC scheme with unlimited n based on the probabilistic model. The proposed scheme allows n to change dynamically in order to include new transparencies without regenerating and redistributing the original transparencies. Specifically, an extended VC scheme based on basis matrices and a probabilistic model is proposed. An equation is derived from the fundamental definitions of the (t, n) VC scheme, and then the (t, ∞) VC scheme achieving maximal contrast can be designed by using the derived equation. The maximal contrasts with t = 2 to 6 are explicitly solved in this paper.

Reversible information-embedding (RIE) is a technique transforming host signals and the message into the stego-signals, and the stego-signals can be losslessly reversed to the host signals and the message. We consider the conditions: 1) the host signals are composed of gray-scale independent and identically distributed (i.i.d.) samples; 2) the mean squared error is adopted as the measure of distortion; and 3) the procedure is a scalar approach, i.e., the encoder only reads a host signal and then outputs the corresponding stego-signal in each iteration. In this paper, we propose an iterative algorithm to calculate the signal transition probabilities approximating the optimal rate-distortion bound. Then we propose an explicit implementation to embed a message in an i.i.d. host sequence. The experiments show that the proposed method closely approaches the expected rate-distortions in i.i.d. gray-scale signals. By the image prediction model, the proposed method can be applied to gray-scale images.

The stego-images generated by many existing hiding techniques are not economic in size, and hence need compression. Unfortunately, compression usually destroys the secret content hidden inside. To solve this dilemma, some hiding methods based on compression code (rather than the image itself) are reported. This paper proposes a high-capacity and high-hiding-ratio "reversible" steganography method based on JPEG-compression code. In the proposed method, the JPEG compression code of an image is used as the cover media. An 8×8 hiding-capacity table is firstly evaluated, which is then utilized to modify the quantization table attached to the given JPEG code. The two quantization tables (modified and original) together can map the DCT coefficients of each block to some larger DCT coefficients, with secret data hidden inside these larger DCT coefficients. In the decoding process, after lossless extraction of the hidden secret data, the proposed method can also recover the original JPEG-compression code. Experimental results show that our method outperforms other JPEG-based hiding methods (reversible or not) regarding both hiding-ratio and stego-image's quality.