Learning Quantization in LDPC Decoders

Marvin Geiselhart1, Ahmed Elkelesh1, Jannis Clausius1, Fei Liang2, Wen Xu3, Jing Liang2 and Stephan ten Brink1

1 Institute of Telecommunications, Pfaffenwaldring 47, University of  Stuttgart, 70569 Stuttgart, Germany

2 Shanghai Research Center, Huawei Technologies Co., Ltd, Shanghai, China

3 Munich Research Center, Huawei Technologies Duesseldorf GmbH, Riesstr. 25, 80992 Munich, Germany

Email<EMAIL_ADDRESS>
MLmaximum likelihood
BPbelief propagation
BPLbelief propagation list
LDPClow-density parity-check
BERbit error-rate
BPSKbinary phase shift keying
AWGNadditive white Gaussian noise
LLRlog-likelihood ratio
MAPmaximum a posteriori
BLERblock error-rate
SCLsuccessive cancellation list
SCsuccessive cancellation
BI-DMCbinary input discrete memoryless channel
CRCcyclic redundancy check
CA-SCLCRC-aided successive cancellation list
BECbinary erasure channel
BSCbinary symmetric channel
3GPP3rd Generation Partnership Project
eMBBenhanced Mobile Broadband
CNcheck node
VNvariable node
GenAlgGenetic Algorithm
CSIchannel state information
OSDordered statistic decoding
MWPC-BPminimum-weight parity-check BP
FFGForney-style factor graph
MBBPmultiple-bases belief propagation
URLLCultra-reliable low-latency communications
DMCdiscrete memoryless channel
SGDstochastic gradient descent
BCEbinary cross entropy
LUTlook-up table
BGbase graph
WSweight sharing

Finding optimal message quantization is a key requirement for low complexity BP decoding.
To this end, we propose a floating-point surrogate model that imitates quantization effects as additions of uniform noise, whose amplitudes are trainable variables.
We verify that the surrogate model closely matches the behavior of a fixed-point implementation and propose a hand-crafted loss function to realize a trade-off between complexity and error-rate performance.
A deep learning-based method is then applied to optimize the message bitwidths.
Moreover, we show that parameter sharing can both ensure implementation-friendly solutions and results in faster training convergence than independent parameters.
We provide simulation results for 5G LDPC codes and report an error-rate performance within 0.2 dB of floating-point decoding at an average message quantization bitwidth of 3.1 bits.
In addition, we show that the learned bitwidths also generalize to other code rates and channels.

§ INTRODUCTION

Channel coding is an essential must in any communication system.
The most widely used channel codes nowadays are LDPC codes (e.g., in WiMAX, WLAN 802.11n, DVB-S2/T2/C2 and 5G data channel) motivated by the presence of a well-understood BP decoder.
Unfortunately, most of the power dissipation in the receiver side is attributed to the channel decoder operations (i.e., error correction consumes most energy and chip area) [1].
Thus, possible improvements might bring large gains in terms of energy efficiency.

BP decoding of LDPC codes involves passing real-valued infinite precision LLR messages between the VN and the CN.
However, in order to reduce the hardware implementation complexity those messages are typically discretized to a practical finite-precision representation.
On one hand, reducing the message bitwidths degrades the error-rate performance especially at high SNR (i.e., error floor region) [2].
On the other hand, reducing the bitwidths of the processed quantities inside the decoder leads to a reduced area/memory requirement, possibly increased maximum operating frequency, reduced routing congestion and, thus, high throughput decoder implementations.

In this paper, we focus on optimizing the quantization of the messages involved in the hardware-popular min-sum LDPC decoder (i.e., channel LLR, VN-to-CN and CN-to-VN messages) using machine learning approaches (i.e., SGD optimizers).
However, as the quantization is a discontinuous operation whose gradient is zero almost everywhere, we propose the usage of a surrogate model for training instead.
It is worth mentioning that this surrogate model approach is also applicable to other applications where quantization optimization is needed.

We investigate the usage of the general concept of the surrogate model in the context of message quantization of an LDPC decoder (i.e., learn quantization bitwidths) in order to reduce the overall decoding complexity without sacrificing the error-rate performance.
This model is used only for training (i.e., finding optimal message bitwidths) and is replaced by a regular decoder with “real” quantization afterwards.
Note that, here, we focus on decoding LDPC codes from the 5G standard, however, it is straightforward to apply the proposed techniques to other (de)coding approaches.

We propose a hand-crafted loss function based on a fixed performance-complexity trade-off parameter $\lambda_c$ (i.e., trade-off between error-rate performance and decoding complexity).
The obtained results use different quantization bitwidths for different messages in the decoding graph which can be interpreted as message importance.
Moreover, we show that weight sharing is possible across different BP iterations.

dots=[line width=1pt , line cap=round,dash pattern=on 0pt off 4pt,black]

arrow = [thick,->, rounded corners=5pt]

loosely dotted=          [dash pattern=on off 8pt]

NN =[rectangle, rounded corners,   align=flush center,minimum width=3cm,minimum height=1.0cm,text centered,
draw=red, fill=red!0 , thick , label=[red]:NN];

box1 =[rectangle, dashed,  align=flush center,minimum width=4.5cm, minimum height=4.5cm,text centered,
draw=blue, fill=red!0 , thick , label=[black]:];
boxText =[rectangle,  align=flush center,minimum width=15.74776cm,
minimum height=15.74776cm,text centered,
draw=black!50, fill=red!0 , thick ];
interleaver =[rectangle, rounded corners,   align=flush center,minimum width=1.0cm, minimum height=1.0cm,text centered,
draw=black, fill=red!0 , thick, text=black];
plus =[circle,draw=black, fill=white, inner sep=2pt,minimum size=5pt];

box =[rectangle,   align=flush center,minimum width=1.0cm, minimum height=1.1cm,text centered,
draw=black, fill=red!0 , thick, text=black];

[box1, draw=anthrazit, minimum width=7.3cm, minimum height=4.cm, label=[black]:Quantized decoder at iteration $i$] at (6.5*,1) ;

[] (start) at (0* ,0) ;

[box, draw= apfelgruen,align=center,minimum height=1.0cm] (enc) at (1* ,0) 5G LDPC

[box, draw= apfelgruen] (map) at (2* ,0) BPSK;

[box, draw= rot] (awgn) at (3* ,0) AWGN;

[box, draw=mittelblau] (demap) at (4* ,0) Demap;

[box, draw=mittelblau] (q1) at (5* ,0) $\operatorname{Q}(\cdot)$;

[box, draw=mittelblau] (VN) at (6* ,0) VN

[box, draw=mittelblau] (q2) at (7.* ,0* ) $\operatorname{Q}(\cdot)$;
[box, draw=mittelblau] (q3) at (7.* ,1* ) $\operatorname{Q}(\cdot)$;

[box, draw=mittelblau] (CN) at (8* ,0* ) CN

[box, draw=lila] (BCE) at (4* ,-1* ) Binary Cross Entropy

[box, draw=lila] (C) at (4* ,1* ) Complexity

[] (end) at (6* ,-2) ;

[dspconn] (start) – node [dspnodefull] (inter1)  node[above]$\mathbf{u}$(enc);
[dspconn] (enc) – node[above]$\mathbf{c}$(map);
[dspconn] (map) – node[above]$\mathbf{x}$(awgn);
[dspconn] (awgn) – node[above]$\mathbf{y}$(demap);
[dspconn] (demap) – node[above]$\mathbf{\ell}_{\mathrm{ch}}$(q1);
[dspconn] (q1) – node[above]$\tilde{\mathbf{\ell}}_{\mathrm{ch}}$(VN);
[dspconn] (VN) – node[above]$\mathbf{q}$(q2);
[dspconn] (q2) – node[above]$\tilde{\mathbf{q}}$(CN);
[dspconn] (CN) |- node[near start, right]$\mathbf{r}$(q3);
[dspconn] (q3) -| node[near start,below ]$\tilde{\mathbf{r}}$(VN);

[dspconn, dashed, draw=lila] (VN)  |- node[near start,right]$\mathbf{\ell}_{\mathrm{total}}$ (BCE);

[dspconn, dashed, draw=lila] (inter1) |- node[above](BCE);

[dspconn, dashed, draw=lila] (q3.150) –  node[near start, above]$\mathbf{\alpha}_{r,i}$(C.20);
[dspconn, dashed, draw=lila] (q1.north) |- node[near start, right]$\mathbf{\alpha}_{\ell}$(C.base east);

[dspconn, dashed, draw=lila] (q2.north) – node[right]$\mathbf{\alpha}_{q,i}$ ($(0,0.5)+(q2.north)$) – ($(-2.5,0.5)+(q2.north)$) – ($(-2.5,2)+(q2)$) – node[above](C);

Block diagram of the surrogate model used for learning the quantization bitwidths.
A hand-crafted loss function is used consisting of a binary cross entropy (BCE) term and a scaled complexity term, see Eq. (<ref>).
Note that we use a systematic 5G LDPC code.

§ PRELIMINARIES

§.§ LDPC Codes

The key aspect of an LDPC code is that the corresponding $(M\times N)$ parity-check matrix $\mathbf{H} = \left [h_{m,l}\right]_{M\times N}$ contains a small number of $1$'s and is therefore sparse. This enables efficient storage of the $\mathbf{H}$-matrix and effective usage of BP decoding. The dimensions $M=N-K$ and $N$ define the code rate $R=\nicefrac{K}{N}$, where $K$ is the number of information bits and $N$ is the length of a codeword.

§.§ Min-Sum Decoding

The min-sum decoder [3] is an iterative message passing decoder that descends from the log-domain version of the BP algorithm introduced by Gallager [4].
The messages, in form of LLR, are exchanged over the Tanner graph [5] of the code, which is a bipartite graph  that divides nodes into $N$ VN and $M$ CN.
We denote messages from VN to CN by $q_{m,l}$ and messages from CN to VN by $r_{m,l}$, where the subscript $l~=~{1,...,N}$ indices a certain VN and $m={1,...,M}$ a specific CN.
The iterative process of exchanging messages is performed until a stopping condition is met (e.g., in this work decoding stops after $N_\mathrm{iters}$ iterations).
The first $q$ messages are initialized by the channel LLR as

\begin{equation*}
q_{m,l} = \ell_{\mathrm{ch},l},~\forall m.
\end{equation*}

Then, the CN are updated and extrinsic $r$ messages are computed as

\begin{equation}\label{eq:CN_update}
r_{m,l} = \left(\prod_{l'\in V(m) \setminus l} \operatorname{sign}\left( q_{m',l} \right)\right)\cdot \underset{l'\in V(m) \setminus l}{\min} | q_{m',l} |,
\end{equation}

where $V(m)$ is the set of VN that is connected to CN $m$.
Correspondingly, the update equation of the VN is

\begin{equation*}
q_{m,l} = \ell_{\mathrm{ch},l} + \sum_{m'\in C(l) \setminus m}r_{m',l},
\end{equation*}

where $C(l)$ is the set of CN that are connected to VN $l$.
Note that the incoming message $r_{m,l}$ is omitted to calculate the extrinsic update of $ q_{m,l}$.
After the final iteration, marginal LLR $\ell_{\mathrm{total}}$ are obtained by adding up all incoming $r$ messages at each VN as

\begin{equation*}
\ell_{\mathrm{total},l} = \ell_{\mathrm{ch},l} + \sum_{m'\in C(l)}r_{m',l}.
\end{equation*}

A hard decision on $\ell_{\mathrm{total}}$ retrieves the codeword bit estimates of the decoder.
Eq. (<ref>) contains the name-giving approximation by $\min(\cdot)$ function. In contrast, the exact formulation results in a product of costly $\tanh(\cdot)$ functions.
As the approximated CN update results in significantly lower complexity at the price of slightly degraded error-rate performance, the min-sum decoder lays the foundation of state-of-the-art implementations for LDPC decoders. Note that the degradation in error-rate performance can be reduced or even nullified by enhancements, such as an attenuation factor or an added offset [6]. However, as both are straightforward extensions in our quantization framework, we stick to the basic min-sum decoder.

§.§ Quantized Decoding

In a hardware-friendly implementation of a message passing LDPC decoder (e.g., min-sum decoder) the messages are usually quantized using a uniform quantization with $b$-bits per message representation.
In [6, 7], $5$-bit and $7$-bit quantizers were used, while in [8] a $4$-bit quantizer was used to implement an unrolled LDPC decoder.
Note that typically the message alphabet does not change over the decoding iterations in order to constraint the hardware implementation complexity.
However, in [2], a quasi-uniform quantization with an adaptive message bitwidth is used, where the messages involved in later iterations are quantized with a larger bitwidth when compared to earlier iterations. In other words, different message representations are used for different iterations.

A quantized min-sum decoding algorithm for LDPC codes is proposed in [9], where the VN update rule is replaced with a LUT that is designed using an information-theoretic criterion (e.g., using density evolution).
Optimizing the LUT-based VN update can accommodate lower bitwidths for all messages involved in the decoding process without sacrificing the error-rate performance (e.g., 3-bit quantizers for internal messages and 4-bit quantizers for the channel LLR).

