On codes induced from Hadamard matrices

Basic Information

• Paper ID: 2410.24027
• Title: On codes induced from Hadamard matrices
• Author: Ted Hurley (University of Galway)
• Classification: cs.IT math.IT (Information Theory)
• Publication Date: October 2024 (v2: November 17, 2025)
• Paper Link: https://arxiv.org/abs/2410.24027

Abstract

This paper applies unit derived schemes to Hadamard matrices for constructing and analyzing linear block codes and convolutional codes. The paper constructs encodings with specified types, lengths, and code rates, and derives multiple families of self-dual codes, dual-containing codes, linear complementary dual codes, and quantum error-correcting codes, covering both linear block codes and convolutional codes.

Research Background and Motivation

Research Problems

1. Missing algebraic methods for convolutional code construction: As pointed out by McEliece et al., convolutional codes lack universal algebraic construction and design methods, severely limiting their scale and availability.
2. Systematic construction of specific code types: Need to construct encodings satisfying specific properties (self-dual, dual-containing, LCD codes, etc.) while controlling length, distance, and code rate.
3. Construction of quantum error-correcting codes: Need to construct quantum error-correcting codes through classical coding theory (e.g., CSS method).

Research Significance

• Theoretical significance: Provides a unified algebraic construction framework for coding theory
• Practical applications:
  • LCD codes can resist side-channel attacks and fault attacks
  • Self-dual and dual-containing codes can construct quantum error-correcting codes
  • Convolutional codes are widely used in communication systems (e.g., Viterbi algorithm decoding)

Limitations of Existing Methods

• Walsh-Hadamard codes, while having good distance properties, have extremely low code rates (1/2^k)
• Lack of systematic methods for constructing different types of codes from Hadamard matrices
• Convolutional code construction has long relied on computer generation, lacking algebraic theoretical support

Research Motivation

This paper extends the unit derived method proposed by the author in 27, applying it to Hadamard matrices to achieve:

• Simultaneous construction of linear block codes and convolutional codes
• Construction to specified types, lengths, and code rates
• Obtainable distance bounds
• Generation of multiple encodings from a single Hadamard matrix

Core Contributions

1. Theoretical Framework: Establishes unit derived encoding construction theory based on Hadamard matrices, proving five core propositions (Propositions 2.1-2.5)
2. Algorithm Design: Proposes four universal construction algorithms:
   • Algorithm 1: Constructs LCD linear block codes with arbitrary code rate r/n
   • Algorithm 2: Constructs self-dual linear block codes of length 2n
   • Algorithm 3: Constructs self-dual convolutional codes of length n
   • Algorithm 4: Constructs dual-containing convolutional codes with code rate r/n (r≥n/2)
3. Unified construction of multiple code types: From a single Hadamard matrix, one can construct LCD, self-dual, DC, and quantum error-correcting codes
4. Distance analysis: Provides algebraic methods for distance computation; convolutional code distances can reach twice those of linear block codes
5. Concrete applications: Provides specific cases with H(20), H(28), etc., constructing numerous new encodings

Detailed Methodology

Task Definition

Input: n×n Hadamard matrix H satisfying HH^T = nI_n with elements ±1 Output:

• Linear block codes: n,r,d_q codes (length n, dimension r, minimum distance d, field GF(q))
• Convolutional codes: (n,k,δ;μ,d_f)_q codes (length n, rank k, degree δ, memory μ, free distance d_f)

Constraints:

• Field characteristic p satisfies p∤n (for most constructions)
• For self-dual convolutional codes, i=√(-1) must exist in the field
• Matrix rank conditions

Core Method Architecture

1. Linear Block Code Construction (Basic Method)

Partition Hadamard matrix: H = (A/B), where A is r×n matrix

Key property:

(A/B)(A^T  B^T) = nI_n

In field GF(p) (p∤n), this becomes:

AA^T + BB^T = 0 (mod p)
i.e., AB^T = 0

Results:

• A generates an n,r code
• B^T is the parity-check matrix
• B generates the dual code

2. LCD Code Construction (Proposition 2.1)

Theorem: For H = (A/B), if p∤n, then A generates an LCD code

Proof outline:

• AB^T = 0 ⟹ B generates the dual code of A
• H invertible ⟹ rows of A cannot be non-trivial combinations of rows of B
• Therefore C∩C^⊥ = 0 (LCD property)

3. Self-Dual Linear Block Codes (Proposition 2.2)

Construction: G = (I_n, αH), where α satisfies 1+α²n=0

Key computation:

(I_n, αH)(I_n / αH^T) = I_n + α²nI_n = (1+α²n)I_n

When 1+α²n=0:

• (I_n / αH^T) is a rank-n parity-check matrix
• K = (I_n, αH) generates the dual code
• Therefore the code is self-dual

