© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

IEEE Transactions on Information Theory

Grassmannian Packings From Operator Reed–Muller Codes

Alexei Ashikhmin, A.R. Calderbank

Published Oct 20, 2010• 33 citations

Abstract

This paper introduces multidimensional generalizations of binary Reed-Muller codes where the codewords are projection operators, and the corresponding subspaces are widely separated with respect to the chordal distance on Grassmannian space. Parameters of these Grassmannian packings are derived and a low complexity decoding algorithm is developed by modifying standard decoding algorithms for binary Reed-Muller codes. The subspaces are associated with projection operators determined by Pauli matrices appearing in the theory of quantum error correction and this connection with quantum stabilizer codes may be of independent interest. The Grassmannian packings constructed here find application in noncoherent wireless communication with multiple antennas, where separation with respect to the chordal distance on Grassmannian space guarantees closeness to the channel capacity. It is shown that the capacity of the noncoherent multiple-input-multiple-output (MIMO) channel at both low and moderate signal-to-noise ratio (SNR) (under the constraint that only isotropically distributed unitary matrices are used for information transmission) is closely approximated by these packings.

DOI: 10.1109/tit.2010.2070192

Related papers

Quantum Codes in Classical Communication: A Space-Time Block Code From Quantum Error Correction

Travis C. Cuvelier, S. Andrew Lanham, Brian R. La Cour +1 more

We propose a general framework for noncoherent communication using techniques from the field of quantum error correction (QEC). We first propose an approach for analyzing a classical communication channel as a quantum channel, and develop an extension of the QEC conditions to the classical case. We derive a quantum analogue of the noncoherent multiantenna wireless channel. Restricting to the case in which the number of transmitter and receiver antennas are equal and a power of two, we use the framework to develop a family of space-time block codes for noncoherent multiple-input multiple-output (MIMO) communication. Under a Rayleigh fading assumption, we derive the optimal decoder and bound the probability of symbol detection error. We compare our performance to comparable coherent and noncoherent approaches and achieve competitive performance for various antenna geometries and rates.

IEEE Open Journal of the Communications Society•Jan 1, 2021•8 citations

A Noncoherent Space-Time Code from Quantum Error Correction

S. Andrew Lanham, Travis C. Cuvelier, Corey Ostrove +3 more

In this work, we develop a space-time block code for noncoherent communication using techniques from the field of quantum error correction. We decompose the multiple-input multiple-output (MIMO) channel into operators from quantum mechanics, and design a non-coherent space time code using the quantum stabilizer formalism. We derive an optimal decoder, and analyze the former through a quantum mechanical lens. We compare our approach to a comparable coherent approach and a noncoherent differential approach, achieving comparable or better performance.

arXiv:1812.07115•Conference on Information Sciences and Systems•Mar 1, 2019•9 citations

Minimum Distance Decoding for Reed-Muller Codes using Projection-Aggregation

Bin Zhang, Qin Huang

This paper shows that projection-aggregation (PA) decoding of Reed-Muller (RM) codes can decode up to half the minimum distance d efficiently. By generalizing the false vote matrix from 1-dimensional to higher-dimensional subspaces, we prove that projecting onto disjoint subspaces, regardless of their dimensions, provides at most d/2 − 1 false votes for each codeword bit. Thus, d disjoint subspaces guarantee the correction for errors of d/2 − 1 or less. Moreover, the flexibility in subspace dimensions allows projecting into repetition codes directly, resulting in decoding efficiency. Finally, we prove that PA decoding with d disjoint subspaces decodes up to half the minimum distance in $O(n\sqrt n )$ for RM codes of length n and half rate or less.

IEEE Information Theory Workshop (ITW)•Sep 29, 2025•0 citations

Recursive projection-aggregation decoding of Reed-Muller codes

Min Ye, Emmanuel A. Abbe

We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms using list-decoding. We run our algorithm for AWGN channels and Binary Symmetric Channels at the short code length ($\le 1024$) regime for a wide range of code rates. Simulation results show that in both low code rate and high code rate regimes, the new algorithm outperforms the widely used decoder for polar codes (SCL+CRC) with the same parameters. The performance of the new algorithm for RM codes in those regimes is in fact close to that of the maximal likelihood decoder. Finally, the new decoder naturally allows for parallel implementations.

arXiv:1902.01470•Feb 4, 2019•0 citations

Recursive Projection-Aggregation Decoding of Reed-Muller Codes

Min Ye, Emmanuel A. Abbe

We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms using list-decoding. We run our algorithm for AWGN channels and Binary Symmetric Channels at the short code length (≤ 1024) regime for a wide range of code rates. Simulation results show that in both low code rate and high code rate regimes, the new algorithm outperforms the widely used decoder for polar codes (SCL+CRC) with the same parameters. The performance of the new algorithm for RM codes in those regimes is in fact close to that of the maximal likelihood decoder. Finally, the new decoder naturally allows for parallel implementations.

