{'fraction_non_alphanumeric': 0.035168396618928746, 'fraction_numerical': 0.013182674199623353, 'mean_word_length': 4.705647176411794, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Error Correction Code Transformer

Error correction code is a major part of the communication physical layer, ensuring the reliable transfer of data over noisy channels. Recently, neural decoders were shown to outperform classical decoding techniques. However, the existing neural approaches present strong overfitting due to the exponential training complexity, or a restrictive inductive bias due to reliance on Belief Propagation. Recently, Transformers have become methods of choice in many applications thanks to their ability to represent complex interactions between elements. In this work, we propose to extend for the first time the Transformer architecture to the soft decoding of linear codes at arbitrary block lengths. We encode each channel's output dimension to high dimension for better representation of the bits information to be processed separately. The element-wise processing allows the analysis of the channel output reliability, while the algebraic code and the interaction between the bits are inserted into the model via an adapted masked self-attention module. The proposed approach demonstrates the extreme power and flexibility of Transformers and outperforms existing state-of-the-art neural decoders by large margins at a fraction of their time complexity.


Introduction
Reliable digital communication is of major importance in the modern information age and involves the design of codes to be robustly decoded under noisy transmission channels. While optimal decoding is defined by the NP-hard maximum likelihood rule, the efficient decoding of algebraic block codes is an open problem. Recently, powerful learning-based techniques have been introduced to this field. At the present time, deep learning models implementing parameterized versions of the legacy Belief Propagation (BP) decoders dominate [19,20,18,21,4]. This approach is appealing since the exponential size of the input space is mitigated by ensuring that certain symmetry conditions are met. In this case, it is sufficient to train the network on a noisy version of the zero codeword. However, this approach remains extremely restrictive due to the strong inductive bias induced by the corresponding Tanner graph.
Model-free decoders [23,10,13] employ generic neural networks and may potentially benefit from the application of powerful architectures that have emerged in recent years in various fields. However, such decoders suffer from the curse of dimensionality, since the training grows exponentially with the number of information bits [29]. A major challenge of models free decoders, therefore, is difficulty of the network to learn the code, and to detect most reliable components of the code, especially for the basic multi-layers perceptron based architectures suggested in the literature.
In this work, we propose a model free decoder built upon the Transformer architecture [28]. As far as we can ascertain, this is the first time Transformers is adapted to error correction codes. Our Transformer employs a high dimensional scaled element-wise embedding of the input that can be seen as a positional and reliability encoding. Our decoder employs an adapted-mask self-attention mechanism, in which the interaction between bits follows the code's parity check matrix, enabling the incorporation of domain knowledge into the model.
Applied to a wide variety of codes, our method outperforms the state-of-the-art learning-based solutions by very large margins even with very shallow architectures, enabling potential deployment. This is the first time a decoder designed de-novo outperforms neural BP-based decoders.

Related Works
Over the past few years, the emergence of deep learning has demonstrated the advantages of Neural Networks in many communication applications such as channel equalization, modulation, detection, quantization, compression, and decoding [12]. In [23] the entire coding-decoding channel transmission pipeline was abstracted as a fully parameterized autoencoder. In many scenarios, neural networks based methods outperform existing decoders, as well as popular codes [20,10].
Two main classes of Neural decoders can be established in the current literature [25]. Model-free decoders employ general neural network architectures as in [5,10,13,2]. The results obtained in [10] for polar codes (n = 16) are similar to the maximum a posteriori (MAP) decoding results. However, the exponential number of possible codewords make the decoding of larger codes infeasible. In [2], a preprocessing of the channel output allows the decoder to remain provably invariant to the codeword and enables the deployment of any kind of model without any overfitting cost. The Model-free approaches generally make use of stacked fully connected networks or recurrent neural networks in order to simulate the iterative process existing in many legacy decoders. However, these architectures have difficulties in learning the code and analyzing the reliability of the output, and generally require prohibitively huge parameterization or expensive graph permutation preprocessing [2].
The second class is that of model-based decoders [19,20] implementing parameterized versions of classical BP decoders where the Tanner graph is unfolded into a neural network in which weights are assigned to each variable edge, showing improvement in comparison to the baseline BP method. Recently, [25] presented a data-driven framework for codeword permutation selection as a predecoding stage. A self-attention mechanism is applied over several permutations embedding to estimate the best permutation (among a given set) to be decoded. A combination of the BP model with hyper-graph network was shown to enhance performance [21]. Further improvements over the latter were obtained by introducing an autoregressive signal based on previous state conditioning and SNR estimation [22].
Transformer neural networks were originally introduced for machine translation [28] and they now dominate the performance tables for most applications in the field of Natural Language Processing (NLP), e.g., [28,7]. Transformer encoders primarily rely on the self-attention operation in conjunction with feed-forward layers, allowing manipulation of variable-size sequences and learning of long-range dependencies. Many works extended the Transformer architecture from NLP to various applications such as computer vision [8], speech analysis [17] and molecular properties prediction [6].

Background
We provide the necessary background on error correction coding and the Transformer architecture.

Coding
We assume a standard transmission that uses a linear code C. The code is defined by the binary generator matrix G of size k × n and the binary parity check matrix H of size (n − k) × n defined such that GH T = 0 over the two elements Galois field.
The input message m ∈ {0, 1} k is encoded by G to a codeword x ∈ C ⊂ {0, 1} n satisfying Hx = 0 and transmitted via a Binary-Input Symmetric-Output channel (e.g. an AWGN channel). Let y denote the channel output represented as y = x s + z where x s denotes the Binary Phase Shift Keying (BPSK) modulation of x (i.e., over {±1}), and z is a random noise which is independent of the transmitted x.
The main goal of the decoder f : R n → R n is to provide a soft approximationx = f (y) of the codeword. An illustration of the coding framework is presented in Figure 1. We wish to employ the Transformer architecture as part of a model-free approach for decoding. We, therefore, follow the preprocessing and post-processing of [2] to remain provably invariant to the transmitted codeword and to avoid overfitting. This step involves a transformation of the channel output y entailing a loss of information without implying any intrinsic performance penalty in decoding, i.e., the preprocessing coupled with an appropriately designed decoder can achieve MMSE decoding.
The preprocessing replaces y with a vector of a dimensionality 2n − k defined as where, [·, ·] denotes vectors concatenation, |y| denotes the absolute value (magnitude) of y and s(y) = Hy b ∈ {0, 1} n−k denotes the binary code syndrome obtained via the multiplication of the binary mapping y b of y by the parity check matrix.
The post-processing step plugs back the vector elements of y. Namely, the prediction takes the form In our setting the decoder is parameterized by θ and our model takes the explicit form: x = y · f θ (|y|, Hy b ).

Transformers
The Transformer was introduced as a novel, attention-based building block for machine translation [28]. The input sequence is first embedded into a high-dimensional space, coupled with positional embedding for each element. The embeddings are then propagated through multiple normalized self-attention and feed-forward blocks.
The self-attention mechanism introduced by Transformers is based on a trainable associative memory with (key, value) vector pairs where a query vector q ∈ R d is matched against a set of k key vectors using scaled inner products as follows where Q ∈ R N ×d , K ∈ R k×d and V ∈ R k×d represent the packed N queries, k keys and values tensors respectively. Keys, queries and values are obtained using linear transformations of the sequence' elements. A multi-head self-attention layer is defined by extending the self-attention mechanism using h attention heads, i.e. h self-attention functions applied to the input, reprojected to values via a dh × D linear layer.

Error Correction Code Transformer
We present the elements of the proposed Transformer decoder, the complete architecture, and the training procedure.

Positional Reliability Encoding
We first consider each dimension of {ỹ i } 2n−k i=1 separately and project each one to a high d dimensional where {W j ∈ R d } 2n−k j=1 denotes the one-hot encoding defined according to the bit position. The embedding is modulated by the magnitude and the syndrome values such that less reliable elements (i.e. low magnitude) collapse to the origin. This propriety becomes especially appealing when applied to the standard dot product of the self-attention module: for the first layer and two distinct information bits embedding φ i , φ j we have where an unreliable information bit vanishes and a non-zero syndrome entails a negative scaling, potentially less impacting the softmax aggregation as illustrated in Sec. 6.
In contrast to [2], which requires permutation of the code in order to artificially provide to the fully connected network indications about the most reliable channel outputs, in our construction, the channel output reliability is directly obtained and maintained in the network via the scaled bit-wise embedding. The proposed scaled encoding can be thought of as a positional encoding according to the input reliability since the bit positions are fixed. We note that representing the codeword by a set of one-hot vectors is very much different than any of the existing methods.

Code Aware Self-Attention
In order to detect and correct errors, a decoder must analyze and compare the received word bits via the parity check equations, such that a non-zero syndrome indicates that channel errors have occurred. In our Transformer based architecture, bits comparisons become natural via the self-attention interaction mechanism.
However, comparing every pair of elements as generally performed in Transformers architectures is sub-optimal, since not every bit is necessarily related to all the others. We propose to make use of the self-attention mechanism in order to incorporate fundamental domain knowledge about the relevant code. Specifically, it is used to indicate that the syndrome values should be dependent on the corresponding parity check bits solely.
Thus, for a given algebraic code defined by the matrix H we propose to defined a function g(H) : {0, 1} (n−k)×k → {−∞, 0} 2n−k×2n−k defining the mask to be applied to the self-attention mechanism such that We propose to build the symmetric mask such that it contains information about every pairwise bit relations as follows. The mask is first initialized as the identity matrix. For each row i of the binary parity check matrix H, we unmask at the locations of every pair of ones in the row, since those bits are connected and may impact each other as well as the syndrome in the decoding procedure. We also unmask the location of pair of ones with the corresponding syndrome bit at n + i, since they define the parity check equations.
We summarize the construction of the mask in Algorithm 11. This construction enables more freedom in decoding than the relations enabled by the Tanner graph, since related bits may have an impact on each other beyond the parity check equations as depicted in Figure 2. While regular Transformer can be assimilated to a neural network applied on a complete graph, the proposed mask can be seen as the adjacency matrix of the Tanner graph extended to a two rings connectivity. In contrast to BP, which collapses the information via interleaved variable and check layers, the masked self-attention allows the simultaneous cross-analysis of related elements.
Most importantly, since the mask is fixed and computed once, the self-attention quadratic complexity bottleneck O(n 2 d) is now reduced to the density of the code O( ij (H) ij d). This propriety is especially appealing for low density codes (e.g. [9]), while in all our experiments the original complexity of the self-attention is reduced by 84% in average as presented in Sec. 6.

Architecture and Training
The initial encoding is defined as one hot encoding of the 2n − k code positions and set the model embedding dimension d. The decoder is defined as a concatenation of N decoding layers composed of self-attention and feed-forward layers interleaved by normalization layers. The output module is defined by two fully connected layers. The first layer reduces the element-wise embedding to a one-dimensional 2n − k vector and the second to a n dimensional vector representing the soft decoded noise. An illustration of the model is given in Figure 3.
The dimension of the feed-forward network is four times the size of the embedding dimension [28] and is composed of GEGLU layers [27] and layer normalization is set in pre-layer norm setting as in [15,30]. We use an eight head self-attention module in all the experiments.
The training objective is the cross-entropy function where the goal is to learn to predict the multiplicative noisez [2]. Denoting the soft multiplicative noisez s such that y = x szs , we obtaiñ z s =z s x 2 s = yx s . Thus, the binary multiplicative noise to be predicted is defined byz = bin(y · x s ), such that the loss computed for a single received word y is The estimated binary codeword is straightforwardly obtained asx = bin(sign(f θ (y) · y)).
The Adam optimizer [14] is used with 128 samples per minibatch for 1000 epochs with 1000 minibatches per epoch. For N = 10 architectures we trained the models for 1500 epochs. We note that more epochs can be beneficial for the performance. However, the current setting is more than enough to already set new SOTA performance. By the model construction and its input preprocessing, Figure 3: Illustration of the proposed Transformer architecture. The main differences from other Transformers are the initial scaled bit-embedding, the construction of the code aware masked selfattention, and the output module.
the zero codeword is enough for training. The additive Gaussian noise is sampled randomly per batch in the {3, . . . , 7} normalized SNR (i.e. E b /N 0 ) range. We initialized the learning rate to 10 −4 coupled with a cosine decay scheduler down to 5 · 10 −7 at the end of the training. No warmup has been employed [30].

Experiments 1
In order to evaluate our method, we train the proposed architecture with three classes of linear block codes: Low-Density Parity Check (LDPC) codes [9], Polar codes [1] and Bose-Chaudhuri-Hocquenghem (BCH) codes [3]. All the parity check matrices are taken from [11]. The proposed architecture is solely defined by the number of encoders layers N and the dimension of the embedding d. We compare our method to the BP algorithm, to the augmented hypernetwork BP algorithm of [21] (hyp BP), to the RNN architecture of [2] and the very recent SOTA performance of [22] (AR BP). All the results are obtained from the corresponding papers. The results are reported as bit error rates (BER) for different normalized SNR values (dB). We follow the testing benchmark of [21,22]. During test, our decoder decodes at least 10 5 random codewords to obtain at least 500 frames with errors at each SNR value.
The results are reported in Tab. 1 where we present the negative natural logarithm of the BER. For each code we present the results of the BP based competing methods for 5 and 50 iterations (first and second row), corresponding to 10 and 100 layers neural network respectively. We present our framework performance for six different architectures with N = {2, 6} d = {32, 64, 128} respectively (first to third row). Since LDPC codes are optimized for BP decoding [26], we also present for these codes the performance of a N = 10, d = 128 architecture. We can see our approach outperforms the current SOTA results by very large margins on several codes at a fraction of the number of iterations and is able to outperform legacy methods (e.g. BP) at convergence even with extremely shallow architecture (e.g. N = 2, d = 32). We remark the proposed method seems to perform better for high rate (i.e. k n ) codes. We provide plots of more BER values for some of the codes in Figure 4(a,b) for Polar(64,32) and BCH(63,51) codes, respectively. Our method is able to outperform the converged AR-BP model by up to two orders of magnitudes for high SNR values.
In Fig. 4(c), We compare our method with the best model of [2] on the only code provided BCH(127,64). Their network is built as a five layers stacked GRU model with five iterations with an embedding of 5(2n − k) = 950 trained for 5000 epochs with a batch size of 1000. As can be seen, our method outperforms this model by up to 211% ratio with only half the number of layers, one-tenth the number of parameters, and a fraction of the training requirements. Concurrent results are obtained after L = 5 BP iterations in first row (i.e. 10 layers neural network) and at convergence results in second row obtained after L = 50 BP iterations (i.e. 100 layers neural network). Best results in bold, second best is underlined, and the minimal Transformer architecture to outperform every other competing method is in italic. Our performance are presented for seven different architectures: for N = {2, 6}, we present results for d = {32, 64, 128} (first to third row), and for N = 10 we run only the d = 128 configuration.

Analysis
We study the impact of the proposed embedding and the masking procedure and we analyze and compare the complexity of our method to other methods.

Impact of the Reliability Embedding
We depict in Figure 5 the impact of the scaled embedding on the self-attention mechanism. We chose the popular Hamming(7, 4) code where we corrupt the zero codeword with additive noise at the first bit (zero bit index), involving a non-zero syndrome at the first parity check equation. We present the masked softmax values of the self-attention map at index zero, i.e. the influence of the first (unreliable) bit on the self-attention aggregation (first column of the map). We can see the first bit embedding is impactless when it is corrupted and then detectable, while its impact on the syndrome embedding is considerably increased. When the network already corrected the bit (last layers(s)) the values return to normal.

Ablation Study: Masking
We present in Figure 6 the impact of the proposed mask on the training convergence (overfitting cannot be noticed in our setting). We show an unmasked architecture where we leave the network at learning the code by itself (i.e. g(H) = 0), compared to our proposed masking approach. The benefit obtained with the mask is clear and can be understood by the difficulties the Transformer may have in learning the code by itself. Therefore, the connectivity provided by the proposed masking framework reduces the loss by 76%, 69% and 66% for the BCH(63, 36), POLAR(64, 32) and LDPC(49, 24) codes respectively.

Complexity Analysis
We first present in Figure 7 the sparsity ratio of the masked self-attention map, as well as the induced complexity ratio of the symmetric map for several codes presented in the Results section. The ratio is computed compared to the O(n 2 ) legacy self-attention map size. We can see the sparsity can reach up to more than 80% while the pairwise computation ratios range from 5 to 35% only.  The complexity of the network is defined by O(N (d 2 (2n − k) + hd) where h n 2 denotes the fixed number of computations of the self-attention module. Acceleration of the proposed Transformer via architectural modification or neural networks acceleration (e.g. pruning, quantization) [16] is left for future work.
In comparison, the existing AR-BP SOTA method of [22] requires O(2N (nd v d f d g + n 2 d v + (n − k) 2 + d f )) more operations than Hyper BP [21], where d v , d f , d g are the number of variable nodes, complexity of the hyper network and the network respectively. Typical networks f and g are a 128 dimensional FC network with 4 layers and a 16 dimensional FC network with 2 layers respectively.With these hyperparameters, the nd v d f d g part of the complexity is approximately nd v 128 2 . Moreover, the method of [22] cannot be parallelized due to the hypernetwork structure, i.e. each sample defines a different set of parameters. Thus, our network largely surpasses the existing state-of-the-art error rates with much less time complexity. Hyper-BP [21] is little less computationally intensive since it adds a complexity term of O (2N nd v d f d g ) on top of BP, but this approach as well as the original model-based network of [19] are much less competitive in term of accuracy.

Conclusions
We present a novel Transformer architecture for the decoding of algebraic block codes. The proposed model allows effective representation of interactions based on the high dimensional embedding of the channel output and a code-dependent masking scheme of the self-attention module. The proposed framework is more efficient than standard Transformers due to the sparse design of existing block codes, making its training and deployment extremely affordable. Even with a limited number of computational blocks, it outperforms popular (neural) decoders on a broad range of code families. We believe this new architecture will allow the development and adoption of new families of performing Transformer based codes capable to set new standards in this field.