Implementation details:

• α may exist in GF(p) or its quadratic extension GF(p²)
• Generator matrix is given directly in systematic form

4. Self-Dual Convolutional Codes (Proposition 2.3)

Construction: H = (A/B), n=2m, A and B each m×n

Define generator matrix:

G(z) = A + iBz, where i=√(-1)

Verification of self-duality:

G(z)(iB^T + A^Tz) = (A+iBz)(iB^T+A^Tz)
                   = 0 + nI_m·z - nI_m·z + 0 = 0

Therefore H^T(z) = iB^T + A^Tz is the parity-check matrix, and H(z^(-1))z = A+iB generates the dual code

Catastrophic-free verification:

(A+iBz)A^T = nI_m

Therefore G(z) has a right polynomial inverse, and the code is non-catastrophic

Distance computation:

d_f = d(A) + d(B)

5. Dual-Containing Convolutional Codes (Proposition 2.4)

Construction: H = (A/B), A is r×n, B is (n-r)×n, r>n-r

Define:

B_1 = (0_{t×n} / B), where t=2r-n
G(z) = A + iB_1z

Verification of DC property:

• Construct parity-check matrix H^T(z) = iB^T + C_1z
• Dual code generator: C_1^T + iB
• Verify that dual code is contained in original code

Technical Innovations

1. Matrix partitioning strategy: Obtain different code types from a single Hadamard matrix through different partitioning methods
2. Parameter control: Achieve code rate control (r/n) by selecting number of rows r
3. Field extension techniques: Utilize existence of √(-1) to construct convolutional codes
4. Computable distance: Algebraically compute distances using orthogonality of Hadamard matrices
5. Unified framework: Unified construction methods for linear block codes and convolutional codes

Experimental Setup

Dataset (Hadamard Matrices)

This paper uses Hadamard matrices of multiple sizes:

• Small size: H(12), H(20), H(24), H(28)
• Medium size: H(36), H(40), H(72)
• Large size: H(144)

Matrix types:

• Paley-Hadamard matrices (for sizes 12k)
• Non-decomposable Hadamard matrices (preferred)

Evaluation Metrics

1. Code length n: Length of encoding
2. Dimension/rank r or k: Number of information bits
3. Code rate: r/n (linear block codes) or k/n (convolutional codes)
4. Minimum distance d: Measure of error-correction capability
5. Memory μ: Memory length of convolutional codes
6. Free distance d_f: Distance measure for convolutional codes

Computational Tools

• GAP computer algebra system and its packages:
  • Guava package: Coding theory computations
  • Gauss package: Matrix operations over finite fields
• Used for: Submatrix operations, finite field computations, distance verification

Implementation Details

• Field selection: Primarily using GF(3), GF(5), GF(7) and their extensions GF(3²), GF(5²)
• Rank computation: Compute matrix rank modulo p
• Distance computation:
  • Small lengths (≤100): Direct computer calculation
  • Large lengths: Algebraic methods (Proposition 2.6, Lemma 2.18)

Experimental Results

Main Results

1. Codes Constructed from H(20)

2. Codes Constructed from H(28)

3. Extremal Properties of Ternary Codes

For Paley-Hadamard matrices of H(12k):

• Construct self-dual 12k, 6k, d₃ codes
• Verification results: For k=1,2,3,4,5 (i.e., n=12,24,36,48,60), constructed codes achieve optimal distance
• Theoretical bound: d ≤ ⌊n/12⌋+3
• No extremal codes exist for n=72 and above

Key Findings

1. Distance Performance

Convolutional codes vs. linear block codes:

• Example H(12):
  • Linear block code A: 12,6,6
  • Convolutional code G(z)=A+iBz: distance d_f=12
  • Convolutional code distance is twice that of linear block code

2. Code Rate Flexibility

• Can construct LCD codes with arbitrary code rate r/n (0<r<n)
• Self-dual codes: fixed code rate 1/2
• DC convolutional codes: code rate r/n, r≥n/2

3. Rank Properties (Lemma 2.7)

For prime p|n (p≠2):

rank(H) ≤ n/2 in GF(p)

Verification: Paley-Hadamard matrix H(12k) has rank exactly 6k in GF(3)

Detailed Case Analysis

Prototype Example 2.9: H(12) Detailed Analysis

Matrix decomposition: H = (A/B), A and B each 6×12

Application 1: Self-dual linear block code (GF(3))

• In GF(3): AA^T = 0 (since 3|12)
• A generates 12,6,6₃ self-dual code
• Optimality: Achieves theoretical optimal distance
• Error-correction capability: Can correct 2 errors

Application 2: LCD code (GF(5))

• A generates 12,6,6₅ LCD code
• B generates dual code, also 12,6,6₅