IEEE Transactions on Information Theory•Mar 3, 2020•79 citations

Recursive projection-aggregation decoding of Reed-Muller codes

Min Ye, Emmanuel A. Abbe

We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms based on list-decoding algorithms and code concatenation. We run our main algorithm for AWGN channels and Binary Symmetric Channels at the short code length (≤ 1024) and low code rate (≤ 0.5) regime. Simulation results show that the new algorithm not only outperforms the previous decoding algorithms for RM codes, it also outperforms the optimal decoder for polar codes (SCL+CRC) with the same parameters by a wide margin. The performance of the new algorithm for RM codes in those regimes is in fact close to that of the maximal likelihood decoder. Finally, the new decoder naturally allows for parallel implementations.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•22 citations

This paper introduces multidimensional generalizations of binary Reed-Muller codes where the codewords are projection operators, and the corresponding subspaces are widely separated with respect to the chordal distance on Grassmannian space. Parameters of these Grassmannian packings are derived and a low complexity decoding algorithm is developed by modifying standard decoding algorithms for binary Reed-Muller codes. The subspaces are associated with projection operators determined by Pauli matrices appearing in the theory of quantum error correction and this connection with quantum stabilizer codes may be of independent interest. The Grassmannian packings constructed here find application in noncoherent wireless communication with multiple antennas, where separation with respect to the chordal distance on Grassmannian space guarantees closeness to the channel capacity. It is shown that the capacity of the noncoherent multiple-input-multiple-output (MIMO) channel at both low and moderate signal-to-noise ratio (SNR) (under the constraint that only isotropically distributed unitary matrices are used for information transmission) is closely approximated by these packings.

We propose a general framework for noncoherent communication using techniques from the field of quantum error correction (QEC). We first propose an approach for analyzing a classical communication channel as a quantum channel, and develop an extension of the QEC conditions to the classical case. We derive a quantum analogue of the noncoherent multiantenna wireless channel. Restricting to the case in which the number of transmitter and receiver antennas are equal and a power of two, we use the framework to develop a family of space-time block codes for noncoherent multiple-input multiple-output (MIMO) communication. Under a Rayleigh fading assumption, we derive the optimal decoder and bound the probability of symbol detection error. We compare our performance to comparable coherent and noncoherent approaches and achieve competitive performance for various antenna geometries and rates.

In this work, we develop a space-time block code for noncoherent communication using techniques from the field of quantum error correction. We decompose the multiple-input multiple-output (MIMO) channel into operators from quantum mechanics, and design a non-coherent space time code using the quantum stabilizer formalism. We derive an optimal decoder, and analyze the former through a quantum mechanical lens. We compare our approach to a comparable coherent approach and a noncoherent differential approach, achieving comparable or better performance.

This paper shows that projection-aggregation (PA) decoding of Reed-Muller (RM) codes can decode up to half the minimum distance d efficiently. By generalizing the false vote matrix from 1-dimensional to higher-dimensional subspaces, we prove that projecting onto disjoint subspaces, regardless of their dimensions, provides at most d/2 − 1 false votes for each codeword bit. Thus, d disjoint subspaces guarantee the correction for errors of d/2 − 1 or less. Moreover, the flexibility in subspace dimensions allows projecting into repetition codes directly, resulting in decoding efficiency. Finally, we prove that PA decoding with d disjoint subspaces decodes up to half the minimum distance in

O(n\sqrt n )

for RM codes of length n and half rate or less.

We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms using list-decoding. We run our algorithm for AWGN channels and Binary Symmetric Channels at the short code length (

\le 1024

) regime for a wide range of code rates. Simulation results show that in both low code rate and high code rate regimes, the new algorithm outperforms the widely used decoder for polar codes (SCL+CRC) with the same parameters. The performance of the new algorithm for RM codes in those regimes is in fact close to that of the maximal likelihood decoder. Finally, the new decoder naturally allows for parallel implementations.

We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms using list-decoding. We run our algorithm for AWGN channels and Binary Symmetric Channels at the short code length (≤ 1024) regime for a wide range of code rates. Simulation results show that in both low code rate and high code rate regimes, the new algorithm outperforms the widely used decoder for polar codes (SCL+CRC) with the same parameters. The performance of the new algorithm for RM codes in those regimes is in fact close to that of the maximal likelihood decoder. Finally, the new decoder naturally allows for parallel implementations.

We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms based on list-decoding algorithms and code concatenation. We run our main algorithm for AWGN channels and Binary Symmetric Channels at the short code length (≤ 1024) and low code rate (≤ 0.5) regime. Simulation results show that the new algorithm not only outperforms the previous decoding algorithms for RM codes, it also outperforms the optimal decoder for polar codes (SCL+CRC) with the same parameters by a wide margin. The performance of the new algorithm for RM codes in those regimes is in fact close to that of the maximal likelihood decoder. Finally, the new decoder naturally allows for parallel implementations.