Source-linked AI summary
Decoding Algorithms for MDS Array Codes
Sara D. Cardell, Gustavo Terra Bastos, Cintya Wink de Oliveira Benedito
TL;DR
The paper studies how to decode MDS array codes constructed from superregular and nonsingular matrices under erasure and q-ary symmetric channels. It exploits their structured parity-check matrices to recover up to n −k erasures and determine locations and values for one or two symbol errors, including a Vandermonde specialization. The examples also delimit the two-error result to cases where both errors occur in information symbols.
Problem
Decoding these structured MDS array codes requires procedures for channels with known erasure locations and unknown symbol-error locations.
Method
The paper exploits parity-check matrices derived from Kronecker products of superregular and nonsingular matrices, with additional Vandermonde structure used to simplify decoding.
Results
The procedures recover any pattern of up to n −k erasures and explicitly determine locations and values for one and two symbol errors.
Takeaways & Limitations
The work shows that algebraic parity-check structure can directly support decoding procedures across substantially different channel conditions.
Takeaways & Limitations
The Vandermonde example does not establish unique correction of every two-symbol-error pattern; it assumes both errors occur in the information part.
Abstract
from arXiv · showhide
We study decoding procedures for a family of MDS array codes previously constructed from the Kronecker product of a superregular matrix and a non-singular matrix over a finite field. By exploiting the particular structure of their parity-check matrices, we develop decoding algorithms for different channel models. For the erasure channel, we provide an algorithm capable of recovering any pattern of up to $n-k$ symbol erasures. For the $q$-ary symmetric channel, we investigate the decoding of one and two symbol errors and give explicit procedures for determining their locations and values. We also consider the particular case in which the superregular matrix is a Vandermonde matrix, showing how its additional algebraic structure can be exploited in the decoding process. Explicit examples over different finite fields are provided to illustrate the proposed procedures.
1 Introduction
The paper situates MDS array codes within reliable transmission and storage, then develops decoding procedures by exploiting structured parity-check matrices for erasures and symbol errors.
- MDS codes attain the Singleton bound and therefore provide the largest possible minimum distance for a given length and dimension.
- Array codes organize symbols multidimensionally, while MDS array codes combine this representation with optimal distance for reliable data recovery.
- Prior MDS array-code constructions address phased burst correction, independent parity symbols, distributed-storage repair, sub-packetization, and deleted-circulant approaches.
- The q-ary symmetric and erasure channels model, respectively, symbol replacement with unknown error locations and symbol loss with known locations.
- The paper exploits Kronecker-product parity-check structure to recover up to n −k erasures and correct one or two unknown-location symbol errors.
2 Preliminaries
The preliminaries define linear and block-superregular structures and connect superregular matrices, Kronecker constructions, and MDS array codes.
- An Fq-linear code over F_bq is a linear subspace whose codewords can also be viewed as length nb vectors over Fq.
- The same codewords may be represented over Fq or F_bq, with normalized dimension defined for the extension-alphabet representation.
- A superregular matrix has every square submatrix nonsingular, and such matrices characterize MDS linear codes in systematic form.
- A block-superregular matrix requires every square submatrix formed from complete b × b blocks to be nonsingular.
- Kronecker products of superregular and nonsingular matrices yield block-superregular matrices and consequently MDS array codes.
3 Decoding algorithm in the Erasure Channel
The erasure decoder converts known erasure locations into a square linear system and proves unique recovery through superregularity, while exploiting smaller matrix inversions for efficiency.
- The q-ary erasure channel reveals erased-symbol locations, and the code is designed to correct up to n −k erasures.
- The decoder partitions erasures between information and parity-check symbols, then represents their unknown block values as n −k variables.
- Superregularity makes the relevant matrix [A∗| B∗] nonsingular, so its Kronecker product with I_b gives a unique solution.
- The unknown error blocks are recovered by applying the inverse system matrix to the syndrome, after which the original error components are reconstructed.
- When all block matrices equal B, only one inverse B^-1 is needed, reducing the algorithm's complexity.
- Instead of inverting the larger matrix M∗, the algorithm can use the inverse of a t × t submatrix of A after suitable permutations.
4 Decoding algorithm no Symmetric Channel
The decoding procedures use syndrome patterns and transformations involving the matrices A and B to identify error locations and values over the q-ary symmetric channel. They provide explicit recovery cases for parity errors, information errors, and combinations of errors, illustrated by finite-field examples.
- Errors in the parity symbols: Parity-symbol errors are read directly from corresponding syndrome positions, revealing both their locations and values.The error in parity position k+j appears in syndrome position j.
- One error in the information symbols: For one information-symbol error, multiplying syndrome symbols by inverses of the B_j matrices identifies the matching column of A and the error value.The decoder tests candidate information positions and verifies the resulting codeword by recomputing its syndrome.
- One error in the information symbols: When all B_j matrices are equal, one inverse matrix suffices and the decoder avoids testing several possible cases.This special case is presented as a lower-complexity recovery procedure.
- One error in the information symbols and one error in the parity symbols: For one information error and one parity error, diagonal scaling makes most syndrome symbols equal to the information error while isolating the parity error.The unequal syndrome component identifies the parity-symbol error, while the repeated components identify the information error.
- One error in the information symbols and one error in the parity symbols: In the worked mixed-error example, equal scaled syndrome symbols identify information error e2 = [0 1], while the third syndrome symbol locates a second error in the third parity symbol.The recovered codeword is [1 0 1 0 0 0 11 0 6 0 7 0].
5 Example with a Vandermonde matrix
The Vandermonde structure supports explicit two-error decoding by testing candidate information-symbol positions, solving for error values, and checking the full syndrome. An F8 example recovers the transmitted codeword while illustrating the method's scope.
- Two-error procedure: For candidate positions j1 and j2, the first 2b equations determine the two error symbols, while remaining equations verify the complete syndrome.This reduces each position-pair test to solving a smaller system followed by a consistency check.
- Vandermonde structure: The Vandermonde representation lets determinant and inverse factors be computed at the exponent level using Zech logarithms when suitable finite-field tables are available.This can simplify implementation in finite fields with discrete-logarithm or Zech-logarithm tables.
- Example setup: In F8, the constructed parity-check matrix defines an MDS linear code with parameters over F2.The example uses a superregular matrix over F8 and a non-singular block matrix.
- Candidate testing: Testing positions (1, 2) produces candidate symbols inconsistent with the complete syndrome, so that pair is rejected.The first four equations yield the candidate error symbols, but the full syndrome check fails.
- Candidate testing: Testing positions (1, 3) is consistent with the complete syndrome and recovers e=[α 0 | 0 0 | α 0 | 0 0 | 0 0 | 0 0].Subtracting this error vector from the received word yields the transmitted codeword.
- Scope: The example assumes both errors occur in the information part and does not establish unique correction of every two-error pattern for an code.It demonstrates candidate-pair value recovery and syndrome-based consistency testing under that assumption.
A Algorithms
The algorithms recover codewords by constructing the Kronecker-structured parity-check system, computing a syndrome, solving for error values, and subtracting the resulting error vector.
- Erasure channel: The erasure decoder builds M=A⊗(B1,...,Bk), forms H=[M|I_b(n−k)], and computes the syndrome from the received word.It then constructs and inverts a selected coefficient matrix for the identified erasure positions.
- Erasure channel: For identified parity-part errors, the decoder obtains their values by applying the corresponding inverse block B_i^-1 to syndrome components.The recovered parity errors are placed into the error vector before codeword reconstruction.
- Single information error: The single-information-error decoder with distinct B_i matrices normalizes the syndrome separately for each candidate information position.It tests candidate locations and accepts a corrected word when the parity-check equation is satisfied.
9. Compute the candidate error beT
The remaining algorithms address single and double errors in the symmetric channel, including mixed information/parity errors and two information errors with a Vandermonde matrix.
- Recovery: Each procedure outputs the recovered codeword after subtracting a candidate error vector that passes the relevant syndrome check.The algorithms explicitly construct c=v−e once the candidate errors are accepted.
- Single information error: With equal matrices B1=⋯=Bk=B, the single-information-error decoder normalizes the syndrome, tests each information position, and verifies the corrected codeword.A candidate is returned only if it satisfies Hc^T=0.
- Mixed errors: For one information error and one parity error, the decoder searches information positions and uses repeated normalized-syndrome values to identify the error locations.It then computes both error values, forms e, and checks the corrected word.
- Two information errors: The Vandermonde two-information-error algorithm computes the syndrome, normalizes it with B^-1, and enumerates candidate pairs j1<j2.For each pair, it sets β=α^j1 and γ=α^j2 before computing candidate error symbols and testing consistency.