Application 3: Self-dual convolutional code (GF(5))

• G(z) = A + 2Bz (2=√(-1) in GF(5))
• Parameters: (12,6,6;1,12)₅
• Distance: d_f = d(A) + d(B) = 6+6 = 12
• Non-catastrophic: (A+2Bz)A^T = 6I₆ = I₆

Application 4: Length 24 self-dual code (GF(5²))

• Requires α²=2, x²-2 irreducible over GF(5)
• In GF(5²): (I₁₂, αH) generates 24,12,8₅₂ self-dual code

Application 5: Length 24 self-dual code (GF(7))

• α=2 satisfies 1+12α²=0 in GF(7)
• (I₁₂, 2H) generates 24,12,8₇ self-dual code

Example 2.10: High-Memory Convolutional Codes

Construct memory-3 convolutional code from H(12):

A = H[1..3][1..12]
B = H[4..6][1..12]
C = H[7..9][1..12]
D = H[10..12][1..12]
G(z) = A + Bz + Cz² + Dz³

Parameters: (12,3,9;3,24) Distance: 24 (since all submatrices have distance 6)

Large-Scale Applications

Example 2.11: Large Length Codes

• H(72): 72,36,18₃ self-dual code
• H(144): 144,72,d₃ code

Example 2.15: H(36)

• 36,18,12₃ self-dual code (GF(3))
• (36,18,18;1,d)₅ self-dual convolutional code (GF(5))
• Quantum error-correcting code: length 36, distance d

Related Work

Coding Theory Foundations

1. Classical textbooks:
   • Blahut 1: Algebraic codes for data transmission
   • MacWilliams & Sloane 4: Error-correcting codes theory
   • McEliece 3: Information and coding theory
2. Convolutional code theory:
   • Johannesson & Zigangirov 2: Convolutional coding fundamentals
   • Rosenthal et al. 35,36,38: MDS convolutional codes
   • Bocharova et al. 12: Dual convolutional codes

Special Code Types

1. LCD codes:
   • Massey 30,31: First introduction of LCD code concept
   • Carlet et al. 15-17: Modern research on LCD codes
   • Applications: Side-channel attack defense 18,19
2. Self-dual codes:
   • Mallows & Sloane 29: Self-dual code bounds
   • Pless 33: Symmetric codes over GF(3)
   • Mallows et al. 37: Self-dual codes over GF(3)
3. Quantum error-correcting codes:
   • Calderbank & Shor 14: CSS construction
   • Calderbank et al. 13: Quantum codes over GF(4)
   • Steane 39: Simple quantum error-correcting codes

Hadamard Matrices

• van Lint & Wilson 5: Combinatorial foundations
• Horadam 6: Hadamard matrices and their applications (monograph)