Another method of designing finite-precision decoders is the information bottleneck algorithm.
Again, the aim is to design lower complexity decoding algorithms with error-rate performance close to high-precision decoders.
Information bottleneck can be used to design LUT-based node update computations.
For more details we refer the interested reader to [10] and the references therein.

§ LEARNING QUANTIZATION

§.§ Quantizer Implementation

legend style=legend cell align=left,align=left,fill opacity=0, text opacity=1, draw=none,at=(0.28,0.8),
legend pos=north west,

+ [rot,line width=1pt , mark options=opacity=0.0,fill=rot, solid]
table[x=x,y=y ,col sep=comma]./tikz/quantizer/quantizer_with_bitwidth_2.txt;
2-bit ;

+ [mittelblau,line width=1pt , mark options=opacity=0.0,fill=rot, solid]
table[x=x,y=y ,col sep=comma]./tikz/quantizer/quantizer_with_bitwidth_3.txt;
3-bit ;

+ [apfelgruen,line width=1pt , mark options=opacity=0.0,fill=rot, solid]
table[x=x,y=y ,col sep=comma]./tikz/quantizer/quantizer_with_bitwidth_4.txt;
4-bit ;

Quantization curves for the proposed “compatible” quantization scheme, $L_\mathrm{limit}=8$.

For maximum efficiency, we allow each value in the decoding algorithm to take a different bitwidth. This way, the memory, wiring and circuit complexity maybe minimized. However, arithmetic operations may require their operands to be the same bitwidth. Therefore, we desire that conversion from a lower bitwidth to a higher bitwidth can be done without any overhead.
For this, we first formulate the constraint that the set of quantization levels of lower bitwidths is always a subset of the set of quantization levels of higher bitwidths. If $\mathcal{Q}_b$ denotes the set of quantization levels for a given bitwidth $b$, this constraint can be expressed as

\begin{equation*}
\mathcal{Q}_b \subseteq \mathcal{Q}_{b+1}.
\end{equation*}

Moreover, $0$ should be a valid quantization level (for all bitwidths) and the quantizer should be symmetric. Thus, there are $2^b-1$ valid quantization levels and the quantization step size is defined as

\begin{equation*}
\alpha(b) = \frac{L_\mathrm{limit}}{2^{b-1}},
\end{equation*}

where $L_\mathrm{limit}$ is an overall scaling parameter that defines the dynamic range of the quantizer

\begin{equation*}
L_{\mathrm{limit}} = \lim_{b\to \infty} \max\{\mathcal{Q}_b\}.
\end{equation*}

Note that the maximum representable value is dependent on $b$ and given by

\begin{equation*}
L_{\mathrm{clip},b} = \max\{\mathcal{Q}_b\} = L_\mathrm{limit} - \alpha(b).
\end{equation*}

Fig. <ref> shows the quantization curves for the proposed scheme for $L_\mathrm{limit}=8$ and $b\in\{2,3,4\}$ bits. Note that a two's complement labeling works naturally with this quantizers, as going to a larger bitwidth corresponds to appending zeros.

§.§ Surrogate Model

Fig. <ref> shows the block diagram of the considered communications model, consisting of LDPC encoding, BPSK mapping, AWGN channel, demapping and min-sum decoding. The goal is finding suitable bitwidths for a fixed-point implementation of the decoder. However, in our proposed approach, we use a floating-point version with a quantizer after each operation, as indicated by blocks labeled $Q(\cdot)$. In particular, we quantize the channel LLR $\ell_\mathrm{ch}$, the VN-to-CN messages $q$ and the CN-to-VN messages $r$. The corresponding quantization steps are the independent trainable parameters $\alpha_{q,i,e}$, $\alpha_{r,i,e}$ and $\alpha_{\ell,l}$, where $i$ denotes the iteration and $e$ denotes the edge of the Tanner graph $(m,l)$ with $h_{m,l}=1$.

To optimize the quantization steps (and, thus, the bitwidths) of the quantizers, we propose to use a surrogate model, where each quantizer is replaced by the addition of a random variable $n$. This random variable models the quantization error (or quantization noise). We use the common assumption that the quantization noise for a uniform quantizer is uniformly distributed and independent of the input signal [11]. For a quantization with quantization step $\alpha$ that rounds to the nearest quantization level, the quantization error is therefore distributed according to $\mathrm{U}(-0.5\alpha,0.5\alpha $). Equivalently, we can draw $n$ from $\mathrm{U}(-0.5,0.5$) and scale it by $\alpha$.
Lastly, we account for the limited number of quantization steps by clipping the result of the addition at $\pm L_\mathrm{clip}$. A block diagram of a single surrogate quantizer is shown in Fig. <ref>. Each quantizer in the surrogate model has its own trainable parameter $\alpha$ that can be optimized using gradient-based methods. For this, we need a suitable differentiable loss function with respect to the trainable parameters $\alpha$.

§.§ Loss Function

dots=[line width=1pt , line cap=round,dash pattern=on 0pt off 7pt,orange]

arrow = [thick,->]

loosely dotted=          [dash pattern=on off 8pt]

NN =[rectangle, rounded corners,   align=flush center,minimum width=3cm,minimum height=1.7cm,text centered,
draw=red, fill=red!0 , thick , label=[red]:NN];

box =[rectangle, rounded corners,   align=flush center,minimum width=1.7cm, minimum height=1.7cm,text centered,
draw=black, fill=red!0 , thick];

boxText =[rectangle,  align=flush center,minimum width=15.74776cm,
minimum height=15.74776cm,text centered,
draw=black!50, fill=red!0 , thick ];

plus =[circle,draw=black, fill=white, inner sep=1,minimum size=30pt, font=];

box1 =[rectangle, dashed,  align=flush center,minimum width=4.5cm, minimum height=5.0cm,text centered,
draw=blue, fill=red!0 , thick , label=[black]:];
[box1, draw=mittelblau, minimum width=4.8cm, minimum height=3.5cm, label=below:$Q(\cdot)$ ] at (2.7,2.75) ;

[dspadder, minimum size=0.6cm] (Demapper) at (2,2) ;
[dspsquare, minimum size=1.4cm, label=above:clipping] (conv_1) at (4,2) ;

($ (conv_1.south west) + (0.5,0.5) $) – ($ (conv_1.north east) + (-0.5,-0.5) $);

($ (conv_1.south west) + (0.5,0.5) $) – node[below]$-L_{\mathrm{clip}}$ ($ (conv_1.south west) + (0.2,0.5) $);

($ (conv_1.north east) + (-0.5,-0.5) $) – node[above]$L_{\mathrm{clip}}$($ (conv_1.north east) + (-0.2,-0.5) $);

[->] ($ (conv_1.south) + (0.0,0.3) $) – ($ (conv_1.north) + (+0.0,-0.3) $);

($ (conv_1) + (-0.1,0.0) $) – node[left]$0$($ (conv_1) + (+0.1,-0.0) $);

[dspmixer, minimum size=0.6cm] (conv_2) at (2,3) ;
[] (end) at (6,2) ;

[label=below :] (h) at (1,3) $\alpha $;
[label=above:$n \sim \mathrm{U} (-0.5\text{,~} 0.5)$] (alpha) at (2,3.55) ;
[label=] (start) at (-0.5,2) ;

[arrow] (start) – node[ near start,above] $x$ (Demapper)  ;
[arrow] (Demapper) – node[ above] $x'$     (conv_1)  ;
[arrow] (conv_1) – node[ above] $\Tilde{x}$     (end)  ;

[arrow] (h) – node[ near start,above]    (conv_2)  ;
[arrow] (alpha.north) – node[ above]      (conv_2)  ;
[arrow] (conv_2) – node[ above]      (Demapper)  ;

A single quantizer $\operatorname{Q}(\cdot)$ of the surrogate model used for training the quantization bitwidths.

A suitable loss function to optimize the error-rate performance using bit-metric decoding is the BCE loss [12]. The reason is that the minimization of the loss is equivalent to maximizing the bit-wise mutual information.
As $\mathbf{\ell}_{\mathrm{total},l}$ are the logits of the message estimate, we apply the sigmoid function in the loss computation. We assume that the code is systematic and, thus, the first $K$ indices of $\mathbf{\ell}_{\mathrm{total}}$ correspond to the information vector $\mathbf{u}$. As a result, the total loss function is given by

\begin{equation}\label{eq:hand_crafted_loss}
\mathcal{L} = \sum_{l=1}^{K}\operatorname{BCE}(\operatorname{sigmoid}(\ell_{\mathrm{total},l}), u_l) + \lambda_\mathrm{c}\cdot C,
\end{equation}

where $C$ models the (bitwidth-based) complexity of the decoding and $\lambda_c$ is a fixed hyper parameter specifying the trade-off between error-rate performance and complexity. In practice, Eq. (<ref>) is estimated using batches of $B$ transmissions of random codewords over the simulated channel. $C$ is defined as the mean of the corresponding quantizer bitwidths

\begin{align*}\label{eq:complexity}
C =& \frac{1}{2 N_\mathrm{iters} \cdot N_\mathrm{msg} + N \cdot N_\mathrm{iters} }  \Bigg. \Bigg[
N_\mathrm{iters} \sum_{l=1}^{N}  \Bigg( \log_2\left(\frac{L_\mathrm{limit}}{\alpha_{\ell,l}}\right)+1 \Bigg) \nonumber\\
&+\sum_{i=1}^{N_\mathrm{iters}} \sum_{e=1}^{N_\mathrm{msg}} \Bigg( \Bigg.  \log_2\left(\frac{L_\mathrm{limit}}{\alpha_{q,i,e}}\right) +1  +\log_2\left(\frac{L_\mathrm{limit}}{\alpha_{r,i,e}}\right) +1 \Bigg) \Bigg. \Bigg] \Bigg..
\end{align*}

As the channel LLR $\ell_\mathrm{ch}$ are required in every iteration, they are counted $N_\mathrm{iters}$ times in the complexity formula.

The surrogate model is then trained (i.e., the parameters $\alpha_{q,i,e}$, $\alpha_{r,i,e}$ and $\alpha_{\ell,l}$) using a SGD-based optimizer, e.g., Adam [13], with batches of $B$ transmissions per epoch.

§.§ Model Conversion

To convert the trained surrogate model to a fixed-point implementation (i.e., real quantizers), the real-valued parameters $\alpha_{q,i,e}$, $\alpha_{r,i,e}$ and $\alpha_{\ell,l}$ are converted to the corresponding bitwidth according to

\begin{equation*}
b(\alpha) = \operatorname{round}\left( \log_2\left(\frac{L_\mathrm{limit}}{\alpha}\right) +1 \right),
\end{equation*}

where $\operatorname{round}(x)$ returns the closest integer to $x$.

§ RESULTS

We evaluate the surrogate model-based quantization bitwidth training using the 5G LDPC code [14, 15] with parameters $N=264$ and $K=132$, which corresponds to the second BG using lifting size $Z=22$. We fix the number of iterations to $N_\mathrm{iters}=10$.

§.§ Surrogate Model Performance

grid style=dotted,anthrazit,
legend columns=1,
legend pos=south west,
legend cell align=left,
legend style=fill,fill opacity=0, text opacity=1, draw=none,
xlabel=$E_\mathrm{b}/N_0$ [dB],
ylabel=BER / BLER,
legend image post style=mark indices=,
mark size=1.5pt,