Unit Derived Method (Author's Prior Work)

• Hurley & Hurley 8,9,22-25: Development of unit derived method
• Hurley 27: Final linear block and convolutional codes (foundation of this paper)
• Hurley 26,28: MDS code construction

Advantages of This Paper Over Related Work

1. Unified framework: First to uniformly handle linear block codes and convolutional codes
2. Algebraic construction: Solves McEliece's problem of missing algebraic convolutional code construction
3. Multiple code types: Construct various code types from a single matrix
4. Computable distances: Provides algebraic distance computation methods
5. Large-scale feasibility: Can construct large-length, high-rate codes

Conclusions and Discussion

Main Conclusions

1. Theoretical contributions:
   • Establishes complete theoretical framework for encoding construction based on Hadamard matrices
   • Proves five core propositions, provides four universal algorithms
   • Unifies construction methods for linear block codes and convolutional codes
2. Construction capabilities:
   • Can construct LCD codes with arbitrary code rates
   • Can construct self-dual, DC, and quantum error-correcting codes
   • Obtain multiple different code types from a single Hadamard matrix
3. Performance advantages:
   • Convolutional code distances can reach twice those of linear block codes
   • Ternary codes achieve extremal properties at small lengths
   • Large-length, high-rate implementation feasible

Limitations

1. Field restrictions:
   • Most constructions require p∤n
   • Self-dual convolutional codes require √(-1) existence
   • Some constructions require field extensions
2. Distance computation:
   • Difficult to compute distances exactly for large lengths
   • Relies on algebraic methods and computer verification
   • Only estimates possible in some cases
3. Hadamard matrix dependence:
   • Requires explicit expression of Hadamard matrices
   • Non-decomposable Hadamard matrices perform better but are harder to construct
   • Unresolved Hadamard conjecture limits available sizes
4. High-memory convolutional codes:
   • Paper mainly focuses on memory-1 cases
   • High-memory cases left for future research (only Example 2.10 given)
5. Practical application verification:
   • Lacks performance testing in actual communication systems
   • Decoding complexity analysis insufficient

Future Directions

1. Theoretical extensions:
   • Systematic construction of high-memory convolutional codes
   • Applications of other types of orthogonal matrices
   • In-depth research over non-binary fields
2. Distance improvements:
   • More precise distance bounds
   • MDS code construction achieving Singleton bound
   • Asymptotic property analysis
3. Application expansion:
   • Practical communication system implementation
   • Applications in quantum computing
   • Cryptographic applications
4. Computational optimization:
   • Efficient decoding algorithms
   • Parallel implementation
   • Hardware-friendly design

In-Depth Evaluation

Strengths

1. Strong theoretical innovation:
   • First systematic application of Hadamard matrices to construct multiple code types
   • Solves long-standing problem of algebraic convolutional code construction
   • Innovative application of unit derived method
2. Good method uniformity:
   • Unified treatment of linear block codes and convolutional codes
   • Unified framework for different code types (LCD, self-dual, DC)
   • Complete chain from theory to algorithms to applications
3. High practical value:
   • Provides explicit construction algorithms
   • Achievable for arbitrary code rates and lengths
   • Easy to implement with GAP system
4. Sufficient experiments:
   • Multiple sizes of Hadamard matrices
   • Multiple finite fields (GF(3), GF(5), GF(7) and extensions)
   • Detailed prototype examples (Example 2.9)
5. Clear writing:
   • Well-structured hierarchy
   • Clear logic in definitions, propositions, algorithms, and applications
   • Rigorous mathematical derivations

Weaknesses

1. Theoretical completeness:
   • Handling of p|n case not systematic enough
   • High-memory convolutional code theory incomplete
   • Some proofs too brief (e.g., distance proof in Proposition 2.3)
2. Experimental limitations:
   • Lacks systematic comparison with existing optimal codes
   • Distance computation mainly relies on computer (length ≤100)
   • Missing decoding performance experiments
3. Insufficient application guidance:
   • How to select appropriate Hadamard matrices?
   • Parameter selection strategies for different application scenarios?
   • Missing decoding complexity analysis
4. Reproducibility:
   • No code or concrete implementation provided
   • Construction of some Hadamard matrices not specified
   • GAP implementation details insufficient
5. Comparative analysis:
   • Insufficient detailed comparison with Walsh-Hadamard codes
   • Missing comparison with other algebraic construction methods
   • Insufficient performance-complexity tradeoff analysis

Impact

1. Academic contribution:
   • Provides new construction tools for coding theory
   • Promotes application of Hadamard matrices in coding
   • May inspire subsequent series of research
2. Practical value:
   • Quantum error-correcting code construction has practical application potential
   • LCD codes have application value in security domain
   • Large-length code construction meets modern communication needs
3. Reproducibility:
   • Theoretical methods clearly reproducible
   • Requires GAP system support
   • Concrete implementation requires some effort
4. Limitations:
   • Depends on existence of Hadamard matrices
   • Some constructions require field extensions
   • Practical system applications need further verification

Applicable Scenarios

1. Theoretical research:
   • Algebraic construction methods in coding theory
   • Application research of Hadamard matrices
   • Quantum information theory
2. Practical applications:
   • Quantum communication: Quantum error-correcting code construction
   • Secure communication: LCD codes resisting side-channel attacks
   • Data storage: High-rate error-correcting codes
   • Wireless communication: Convolutional code applications
3. Teaching purposes:
   • Case studies in coding theory courses
   • Application examples of algebraic methods in coding
   • Teaching applications of Hadamard matrices
4. Inapplicable scenarios:
   • Applications requiring extremely high code rates (>0.9)
   • Scenarios extremely sensitive to decoding complexity
   • Applications requiring soft-decision decoding

Key References

1. 3 McEliece: Classical textbook on information and coding theory, points out missing algebraic construction for convolutional codes
2. 6 Horadam: Authoritative monograph on Hadamard matrices and their applications
3. 13,14 Calderbank & Shor: Pioneering work on CSS quantum error-correcting code construction
4. 27 Hurley: Theoretical foundation of this paper, final linear block and convolutional codes
5. 31 Massey: Pioneering work on LCD codes
6. 35,38 Rosenthal et al.: Important research on MDS convolutional codes

Overall Assessment: This is an excellent paper with strong theoretical innovation and systematic complete methodology. The author successfully combines Hadamard matrices with the unit derived method, establishing a unified framework for constructing multiple code types, particularly solving the difficult problem of algebraic convolutional code construction. The paper's main value lies in providing a complete methodology from theory to algorithms to applications, with significant academic significance and application potential. Main weaknesses include incomplete high-memory convolutional code theory and insufficient practical application verification. Recommended future work should strengthen practical system implementation and performance testing.