[color=magenta,line width = 1pt, solid,mark=square,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 9.993e-01
0.50, 9.973e-01
1.00, 9.719e-01
1.50, 8.860e-01
2.00, 6.741e-01
2.50, 3.811e-01
3.00, 1.438e-01
3.50, 3.278e-02
4.00, 4.344e-03
4.50, 3.888e-04

[color=apfelgruen,line width = 1pt, solid,mark=x,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 1.000e+00
0.50, 9.995e-01
1.00, 9.978e-01
1.50, 9.846e-01
2.00, 8.645e-01
2.50, 5.740e-01
3.00, 2.388e-01
3.50, 5.477e-02
4.00, 6.795e-03
4.50, 4.096e-04

[color=black,line width = 1pt, solid,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 9.956e-01
0.50, 9.775e-01
1.00, 9.104e-01
1.50, 7.356e-01
2.00, 4.795e-01
2.50, 2.078e-01
3.00, 6.047e-02
3.50, 1.099e-02
4.00, 1.266e-03
4.50, 7.994e-05

[color=magenta,line width = 1pt, dashed,mark=square,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 3.007e-01
0.50, 2.824e-01
1.00, 2.480e-01
1.50, 1.950e-01
2.00, 1.223e-01
2.50, 5.533e-02
3.00, 1.609e-02
3.50, 3.211e-03
4.00, 3.041e-04
4.50, 2.434e-05

[color=apfelgruen,line width = 1pt, dashed,mark=x,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 3.093e-01
0.50, 2.941e-01
1.00, 2.733e-01
1.50, 2.389e-01
2.00, 1.684e-01
2.50, 8.495e-02
3.00, 2.728e-02
3.50, 4.652e-03
4.00, 5.233e-04
4.50, 2.390e-05

[color=black,line width = 1pt, dashed,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 2.644e-01
0.50, 2.348e-01
1.00, 1.890e-01
1.50, 1.290e-01
2.00, 6.558e-02
2.50, 2.195e-02
3.00, 5.441e-03
3.50, 7.668e-04
4.00, 7.589e-05
4.50, 4.357e-06

(legend) at (axis description cs:0.02,.02);

fill opacity=0,
text opacity=1,
matrix of nodes,
align =left,
row sep = -1,
column sep = -5,
inner sep= 2,
anchor=south west,
column 3/.style=anchor=base west,
] at (legend)
BLER     BER

<ref>     <ref>     3-bit uniform

<ref>     <ref>     3-bit surrogate

<ref>     <ref>     float

Error-rate performance comparison of unquantized, quantized and surrogate min-sum decoding for the (264,132) 5G LDPC code.

First, we assess how close the surrogate model matches a real fixed-point quantization. In Fig. <ref>, we compare the error-rate performance of a 3-bit fixed-point model with the (untrained) surrogate model with an equivalent bitwidth of 3-bit. As a baseline, we also plot the performance of a floating-point implementation. We see that there is a gap of approximately 0.3 dB of the fixed-point implementation to the floating-point baseline. Moreover, the surrogate model performance is slightly worse than that of the fixed-point implementation. We can explain that by the mismatch of the distribution of the quantization error, which is not quite uniform in the actual fixed-point scenario. Hence, the surrogate model's quantization error has a larger variance than the real model.

§.§ Trained Model

[left] at (0, 1.5in)   (i1) $i = 1$;
[left] at (0, -.5in)   (i5) $i = 6$;
[left] at (0, -2.5in)   (i10) $i = 10$;

axis equal,
scale only axis,
axis x line=none,
axis y line=none,
y dir=reverse,
title style=at=(0.5,0.8),anchor=south,
[scatter,only marks, mark=*, mark size=1pt,
point meta=explicit, point meta min=0, point meta max=5]
table[x=y,y=x,meta=color,col sep=comma]tikz/q_i0.csv;

in 0,...,14

[black] (axis cs:*22-.5,-0.5) – (axis cs:*22-.5,176.5);

in 0,...,8

[black] (axis cs:-0.5,*22-0.5) – (axis cs:308.5,*22-0.5);

axis equal,
scale only axis,
axis x line=none,
axis y line=none,
y dir=reverse,
title style=at=(0.5,0.8),anchor=south,
[scatter,only marks, mark=*, mark size=1pt,
point meta=explicit, point meta min=0, point meta max=5]
table[x=y,y=x,meta=color,col sep=comma]tikz/r_i0.csv;

in 0,...,14

[black] (axis cs:*22-.5,-0.5) – (axis cs:*22-.5,176.5);

in 0,...,8

[black] (axis cs:-0.5,*22-0.5) – (axis cs:308.5,*22-0.5);

axis equal,
scale only axis,
axis x line=none,
axis y line=none,
y dir=reverse,
[scatter,only marks, mark=*, mark size=1pt,
point meta=explicit, point meta min=0, point meta max=5]
table[x=y,y=x,meta=color,col sep=comma]tikz/q_i5.csv;

in 0,...,14

[black] (axis cs:*22-.5,-0.5) – (axis cs:*22-.5,176.5);

in 0,...,8

[black] (axis cs:-0.5,*22-0.5) – (axis cs:308.5,*22-0.5);

axis equal,
scale only axis,
axis x line=none,
axis y line=none,
y dir=reverse,
colorbar style=

[scatter,only marks, mark=*, mark size=1pt,
point meta=explicit, point meta min=0, point meta max=5]
table[x=y,y=x,meta=color,col sep=comma]tikz/r_i5.csv;

in 0,...,14

[black] (axis cs:*22-.5,-0.5) – (axis cs:*22-.5,176.5);

in 0,...,8

[black] (axis cs:-0.5,*22-0.5) – (axis cs:308.5,*22-0.5);

axis equal,
scale only axis,
axis x line=none,
axis y line=none,
y dir=reverse,
[scatter,only marks, mark=*, mark size=1pt,
point meta=explicit, point meta min=0, point meta max=5]
table[x=y,y=x,meta=color,col sep=comma]tikz/q_i9.csv;

in 0,...,14

[black] (axis cs:*22-.5,-0.5) – (axis cs:*22-.5,176.5);

in 0,...,8

[black] (axis cs:-0.5,*22-0.5) – (axis cs:308.5,*22-0.5);

axis equal,
scale only axis,
axis x line=none,
axis y line=none,
y dir=reverse,
[scatter,only marks, mark=*, mark size=1pt,
point meta=explicit, point meta min=0, point meta max=5]
table[x=y,y=x,meta=color,col sep=comma]tikz/r_i9.csv;

in 0,...,14

[black] (axis cs:*22-.5,-0.5) – (axis cs:*22-.5,176.5);

in 0,...,8

[black] (axis cs:-0.5,*22-0.5) – (axis cs:308.5,*22-0.5);

Learned quantization bitwidths (color-coded) for the $q$ messages (left) and $r$ messages (right) in the first, sixth and tenth iteration for the $(264,132)$ 5G LDPC code. No weight sharing is applied, grid size is $Z=22$. Note that dark blue points correspond to a bitwidth of 0, implying that this message is zero-valued.

For training, we set the hyper parameter $\lambda_c=0.15$, fix $L_\mathrm{limit}=8$ and initialize all trainable parameters to $\alpha=1$, corresponding to 4-bit quantization. The system is trained in an AWGN scenario at an SNR of $E_\mathrm{b}/N_0=2.5\text{ dB}$ using Adam [13] with learning rate $\gamma=2.5\cdot10^{-3}$ and a batch size $B=2048$ for 3000 epochs. The resulting bitwidths (not rounded) for $q$ and $r$ are depicted in Fig. <ref> for iterations $i=1,6,10$, respectively. The values are arranged according to the parity-check matrix $\mathbf{H}$ of the code. We observe that in the first iteration, only very few checks are important; the other checks do not require any accuracy (i.e., the values are just 0). This can be explained by the punctured message bits of the 5G LDPC code. The first $2Z = 44$ VN are initialized with LLR $=0$, therefore, all checks involving two of these punctured VN only output zero-valued messages. Only the $q$ and $r$ values needed to reconstruct the punctured message bits are active.
Similarly, the $r$ messages of the extension parity-bits are quantized with a low resolution. This makes sense, as the extension VN are degree-1 and therefore, the values are not used by the VN update. The $q$ messages outgoing of the extension parity-bits are generally more important than other messages and are quantized with a higher resolution. Finally, in the last iteration, only the $r$ messages corresponding to the $K$ message bits are quantized with a reasonable bitwidth. This is easily explained by the fact that those are the only bits used in the BCE loss calculation. The learned bitwidths for the channel LLR remained approximately at 4, resulting in an overall average complexity of 3.1 bits per message.

§.§ Weight Sharing

grid style=dotted,anthrazit,
legend columns=1,
legend pos=north east,
legend cell align=left,
legend style=fill,fill opacity=0, text opacity=1,draw=none,
ylabel=Loss $\mathcal{L}$,
legend image post style=mark indices=,
mark size=1.5pt,

[color=mittelblau,line width = 1pt, solid,mark size=2.5pt,mark=x,mark repeat=10, mark options=solid]
table[col sep=comma]
0, 6.977e-01
50, 6.997e-01
100, 6.872e-01
150, 6.786e-01
200, 6.701e-01
250, 6.641e-01
300, 6.588e-01
350, 6.532e-01
400, 6.510e-01
450, 6.457e-01
500, 6.448e-01
550, 6.402e-01
600, 6.396e-01
650, 6.367e-01
700, 6.345e-01
750, 6.302e-01
800, 6.291e-01
850, 6.272e-01
900, 6.288e-01
950, 6.250e-01
1000, 6.233e-01
1050, 6.231e-01
1100, 6.224e-01
1150, 6.206e-01
1200, 6.200e-01
1250, 6.172e-01
1300, 6.157e-01
1350, 6.163e-01
1400, 6.149e-01
1450, 6.126e-01
1500, 6.119e-01
1550, 6.111e-01
1600, 6.104e-01
1650, 6.097e-01
1700, 6.104e-01
1750, 6.084e-01
1800, 6.085e-01
1850, 6.075e-01
1900, 6.041e-01
1950, 6.042e-01
2000, 6.042e-01
2050, 6.024e-01
2100, 6.026e-01
2150, 6.018e-01
2200, 6.018e-01
2250, 6.015e-01
2300, 6.000e-01
2350, 6.000e-01
2400, 5.973e-01
2450, 5.978e-01
2500, 5.994e-01
2550, 5.973e-01
2600, 5.970e-01
2650, 5.966e-01
2700, 5.962e-01
2750, 5.956e-01
2800, 5.947e-01
2850, 5.944e-01
2900, 5.931e-01
2950, 5.922e-01
3000, 5.923e-01

No weight sharing (WS);

[color=red,line width = 1pt, solid,mark size=2.5pt,mark=diamond,mark repeat=10, mark options=solid]
table[col sep=comma]
0, 7.056e-01
50, 6.957e-01
100, 6.780e-01
150, 6.651e-01
200, 6.560e-01
250, 6.497e-01
300, 6.448e-01
350, 6.398e-01
400, 6.367e-01
450, 6.336e-01
500, 6.293e-01
550, 6.282e-01
600, 6.256e-01
650, 6.242e-01
700, 6.227e-01
750, 6.201e-01
800, 6.194e-01
850, 6.177e-01
900, 6.161e-01
950, 6.157e-01
1000, 6.115e-01
1050, 6.120e-01
1100, 6.120e-01
1150, 6.088e-01
1200, 6.075e-01
1250, 6.073e-01
1300, 6.091e-01
1350, 6.044e-01
1400, 6.042e-01
1450, 6.040e-01
1500, 6.035e-01
1550, 6.031e-01
1600, 6.025e-01
1650, 6.023e-01
1700, 6.007e-01
1750, 6.011e-01
1800, 6.009e-01
1850, 5.985e-01
1900, 5.978e-01
1950, 5.989e-01
2000, 5.970e-01
2050, 5.954e-01
2100, 5.961e-01
2150, 5.954e-01
2200, 5.936e-01
2250, 5.948e-01
2300, 5.939e-01
2350, 5.943e-01
2400, 5.926e-01
2450, 5.914e-01
2500, 5.928e-01
2550, 5.907e-01
2600, 5.890e-01
2650, 5.907e-01
2700, 5.906e-01
2750, 5.879e-01
2800, 5.895e-01
2850, 5.887e-01
2900, 5.875e-01
2950, 5.885e-01
3000, 5.877e-01

Base graph weight sharing (BG-WS);

[color=apfelgruen,line width = 1pt, solid,mark=o,mark repeat=10,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0, 7.086e-01
50, 6.938e-01
100, 6.755e-01
150, 6.612e-01
200, 6.548e-01
250, 6.508e-01
300, 6.465e-01
350, 6.443e-01
400, 6.435e-01
450, 6.409e-01
500, 6.388e-01
550, 6.408e-01
600, 6.389e-01
650, 6.370e-01
700, 6.361e-01
750, 6.387e-01
800, 6.369e-01
850, 6.362e-01
900, 6.370e-01
950, 6.359e-01
1000, 6.345e-01
1050, 6.345e-01
1100, 6.335e-01
1150, 6.318e-01
1200, 6.343e-01
1250, 6.329e-01
1300, 6.333e-01
1350, 6.348e-01
1400, 6.342e-01
1450, 6.323e-01
1500, 6.327e-01
1550, 6.313e-01
1600, 6.324e-01
1650, 6.314e-01
1700, 6.297e-01
1750, 6.307e-01
1800, 6.312e-01
1850, 6.309e-01
1900, 6.319e-01
1950, 6.301e-01
2000, 6.307e-01
2050, 6.298e-01
2100, 6.284e-01
2150, 6.293e-01
2200, 6.300e-01
2250, 6.279e-01
2300, 6.280e-01
2350, 6.295e-01
2400, 6.271e-01
2450, 6.288e-01
2500, 6.279e-01
2550, 6.286e-01
2600, 6.265e-01
2650, 6.268e-01
2700, 6.279e-01
2750, 6.281e-01
2800, 6.276e-01
2850, 6.261e-01
2900, 6.273e-01
2950, 6.283e-01
3000, 6.271e-01

Check node weight sharing (CN-WS);

Loss vs. training epoch for different weight sharing methods, using the (264,132) 5G LDPC code.

Method     No WS     BG-WS     CN-WS

# of parameters     19228     874     161

Avg. bitwidth, surrogate     3.289     3.304     3.486

Avg. bitwidth, converted     3.103     3.126     3.452

Resulting complexity of different weight sharing methods for the (264,132) 5G LDPC code.

grid style=dotted,anthrazit,

legend columns=1,
legend pos=south west,
legend cell align=left,
legend style=fill,fill opacity=0.8,
xlabel=$E_\mathrm{b}/N_0$ [dB],
ylabel=BER / BLER,
legend image post style=mark indices=,
mark size=1.5pt,

[color=magenta,line width = 1pt, solid,mark=square,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 9.993e-01
0.50, 9.973e-01
1.00, 9.719e-01
1.50, 8.860e-01
2.00, 6.741e-01
2.50, 3.811e-01
3.00, 1.438e-01
3.50, 3.278e-02
4.00, 4.344e-03
4.50, 3.888e-04

[color=mittelblau,line width = 1pt, solid,mark=x,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 9.998e-01
0.50, 9.976e-01
1.00, 9.751e-01
1.50, 8.831e-01
2.00, 6.692e-01
2.50, 3.474e-01
3.00, 1.128e-01
3.50, 2.409e-02
4.00, 2.574e-03
4.50, 1.990e-04

[color=rot,line width = 1pt, solid,mark=diamond,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 1.000e+00
0.50, 9.973e-01
1.00, 9.814e-01
1.50, 9.026e-01
2.00, 6.870e-01
2.50, 3.743e-01
3.00, 1.316e-01
3.50, 2.694e-02
4.00, 2.707e-03
4.50, 1.838e-04

[color=apfelgruen,line width = 1pt, solid,mark=o,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 9.998e-01
0.50, 9.983e-01
1.00, 9.795e-01
1.50, 9.070e-01
2.00, 6.990e-01
2.50, 3.716e-01
3.00, 1.260e-01
3.50, 2.417e-02
4.00, 2.906e-03
4.50, 1.855e-04

[color=black,line width = 1pt, solid,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 9.956e-01
0.50, 9.775e-01
1.00, 9.104e-01
1.50, 7.356e-01
2.00, 4.795e-01
2.50, 2.078e-01
3.00, 6.047e-02
3.50, 1.099e-02
4.00, 1.266e-03
4.50, 7.994e-05

[color=magenta,line width = 1pt, dashed,mark=square,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 3.007e-01
0.50, 2.824e-01
1.00, 2.480e-01
1.50, 1.950e-01
2.00, 1.223e-01
2.50, 5.533e-02
3.00, 1.609e-02
3.50, 3.211e-03
4.00, 3.041e-04
4.50, 2.434e-05

[color=mittelblau,line width = 1pt, dashed,mark=x,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 2.968e-01
0.50, 2.764e-01
1.00, 2.425e-01
1.50, 1.842e-01
2.00, 1.114e-01
2.50, 4.398e-02
3.00, 1.128e-02
3.50, 1.740e-03
4.00, 1.805e-04
4.50, 1.128e-05

[color=rot,line width = 1pt, dashed,mark=diamnond,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 2.978e-01
0.50, 2.761e-01
1.00, 2.460e-01
1.50, 1.934e-01
2.00, 1.145e-01
2.50, 4.824e-02
3.00, 1.332e-02
3.50, 2.089e-03
4.00, 1.759e-04
4.50, 8.596e-06

[color=apfelgruen,line width = 1pt, dashed,mark=o,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 2.992e-01
0.50, 2.810e-01
1.00, 2.492e-01
1.50, 1.952e-01
2.00, 1.197e-01
2.50, 4.860e-02
3.00, 1.369e-02
3.50, 2.089e-03
4.00, 1.890e-04
4.50, 9.636e-06

[color=black,line width = 1pt, dashed,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 2.644e-01
0.50, 2.348e-01
1.00, 1.890e-01
1.50, 1.290e-01
2.00, 6.558e-02
2.50, 2.195e-02
3.00, 5.441e-03
3.50, 7.668e-04
4.00, 7.589e-05
4.50, 4.357e-06

(legend) at (axis description cs:0.02,.02);

fill opacity=0,
text opacity=1,
matrix of nodes,
align =left,
row sep = -1,
column sep = -5,
inner sep= 2,
anchor=south west,
column 3/.style=anchor=base west,
] at (legend)
BLER     BER

<ref>     <ref>     3-bit uniform

<ref>     <ref>     trained surrogate, no WS

<ref>     <ref>     trained surrogate, BG-WS

<ref>     <ref>     trained surrogate, CN-WS

<ref>     <ref>     float

Error-rate performance comparison of the trained surrogate decoder for different weight sharing methods, using the (264,132) 5G LDPC code.

grid style=dotted,anthrazit,

legend columns=1,
legend pos=south west,
legend cell align=left,
legend style=fill,fill opacity=0.8,
xlabel=$E_\mathrm{b}/N_0$ [dB],
ylabel=BER / BLER,
legend image post style=mark indices=,
mark size=1.5pt,

[color=magenta,line width = 1pt, solid,mark=square,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 9.993e-01
0.50, 9.973e-01
1.00, 9.719e-01
1.50, 8.860e-01
2.00, 6.741e-01
2.50, 3.811e-01
3.00, 1.438e-01
3.50, 3.278e-02
4.00, 4.344e-03

[color=mittelblau,line width = 1pt, solid,mark=x,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 9.988e-01
0.50, 9.890e-01
1.00, 9.429e-01
1.50, 7.966e-01
2.00, 5.479e-01
2.50, 2.886e-01
3.00, 9.717e-02
3.50, 2.181e-02
4.00, 5.837e-03

[color=rot,line width = 1pt, solid,mark=diamond,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 9.993e-01
0.50, 9.915e-01
1.00, 9.448e-01
1.50, 8.132e-01
2.00, 5.627e-01
2.50, 2.817e-01
3.00, 9.229e-02
3.50, 2.376e-02
4.00, 5.815e-03

[color=apfelgruen,line width = 1pt, solid,mark=o,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 9.993e-01
0.50, 9.941e-01
1.00, 9.539e-01
1.50, 8.181e-01
2.00, 5.725e-01
2.50, 2.842e-01
3.00, 9.058e-02
3.50, 2.140e-02
4.00, 3.277e-03

[color=black,line width = 1pt, solid,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 9.956e-01
0.50, 9.775e-01
1.00, 9.104e-01
1.50, 7.356e-01
2.00, 4.795e-01
2.50, 2.078e-01
3.00, 6.047e-02
3.50, 1.099e-02
4.00, 1.266e-03

[color=magenta,line width = 1pt, dashed,mark=square,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 3.007e-01
0.50, 2.824e-01
1.00, 2.480e-01
1.50, 1.950e-01
2.00, 1.223e-01
2.50, 5.533e-02
3.00, 1.609e-02
3.50, 3.211e-03
4.00, 3.041e-04

[color=mittelblau,line width = 1pt, dashed,mark=x,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 2.439e-01
0.50, 2.209e-01
1.00, 1.843e-01
1.50, 1.282e-01
2.00, 6.807e-02
2.50, 2.846e-02
3.00, 6.819e-03
3.50, 9.624e-04
4.00, 1.686e-04

[color=rot,line width = 1pt, dashed,mark=diamond,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 2.401e-01
0.50, 2.160e-01
1.00, 1.794e-01
1.50, 1.255e-01
2.00, 6.955e-02
2.50, 2.628e-02
3.00, 6.938e-03
3.50, 9.655e-04
4.00, 1.572e-04

[color=apfelgruen,line width = 1pt, dashed,mark=o,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 2.578e-01
0.50, 2.322e-01
1.00, 1.923e-01
1.50, 1.368e-01
2.00, 7.491e-02
2.50, 2.957e-02
3.00, 7.315e-03
3.50, 1.305e-03
4.00, 1.548e-04

[color=black,line width = 1pt, dashed,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 2.644e-01
0.50, 2.348e-01
1.00, 1.890e-01
1.50, 1.290e-01
2.00, 6.558e-02
2.50, 2.195e-02
3.00, 5.441e-03
3.50, 7.668e-04
4.00, 7.589e-05

(legend) at (axis description cs:0.02,.02);

fill opacity=0,
text opacity=1,
matrix of nodes,
align =left,
row sep = -1,
column sep = -5,
inner sep= 2,
anchor=south west,
column 3/.style=anchor=base west,
] at (legend)
BLER     BER

<ref>     <ref>     3-bit uniform

<ref>     <ref>     trained converted, no WS

<ref>     <ref>     trained converted, BG-WS

<ref>     <ref>     trained converted, CN-WS

<ref>     <ref>     float

Error-rate performance comparison of the converted decoder for different weight sharing methods, using the (264,132) 5G LDPC code.

One can observe from Fig. <ref> that messages corresponding to the same BG edge should be quantized with a similar bitwidth. Therefore it is reasonable to share a single trainable parameter for $Z$ edges, reducing the training complexity. Another possible WS approach is to share the same bitwidth across each BG-CN (i.e., groups of $Z$ rows in the parity-check matrix). The number of parameters and their resulting complexity (after training and conversion) is listed in Tab. <ref>. Fig. <ref> shows the development of the loss value $\mathcal{L}$ over the training epochs. We can see that WS does not only reduce the number of trainable parameters, it also speeds up the model convergence. While CN-based WS converges similarly fast, it cannot reach loss values as low as the other methods. This is expected by the previously observed diversity in the message bitwidths of the inbound and outbound messages to one CN. Consequently, training cannot achieve complexity values as low as in the other WS approaches. The error-rate performance of the surrogate and converted decoders are depicted in Fig. <ref> and Fig. <ref>, respectively. We do not observe any difference in error-rate performance in case of the surrogate models for different WS methods. However, the converted model with CN-WS seems to achieve a lower error floor than the other methods.

§.§ Generalization

grid style=dotted,anthrazit,

legend columns=1,
legend pos=south west,
legend cell align=left,
legend style=fill,fill opacity=0.8,
xlabel=$E_\mathrm{b}/N_0$ [dB],
ylabel=BER / BLER,
legend image post style=mark indices=,
mark size=1.5pt,

[color=magenta,line width = 1pt, solid,mark=square,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 1.000e+00
0.50, 1.000e+00
1.00, 9.998e-01
1.50, 9.998e-01
2.00, 9.985e-01
2.50, 9.902e-01
3.00, 9.680e-01
3.50, 9.111e-01
4.00, 7.925e-01
4.50, 6.199e-01
5.00, 4.243e-01
5.50, 2.432e-01
6.00, 1.201e-01
6.50, 4.744e-02
7.00, 1.703e-02

[color=apfelgruen,line width = 1pt, solid,mark=o,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 1.000e+00
0.50, 1.000e+00
1.00, 1.000e+00
1.50, 9.995e-01
2.00, 9.971e-01
2.50, 9.902e-01
3.00, 9.629e-01
3.50, 8.857e-01
4.00, 7.515e-01
4.50, 5.596e-01
5.00, 3.398e-01
5.50, 1.719e-01
6.00, 8.496e-02
6.50, 2.959e-02
7.00, 8.963e-03

[color=mittelblau,line width = 1pt, solid,mark=x,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 1.000e+00
0.50, 1.000e+00
1.00, 1.000e+00
1.50, 1.000e+00
2.00, 9.990e-01
2.50, 9.917e-01
3.00, 9.580e-01
3.50, 8.884e-01
4.00, 7.651e-01
4.50, 5.710e-01
5.00, 3.481e-01
5.50, 1.865e-01
6.00, 7.031e-02
6.50, 2.791e-02
7.00, 9.417e-03

[color=black,line width = 1pt, solid,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 1.000e+00
0.50, 1.000e+00
1.00, 1.000e+00
1.50, 9.973e-01
2.00, 9.875e-01
2.50, 9.685e-01
3.00, 9.121e-01
3.50, 8.013e-01
4.00, 6.152e-01
4.50, 4.141e-01
5.00, 2.373e-01
5.50, 1.082e-01
6.00, 4.305e-02
6.50, 1.367e-02
7.00, 3.495e-03

[color=magenta,line width = 1pt, dashed,mark=square,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 3.229e-01
0.50, 3.155e-01
1.00, 3.051e-01
1.50, 2.944e-01
2.00, 2.830e-01
2.50, 2.638e-01
3.00, 2.366e-01
3.50, 2.019e-01
4.00, 1.526e-01
4.50, 1.025e-01
5.00, 5.791e-02
5.50, 2.855e-02
6.00, 1.235e-02
6.50, 4.507e-03
7.00, 1.406e-03

[color=apfelgruen,line width = 1pt, dashed,mark=o,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 2.981e-01
0.50, 2.857e-01
1.00, 2.701e-01
1.50, 2.545e-01
2.00, 2.409e-01
2.50, 2.186e-01
3.00, 1.908e-01
3.50, 1.548e-01
4.00, 1.136e-01
4.50, 7.306e-02
5.00, 3.664e-02
5.50, 1.456e-02
6.00, 6.268e-03
6.50, 2.082e-03
7.00, 4.875e-04

[color=mittelblau,line width = 1pt, dashed,mark=x,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 2.969e-01
0.50, 2.830e-01
1.00, 2.674e-01
1.50, 2.541e-01
2.00, 2.370e-01
2.50, 2.151e-01
3.00, 1.884e-01
3.50, 1.539e-01
4.00, 1.134e-01
4.50, 7.191e-02
5.00, 3.815e-02
5.50, 1.744e-02
6.00, 5.456e-03
6.50, 2.036e-03
7.00, 5.409e-04

[color=black,line width = 1pt, dashed,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 3.090e-01
0.50, 2.982e-01
1.00, 2.872e-01
1.50, 2.717e-01
2.00, 2.522e-01
2.50, 2.224e-01
3.00, 1.834e-01
3.50, 1.384e-01
4.00, 9.180e-02
4.50, 5.276e-02
5.00, 2.531e-02
5.50, 1.015e-02
6.00, 3.563e-03
6.50, 1.002e-03
7.00, 2.350e-04

(legend) at (axis description cs:0.02,.02);

fill opacity=0,
text opacity=1,
matrix of nodes,
align =left,
row sep = -1,
column sep = -5,
inner sep= 2,
anchor=south west,
column 3/.style=anchor=base west,
] at (legend)
BLER     BER

<ref>     <ref>     3-bit uniform

<ref>     <ref>     converted, trained @ 5 dB Rayleigh

<ref>     <ref>     converted, generalized from AWGN

<ref>     <ref>     float

Error-rate performance of converted decoder model trained for AWGN and Rayleigh fading channel, evaluated on a Rayleigh fading channel with the (264,132) 5G LDPC code. Both trained models have an average bitwidth of $3.1$ bits.

grid style=dotted,anthrazit,
legend columns=1,
legend pos=south west,
legend cell align=left,
legend style=fill,fill opacity=0.8,
xlabel=$E_\mathrm{b}/N_0$ [dB],
ylabel=BER / BLER,
legend image post style=mark indices=,
mark size=1.5pt,

[color=magenta,line width = 1pt, solid,mark=square,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 9.998e-01
0.50, 9.939e-01
1.00, 9.575e-01
1.50, 8.232e-01
2.00, 5.386e-01
2.50, 2.261e-01
3.00, 4.997e-02
3.50, 6.274e-03
4.00, 4.854e-04

[color=apfelgruen,line width = 1pt, solid,mark=o,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 9.976e-01
0.50, 9.824e-01
1.00, 8.948e-01
1.50, 6.646e-01
2.00, 3.425e-01
2.50, 9.814e-02
3.00, 1.660e-02
3.50, 1.532e-03
4.00, 6.286e-05

[color=mittelblau,line width = 1pt, solid,mark=x,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 9.990e-01
0.50, 9.883e-01
1.00, 9.072e-01
1.50, 6.934e-01
2.00, 3.936e-01
2.50, 1.179e-01
3.00, 2.262e-02
3.50, 1.726e-03
4.00, 1.023e-04

[color=black,line width = 1pt, solid,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 9.829e-01
0.50, 9.336e-01
1.00, 7.725e-01
1.50, 4.788e-01
2.00, 2.034e-01
2.50, 5.306e-02
3.00, 7.229e-03
3.50, 5.651e-04
4.00, 3.247e-05

[color=magenta,line width = 1pt, dashed,mark=square,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 3.492e-01
0.50, 3.174e-01
1.00, 2.593e-01
1.50, 1.719e-01
2.00, 8.070e-02
2.50, 2.404e-02
3.00, 3.372e-03
3.50, 3.566e-04
4.00, 1.957e-05

[color=apfelgruen,line width = 1pt, dashed,mark=o,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 3.069e-01
0.50, 2.583e-01
1.00, 1.858e-01
1.50, 9.690e-02
2.00, 3.519e-02
2.50, 6.904e-03
3.00, 8.513e-04
3.50, 5.683e-05
4.00, 2.242e-06

[color=mittelblau,line width = 1pt, dashed,mark=x,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 3.205e-01
0.50, 2.800e-01
1.00, 2.077e-01
1.50, 1.110e-01
2.00, 4.286e-02
2.50, 8.695e-03
3.00, 1.158e-03
3.50, 7.185e-05
4.00, 2.422e-06

[color=black,line width = 1pt, dashed,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 2.750e-01
0.50, 2.148e-01
1.00, 1.343e-01
1.50, 5.695e-02
2.00, 1.780e-02
2.50, 3.480e-03
3.00, 3.791e-04
3.50, 2.108e-05
4.00, 9.459e-07

(legend) at (axis description cs:0.02,.02);

fill opacity=0,
text opacity=1,
matrix of nodes,
align =left,
row sep = -1,
column sep = -5,
inner sep= 2,
anchor=south west,
column 3/.style=anchor=base west,
] at (legend)
BLER     BER

<ref>     <ref>     3-bit uniform

<ref>     <ref>     trained surrogate, 3.6 bits

<ref>     <ref>     trained converted, 3.6 bits

<ref>     <ref>     float

Error-rate performance of the surrogate and converted trained model for the (528,132) 5G LDPC code with $R = 1/4$.

grid style=dotted,anthrazit,
legend columns=1,
legend pos=south west,
legend cell align=left,
legend style=fill,fill opacity=0.8,
xlabel=$E_\mathrm{b}/N_0$ [dB],
ylabel=BER / BLER,
legend image post style=mark indices=,
mark size=1.5pt,

[color=magenta,line width = 1pt, solid,mark=square,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 9.998e-01
0.50, 9.939e-01
1.00, 9.673e-01
1.50, 8.965e-01
2.00, 7.292e-01
2.50, 4.556e-01
3.00, 2.151e-01
3.50, 6.506e-02
4.00, 1.440e-02
4.50, 2.081e-03

[color=apfelgruen,line width = 1pt, solid,mark=o,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 9.995e-01
0.50, 9.949e-01
1.00, 9.714e-01
1.50, 8.943e-01
2.00, 7.114e-01
2.50, 4.590e-01
3.00, 2.061e-01
3.50, 7.178e-02
4.00, 1.270e-02
4.50, 1.702e-03

[color=mittelblau,line width = 1pt, solid,mark=x,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 9.990e-01
0.50, 9.956e-01
1.00, 9.805e-01
1.50, 9.316e-01
2.00, 7.725e-01
2.50, 5.161e-01
3.00, 2.437e-01
3.50, 7.397e-02
4.00, 1.703e-02
4.50, 2.270e-03

[color=black,line width = 1pt, solid,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 9.976e-01
0.50, 9.917e-01
1.00, 9.575e-01
1.50, 8.723e-01
2.00, 6.768e-01
2.50, 4.089e-01
3.00, 1.929e-01
3.50, 5.501e-02
4.00, 1.116e-02
4.50, 1.332e-03

[color=magenta,line width = 1pt, dashed,mark=square,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 2.381e-01
0.50, 2.164e-01
1.00, 1.822e-01
1.50, 1.426e-01
2.00, 9.142e-02
2.50, 4.334e-02
3.00, 1.698e-02
3.50, 3.866e-03
4.00, 6.157e-04
4.50, 6.580e-05

[color=apfelgruen,line width = 1pt, dashed,mark=o,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 2.311e-01
0.50, 2.086e-01
1.00, 1.814e-01
1.50, 1.377e-01
2.00, 8.786e-02
2.50, 4.403e-02
3.00, 1.498e-02
3.50, 3.967e-03
4.00, 5.290e-04
4.50, 5.281e-05

[color=mittelblau,line width = 1pt, dashed,mark=x,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 2.390e-01
0.50, 2.173e-01
1.00, 1.885e-01
1.50, 1.471e-01
2.00, 9.972e-02
2.50, 4.839e-02
3.00, 1.783e-02
3.50, 3.941e-03
4.00, 6.677e-04
4.50, 7.309e-05

[color=black,line width = 1pt, dashed,mark size=2.5pt, mark options=solid]
table[col sep=comma]
0.00, 2.263e-01
0.50, 2.032e-01
1.00, 1.711e-01
1.50, 1.289e-01
2.00, 8.008e-02
2.50, 3.745e-02
3.00, 1.416e-02
3.50, 2.842e-03
4.00, 4.873e-04
4.50, 4.747e-05

(legend) at (axis description cs:0.02,.02);

fill opacity=0,
text opacity=1,
matrix of nodes,
align =left,
row sep = -1,
column sep = -5,
inner sep= 2,
anchor=south west,
column 3/.style=anchor=base west,
] at (legend)
BLER     BER

<ref>     <ref>     4-bit uniform

<ref>     <ref>     converted, trained @ $R'=2/3$

<ref>     <ref>     converted, generalized from $R=1/4$

<ref>     <ref>     float

Error-rate performance of the surrogate and converted trained model for the (198,132) 5G LDPC code with $R' = 2/3$ as well as the generalized converted model from $R = 1/4$. Both trained models have an average bitwidth of $3.95$ bits.

Finally, we evaluate how the proposed method can generalize to other channels or rates. For this, we train a model for one scenario and evaluate the learned parameters in a different scenario. Fig. <ref> shows the performance of the AWGN trained model in an ergodic Rayleigh fading channel scenario with perfect channel state information. As we can see, the generalized model has almost the same performance as a model that was trained in this environment (same complexity of $3.1$ bits, using $\lambda_c=0.15$ at $E_\mathrm{b}/N_0 = 5 \text{ dB}$).

Next, we evaluate how the model can generalize to other code rates.
For this we train the surrogate model at a low code rate of $R=1/4$, corresponding to $K=132$ and $N=528$, using $\lambda_c=0.003$.
This performance is shown in Fig. <ref>; the corresponding complexity is $3.6$ bits.
Then, we take the bitwidths from this model and evaluate it for a rate of $R'=2/3$, i.e., $N'=198$.
This is possible, as in the 5G standard, all codes with the same code dimension use the same parity-check matrix, and merely differ in the number of transmitted/punctured extension parity-bits.
Fig. <ref> shows the results where again it can be seen that the model performs very similarly to the one trained at this rate (same complexity of $3.95$ bits, using $\lambda_c=0.011$ at $E_\mathrm{b}/N_0 = 3 \text{ dB}$).
Note that the higher rate code has fewer of the coarsely quantized extension checks, increasing its average complexity.

§ CONCLUSION AND OUTLOOK

We propose a novel method to optimize the bitwidths of a fixed-point min-sum LDPC decoder.
The method is based on a surrogate model where quantization has been replaced by the addition of noise, such that the model remains differentiable and gradient-based optimization can be applied.

Weight sharing across base graph edges reduces the training complexity and improves the convergence speed.
Furthermore, as all parameters are on base graph level, it allows for easy generalization to other blocklengths and rates via the standard rate-matching schemes.

The proposed methodology can be straightforwardly extended to attenuated or offset min-sum decoding [6].
Moreover, many other parts of a communications system, where fixed-point implementations are used, can be optimized using the surrogate approach.

[1]
M. Kuschnerov, T. Bex, and P. Kainzmaier, “Energy efficient digital signal
processing,” in Optical Fiber Commun. Conf. and Exhibition (OFC),
Mar. 2014, pp. 1–3.

[2]
X. Zhang and P. H. Siegel, “Quantized iterative message passing decoders with
low error floor for LDPC codes,” IEEE Trans. Commun., vol. 62,
no. 1, pp. 1–14, Jan. 2014.

[3]
M. Fossorier, M. Mihaljevic, and H. Imai, “Reduced complexity iterative
decoding of low-density parity check codes based on belief propagation,”
IEEE Trans. Commun., vol. 47, no. 5, pp. 673–680, May 1999.

[4]
R. Gallager, “Low-density parity-check codes,” IRE Trans. Inf.
Theory, vol. 8, no. 1, pp. 21–28, Jan. 1962.

[5]
R. Tanner, “A recursive approach to low complexity codes,” IEEE
Trans. Inf. Theory, vol. 27, no. 5, pp. 533–547, Sep. 1981.

[6]
J. Chen, A. Dholakia, E. Eleftheriou, M. Fossorier, and X.-Y. Hu,
“Reduced-complexity decoding of LDPC codes,” IEEE Trans. Commun.,
vol. 53, no. 8, pp. 1288–1299, Aug. 2005.

[7]
C. Studer, N. Preyss, C. Roth, and A. Burg, “Configurable high-throughput
decoder architecture for quasi-cyclic LDPC codes,” in 42nd Asilomar
Conference on Signals, Systems and Computers, Oct. 2008, pp. 1137–1142.

[8]
P. Schläfer, N. Wehn, M. Alles, and T. Lehnigk-Emden, “A new
dimension of parallelism in ultra high throughput LDPC decoding,” in
IEEE Workshop on Signal Processing Systems (SiPS), Oct. 2013, pp.

[9]
A. Balatsoukas-Stimming, M. Meidlinger, R. Ghanaatian, G. Matz, and A. Burg,
“A fully-unrolled LDPC decoder based on quantized message passing,” in
IEEE Workshop on Signal Processing Systems (SiPS), Oct. 2015, pp.

[10]
M. Stark, L. Wang, G. Bauch, and R. D. Wesel, “Decoding rate-compatible
5G-LDPC codes with coarse quantization using the information bottleneck
method,” IEEE Open Journal of the Communications Society, pp.
646–660, May 2020.

[11]
R. Gray and D. Neuhoff, “Quantization,” IEEE Trans. Inf. Theory,
vol. 44, no. 6, pp. 2325–2383, Oct. 1998.

[12]
S. Cammerer, F. A. Aoudia, S. Dörner, M. Stark, J. Hoydis, and S. ten Brink,
“Trainable communication systems: Concepts and prototype,” IEEE
Trans. Commun., vol. 68, no. 9, pp. 5489–5503, Sep. 2020.

[13]
D. P. Kingma and J. L. Ba, “Adam: A method for stochastic optimization,”
ArXiv e-prints, Jan. 2017.

[14]
3GPP TSG RAN Meeting no. 71, RP-160671, “New SID proposal: Study on new
radio access technology,” NTT DOCOMO Inc., Göteborg, Sweden, Mar.

[15]
T. Richardson and S. Kudekar, “Design of low-density parity check codes
for 5G new radio,” IEEE Commun. Mag., vol. 56, no. 3, pp. 28–34,
Mar. 2018.


conferences. Furthermore, he is the holder of two (one national and one
European) patents. His current research interests spans in the area of
wireless communications and networks with emphasis in high frequency
communications, intelligent communication systems, optical wireless
communications, and signal processing and communications for biomedical
applications. Dr. Boulogeorgos was awarded the Distinction Scholarship Award
from the Research Committee of AUTh in 2014, and was recognized as an
Exemplary Reviewer for IEEE COMMUNICATION LETTERS in 2016 (top 3% of
reviewers). Moreover, he was named a Top Peer Reviewer (top 1% of reviewers)
in Cross-Field and Computer Science in the Global Peer Review Awards 2019,
which was presented by the Web of Science and Publons. Finally, in 2021, he
received the best oral presentation award in the International Conference on
Modern Circuits and Systems Technologies (MOCAST) 2021. He has been involved
as a member of organizational and technical program committees in several IEEE
and non-IEEE conferences and served as a reviewer in various IEEE journals and
conferences. He is an IEEE Senior Member and a Member of the Technical Chamber
of Greece. He is currently an Editor for IEEE COMMUNICATIONS LETTERS, an
Associate Editor for the Frontier in Communications and Networks, and for the
MDPI Telecom. Finally, Dr Boulogeorgos has participated as a guest editor in
the organization of a number of special issues in IEEE and non-IEEE journals.
---|---
|  Dimitrios Pliatsios received his diploma degree from the Department of
Electrical and Computer Engineering, Aristotle University of Thessaloniki,
Greece in 2016 and his PhD from the Department of Electrical and Computer
Engineering, University of Western Macedonia, Kozani, Greece in 2022.
Currently, he works as a postdoctoral researcher at the ITHACA Lab, Department
of Electrical and Computer Engineering, University of Western Macedonia, in
EU-funded research projects and participates in drafting research funding
proposals. His research interests include resource allocation in wireless
communications and edge computing environments, optimization theory, B5G/6G
mobile networks, and computer and network security. He is a member of the IEEE
and the Technical Chamber of Greece and he has served as a reviewer in several
scientific journals (IEEE Internet of Things Journal, IEEE Communication
Letters, Elsevier Computer Networks, IEEE Access, MDPI Sensors) and
conferences (IEEE GLOBECOM, IEEE ICC, IEEE NetSoft, IEEE CAMAD, IEEE INFOCOM,
IEEE PIMRC). His PhD research was funded by the Greek State Scholarship
Foundation and he has received the 1st Research Excellence Award by the
Research Committee of the University of Western Macedonia.
---|---
|  Konstantinos Ntontin (Member, IEEE) is currently a research scientist of
the SIGCOM Research Group at SnT, University of Luxembourg. In the past, he
held research associate positions at the Electronic Engineering and
Telecommunications department of the University of Barcelona, the Informatics
and Telecommunications department of the University of Athens, and the
National Centre of Scientific Research-“Demokritos”. In addition, he held an
internship position at Ericsson Eurolab Gmbh, Germany. He received the Diploma
in Electrical and Computer Engineering in 2006, the M. Sc. Degree in Wireless
Systems in 2009, and the Ph. D. degree in 2015 from the University of Patras,
Greece, the Royal Institute of Technology (KTH), Sweden, and the Technical
University of Catalonia (UPC), Spain, respectively. His research interests are
related to the physical layer of wireless telecommunications with focus on
performance analysis in fading channels, MIMO systems, array beamforming,
transceiver design, and stochastic modeling of wireless channels.
---|---
|  Panagiotis Sarigiannidis is the Director of the ITHACA lab
(https://ithaca.ece.uowm.gr/), co-founder of the 1st spin-off of the
University of Western Macedonia: MetaMind Innovations P.C.
(https://metamind.gr), and Associate Professor in the Department of Electrical
and Computer Engineering in the University of Western Macedonia, Kozani,
Greece. He received the B.Sc. and Ph.D. degrees in computer science from the
Aristotle University of Thessaloniki, Thessaloniki, Greece, in 2001 and 2007,
respectively. He has published over 260 papers in international journals,
conferences and book chapters, including IEEE Communications Surveys and
Tutorials, IEEE Transactions on Communications, IEEE Internet of Things, IEEE
Transactions on Broadcasting, IEEE Systems Journal, IEEE Wireless
Communications Magazine, IEEE Open Journal of the Communications Society,
IEEE/OSA Journal of Lightwave Technology, IEEE Transactions on Industrial
Informatics, IEEE Access, and Computer Networks. He received 5 best paper
awards. He has been involved in several national, European and international
projects. He is currently the project coordinator of three H2020 projects,
namely a) H2020-DS-SC7-2017 (DS-07-2017), SPEAR: Secure and PrivatE smArt
gRid, b) H2020-LC-SC3-EE-2020-1 (LC-SC3-EC-4-2020), EVIDENT: bEhaVioral
Insgihts anD Effective eNergy policy acTions, and c) H2020-ICT-2020-1
(ICT-56-2020), TERMINET: nexT gEneRation sMart INterconnectEd ioT, while he
coordinates the Operational Program MARS: sMart fArming with dRoneS
(Competitiveness, Entrepreneurship, and Innovation) and the Erasmus+ KA2
ARRANGE-ICT: SmartROOT: Smart faRming innOvatiOn Training. He also serves as a
principal investigator in the H2020-SU-DS-2018 (SU-DS04-2018), SDN-microSENSE:
SDN-microgrid reSilient Electrical eNergy SystEm and in three Erasmus+ KA2: a)
ARRANGE-ICT: pArtneRship foR AddressiNG mEgatrends in ICT, b) JAUNTY: Joint
undergAduate coUrses for smart eNergy managemenT sYstems, and c) STRONG:
advanced firST RespONders traininG (Cooperation for Innovation and the
Exchange of Good Practices). His research interests include telecommunication
networks, internet of things and network security. He is an IEEE member and
participates in the Editorial Boards of various journals.
---|---
|  Symeon Chatzinotas (Fellow, IEEE) is currently Full Professor / Chief
Scientist I and Co-Head of the SIGCOM Research Group at SnT, University of
Luxembourg. In the past, he has been a Visiting Professor at the University of
Parma, Italy and he was involved in numerous Research and Development projects
for the National Center for Scientific Research Demokritos, the Center of
Research and Technology Hellas and the Center of Communication Systems
Research, University of Surrey. He received the M.Eng. degree in
telecommunications from the Aristotle University of Thessaloniki,
Thessaloniki, Greece, in 2003, and the M.Sc. and Ph.D. degrees in electronic
engineering from the University of Surrey, Surrey, U.K., in 2006 and 2009,
respectively. He was a co-recipient of the 2014 IEEE Distinguished
Contributions to Satellite Communications Award, the CROWNCOM 2015 Best Paper
Award and the 2018 EURASIP JWCN Best Paper Award. He has (co-)authored more
than 450 technical papers in refereed international journals, conferences and
scientific books. He is currently in the editorial board of the IEEE Open
Journal of Vehicular Technology and the International Journal of Satellite
Communications and Networking.
---|---
|  Marco Di Renzo (Fellow, IEEE) received the Laurea (cum laude) and Ph.D.
degrees in electrical engineering from the University of L’Aquila, Italy, in
2003 and 2007, respectively, and the Habilitation à Diriger des Recherches
(Doctor of Science) degree from University Paris-Sud (now Paris-Saclay
University), France, in 2013. Since 2010, he has been with the French National
Center for Scientific Research (CNRS), where he is a CNRS Research Director
(Professor) with the Laboratory of Signals and Systems (L2S) of Paris-Saclay
University – CNRS and CentraleSupelec, Paris, France. In Paris-Saclay
University, he serves as the Coordinator of the Communications and Networks
Research Area of the Laboratory of Excellence DigiCosme, and as a Member of
the Admission and Evaluation Committee of the Ph.D. School on Information and
Communication Technologies. He is the Editor-in-Chief of IEEE Communications
Letters and a Distinguished Speaker of the IEEE Vehicular Technology Society.
In 2017-2020, he was a Distinguished Lecturer of the IEEE Vehicular Technology
Society and IEEE Communications Society. He has received several research
distinctions, which include the SEE-IEEE Alain Glavieux Award, the IEEE Jack
Neubauer Memorial Best Systems Paper Award, the Royal Academy of Engineering
Distinguished Visiting Fellowship, the Nokia Foundation Visiting
Professorship, the Fulbright Fellowship, and the 2021 EURASIP Journal on
Wireless Communications and Networking Best Paper Award. He is a Fellow of the
UK Institution of Engineering and Technology (IET), a Fellow of the Asia-
Pacific Artificial Intelligence Association (AAIA), an Ordinary Member of the
European Academy of Sciences and Arts (EASA), and an Ordinary Member of the
Academia Europaea (AE). Also, he is a Highly Cited Researcher.
---|---


# The Impact of Main Content Extraction on Near-Duplicate Detection

Maik Fröbe,∗ Matthias Hagen,∗ Martin-Luther-Universität Halle-Wittenberg,
Germany Janek Bevendorff,† Michael Völske,† Benno Stein,†Bauhaus-Universität
Weimar, Germany
Christopher Schröder,‡ Robby Wagner,‡ Lukas Gienapp,‡ Martin Potthast,‡
Leipzig University, Germany

###### Abstract.

Commercial web search engines employ near-duplicate detection to ensure that
users see each relevant result only once, albeit the underlying web crawls
typically include (near-)duplicates of many web pages. We revisit the risks
and potential of near-duplicates with an information retrieval focus,
motivating that current efforts toward an open and independent European web
search infrastructure should maintain metadata on duplicate and near-duplicate
documents in its index.

Near-duplicate detection implemented in an open web search infrastructure
should provide a suitable similarity threshold, a difficult choice since
identical pages may substantially differ in parts of a page that are
irrelevant to searchers (templates, advertisements, etc.). We study this
problem by comparing the similarity of pages for five (main) content
extraction methods in two studies on the ClueWeb crawls. We find that the full
content of pages serves precision-oriented near-duplicate-detection, while
main content extraction is more recall-oriented.

00footnotetext: Published at the 3nd International Symposium on Open Search
Technology
(OSSYM 2021), 11-13 October 2021, CERN, Geneva, Switzerland11footnotetext:
<EMAIL_ADDRESS><EMAIL_ADDRESS>$<$first-
<EMAIL_ADDRESS>
## Introduction

Typical web crawls contain many pages with identical or very similar content
and different URLs (fetterly:2003, ). Search engines retrieving pages from
such web crawls may encounter those near-duplicates in multiple stages of
their pipeline. During indexing, omitting near-duplicates might reduce the
index size. During retrieval, near-duplicates might occur in the search engine
result pages, reducing the user experience because users gain nothing from
viewing the same result twice or more on the search engine result pages
(bernstein:2004, ). Hence, identifying near-duplicates is a mandatory step in
web search, with commercial search engines like Google showing only the “best”
version from a set of near-duplicates for a
query.111developers.google.com/search/docs/advanced/guidelines/duplicate-
content

Figure 1. Pages with different URLs and the same article. Both pages have
identical content (indicated by green boxes) but vary in parts irrelevant to
searchers (indicated by red dashed boxes).

Widely available web crawls—most notably the
ClueWebs222lemurproject.org/clueweb09.php/ and lemurproject.org/clueweb12/ and
the Common Crawl333commoncrawl.org/—contain the (near-)duplicate documents
that the crawler encountered during the crawling process. While the inclusion
of near-duplicates enables many applications (like research on text reuse
(alshomary:2019, )), it introduces problems for search engines (that we will
discuss later in this paper). The CopyCat resource (froebe:2021, ) addresses
the problems introduced by near-duplicates in information retrieval
experiments by providing a precision-oriented near-duplicate detection.
CopyCat comes in two parts: (1) ready-to-use compilations of near-duplicate
documents within and between selected web crawls, and (2) a software library
to deduplicate arbitrary document sets, e.g., search engine result pages
before they are shown to searchers.

Removing near-duplicates from the search engine result pages with a framework
like CopyCat comes with the inherent difficulty of balancing precision and
recall. A low precision might reduce the effectiveness of a search engine
because relevant and novel documents might be omitted. In contrast, low recall
reduces the user experience because users see more near-duplicates. In the
context of web search, tuning a similarity measure faces additionally the
problem that some parts of the pages that are irrelevant for searchers can
increase or decrease the similarity of pages. Figure 1 shows an example of two
identical articles located at different URLs where the “noise,” i.e., the
navigation bar, reduces the similarity, eventually having a negative impact on
the recall.

Using only the “retrieval-relevant” part of documents for the near-duplicate
detection might be a promising direction to improve the recall in cases as
exemplified in Figure 1. However, the impact of main content extraction on
near-duplicate detection is not studied so far. While a “perfect” main content
extraction should positively affect precision and recall, existing
implementations might even harm precision and recall. E.g., invisible changes
in the HTML structure of a page might cause tag-based main content extraction
approaches to extract different main contents from pages that have identical
content from the users’ perspective.

We conduct experiments on the ClueWeb crawls to investigate to what extent
main content extraction may improve near-duplicate detection in information
retrieval. Therefore, we extract document pairs from the ClueWebs containing
redundant content (according to their canonical URL) to draw a sharp line
between “roughly similar” documents and near-duplicates. We calculate the
syntactic similarities for all document pairs after extracting the text from
the raw HTML with four main content extraction methods and one full content
extraction method that does not discard the “noise” parts from the document.
We evaluate the precision and recall of all five content extraction methods
based on manual near-duplicate judgments in two case studies. First, we review
document pairs uniformly sampled from the full similarity range for all
content extraction methods confirming that main content extraction increases
the recall as exemplified in Figure 1. Secondly, we review 100 cases per main
content extraction method in which main content extraction changes the
similarity drastically, e.g., with identical documents having disjoint main
content, or dissimilar pages having duplicate main content, finding inaccurate
main content extraction in most of those cases.

## Related Work

This section reviews definitions for near-duplicates, their prevalence on the
web, and approaches to near-duplicate detection implemented in the CopyCat
framework.

### Defining Near-Duplicates

The fact that there is no universal near-duplicate definition renders their
detection and comparable analysis difficult. Restrictive near-duplicate
definitions (henzinger:2006, ; manku:2007, ) consider documents as near-
duplicates if they differ only by their session or message IDs, timestamps,
visitor counts, server names, invisible differences, URL parts, or if they are
entry pages to the same site. Note that documents, even with minimal content
changes, are often not considered near-duplicates under such a restrictive
definition. Bernstein and Zobel (bernstein:2005, ) relax the near-duplicate
definition by applying an information retrieval focus, allowing minimal
changes in the content. They consider a document pair as near-duplicate if
users get the same information from both documents for all “reasonable
queries.” We adopt the near-duplicate definition of Bernstein and Zobel since
it considers a pair of pages as duplicates if they are equivalent in terms of
information provided, i.e., ignoring parts of pages irrelevant to searchers
(templates, advertisements, etc.).

### Studies on Near-Duplicates on the Web

According to previous studies by Fetterly et al. (fetterly:2003, ;
fetterly:2003b, ), 30% of the pages on the web are near-duplicates. While web
pages change regularly, consecutive versions of the same web page are usually
highly similar (cho:2000, ). Subsequent investigations (fetterly:2003, ;
fetterly:2003b, ; ntoulas:2004, ; adar:2009, ; olston:2008, ) confirm this
observation by tracking web pages between 5 weeks and one year. For example,
Adar et al. (adar:2009, ) repeatedly crawl 55,000 URLs over 5 weeks, finding
two-thirds of the pages changed their content, observing that most of these
changes were minimal. Ntoulas et al. (ntoulas:2004, ) tracked 150 pages over
one year, finding that 40% of them were still accessible after one year,
noticing only insignificant changes on most pages.

### Near-Duplicate Detection

There are syntactic, URL-based, and semantic algorithms for detecting near-
duplicates (alsulami:2012, ), from which the detection of syntactic near-
duplicates received the most attention, resulting in many effective algorithms
based on fingerprinting techniques (broder:1997, ; charikar:2002, ;
henzinger:2006, ; manku:2007, ). The CopyCat framework implements syntactic
near-duplicate detection in large web crawls with the SimHash algorithm using
a fingerprint size of 64 bit and a Hamming-threshold of 3 bits as suggested by
Manku et al. (manku:2007, ), while reducing the number of calculated pairwise
similarities with the partitioning scheme proposed by Henzinger et al.
(henzinger:2006, ). Complementary to estimating the similarity of documents
with SimHash, CopyCat can calculate the lossless $S_{3}$ fingerprint
similarity (bernstein:2004, ) for near-duplicate detection in small sets of
documents, such as run and qrel files frequently used in information retrieval
experiments.

##  Near-Duplicates in Web Crawls: Risks and Potentials

We recapitulate two risks and one potential of near-duplicate pages in web
crawls that the CopyCat framework addresses. Please note that we here focus on
information retrieval and that other risks, e.g., in the training of large
language models (raffel:2020, ), exist.

### Risk: Evaluation of Search Engines

Bernstein and Zobel (bernstein:2005, ) found that near-duplicates cause
problems in information retrieval evaluations because search engine users do
not benefit from seeing near-duplicates. Therefore, they introduce the so-
called novelty principle, which states that a document, though relevant in
isolation, is irrelevant if it is a near-duplicate to a document the user has
already seen on the search engine result page. Especially on web crawls with
many near-duplicates, the novelty principle has a non-negligible impact on
evaluating search engines (webis:2020b, ). E.g., applying the novelty
principle on the runs submitted to the Terabyte track 2004 decreases mean
average precision scores by 20% on average (bernstein:2005, ).

The classical evaluation setup of search engines employs the Cranfield
paradigm, making it pretty easy to oversee negative impacts caused by near-
duplicates. Relevance assessors judge the relevance of documents to a query in
isolation, seeing only one document at a time. Hence, situations that would
severely reduce the experience for searchers, e.g., when many near-duplicates
occur at subsequent positions in the ranking, can be overlooked because
assessors do not look at the ranking. Topic 194 of the ClueWeb09 Web Tracks
includes a particularly striking example, where among 47 relevant documents,
there are 40 near-duplicates of the same Wikipedia article.

### Risk: Training of Learning to Rank Models

Near-duplicates form a kind of oversampling because multiple identical or very
similar copies of a page are in the dataset. As recently exemplified
(vandewiele:2020, ), oversampling data before partitioning it into training
and test sets can invalidate evaluations in machine learning because models
may see the same object during training and test. This leakage of information
is not possible during the training of learning to rank models because the
train/test partitioning is done per query. Still, not removing near-duplicates
during the training of learning to rank models decreases the effectiveness of
models and biases the trained models (webis:2020d, ).

A study (webis:2020d, ) on the ClueWeb09 with 42 ranking features using
popular algorithms finds that near-duplicates in the training data harm the
retrieval performance, since the presence of near-duplicates is unaccounted
for in the loss-minimization of learning to rank and in subsequent
evaluations. Furthermore, by varying the number of Wikipedia near-duplicates
in the training set, the study showed that models might be biased towards
retrieving near-duplicates at higher positions. Hence, these observations make
a strong case that learning to rank pipelines benefit from removing duplicate
documents from the data before training the model.

Mitigating the negative effects of near-duplicates during the training of
retrieval models is easily possible with the CopyCat framework, which can
deduplicate the training and test set.

### Potential: Transfer of Relevance Labels

In contrast to the previous two risks to the validity and robustness of search
engine evaluation and tuning, near-duplicate detection enables the transfer of
relevance judgments between different editions (or updates) of web crawls
(froebe:2021, ). Relevance judgments—obtained from click logs or expert
assessments—are an important and costly resource for the development of search
engines. E.g., the effort for the 73,883 relevance judgments for the TREC Web
tracks on the ClueWeb09 crawl can be estimated at a manual labor of about 4–8
full-time person-months (assuming 40-hour weeks with 30–60 seconds per
judgment (voorhees:2001, )).

To “reduce” the costs of keeping the relevance judgments up-to-date for ever-
evolving web-indices, search engines might transfer relevance judgments from
the previous version of a crawl to the next version when they find the judged
documents (or near-duplicates of them) in the newer version of the crawl. In a
showcase (froebe:2021, ) using precision-oriented near-duplicate detection
with the CopyCat framework, 10% of the ClueWeb09 relevance judgments could be
transferred to the ClueWeb12. The number of transferred relevance judgments
would even increase to 15% when the ClueWeb12 crawling process would have
ensured that the URLs judged in the ClueWeb09 are part of the URL seeds for
the next crawling round. More frequent updates (compared to the gap of three
years in the relevance transfer showcase) would likely further increase the
amount of transferrable relevance judgments. Additionally, the reported
experiments on the transfer of relevance labels have used only the full
content of the pages. Hence, further improvements, e.g., by leveraging main
content extraction to increase the recall while maintaining good precision,
are possible.

## Content Extraction Experiments

To experimentally compare the impact of main content extraction on near-
duplicate detection, we construct a dataset of $186\,819$ ClueWeb document
pairs with redundant content as indicated by canonical URLs. For each document
pair, we calculate its syntactic similarity with the lossless $S_{3}$
fingerprinting (bernstein:2004, ) for four main content extraction algorithms
and the full content of pages. We label 900 document pairs as near-duplicates
or not sampled with two approaches: (1) with 100 document pairs stratified
sampled from the $S_{3}$ distribution of each of the five content extraction
methods, and (2) with 50 document pairs with maximal positive/negative $S_{3}$
differences between each of the four main content extraction methods and the
full content of a page.

### Dataset Construction

We aim at constructing a manageable dataset for our experiments that allows us
to draw a sharp line between “only similar” documents and near-duplicates.
Therefore, we identify document pairs in the ClueWeb09 and ClueWeb12 that
should contain redundant content because they share the same canonical URL. We
inspect all documents in the ClueWeb, group them by their canonical URL, and
select 5,000 groups having the same canonical link at random. From each group,
we select all possible pairs (with a maximum of 50 document pairs per group)
yielding 186,819 document pairs.

Figure 2. Cumulative distribution plot showing the proportion of document
pairs in our dataset below a given similarity measured by their $S_{3}$ score
for all five considered content extraction methods.

### Document Preprocessing

We preprocess all documents with the CopyCat framework. CopyCat provides five
content extraction approaches that transform the raw HTML of a page into text:
four main content extraction approaches and one full content extraction. The
four provided main content extraction approaches are Boilerpipe
(kohlschuetter:2010, ), Jericho,444http://jericho.htmlparser.net Justext
(pomikalek:2011, ), and Trafilatura (barbaresi:2019, ). The full content
extraction uses JSoup555https://jsoup.org/ to extract the plain text—without
any main content extraction—from the HTML. After extracting the documents
text, we remove stop words using Lucene’s default stop word list for English,
apply stemming with the Porter Stemmer, and lower case the remaining words.

### Similarity in our Dataset

We use the lossless $S_{3}$ fingerprint similarity (bernstein:2004, ) using
word-8-grams to calculate the similarities between all document pairs for all
five content extraction methods in our dataset. An $S_{3}$ score of $0$
indicates no overlap between documents, and an $S_{3}$ score of 1 means
equality. Figure 2 shows the cumulative distribution plot for all five content
extraction methods regarding the portion of document pairs below a given
$S_{3}$ score.

We can identify two groups of content extraction methods that share similar
overall behavior. The first group consists of the main content extraction
methods Trafilatura and Boilerpipe that show many document pairs with an
$S_{3}$ score of $0$ (26% for Boilerpipe and 27% for Trafilatura), indicating
that the main content extraction produces disjoint main contents from the
considered documents in a pair. This group additionally contains many document
pairs with an $S_{3}$ score of $1$ (55% for Boilerpipe and 39% for
Trafilatura), indicating that for documents in a pair often the same main
content is extracted.

Table 1. Overview of (a) precision and recall for near-duplicates in the
uniform sampled document pairs at high syntactic similarity ($S_{3}=1$ and
$S_{3}\geq 0.9$), and (b) near-duplicates per $S_{3}$ similarity in the
uniform sampled document pairs for all five content extraction methods.
Lastly, (c) shows near-duplicates per $S_{3}$ similarity in document pairs
with large $S_{3}$ differences to the full content extraction.

(a)
---
| $S_{3}=1$ | $S_{3}\geq 0.9$
| Pr. | Re. | Pr. | Re.
Full Content | 1.00 | 0.06 | 0.98 | 0.26
JusText | 1.00 | 0.07 | 1.00 | 0.24
Trafilatura | 0.76 | 0.33 | 0.77 | 0.41
Jericho | 0.93 | 0.07 | 0.97 | 0.26
Boilerpipe | 0.60 | 0.50 | 0.61 | 0.59

(b) | (c)
---|---
|

The second group consists of the full content, Justext, and Jericho methods of
content extraction. Approaches in this group have very few document pairs with
an $S_{3}$ score of $0$ (the Justext approach from this group has the maximum
of 0.35% of document pairs with an $S_{3}$ score of $0$), and much fewer
document pairs with an $S_{3}$ score of $1$ (all three have around 15.6% of
document pairs with an $S_{3}$ score of $1$). We calculated the Pearson
correlation between the full content extraction and all other methods. We
found a very high correlation to Justext and Jericho (0.97 respectively 0.99)
and only a moderate correlation to Boilerpipe and Trafilatura (0.65
respectively 0.73). Overall, Figure 2 shows that the $S_{3}$ scores in our
dataset differ substantially between the two groups, which motivates us to
manually verify which of the document pairs are indeed near-duplicates.

### Labeling Near-Duplicates

After calculating the $S_{3}$ scores for all document pairs with all content
extraction methods, we sample two sets of document pairs for manual review.
First, we sample 100 document pairs uniformly covering $S_{3}$ scores between
0 and 1 for all five content extraction methods. Second, we sample document
pairs with large $S_{3}$ differences between a main content extraction method
and the full content extraction aiming at identifying document pairs where
main content extraction yields opposite $S_{3}$ scores to full content
extraction. Therefore, we select the 50 document pairs with the largest
positive and largest negative $S_{3}$ difference for all four main content
extraction methods for manual review.

We use the near-duplicate definition and review guidelines of Bernstein and
Zobel (bernstein:2005, ) to label near-duplicates: A document pair is
considered as near-duplicate when both documents are content-equivalent, and
users would be able to extract the same information from either one for all
reasonable queries. Two versions of the same Wikipedia article with only minor
non-content changes are an example of near-duplicates under this definition.

We labeled the two document pair samples with two assessors. We applied a
$\kappa$-test on the 100 document pairs sampled for $S_{3}$ similarities
between $0$ and $1$ for the full content method, finding a high Fleiss’
$\kappa$ of 0.78, indicating good agreement between both assessors. In a
follow-up discussion among the annotators, we discussed all 11 document pairs
with different near-duplicate judgments, finally agreeing in all cases. After
our $\kappa$ test, each annotator judged the document pairs for the same two
main content extraction methods for both user studies.

### Evaluation

Table 1a and the plot in Table 1b show the ability of all five content
extraction methods to identify near-duplicate documents in our set of 500
manually reviewed document pairs that uniformly cover $S_{3}$ scores between 0
and 1. In Table 1a, we report precision and recall for $S_{3}$ thresholds of 1
(for exact duplicates after content extraction) and 0.9 (highly similar
extracted content). As in our initial discussion on similarity scores produced
by the five content extraction methods, Trafilatura and Boilerpipe (the group
with many document pairs at an $S_{3}$ score of 1 in Figure 2) as well as the
full content, Justext, and Jericho (the group with fewer document pairs with
an $S_{3}$ score of 1 in Figure 2) show similar behavior in terms of precision
and recall. The full content and Justext approaches show a perfect precision
of 1.0 at an $S_{3}$ threshold of 1, and Justext even has a perfect precision
at an $S_{3}$ threshold of 0.9. On the other side, Trafilatura and Boilerpipe
show a very high recall. Even for an $S_{3}$ score of 1, Boilerpipe achieves a
remarkable Recall of 0.5.

The plot in Table-1b shows the correctly and wrongly identified near-
duplicates per $S_{3}$ score for all content extraction methods in our set of
500 manually reviewed document pairs that uniformly cover $S_{3}$ scores
between 0 and 1. Again, we can see similar behavior for the full content,
Justext, and Jericho methods which make almost no mistakes at high
respectively low $S_{3}$ scores. In the opposite group, with Trafilatura and
Boilerpipe, we see quite some mistakes (even at $S_{3}$ = 1 and $S_{3}$ = 0).

The plot in Table 1c shows the correctly and wrongly identified near-
duplicates per $S_{3}$ score for all content extraction methods in our set of
400 manually reviewed document pairs for which the main content extraction
changes the similarity drastically. In almost all cases, barring few
exceptions, we find that for such large differences, the $S_{3}$ score
calculated on the full content correctly identifies near-duplicates and non-
near-duplicates. This is visible since the full content method assigns, almost
perfectly, non-near-duplicates an $S_{3}$ score near 0, and near-duplicates an
$S_{3}$ score near 1. All other approaches make substantial mistakes in this
selection of document pairs, indicated by assigning many non-near-duplicates
an $S_{3}$ score near 1 (for which the full content method assigned scores
near 0, since we selected large differences), and many near-duplicates an
$S_{3}$ score near 0 (for which the full content method assigned scores near
1). Especially for cases in which highly similar documents get dissimilar main
content extracted, we often found that the main content extraction had
problems in identifying the correct main content. Overall, Trafilatura is the
most vulnerable in this setting (the most near-duplicates near $S_{3}$ of 0,
and most non-near-duplicates near $S_{3}$ of 1). Still, even main content
extraction approaches with a very high correlation to the full content
extraction method, like Jericho and Justext in our experiments, make
substantial mistakes.

## Conclusion and Future Work

We have recapitulated two risks and one potential application of near-
duplicates in web search to motivate the maintenance of metadata on duplicate
and near-duplicate documents. Given metadata on near-duplicates, it is easy to
remove risks such as overestimated evaluation scores of retrieval systems or
overfitted learning to rank models. Additionally, updating relevance judgments
to the next version of the underlying web crawl can be done at lower costs
because relevance labels might automatically be transferred to near-duplicates
in the newer version.

In a first attempt to simplify the difficult decision of choosing an
appropriate similarity threshold, we investigated how removing parts of
documents that are rather irrelevant for the retrieval impacts the similarity
of documents. Therefore, we have compared document similarities after
preprocessing documents with five (main) content extraction methods. We found
that main content extraction can yield very high recall for near-duplicate
detection, even when only documents with identical main content are considered
as near-duplicates.

An interesting prospect for future work is to include more main content
extraction methods and expand the experiments to more document pairs. Another
interesting direction for future work might be a further inspection of our
observation that highly similar documents having very dissimilar extracted
main contents were in most cases caused by mistakes in the main content
extraction. This technique might help bootstrap a distant supervision dataset
of documents with main content that is difficult to extract.

## References

  * [1] E. Adar, J. Teevan, S. T. Dumais, and J. L. Elsas.  The Web Changes Everything: Understanding the Dynamics of Web Content.  In Proceedings of the Second International Conference on Web Search and Web Data Mining, WSDM 2009, Barcelona, Spain, February 9-11, 2009, pages 282–291, 2009.
  * [2] M. Alshomary, M. Völske, T. Licht, H. Wachsmuth, B. Stein, M. Hagen, and M. Potthast.  Wikipedia Text Reuse: Within and Without.  In L. Azzopardi, B. Stein, N. Fuhr, P. Mayr, C. Hauff, and D. Hiemstra, editors, Advances in Information Retrieval. 41st European Conference on IR Research (ECIR 2019), volume 11437 of Lecture Notes in Computer Science, pages 747–754, Berlin Heidelberg New York, Apr. 2019. Springer.
  * [3] B. Alsulami, M. Abulkhair, and F. Eassa.  Near Duplicate Document Detection Survey.  International Journal of Computer Science and Communications Networks, 2(2):147–151, 2012.
  * [4] A. Barbaresi.  Generic web content extraction with open-source software.  In Proceedings of the 15th Conference on Natural Language Processing, KONVENS 2019, Erlangen, Germany, October 9-11, 2019, 2019.
  * [5] Y. Bernstein and J. Zobel.  A Scalable System for Identifying Co-derivative Documents.  In String Processing and Information Retrieval, 11th International Conference, SPIRE 2004, Padova, Italy, October 5-8, 2004, Proceedings, pages 55–67, 2004.
  * [6] Y. Bernstein and J. Zobel.  Redundant Documents and Search Effectiveness.  In Proceedings of the 2005 ACM CIKM International Conference on Information and Knowledge Management, Bremen, Germany, October 31 - November 5, 2005, pages 736–743, 2005.
  * [7] A. Z. Broder.  On the Resemblance and Containment of Documents.  In Compression and Complexity of SEQUENCES 1997, Positano, Amalfitan Coast, Salerno, Italy, June 11-13, 1997, Proceedings, pages 21–29, 1997.
  * [8] M. Charikar.  Similarity Estimation Techniques from Rounding Algorithms.  In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 380–388, 2002.
  * [9] J. Cho and H. Garcia-Molina.  The Evolution of the Web and Implications for an Incremental Crawler.  In VLDB 2000, Proceedings of 26th International Conference on Very Large Data Bases, September 10-14, 2000, Cairo, Egypt, pages 200–209, 2000\.
  * [10] D. Fetterly, M. S. Manasse, and M. Najork.  On the Evolution of Clusters of Near-Duplicate Web Pages.  In 1st Latin American Web Congress (LA-WEB 2003), Empowering Our Web, 10-12 November 2003, Sanitago, Chile, pages 37–45, 2003.
  * [11] D. Fetterly, M. S. Manasse, M. Najork, and J. L. Wiener.  A Large-Scale Study of the Evolution of Web Pages.  In Proceedings of the Twelfth International World Wide Web Conference, WWW 2003, Budapest, Hungary, May 20-24, 2003, pages 669–678, 2003\.
  * [12] M. Fröbe, J. Bevendorff, L. Gienapp, M. Völske, B. Stein, M. Potthast, and M. Hagen.  CopyCat: Near-Duplicates within and between the ClueWeb and the Common Crawl.  In 44th International ACM Conference on Research and Development in Information Retrieval (SIGIR 2021). ACM, July 2021.
  * [13] M. Fröbe, J. Bevendorff, J. H. Reimer, M. Potthast, and M. Hagen.  Sampling Bias Due to Near-Duplicates in Learning to Rank.  In J. Huang, Y. Chang, X. Cheng, J. Kamps, V. Murdock, J. Wen, and Y. Liu, editors, Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, SIGIR 2020, Virtual Event, China, July 25-30, 2020, pages 1997–2000. ACM, 2020.
  * [14] M. Fröbe, J. P. Bittner, M. Potthast, and M. Hagen.  The Effect of Content-Equivalent Near-Duplicates on the Evaluation of Search Engines.  In J. M. Jose, E. Yilmaz, J. Magalhães, P. Castells, N. Ferro, M. J. Silva, and F. Martins, editors, Advances in Information Retrieval \- 42nd European Conference on IR Research, ECIR 2020, Lisbon, Portugal, April 14-17, 2020, Proceedings, Part II, volume 12036 of Lecture Notes in Computer Science, pages 12–19. Springer, 2020.
  * [15] M. R. Henzinger.  Finding Near-Duplicate Web Pages: A Large-Scale Evaluation of Algorithms.  In SIGIR 2006: Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Seattle, Washington, USA, August 6-11, 2006, pages 284–291, 2006\.
  * [16] C. Kohlschütter, P. Fankhauser, and W. Nejdl.  Boilerplate Detection Using Shallow Text Features.  In B. D. Davison, T. Suel, N. Craswell, and B. Liu, editors, Proceedings of the Third International Conference on Web Search and Web Data Mining, WSDM 2010, New York, NY, USA, February 4-6, 2010, pages 441–450. ACM, 2010.
  * [17] G. S. Manku, A. Jain, and A. D. Sarma.  Detecting Near-Duplicates for Web Crawling.  In C. L. Williamson, M. E. Zurko, P. F. Patel-Schneider, and P. J. Shenoy, editors, Proceedings of the 16th International Conference on World Wide Web, WWW 2007, Banff, Alberta, Canada, May 8-12, 2007, pages 141–150. ACM, 2007.
  * [18] A. Ntoulas, J. Cho, and C. Olston.  What’s new on the Web?: The Evolution of the Web from a Search Engine Perspective.  In S. I. Feldman, M. Uretsky, M. Najork, and C. E. Wills, editors, Proceedings of the 13th international conference on World Wide Web, WWW 2004, New York, NY, USA, May 17-20, 2004, pages 1–12. ACM, 2004.
  * [19] C. Olston and S. Pandey.  Recrawl Scheduling Based on Information Longevity.  In J. Huai, R. Chen, H. Hon, Y. Liu, W. Ma, A. Tomkins, and X. Zhang, editors, Proceedings of the 17th International Conference on World Wide Web, WWW 2008, Beijing, China, April 21-25, 2008, pages 437–446. ACM, 2008\.
  * [20] J. Pomikálek.  Removing boilerplate and duplicate content from web corpora.  PhD thesis, Masarykova univerzita, Fakulta informatiky, 2011.
  * [21] C. Raffel, N. Shazeer, A. Roberts, K. Lee, S. Narang, M. Matena, Y. Zhou, W. Li, and P. J. Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  J. Mach. Learn. Res., 21:140:1–140:67, 2020.
  * [22] G. Vandewiele, I. Dehaene, G. Kovács, L. Sterckx, O. Janssens, F. Ongenae, F. D. Backere, F. D. Turck, K. Roelens, J. Decruyenaere, S. V. Hoecke, and T. Demeester.  Overly Optimistic Prediction Results on Imbalanced Data: A Case Study of Flaws and Benefits when Applying Over-Sampling.  Artif. Intell. Medicine, 111:101987, 2021.
  * [23] E. M. Voorhees.  The Philosophy of Information Retrieval Evaluation.  In C. Peters, M. Braschler, J. Gonzalo, and M. Kluck, editors, Evaluation of Cross-Language Information Retrieval Systems, Second Workshop of the Cross-Language Evaluation Forum, CLEF 2001, Darmstadt, Germany, September 3-4, 2001, Revised Papers, volume 2406 of Lecture Notes in Computer Science, pages 355–370. Springer, 2001.