Entanglement, partial set of measurements, and diagonality of the density
matrix in the parton model

Haowu Duan1,

1 North Carolina State University *<EMAIL_ADDRESS>
Proceedings for the XXVIII International Workshop
on Deep-Inelastic Scattering and Related Subjects,
Stony Brook University, New York, USA, 12-16 April 2021
10.21468/SciPostPhysProc.?

## Abstract

To study quantum properties of the hadron wavefunction at small x, we derived
the reduced density matrix for soft gluons in the CGC framework. We explicitly
showed that the reduced density matrix is not diagonal in the particle number
basis. The off-diagonal components are usually ignored in the conventional
parton model. We thus defined the density matrix of ignorance by keeping only
the part of the reduced density matrix which can be probed in a limited set of
experimental measurements. We calculated Von Neumann entropy for both the
reduced and ignorance density matrices. The entropy of ignorance is always
greater than the entanglement entropy (computed drom the reduced density
matrix) of gluons. Finally, we showed that the CGC reduced density matrix for
soft gluons can be diagonalized in a thermal basis with Boltzmann weights
suggesting thermalization of new quasi-particle states which we dubbed
entangolons.

##  1 Introduction

This work was motivated by the paradox raised in Ref. [1]. On one hand the
proton as a quantum object is in a pure state and is described by a completely
coherent wavefunction with zero entropy. On the other hand in high energy
experiments when probed by a small external probe, it behaves like an
incoherent ensemble of (quasi-free) partons. Such an ensemble carries a
nonvanishing entropy. Reference [1] suggested that the origin of this entropy
is entanglement between the degrees of freedom one observes in DIS (partons in
the small spatial region of the proton) and the rest of the proton
wavefunction which are not measured in the final state and therefore play the
role of an “environment”. Formally, this can be formulated in terms of the
reduced density matrix

$\hat{\rho}_{r}={\rm Tr}_{\rm unobs}\,\Big{[}\,|P\rangle\langle
P|\,\Big{]}\,,$ (1)

where $|P\rangle$ is the proton wave function and the partial trace is taken
over the unobserved degrees of freedom. The entropy of the parton model is
then identified with the von Neumann entropy of the reduced density matrix
according to

$S_{\rm PM}=-{\rm Tr}\Big{[}\,\hat{\rho}_{r}\,\ln\hat{\rho}_{r}\,\Big{]}\,.$
(2)

Most of the quantities measured DIS are related to the average number of
particles or multi-parton momentum distributions $\langle
a^{\dagger}({\underline{k}}_{1})a({\underline{k}}_{1})...a^{\dagger}({\underline{k}}_{n})a({\underline{k}}_{n})\rangle$.
These quantities do not provide an access to the off-diagonal elements of the
density matrix in the number operator basis. This leads to the fundamental
problem that one cannot reconstruct the full density matrix from the available
experimental data.

This lack of knowledge of the actual density matrix of the system can be
characterized by an entropy. We will dub this entropy “the entropy of
ignorance”. Among the family of all density matrices that reproduce the same
experimental observable, we defined the matrix that have zeros on all off-
diagonal elements as the density matrix of ignorance (the operation of
dropping the off-diagonal elements of the density matrix can be considered as
an example of a quantum-to-classical channel). The associated entropy

$S_{I}=-{\rm Tr}\Big{[}\hat{\rho}_{I}\ln\hat{\rho}_{I}\Big{]}\,.$ (3)

It has the following property $S_{I}\geq-{\rm
Tr}\Big{[}\hat{\rho}_{r}\ln\hat{\rho}_{r}\Big{]}$ (see e.g. Refs. [2, 3]). The
entropy of ignorance is exactly equal to the Boltzmann entropy of the
classical ensemble of partons with the probability distribution defined by the
diagonal matrix elements

$S_{I}=S_{B}=-\sum_{n}\,p_{n}\ln p_{n};\quad\quad p_{n}=\langle
n|\hat{\rho}_{r}|n\rangle\,.$ (4)

##  2 The CGC density matrices

The Color Glass Condensate (CGC) effective theory describes scattering at high
energy (see Refs. [4, 5, 6, 7, 8] for reviews). According to the CGC, the
valence (“hard”) partons can be treated as static classical sources of the
small-x “soft” gluons. This partial separation of degrees of freedom can be
formalized by

$|\psi\rangle=|s\rangle\otimes|v\rangle\,,$ (5)

where $|v\rangle$ is the state vector characterizing the valence degrees of
freedom and $|s\rangle$ is the soft fields in the presence of the valence
source. Despite appearances, the state is not of a direct product form since
the soft vacuum depends on the valence degrees of freedom. In the leading
perturbative order, the CGC soft gluon state is

$|s\rangle=\mathcal{C}|0\rangle$ (6)

with the coherent operator

${\cal C}=\exp\left\\{2i{\rm
tr}\int\frac{d^{2}k}{(2\pi)^{2}}b^{i}({\underline{k}})\phi_{i}({\underline{k}})\right\\}=\exp\left\\{2i{\rm
tr}\int_{{\underline{k}}}b^{i}({\underline{k}})\phi_{i}({\underline{k}})\right\\}\,,$
(7)

where $\phi_{i}({\underline{k}})\equiv
a_{i}^{+}({\underline{k}})+a_{i}(-{\underline{k}})$, and the trace operation
(tr) is over all colors. The background field $b^{i}_{a}$ is determined by the
valence color charge density $\rho$ via:

$b^{i}_{a}({\underline{k}})=g\rho_{a}({\underline{k}})\frac{i{\underline{k}}_{i}}{k^{2}}+{\cal
O}(\rho^{2})\,.$ (8)

For simplicity we restrict our consideration only to the leading order
contribution in the charge density $\rho$ which captures only the longitudinal
polarization of the soft gluons. We do not expect our results to change if
higher order corrections are included.

The valence wave function $|v\rangle$ is customarily modeled following the
McLerran-Venugopalan (MV) model [9, 10]

$\langle\rho|v\rangle\langle
v|\rho\rangle={\mathcal{N}}e^{-\int_{{\underline{k}}}\frac{1}{2\mu^{2}}\rho_{a}({\underline{k}})\rho^{*}_{a}({\underline{k}})}\,,$
(9)

where ${\mathcal{N}}$ is the normalization factor and the parameter $\mu^{2}$
determines the average color charge density. Now we can formally define the
hadron density matrix:

$\hat{\rho}=|v\rangle\otimes|s\rangle\langle s|\otimes\langle v|\,.$ (10)

Integrating out the valence degrees of freedom, we obtain the reduced density
matrix for the soft gluons:

$\displaystyle\hat{\rho}_{r}=\mathcal{N}\int
D\rho\,\,e^{-\int_{{\underline{k}}}\frac{1}{2\mu^{2}}\rho_{a}({\underline{k}})\rho^{*}_{a}({\underline{k}})}\mathcal{C}(\rho_{b},\phi_{b}^{i})|0\rangle\langle
0|\mathcal{C}^{\dagger}(\rho_{c},\phi_{c}^{j})\,.$ (11)

To extract the ignorance density matrix, $\hat{\rho}_{I}$, in gluon number
basis, we need the basis vectors

$\displaystyle\prod_{c}\prod_{k}|n_{c}({\underline{k}}),m_{c}(-{\underline{k}})\rangle\propto\prod_{c}\prod_{k}\left(\frac{[a^{\dagger}_{c}({\underline{k}})]^{n_{c}}}{\sqrt{n_{c}!}}\right)\left(\frac{[a^{\dagger}_{c}(-{\underline{k}})]^{m_{c}}}{\sqrt{m_{c}!}}\right)|0\rangle\,$
(12)

where $c$ is the color indices, and we only consider longitudinal
polarization. Since a mode with momentum ${\underline{k}}$ mixes only with the
mode with momentum $-{\underline{k}}$ due to the fact that
$\rho^{*}_{a}({\underline{k}})=\rho_{a}(-{\underline{k}})$, we introduce
$N_{c}=n_{c}+m_{c}$. Furthermore, $\hat{\rho}_{r}$ is a direct product of
density matrices in a fixed transverse momentum sector due to transnational in
variance, see [11] for details.

The matrix elements of the density matrix for a given value of momentum $q$
and given color c are

$\displaystyle\langle
n_{c}({\underline{q}}),m_{c}(-{\underline{q}})|\hat{\rho}_{r}({\underline{q}})|\alpha_{c}({\underline{q}}),\beta_{c}(-{\underline{q}})\rangle=(1-R)\frac{\left(n+\beta\right)!}{\sqrt{n!m!\alpha!\beta!}}\left(\frac{R}{2}\right)^{n+\beta}\delta_{\left(n+\beta\right),\left(m+\alpha\right)}\,,$
(13) $\displaystyle R=\left(1+\frac{q^{2}}{2g^{2}\mu^{2}}\right)^{-1}\,.$ (14)

We thus explicitly demonstrated that the off-diagonal components are non zero!
This is one of the main results of this paper. If we ignore the off-diagonal
elements we obtain the ignorance density matrix in the number of gluons
representation

$\displaystyle\langle
n_{c}({\underline{q}}),m_{c}(-{\underline{q}})|\hat{\rho}_{I}({\underline{q}})|n_{c}({\underline{q}}),m_{c}(-{\underline{q}})\rangle=(1-R)\frac{\left(n+m\right)!}{n!m!}\left(\frac{R}{2}\right)^{n+m}\,.$
(15)

##  3 Quantum Entropies

Using the reduced density matrix, the entropy of entanglement can be readily
calculated. It reproduces the known result obtained in Ref. [12]:

$\displaystyle S_{E}$
$\displaystyle=\frac{(N_{c}^{2}-1)S_{\perp}}{2}\int\frac{d^{2}q}{(2\pi)^{2}}\Bigg{[}\ln(\frac{g^{2}\mu^{2}}{q^{2}})+\sqrt{1+4\frac{g^{2}\mu^{2}}{q^{2}}}$
$\displaystyle\times\ln(1+\frac{q^{2}}{2g^{2}\mu^{2}}+\frac{q^{2}}{2g^{2}\mu^{2}}\sqrt{1+4\frac{g^{2}\mu^{2}}{q^{2}}})\Bigg{]}\,.$
(16)

There is no analytic expression for the entropy of ignorance. Hence, we
compare the results numerically in Fig. 1.

Figure 1: Ratios of entropy densities at a given magnitude of the transverse
momentum $q/g\mu$. $S_{I}(q^{2})$ is the von Neumann entropy density of
ignorance and $S_{E}(q^{2})$ is the corresponding entanglement entropy
density.

According to the ratio $S_{I}/S_{E}$, the dominant contribution to their
difference is at small q where states with more than one particle cannot be
ignored. While at large q, only the vacuum state survives and the two density
matrix are approximately the same hence the ratio approaching 1.

##  4 Thermal quasi-particle basis

It is amusing that the entanglement entropy can be rewritten in the form

$\displaystyle
S_{E}=(N_{c}^{2}-1)S_{\perp}\int\frac{d^{2}q}{(2\pi)^{2}}\Bigg{[}(1+f)\ln(1+f)-f\ln
f\Bigg{]}$ (17)

with $f=(\exp(\beta\omega)-1)^{-1}$ and
$\omega\beta=2\ln\left(\frac{q}{2g\mu}+\sqrt{1+\left(\frac{q}{2g\mu}\right)^{2}}\right)$.
This suggests that there exists a quasi-particle basis in the reduced density
matrix is diagonal and thermal (i.e. all eigenvalues of the density matrix are
powers of the same number.). We named this quasi-particles entangalons.

At small momentum, $\omega\beta\approx\frac{q}{g\mu}$, we thus can identify
the effective temperature of entangolons with $g\mu$.

At large momentum, the quasi-particle distribution function coincides with the
Weizsacker-Williams distribution of gluons $f\approx g^{2}\mu^{2}/q^{2}$.

##  5 Conclusions

Our explicit calculation confirms that, within the CGC framework, the reduced
density matrix for soft gluons is not diagonal in parton/particle number
basis. Neglecting the off-diagonal elements results in the loss of information
and thus in larger entropy. We introduced a new form of entropy associated
with this loss and called it entropy of ignorance. It is greater than the
entanglement entropy which is supposedly related to the entropy of final state
particles. In addition, by analysing the entanglement entropy, we hypothesized
that the reduced density matrix directly is diagonal in some quasi-particle
basis with the eigenvalues having the form of Boltzmann weights.

##  6 Acknowledgements

We thanks A. Kovner and V. Skokov for collaborating on this project. This
works is supported by the DOE Office of Nuclear Physics through Grant No. DE-
SC0020081.

## References

  * [1] D. E. Kharzeev and E. M. Levin,  _Deep inelastic scattering as a probe of entanglement_ ,  Phys. Rev. D95(11), 114008 (2017),  10.1103/PhysRevD.95.114008,  1702.03489.
  * [2] A. Wehrl,  _General properties of entropy_ ,  Rev. Mod. Phys. 50, 221 (1978),  10.1103/RevModPhys.50.221.
  * [3] E. Witten,  _A Mini-Introduction To Information Theory_ (2018),  1805.11965.
  * [4] E. Iancu, A. Leonidov and L. McLerran,  _The Color glass condensate: An Introduction_ ,  In _QCD perspectives on hot and dense matter. Proceedings, NATO Advanced Study Institute, Summer School, Cargese, France, August 6-18, 2001_ , pp. 73–145 (2002), hep-ph/0202270.
  * [5] A. Kovner,  _High energy evolution: The Wave function point of view_ ,  Acta Phys. Polon. B36, 3551 (2005),  hep-ph/0508232.
  * [6] L. McLerran,  _The Color Glass Condensate and Glasma_ (2008),  0804.1736.
  * [7] F. Gelis, E. Iancu, J. Jalilian-Marian and R. Venugopalan,  _The Color Glass Condensate_ ,  Ann. Rev. Nucl. Part. Sci. 60, 463 (2010),  10.1146/annurev.nucl.010909.083629,  1002.0333.
  * [8] Y. V. Kovchegov and E. Levin,  _Quantum chromodynamics at high energy_ ,  Camb. Monogr. Part. Phys. Nucl. Phys. Cosmol. 33, 1 (2012),  10.1017/CBO9781139022187.
  * [9] L. D. McLerran and R. Venugopalan,  _Computing quark and gluon distribution functions for very large nuclei_ ,  Phys. Rev. D49, 2233 (1994),  10.1103/PhysRevD.49.2233,  hep-ph/9309289.
  * [10] L. D. McLerran and R. Venugopalan,  _Gluon distribution functions for very large nuclei at small transverse momentum_ ,  Phys. Rev. D49, 3352 (1994),  10.1103/PhysRevD.49.3352,  hep-ph/9311205.
  * [11] H. Duan, C. Akkaya, A. Kovner and V. V. Skokov,  _Entanglement, partial set of measurements, and diagonality of the density matrix in the parton model_ ,  Phys. Rev. D 101(3), 036017 (2020),  10.1103/PhysRevD.101.036017,  2001.01726.
  * [12] A. Kovner and M. Lublinsky,  _Entanglement entropy and entropy production in the Color Glass Condensate framework_ ,  Phys. Rev. D92(3), 034016 (2015),  10.1103/PhysRevD.92.034016,  1506.05394.


Successive Syndrome-Check Decoding of
Polar Codes

Seyyed Ali Hashemi1, Marco Mondelli2, John Cioffi3, Andrea Goldsmith4

1Qualcomm, USA
2Institute of Science and Technology, Austria
3Department of Electrical Engineering, Stanford University, USA
4Department of Electrical and Computer Engineering, Princeton University, USA

A two-part successive syndrome-check decoding of polar codes is proposed with the first part successively refining the received codeword and the second part checking its syndrome. A new formulation of the successive-cancellation (SC) decoding algorithm is presented that allows for successively refining the received codeword by comparing the log-likelihood ratio value of a frozen bit with its predefined value. The syndrome of the refined received codeword is then checked for possible errors. In case there are no errors, the decoding process is terminated. Otherwise, the decoder continues to refine the received codeword. The proposed method is extended to the case of SC list (SCL) decoding by terminating the decoding process when the syndrome of the best candidate in the list indicates no errors. Simulation results show that the proposed method reduces the time-complexity of SC and SCL decoders and their fast variants, especially at high signal-to-noise ratios.

§ INTRODUCTION

Polar codes are a class of coding schemes that can provably achieve the capacity of a binary-input memoryless symmetric channel with low-complexity encoding and decoding algorithms as the code length tends to infinity [1].
The successive-cancellation (SC) decoder for a polar code of length $N$, with which polar codes can achieve capacity, has complexity $O(N\log N)$. The SC list (SCL) decoding with list size $L>1$ improves the error rate performance of polar codes at finite block lengths and has complexity $O(LN\log N)$ [2]. SC and SCL decoding algorithms are serial in nature in the sense that the decoders progress by decoding the bits one by one. Consequently, the latency of SC and SCL decoders is high, which adversely affects their practical implementation.

Several attempts have been made to improve the speed of SC and SCL decoders for polar codes. In particular, the decoding process is represented as message passing on a binary tree where the messages are either soft log-likelihood ratio (LLR) values or hard bit estimations. Since the calculation of soft messages is more costly than hard bit estimations, the decoding latency is modeled as the number of edges in the binary tree that need to be traversed by the underlying decoder to calculate the soft messages. The goal of fast SC and SCL decoders is to prune the decoding tree to reduce the number of edges. This pruning is achieved by the following main methods:

* Identifying specific constituent codes of polar codes that can be decoded efficiently without traversing the decoding tree [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19];

* Checking the syndrome of the constituent codes of polar codes to avoid traversing the decoding tree when the syndrome check is satisfied [20, 21, 22];

* Adjusting the code to increase the number of specific constituent codes of polar codes [23, 24, 25, 26, 27];

* Comparing the error probability of constituent codes of polar codes with a threshold to avoid traversing the decoding tree when the error probability is small [28, 29].

The first two methods are lossless in the sense that they do not result in error-correction performance degradation with respect to the conventional SC and SCL decoders, while the other two methods may cause error-correction performance loss.

In this paper, SC decoding is reformulated from a novel perspective that allows for successively refining the codeword that was received from the channel. It is shown that this codeword refinement strategy can only take place when a frozen bit that has a predefined value is decoded. Thus, there is no need to calculate soft messages for information bits. Moreover, the refinement of the received codeword is only necessary for those frozen bits whose LLR values do not match their predefined values. Using the equivalence of soft and hard decoding when there is no error, a successive syndrome-check decoder is presented that significantly speeds up the decoding process, especially when the transmission channel experiences low levels of noise.

§ PRELIMINARIES

§.§ Polar Codes

Let $K$ denote the number of information bits and $N=2^n$ denote the block length of the code. A polar code is represented by $\mathcal{P}\left(N,K\right)$ that has rate $R = \frac{K}{N}$. The encoded vector $\bm{x} = \{x_0,x_1,\ldots,x_{N-1}\}$ is generated by the multiplication of the input vector $\bm{u} = \{u_0,u_1,\ldots,u_{N-1}\}$ and the generator matrix $\bm{G}^{\otimes n}$, and it is expressed as $\bm{x}=\bm{u}\bm{G}^{\otimes n}$. The generator matrix is constructed by the $n$-th Kronecker power of the matrix $\bm{G}=\left[\begin{smallmatrix}1&0\\1&1\end{smallmatrix}\right]$.

The input vector $\bm{u}$ is divided into two sets: the set of $K$ information bits $\mathcal{I}$, and the set of $N-K$ frozen bits $\mathcal{F}$ whose values are known to the receiver. Without loss of generality, in this paper, all frozen bits are set to zero [1]. Furthermore, the codeword $\bm{x}$ is modulated with binary phase-shift keying (BPSK) modulation that maps $\left\{0,1\right\}$ to $\left\{+1,-1\right\}$. The modulated signal is then transmitted through an additive white Gaussian noise (AWGN) channel. The received signal is transformed into log-likelihood ratio (LLR) values $\bm{y} = \{y_0,y_1,\ldots,y_{N-1}\}$ that is then processed for decoding.

[very thin,gray,dashed] (1,.5) – (1,-7.5);
[very thin,gray,dashed] (3,.5) – (3,-7.5);
[very thin,gray,dashed] (5,.5) – (5,-7.5);
[very thin,gray,dashed] (7,.5) – (7,-7.5);

at (.5,0) $0$;
at (.5,-1) $0$;
at (.5,-2) $0$;
at (.5,-3) $u_3$;
at (.5,-4) $0$;
at (.5,-5) $u_5$;
at (.5,-6) $u_6$;
at (.5,-7) $u_7$;

(1,0) – (7,0);
(1,-1) – (7,-1);
(1,-2) – (7,-2);
(1,-3) – (7,-3);
(1,-4) – (7,-4);
(1,-5) – (7,-5);
(1,-6) – (7,-6);
(1,-7) – (7,-7);

(2,0) circle [radius=.25];
(2,-2) circle [radius=.25];
(2,-4) circle [radius=.25];
(2,-6) circle [radius=.25];

(2,-1) – ++(0,1.25);
(2,-3) – ++(0,1.25);
(2,-5) – ++(0,1.25);
(2,-7) – ++(0,1.25);

(4.5,0) circle [radius=.25];
(3.5,-1) circle [radius=.25];
(4.5,-4) circle [radius=.25];
(3.5,-5) circle [radius=.25];

(4.5,-2) – ++(0,2.25);
(3.5,-3) – ++(0,2.25);
(4.5,-6) – ++(0,2.25);
(3.5,-7) – ++(0,2.25);

(6.6,0) circle [radius=.25];
(6.2,-1) circle [radius=.25];
(5.8,-2) circle [radius=.25];
(5.4,-3) circle [radius=.25];

(6.6,-4) – ++(0,4.25);
(6.2,-5) – ++(0,4.25);
(5.8,-6) – ++(0,4.25);
(5.4,-7) – ++(0,4.25);

at (7.5,0) $x_0$;
at (7.5,-1) $x_1$;
at (7.5,-2) $x_2$;
at (7.5,-3) $x_3$;
at (7.5,-4) $x_4$;
at (7.5,-5) $x_5$;
at (7.5,-6) $x_6$;
at (7.5,-7) $x_7$;

§.§ Successive-Cancellation Decoding

[scale=.6, thick]

[very thin,gray,dashed] (1,.5) – (1,-7.5);
[very thin,gray,dashed] (3,.5) – (3,-7.5);
[very thin,gray,dashed] (5,.5) – (5,-7.5);
[very thin,gray,dashed] (7,.5) – (7,-7.5);

at (.5,0) $0$;
at (.5,-1) $0$;
at (.5,-2) $0$;
at (.5,-3) $u_3$;
at (.5,-4) $0$;
at (.5,-5) $u_5$;
at (.5,-6) $u_6$;
at (.5,-7) $u_7$;

(1,0) – ++(.75,0);
(2.25,0) – ++(.75,0);
(1,-1) – ++(.75,0);
(2.25,-1) – ++(.75,0);

(2,0) circle [radius=.25] node $f$;
(2,-1) circle [radius=.25] node $g$;

(3,-1) – ++(-.75,1);
(3,0) – ++(-.75,-1);

(1.75,-1.5) – ++(.25,0) – ++(0,.25);

(1,-2) – ++(.75,0);
(2.25,-2) – ++(.75,0);
(1,-3) – ++(.75,0);
(2.25,-3) – ++(.75,0);

(2,-2) circle [radius=.25] node $f$;
(2,-3) circle [radius=.25] node $g$;

(3,-3) – ++(-.75,1);
(3,-2) – ++(-.75,-1);

(1.75,-3.5) – ++(.25,0) – ++(0,.25);

(1,-4) – ++(.75,0);
(2.25,-4) – ++(.75,0);
(1,-5) – ++(.75,0);
(2.25,-5) – ++(.75,0);

(2,-4) circle [radius=.25] node $f$;
(2,-5) circle [radius=.25] node $g$;

(3,-5) – ++(-.75,1);
(3,-4) – ++(-.75,-1);

(1.75,-5.5) – ++(.25,0) – ++(0,.25);

(1,-6) – ++(.75,0);
(2.25,-6) – ++(.75,0);
(1,-7) – ++(.75,0);
(2.25,-7) – ++(.75,0);

(2,-6) circle [radius=.25] node $f$;
(2,-7) circle [radius=.25] node $g$;

(3,-7) – ++(-.75,1);
(3,-6) – ++(-.75,-1);

(1.75,-7.5) – ++(.25,0) – ++(0,.25);

(3,0) – ++(.75,0);
(4.25,0) – ++(.75,0);
(3,-2) – ++(.75,0);
(4.25,-2) – ++(.75,0);

(4,0) circle [radius=.25] node $f$;
(4,-2) circle [radius=.25] node $g$;

(5,-2) – ++(-.75,2);
(5,0) – ++(-.75,-2);

(3.75,-2.5) – ++(.25,0) – ++(0,.25);

(3,-1) – ++(.75,0);
(4.25,-1) – ++(.75,0);
(3,-3) – ++(.75,0);
(4.25,-3) – ++(.75,0);

(4,-1) circle [radius=.25] node $f$;
(4,-3) circle [radius=.25] node $g$;

(5,-3) – ++(-.75,2);
(5,-1) – ++(-.75,-2);

(3.75,-3.5) – ++(.25,0) – ++(0,.25);

(3,-4) – ++(.75,0);
(4.25,-4) – ++(.75,0);
(3,-6) – ++(.75,0);
(4.25,-6) – ++(.75,0);

(4,-4) circle [radius=.25] node $f$;
(4,-6) circle [radius=.25] node $g$;

(5,-6) – ++(-.75,2);
(5,-4) – ++(-.75,-2);

(3.75,-6.5) – ++(.25,0) – ++(0,.25);

(3,-5) – ++(.75,0);
(4.25,-5) – ++(.75,0);
(3,-7) – ++(.75,0);
(4.25,-7) – ++(.75,0);

(4,-5) circle [radius=.25] node $f$;
(4,-7) circle [radius=.25] node $g$;

(5,-7) – ++(-.75,2);
(5,-5) – ++(-.75,-2);

(3.75,-7.5) – ++(.25,0) – ++(0,.25);

(5,0) – ++(.75,0);
(6.25,0) – ++(.75,0);
(5,-4) – ++(.75,0);
(6.25,-4) – ++(.75,0);

(6,0) circle [radius=.25] node $f$;
(6,-4) circle [radius=.25] node $g$;

(7,-4) – ++(-.75,4);
(7,0) – ++(-.75,-4);

(5.75,-4.5) – ++(.25,0) – ++(0,.25);

(5,-1) – ++(.75,0);
(6.25,-1) – ++(.75,0);
(5,-5) – ++(.75,0);
(6.25,-5) – ++(.75,0);

(6,-1) circle [radius=.25] node $f$;
(6,-5) circle [radius=.25] node $g$;

(7,-5) – ++(-.75,4);
(7,-1) – ++(-.75,-4);

(5.75,-5.5) – ++(.25,0) – ++(0,.25);

(5,-2) – ++(.75,0);
(6.25,-2) – ++(.75,0);
(5,-6) – ++(.75,0);
(6.25,-6) – ++(.75,0);

(6,-2) circle [radius=.25] node $f$;
(6,-6) circle [radius=.25] node $g$;

(7,-6) – ++(-.75,4);
(7,-2) – ++(-.75,-4);

(5.75,-6.5) – ++(.25,0) – ++(0,.25);

(5,-3) – ++(.75,0);
(6.25,-3) – ++(.75,0);
(5,-7) – ++(.75,0);
(6.25,-7) – ++(.75,0);

(6,-3) circle [radius=.25] node $f$;
(6,-7) circle [radius=.25] node $g$;

(7,-7) – ++(-.75,4);
(7,-3) – ++(-.75,-4);

(5.75,-7.5) – ++(.25,0) – ++(0,.25);

at (7.5,0) $y_0$;
at (7.5,-1) $y_1$;
at (7.5,-2) $y_2$;
at (7.5,-3) $y_3$;
at (7.5,-4) $y_4$;
at (7.5,-5) $y_5$;
at (7.5,-6) $y_6$;
at (7.5,-7) $y_7$;

[scale=.93, thick]

[very thin,gray,dashed] (1,.5) – (1,-1.5);
[very thin,gray,dashed] (3,.5) – (3,-1.5);

at (.5,0) $u_0,l_0$;
at (.5,-1) $u_1,l_1$;

(1,0) – (1.75,0);
(2.25,0) – (3,0);
(1,-1) – (1.75,-1);
(2.25,-1) – (3,-1);

(2,0) circle [radius=.25] node $f$;
(2,-1) circle [radius=.25] node $g$;

(3,-1) – (2.25,0);
(3,0) – (2.25,-1);

(1.75,-1.5) – ++(.25,0) – ++(0,.25);

at (1.5,-1.5) $\hat{u}_0$;

at (3.5,0) $x_0,y_0$;
at (3.5,-1) $x_1,y_1$;

SC decoding on the factor graph of $\mathcal{P}(8,4)$ with $\mathcal{I} = \{u_3,u_5,u_6,u_7\}$ and $\mathcal{F} = \{u_0,u_1,u_2,u_4\}$ (left), and the building block of the SC decoder (right).

SC decoding can be represented on a factor graph as illustrated in Fig. <ref> for $\mathcal{P}(8,4)$ with $\mathcal{I} = \{u_3,u_5,u_6,u_7\}$ and $\mathcal{F} = \{u_0,u_1,u_2,u_4\}$. The factor graph has $n+1$ levels and each decoding step consists of traversing the factor graph by performing $f$ and $g$ functions on the building block of the SC decoder (see Fig. <ref>) as

\begin{align}
l_0 = f(y_0,y_1) &= 2 \atanh\left(\tanh\left(\frac{y_0}{2}\right)\tanh\left(\frac{y_1}{2}\right)\right) \\
&\approx \sgn(y_0y_1)\min(|y_0|,|y_1|) \text{,} \label{eq:fFunction} \\
\hat{u}_0 &= 0 \text{ if } l_0>0 \text{ or } u_0\in\mathcal{F} \text{ else } 1 \text{,} \label{eq:fu0} \\
l_1 = g(y_0,y_1,\hat{u}_0) &= y_1 + (-1)^{\hat{u}_0}y_0 \text{,} \label{eq:gFunction} \\
\hat{u}_1 &= 0 \text{ if } l_1>0 \text{ or } u_1\in\mathcal{F} \text{ else } 1 \text{.} \label{eq:gu1}
\end{align}

Note that after performing the $f$ function, the bit $u_0$ is estimated as $\hat{u}_0$, which is an input to the $g$ function. Finally, when $u_1$ is estimated as $\hat{u}_1$, the partial sums, $x_0$ and $x_1$, can be calculated as

\begin{align}
x_0 &= \hat{u}_0 \oplus \hat{u}_1 \text{,} \label{eq:x0} \\
x_1 &= \hat{u}_1 \text{.} \label{eq:x1}
\end{align}

SC decoding has strong data dependency in the sense that the decoding of each bit $u_i$ requires the estimation of all the previous bits $\{u_0,u_1,\ldots,u_{i-1}\}$. In a fully-parallel implementation of the SC decoder [1], all the $f$ and $g$ functions that can be performed in parallel are grouped together. Thus, the latency is modeled as the number of times the groups of functions in (<ref>) and (<ref>) are performed to move from one level of the factor graph to another. This is due to the fact that the bit-wise calculations in (<ref>) and (<ref>) are of lower complexity than calculating the LLR values.

SCL decoding [2] improves the error-correction performance of SC decoding by keeping a list of the most likely candidates at each decoding step. Instead of estimating each information bit as either $0$ or $1$ as in (<ref>) and (<ref>), SCL decoding considers both possibilities $0$ and $1$. To avoid an exponential growth in the number of candidates, SCL decoding keeps the $L$ most likely ones based on calculating a path metric. The latency of SCL decoding can be modelled similar to that of SC decoding, with the addition of $K$ time steps to update and sort the path metrics.

§.§ Syndrome-Check Decoding

The LLR values that are calculated based on the received message can be readily converted into estimated bits. A parity-check matrix can be used to check if these estimated bits represent a potential transmitted codeword. The idea is to generate a syndrome by multiplying the estimated bits $\bm{x}$ and the parity-check matrix $\bm{H}$, and check if all the parity constraints are satisfied. In case of a mismatch, the estimated bits $\bm{x}$ are refined as $\bm{x} = \bm{x}\oplus\bm{e}$ using an error vector $\bm{e}$ and checked again against any parity violations. This process can be performed until $\bm{x}$ passes the syndrome check or a predefined maximum number of syndrome-check attempts is reached. Note that the parity-check matrix of polar codes is formed by selecting the columns of $\bm{G}^{\otimes n}$ that correspond to frozen bits. For $\mathcal{P}(8,4)$ with $\mathcal{I} = \{u_3,u_5,u_6,u_7\}$ and $\mathcal{F} = \{u_0,u_1,u_2,u_4\}$, $\bm{G}^{\otimes 3}$ and $\bm{H}$ are

\begin{equation*}
\bm{G}^{\otimes 3} = \left[
\begin{smallmatrix}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
1 & 1 & 0 & 0 & 1 & 1 & 0 & 0\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
\end{smallmatrix}
\right] \text{, }
\bm{H} = \left[
\begin{smallmatrix}
1 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 \\
1 & 1 & 1 & 0 \\
1 & 0 & 0 & 1 \\
1 & 1 & 0 & 1 \\
1 & 0 & 1 & 1 \\
1 & 1 & 1 & 1 \\
\end{smallmatrix}
\right] \text{.}
\end{equation*}

Chase decoding [30] and guessing random additive noise decoding [31] are examples that incorporate syndrome-check decoding.

§ SUCCESSIVE SYNDROME-CHECK DECODING OF POLAR CODES

In this section, SC decoding is reformulated to allow for performing successive syndrome checks. This results in an early-termination scheme for SC decoding that reduces the decoding latency, especially when the transmission channel experiences low levels of noise.

§.§ Successive Syndrome-Check Decoding

[scale=1.2,thick](0,.5) rectangle ++(2,-1) node [pos=.5,align=center] Initialize $\bm{x}$
$x_i \!=\! \begin{cases}0 & \text{if } y_i\geq0 \\1 & \text{if } y_i<0 \end{cases}$;

[->] (1,-.5) – ++(0,-.5);
(0,-1) rectangle ++(2,-.5) node [pos=.5,align=center] $\bm{x}\bm{H} = 0$?;

[->] (2,-1.25) – ++(1,0) node [midway,fill=white] Yes;
(3,-.75) rectangle ++(1.5,-1) node [pos=.5,align=center] Output
$\bm{u} = \bm{x}\bm{G}^{\otimes n}$;

[->] (1,-1.5) – ++(0,-.75) node [midway,fill=white] No;
(0,-2.25) rectangle ++(2,-1) node [pos=.5,align=center] Identify first $u_i\!\in\!\mathcal{F}$
where $u_i \neq 0$;

[->] (1,-3.25) – ++(0,-.5);
(0,-3.75) rectangle ++(2,-.5) node [pos=.5,align=center] Generate $\bm{e}_i$;

[->] (1,-4.25) – ++(0,-.5);
(0,-4.75) rectangle ++(2,-.5) node [pos=.5,align=center] $\bm{x} = \bm{x} \oplus \bm{e}_i$;

[->] (0,-5) – ++(-1,0) – ++(0,3.75) – ++(1,0);

Block diagram of the proposed successive syndrome-check decoder.

Fig. <ref> shows the block diagram of the proposed successive syndrome-check decoder. The decoder starts by making an initial estimate on the received codeword $\bm{x}$ based on the received LLR values as

\begin{equation}
x_i = \begin{cases}0 & \text{if } y_i\geq0 \text{,}
\\1 & \text{if } y_i<0 \text{.} \end{cases} \label{eq:xinit}
\end{equation}

The syndrome of $\bm{x}$ is calculated as $\bm{x}\bm{H}$ and is checked for possible errors. If $\bm{x}\bm{H}=0$, then $\bm{x}$ represents a valid codeword and thus $\bm{u} = \bm{x}\bm{G}^{\otimes n}$ is reported as the decoding result. Otherwise, if $\bm{x}\bm{H}\neq 0$, then there must be an error in the received message. To correct the error, the bit-by-bit decoding schedule of the SC decoder is exploited and the first $u_i \in \mathcal{F}$ is identified whose corresponding value in $\bm{x}\bm{H}$ is not $0$. In fact, starting from $u_0$ and up to the first $u_i \in \mathcal{F}$ where $u_i \neq 0$, any frozen bit whose corresponding value in the syndrome is $0$ does not need to be considered for error correction.

After identifying the first $u_i \in \mathcal{F}$ where $u_i \neq 0$, an error vector $\bm{e}_i$ is generated in an attempt to refine the received message $\bm{x}$. To generate $\bm{e}_i$, the LLR value associated with $u_i$ is calculated by moving from the right to the left of the factor-graph of Fig. <ref>, using a reformulation of SC decoding as depicted in Fig. <ref>. In particular, the $g$ function in the SC decoder (<ref>) is replaced with

\begin{equation}
l_1 = g(y_0,y_1,x_0,x_1) = y_1 + (-1)^{x_0\oplus x_1}y_0 \text{,} \label{eq:gFunctionS}
\end{equation}

where we used the fact that $u_0$ is decoded correctly and $\hat{u}_0 = x_0 \oplus x_1$. In other words, $\bm{x}$ includes all the refinements that result from decoding $u_0$. Note that due to the equivalence of soft and hard decoding when there is no error, the LLR of the first frozen bit whose corresponding estimate in the syndrome is $1$ must be negative, which is in violation of its estimate.

[scale=.93, thick]

[very thin,gray,dashed] (1,.5) – (1,-1.5);
[very thin,gray,dashed] (3,.5) – (3,-1.5);

at (.5,0) $u_0,l_0$;
at (.5,-1) $u_1,l_1$;

(1,0) – (1.75,0);
(2.25,0) – (3,0);
(1,-1) – (1.75,-1);
(2.25,-1) – (3,-1);

(2,0) circle [radius=.25] node $f$;
(2,-1) circle [radius=.25] node $g$;

(3,-1) – (2.25,0);
(3,0) – (2.25,-1);

(1.75,-1.5) – ++(.25,0) – ++(0,.25);

at (1.15,-1.5) $x_0 \!\oplus\! x_1$;

at (3.5,0) $x_0,y_0$;
at (3.5,-1) $x_1,y_1$;

The building block of the proposed successive syndrome-check decoder.

Following the calculation of the LLR value, the error vector $\bm{e}_i$ is generated by moving from the left to the right of the factor-graph of Fig. <ref>. When an $f$ function is encountered, the error follows the path corresponding to the input of $f$ function with the minimum absolute LLR value. When a $g$ function is encountered, the error follows both paths connected to the input of the $g$ function. In Fig. <ref>, the generation of $\bm{e}_i$ translates to

\begin{align}
\begin{cases}
m = \displaystyle\argmin_{i\in \{0,1\}} |y_i| \text{,} \\
x_m = 1 \oplus x_m \text{,}
\end{cases} \label{eq:ferror} \\
\begin{cases}
x_0 = 1 \oplus x_0 \text{,} \\
x_1 = 1 \oplus x_1 \text{.}
\end{cases} \label{eq:gerror}
\end{align}

$\bm{e}_i$ is then used to refine the received codeword $\bm{x}$ as

\begin{equation}
\bm{x} = \bm{x}\oplus\bm{e}_i \text{.}
\end{equation}

The received codeword is repeatedly updated until its syndrome becomes $0$.

[scale=.8, thick]

[very thin,gray,dashed] (1,.5) – (1,-7.5);
[very thin,gray,dashed] (3,.5) – (3,-7.5);
[very thin,gray,dashed] (5,.5) – (5,-7.5);
[very thin,gray,dashed] (7,.5) – (7,-7.5);

at (.5,0) $0$;
at (.5,-1) $0$;
at (.5,-2) $0$;
at (.5,-3) $u_3$;
at (.5,-4) $0$;
at (.5,-5) $u_5$;
at (.5,-6) $u_6$;
at (.5,-7) $u_7$;

(1,0) – ++(.75,0);
(2.25,0) – ++(.75,0);
(1,-1) – ++(.75,0);
(2.25,-1) – ++(.75,0);

(2,0) circle [radius=.25] node $f$;
(2,-1) circle [radius=.25] node $g$;

(3,-1) – ++(-.75,1);
(3,0) – ++(-.75,-1);

(1.75,-1.5) – ++(.25,0) – ++(0,.25);

[red,very thick] (1,-2) – ++(.75,0) node [above,midway] -$.85$;
[blue,very thick] (1,-2.1) – ++(.75,0);
[red,very thick] (2.25,-2) – ++(.75,0);
[blue,very thick] (2.25,-2.1) – ++(.75,0);
(1,-3) – ++(.75,0);
(2.25,-3) – ++(.75,0);

[red,very thick] (2,-2) circle [radius=.25] node $f$;
(2,-3) circle [radius=.25] node $g$;

[red,very thick] (3,-3) – ++(-.75,1);
(3,-2) – ++(-.75,-1);

(1.75,-3.5) – ++(.25,0) – ++(0,.25);

(1,-4) – ++(.75,0);
(2.25,-4) – ++(.75,0);
(1,-5) – ++(.75,0);
(2.25,-5) – ++(.75,0);

(2,-4) circle [radius=.25] node $f$;
(2,-5) circle [radius=.25] node $g$;

(3,-5) – ++(-.75,1);
(3,-4) – ++(-.75,-1);

(1.75,-5.5) – ++(.25,0) – ++(0,.25);

(1,-6) – ++(.75,0);
(2.25,-6) – ++(.75,0);
(1,-7) – ++(.75,0);
(2.25,-7) – ++(.75,0);

(2,-6) circle [radius=.25] node $f$;
(2,-7) circle [radius=.25] node $g$;

(3,-7) – ++(-.75,1);
(3,-6) – ++(-.75,-1);

(1.75,-7.5) – ++(.25,0) – ++(0,.25);

(3,0) – ++(.75,0);
(4.25,0) – ++(.75,0);
[red,very thick] (3,-2) – ++(.75,0) node [above,midway] -$.85$;
[blue,very thick] (3,-2.1) – ++(.75,0);
[red,very thick] (4.25,-2) – ++(.75,0);
[blue,very thick] (4.25,-2.1) – ++(.75,0);

(4,0) circle [radius=.25] node $f$;
[red,very thick] (4,-2) circle [radius=.25] node $g$;

(5,-2) – ++(-.75,2);
[red,very thick] (5,0) – ++(-.75,-2);
[blue,very thick] (5.1,-.1) – ++(-.75,-2);

[red,very thick] (3.75,-2.5) – ++(.25,0) – ++(0,.25);
[red] at (3.5,-2.5) $0$;

(3,-1) – ++(.75,0);
(4.25,-1) – ++(.75,0);
[red,very thick] (3,-3) – ++(.75,0) node [midway,fill=white] $1.3$;
[red,very thick] (4.25,-3) – ++(.75,0);

(4,-1) circle [radius=.25] node $f$;
[red,very thick] (4,-3) circle [radius=.25] node $g$;

(5,-3) – ++(-.75,2);
[red,very thick] (5,-1) – ++(-.75,-2);

[red,very thick] (3.75,-3.5) – ++(.25,0) – ++(0,.25);
[red] at (3.5,-3.5) $0$;

(3,-4) – ++(.75,0);
(4.25,-4) – ++(.75,0);
(3,-6) – ++(.75,0);
(4.25,-6) – ++(.75,0);

(4,-4) circle [radius=.25] node $f$;
(4,-6) circle [radius=.25] node $g$;

(5,-6) – ++(-.75,2);
(5,-4) – ++(-.75,-2);

(3.75,-6.5) – ++(.25,0) – ++(0,.25);

(3,-5) – ++(.75,0);
(4.25,-5) – ++(.75,0);
(3,-7) – ++(.75,0);
(4.25,-7) – ++(.75,0);

(4,-5) circle [radius=.25] node $f$;
(4,-7) circle [radius=.25] node $g$;

(5,-7) – ++(-.75,2);
(5,-5) – ++(-.75,-2);

(3.75,-7.5) – ++(.25,0) – ++(0,.25);

[red,very thick] (5,0) – ++(.75,0) node [above,midway] -$.77$;
[blue,very thick] (5.1,-.1) – ++(.65,0);
[red,very thick] (6.25,0) – ++(.75,0);
[blue,very thick] (6.25,-.1) – ++(.75,0);
(5,-4) – ++(.75,0);
(6.25,-4) – ++(.75,0);

[red,very thick] (6,0) circle [radius=.25] node $f$;
(6,-4) circle [radius=.25] node $g$;

[red,very thick] (7,-4) – ++(-.75,4);
(7,0) – ++(-.75,-4);

(5.75,-4.5) – ++(.25,0) – ++(0,.25);

[red,very thick] (5,-1) – ++(.75,0) node [above,midway] $.56$;
[red,very thick] (6.25,-1) – ++(.75,0);
(5,-5) – ++(.75,0);
(6.25,-5) – ++(.75,0);

[red,very thick] (6,-1) circle [radius=.25] node $f$;
(6,-5) circle [radius=.25] node $g$;

[red,very thick] (7,-5) – ++(-.75,4);
(7,-1) – ++(-.75,-4);

(5.75,-5.5) – ++(.25,0) – ++(0,.25);

[red,very thick] (5,-2) – ++(.75,0) node [above,midway] -$.08$;
[blue,very thick] (5,-2.1) – ++(.75,0);
[red,very thick] (6.25,-2) – ++(.75,0);
[blue,very thick] (6.25,-2.1) – ++(.75,0);
(5,-6) – ++(.75,0);
(6.25,-6) – ++(.75,0);

[red,very thick] (6,-2) circle [radius=.25] node $f$;
(6,-6) circle [radius=.25] node $g$;

[red,very thick] (7,-6) – ++(-.75,4);
(7,-2) – ++(-.75,-4);

(5.75,-6.5) – ++(.25,0) – ++(0,.25);

[red,very thick] (5,-3) – ++(.75,0) node [above,midway] $.69$;
[red,very thick] (6.25,-3) – ++(.75,0);
(5,-7) – ++(.75,0);
(6.25,-7) – ++(.75,0);

[red,very thick] (6,-3) circle [radius=.25] node $f$;
(6,-7) circle [radius=.25] node $g$;

[red,very thick] (7,-7) – ++(-.75,4);
(7,-3) – ++(-.75,-4);

(5.75,-7.5) – ++(.25,0) – ++(0,.25);

at (7.75,.5) $\bm{y}$;
at (7.75,0) $0.77$;
at (7.75,-1) $0.56$;
at (7.75,-2) -$0.08$;
at (7.75,-3) -$1.51$;
at (7.75,-4) -$1.44$;
at (7.75,-5) $2.89$;
at (7.75,-6) $2.33$;
at (7.75,-7) -$0.69$;

at (8.75,.5) $\bm{e}_2$;
at (8.75,0) $1$;
at (8.75,-1) $0$;
at (8.75,-2) $1$;
at (8.75,-3) $0$;
at (8.75,-4) $0$;
at (8.75,-5) $0$;
at (8.75,-6) $0$;
at (8.75,-7) $0$;

Example of the proposed successive syndrome-check decoder for $\mathcal{P}(8,4)$ with $\mathcal{I} = \{u_3,u_5,u_6,u_7\}$ and $\mathcal{F} = \{u_0,u_1,u_2,u_4\}$. The LLR values received from the channel represent $\bm{x} = \{0,0,1,1,1,0,0,1\}$ with the syndrome $\bm{x}\bm{H} = \{0,0,1,0\}$. Therefore, the successive syndrome-check decoder starts by calculating the LLR value associated with $u_2$. The corresponding error vector is $\bm{e}_2 = \{1,0,1,0,0,0,0,0\}$ that is used to refine $\bm{x}$ to $\{1,0,0,1,1,0,0,1\}$. Since the syndrome of the refined $\bm{x}$ is $0$, the decoder outputs $\bm{u} = \bm{x}\bm{G}^{\otimes 3} = \{0,0,0,0,0,1,1,1\}$.

Fig. <ref> shows an example of the proposed successive syndrome-check decoder on the factor graph of $\mathcal{P}(8,4)$ with $\mathcal{I} = \{u_3,u_5,u_6,u_7\}$ and $\mathcal{F} = \{u_0,u_1,u_2,u_4\}$. The received values from the channel are turned into the LLR vector $\bm{y} = \{0.77,0.56,-0.08,-1.51,-1.44,2.89,2.33,-0.69\}$. The received codeword is then initialized based on (<ref>) as $\bm{x} = \{0,0,1,1,1,0,0,1\}$. The syndrome of $\bm{x}$ is calculated as $\bm{x}\bm{H} = \{0,0,1,0\}$, which corresponds to $\{u_0,u_1,u_2,u_4\}$. Since $u_0 = u_1 = 0$, these two bits match the frozen bit value and thus, they do not need to undergo the decoding process. However, since $u_2 = 1$, the proposed successive syndrome-check decoder calculates its LLR value by traversing the factor graph from right to left, and stores the intermediate LLRs for error vector generation (see the red lines in Fig. <ref>). Note that the calculated LLR value of $u_2$ is indeed negative. The error vector $\bm{e}_2$ is then generated by traversing the factor graph from left to right (see the blue lines in Fig. <ref>). First, an $f$ function is encountered whose inputs are $-0.85$ and $1.3$. Therefore, the path corresponding to $-0.85$ is selected. Then, there is a $g$ function with inputs $-0.77$ and $-0.08$, and the path is extended on both inputs. Finally, the two paths are extended on the input of the two $f$ functions whose absolute LLR values are smaller. This results in $\bm{e}_2 = \{1,0,1,0,0,0,0,0\}$.

After $\bm{e}_2$ is generated, $\bm{x}$ is refined as

\begin{equation}
\bm{x} = \bm{x} \oplus \bm{e}_2 = \{1,0,0,1,1,0,0,1\} \text{.}
\end{equation}

This refined codeword has the syndrome $\bm{x}\bm{H} = \{0,0,0,0\}$, which passes the syndrome check. Therefore, the proposed decoder terminates the decoding process and outputs $\bm{u} = \bm{x}\bm{G}^{\otimes 3} = \{0,0,0,0,0,1,1,1\}$.

Note that the proposed decoder only needs to generate an error vector for the bits whose LLR values do not match their bit estimation[An LLR value matches a bit estimation if the LLR value is negative and the bit estimation is $1$, or if the LLR value is positive and bit estimation is $0$.]. In SC decoding, each information bit is decoded by making a decision based on the sign of the LLR value. Therefore, in SC decoding, the LLR values of information bits always match their bit estimation. Consequently, the error vector generation is only needed for the violating frozen bits whose LLR values are negative.

§.§ Extension to SCL Decoding

In SCL decoding, each information bit is estimated as both $0$ and $1$. Therefore, if the calculated LLR value of an information bit for each candidate in the list does not match its bit estimation, an error vector needs to be generated. As a result, the proposed successive syndrome-check decoder can be adapted to SCL decoding by generating error vectors not only for the violating frozen bits, but also for information bits. Similar to the case of SC decoding, if the syndrome of $\bm{x}$ is not zero, the first $u_i\in\mathcal{F}$ with $u \neq 0$ is identified. However, if there are information bits before that frozen bit, error vectors are generated for each information bit, $\bm{x}$ is refined for each candidate in the list, and the syndrome is calculated again for all $\bm{x}$. The process is continued until the syndrome of the best path in the list becomes $0$. Note that since there is a list of candidates, the error vector is generated based on the first violating frozen bit throughout the list. This guarantees that the error-correction performance of the proposed decoder is equivalent to that of the SCL decoder.

§ RESULTS

This section presents latency results for the proposed successive syndrome-check decoder in terms of the number of time steps and compares them with the latency of the SC and SCL decoders. Similar to the case of SC and SCL decoding, the latency of the successive syndrome-check decoder is calculated by considering a fully-parallel implementation. Moreover, each level traversal on the factor graph based on (<ref>) and (<ref>) is equivalent to $1$ time step, and the bit-wise operations in (<ref>) and (<ref>) to generate the error vector and the calculation of the syndrome do not incur additional latency.

Fig. <ref> presents the required number of decoding time-steps for the proposed successive syndrome-check decoder that is based on SC decoding for $\mathcal{P}(128,64)$ used in the 5G standard. The results are compared with three fast SC decoders in the literature [6, 7, 9]. Fig. <ref> shows the latency results of the proposed successive syndrome-check decoder based on SCL decoding for $\mathcal{P}(128,64)$ used in the 5G standard. The results are compared with three fast SCL decoders in [15, 16, 17] and for all the decoders, $L=8$. Fig. <ref> plots the number of time-steps required for the proposed decoders and the fast SCL decoders in [15, 16, 17] to decode a Reed-Muller (RM) code of length $128$ and rate $\frac{1}{2}$. The list size is set to $L=32$ to provide a frame error rate (FER) close to the maximum-likelihood decoding performance. It can be seen that in all the considered cases, the proposed method requires a smaller number of decoding time-steps in comparison with all the considered fast SC and SCL decoders at high signal-to-noise ratio (SNR) values. Note that in each considered scenario, the FER performance of the decoders are identical.

grid style=dashed,
width=, height=4.5cm,

legend cell align=left,
legend pos=north east,
legend style=
column sep=0mm,
legend to name=legend-PLatcomp,
legend columns=4,

-3 97.80
-2 97.13
-1 94.68
0 88.88
1 78.09
2 63.81
3 49.87
4 37.13
5 25.98
6 16.52
7 9.74
8 5.07
9 2.15
10 0.68

-3 86
10 86
SC [6]

-3 42
10 42
SC [7]

-3 16
10 16
SC [9]

Required number of decoding time-steps for $\mathcal{P}(128,64)$ used in the 5G standard. The FER at SNR $=4$ dB is $1.6\times 10^{-3}$.

§ SUMMARY AND FUTURE WORK

In this paper, a successive syndrome-check decoder is presented that allows for early termination in SC and SCL decoding of polar codes. The proposed decoder is lossless in the sense that it does not degrade the error-correction performance of the underlying SC or SCL decoder. Moreover, the generation of error vectors in the proposed decoder obviates the need for generating partial sums, which are required in SC and SCL decoding. Simulation results show that at the same FER, the latency of the proposed decoder is smaller than that of the SC and SCL decoders at high SNR values.

Future work includes adapting the proposed successive syndrome-check decoder to the fast SC and SCL decoders. This ensures the worst-case latency of the decoder is the latency of the corresponding fast SC or SCL decoder. Another interesting direction for future work is to use a cyclic redundancy-check (CRC) to enable early-termination in addition to checking the syndrome. This is particularly useful in applications where polar codes are concatenated with a CRC.

grid style=dashed,
width=, height=4.5cm,

legend cell align=left,
legend pos=north east,
legend style=
column sep=0mm,
legend to name=legend-PLatcompSCL,
legend columns=4,

-3 197.00
-2 195.83
-1 192.39
0  182.71
1  164.27
2  140.40
3  113.17
4  82.320
5  52.460
6  28.590
7  14.090
8  6.2700
9  2.2800
10 0.6900

-3 105
10 105
SCL [15]

-3 94
10 94
SCL [16]

-3 43
10 43
SCL [17]

Required number of decoding time-steps for $\mathcal{P}(128,64)$ used in the 5G standard. Note that $L=8$ for the SCL decoders. The FER at SNR $=4$ dB is $1.1\times 10^{-3}$.

grid style=dashed,
width=, height=4.5cm,

legend cell align=left,
legend pos=north east,
legend style=
column sep=0mm,
legend to name=legend-RMLatcomp,
legend columns=4,

-3 244.39
-2 242.99
-1 236.79
0  219.77
1  191.72
2  162.85
3  134.82
4  103.53
5  69.610
6  38.330
7  17.890
8  7.5500
9  2.5100
10 0.7300

-3 112
10 112
SCL [15]

-3 112
10 112
SCL [16]

-3 76
10 76
SCL [17]

Required number of decoding time-steps for a RM code of length $128$ and rate $\frac{1}{2}$. Note that $L=32$ for the SCL decoders. The FER at SNR $=4$ dB is $2.3\times 10^{-5}$.

§ ACKNOWLEDGMENT

This work is supported in part by ONR grant N00014-18-1-2191. S. A. Hashemi was supported by a Postdoctoral Fellowship from the Natural Sciences and Engineering Research Council of Canada (NSERC) and by Huawei. M. Mondelli was partially supported by the 2019 Lopez-Loreta Prize.

[1]
E. Arıkan, “Channel polarization: A method for constructing
capacity-achieving codes for symmetric binary-input memoryless channels,”
IEEE Trans. Inf. Theory, vol. 55, no. 7, pp. 3051–3073, Jul. 2009.

[2]
I. Tal and A. Vardy, “List decoding of polar codes,” IEEE Trans. Inf.
Theory, vol. 61, no. 5, pp. 2213–2226, 2015.

[3]
B. Yuan and K. K. Parhi, “Low-latency successive-cancellation polar
decoder architectures using 2-bit decoding,” IEEE Trans. Circ. Syst.
I: Regul., vol. 61, no. 4, pp. 1241–1254, April. 2014.

[4]
G. Sarkis and W. J. Gross, “Increasing the throughput of polar decoders,”
IEEE Commun. Lett., vol. 17, no. 4, pp. 725–728, Apr. 2013.

[5]
C. Husmann, P. C. Nikolaou, and K. Nikitopoulos, “Reduced latency ML polar
decoding via multiple sphere-decoding tree searches,” IEEE Trans. Veh.
Technol., vol. 67, no. 2, pp. 1835–1839, Feb. 2017.

[6]
A. Alamdar-Yazdi and F. R. Kschischang, “A simplified successive-cancellation
decoder for polar codes,” IEEE Commun. Lett., vol. 15, no. 12, pp.
1378–1380, Dec. 2011.

[7]
G. Sarkis, P. Giard, A. Vardy, C. Thibeault, and W. J. Gross, “Fast polar
decoders: Algorithm and implementation,” IEEE J. Sel. Areas Commun.,
vol. 32, no. 5, pp. 946–957, May. 2014.

[8]
P. Giard, G. Sarkis, C. Thibeault, and W. J. Gross, “Multi-mode unrolled
architectures for polar decoders,” IEEE Trans. Circ. Syst. I: Regul.,
vol. 63, no. 9, pp. 1443–1453, Sep. 2016.

[9]
M. Hanif and M. Ardakani, “Fast successive-cancellation decoding of polar
codes: identification and decoding of new nodes,” IEEE Commun. Lett.,
vol. 21, no. 11, pp. 2360–2363, Nov. 2017.

[10]
C. Condo, V. Bioglio, and I. Land, “Generalized fast decoding of polar
codes,” in IEEE Global Commun. Conf., Dec. 2018, pp. 1–6.

[11]
H. Gamage, V. Ranasinghe, N. Rajatheva, and M. Latva-aho, “Low latency decoder
for short blocklength polar codes,” in European Conf. Netw. Commun.,
2020, pp. 305–310.

[12]
F. Ercan, C. Condo, and W. J. Gross, “Reduced-memory high-throughput
Fast-SSC polar code decoder architecture,” in IEEE Int. Workshop
Signal Process. Syst., Oct. 2017, pp. 1–6.

[13]
F. Ercan, T. Tonnellier, C. Condo, and W. J. Gross, “Operation merging for
hardware implementations of fast polar decoders,” J. Signal Process.
Syst., vol. 91, no. 9, pp. 995–1007, Sep. 2019.

[14]
G. Sarkis, P. Giard, A. Vardy, C. Thibeault, and W. J. Gross, “Fast list
decoders for polar codes,” IEEE J. Sel. Areas Commun., vol. 34,
no. 2, pp. 318–328, Feb. 2016.

[15]
S. A. Hashemi, C. Condo, and W. J. Gross, “A fast polar code list decoder
architecture based on sphere decoding,” IEEE Trans. Circ. Syst. I:
Regul., vol. 63, no. 12, pp. 2368–2380, Dec. 2016.

[16]
S. A. Hashemi, C. Condo, and W. J. Gross, “Fast and flexible
successive-cancellation list decoders for polar codes,” IEEE Trans.
Signal Process., vol. 65, no. 21, pp. 5756–5769, 2017.

[17]
M. Hanif, M. H. Ardakani, and M. Ardakani, “Fast list decoding of polar codes:
Decoders for additional nodes,” in IEEE Wireless Commun. Netw. Conf.
Workshops.1em plus 0.5em minus 0.4emIEEE, 2018, pp. 37–42.

[18]
M. Mondelli, S. A. Hashemi, J. M. Cioffi, and A. Goldsmith, “Sublinear latency
for simplified successive cancellation decoding of polar codes,” IEEE
Trans. Wireless Commun., vol. 20, no. 1, pp. 18–27, 2021.

[19]
S. A. Hashemi, M. Mondelli, A. Fazeli, A. Vardy, J. Cioffi, and A. Goldsmith,
“Parallelism versus latency in simplified successive-cancellation decoding
of polar codes,” IEEE Trans. Wireless Commun., pp. 1–1, 2021.

[20]
H. Yoo and I. Park, “Efficient pruning for successive-cancellation
decoding of polar codes,” IEEE Commun. Lett., vol. 20, no. 12, pp.
2362–2365, Dec. 2016.

[21]
J. Choi and I. Park, “Improved successive-cancellation decoding of polar
codes based on recursive syndrome decomposition,” IEEE Commun. Lett.,
vol. 21, no. 11, pp. 2344–2347, Nov. 2017.

[22]
D. Kim and I.-C. Park, “A fast successive cancellation list decoder for polar
codes with an early stopping criterion,” IEEE Trans. Signal Process.,
vol. 66, no. 18, pp. 4971–4979, 2018.

[23]
Z. Huang, C. Diao, and M. Chen, “Latency reduced method for modified
successive cancellation decoding of polar codes,” Electron. Lett.,
vol. 48, no. 23, pp. 1505–1506, Nov. 2012.

[24]
A. Balatsoukas-Stimming, G. Karakonstantis, and A. Burg, “Enabling
complexity-performance trade-offs for successive cancellation decoding of
polar codes,” in IEEE Int. Symp. Inf. Theory, Jun. 2014, pp.

[25]
L. Zhang, Z. Zhang, X. Wang, C. Zhong, and L. Ping, “Simplified
successive-cancellation decoding using information set reselection for polar
codes with arbitrary blocklength,” IET Commun., vol. 9, no. 11, pp.
1380–1387, Jul. 2015.

[26]
P. Giard, G. Sarkis, C. Thibeault, and W. J. Gross, “A 638 Mbps
low-complexity rate 1/2 polar decoder on FPGAs,” in IEEE Int.
Workshop on Sig. Proc. Systems, Oct. 2015, pp. 1–6.

[27]
P. Giard, A. Balatsoukas-Stimming, G. Sarkis, C. Thibeault, and W. J. Gross,
“Fast low-complexity decoders for low-rate polar codes,” J. Signal
Process. Syst., vol. 90, no. 5, pp. 675–685, May. 2018.

[28]
S. Li, Y. Deng, L. Lu, J. Liu, and T. Huang, “A low-latency simplified
successive cancellation decoder for polar codes based on node error
probability,” IEEE Commun. Lett., vol. 22, no. 12, pp. 2439–2442,
Dec. 2018.

[29]
H. Zheng, S. A. Hashemi, Z. Cao, A. M. J. Koonen, J. Cioffi, and
A. Goldsmith, “Threshold-based successive-cancellation decoding of polar
codes,” in IEEE Int. Conf. on Commun., Jun. 2020, pp. 1–6.

[30]
D. Chase, “Class of algorithms for decoding block codes with channel
measurement information,” IEEE Trans. Inf. Theory, vol. 18, no. 1,
pp. 170–182, 1972.

[31]
K. R. Duffy, J. Li, and M. Médard, “Capacity-achieving guessing random
additive noise decoding,” IEEE Trans. Inf. Theory, vol. 65, no. 7,
pp. 4023–4040, 2019.


# DIETERpy: a Python framework for The Dispatch and Investment Evaluation Tool
with Endogenous Renewables

Carlos Gaete-Morales111Corresponding author<EMAIL_ADDRESS>Martin Kittel
<EMAIL_ADDRESS>Alexander Roth<EMAIL_ADDRESS>Wolf-Peter Schill<EMAIL_ADDRESS>All authors are at the German Institute for Economic Research (DIW Berlin),
Mohrenstr. 58, D-10117 Berlin, Germany

###### Abstract

DIETER is an open-source power sector model designed to analyze future
settings with very high shares of variable renewable energy sources. It
minimizes overall system costs, including fixed and variable costs of various
generation, flexibility and sector coupling options. Here we introduce
DIETERpy that builds on the existing model version, written in the General
Algebraic Modeling System (GAMS), and enhances it with a Python framework.
This combines the flexibility of Python regarding pre- and post-processing of
data with a straightforward algebraic formulation in GAMS and the use of
efficient solvers. DIETERpy also offers a browser-based graphical user
interface. The new framework is designed to be easily accessible as it enables
users to run the model, alter its configuration, and define numerous scenarios
without a deeper knowledge of GAMS. Code, data, and manuals are available in
public repositories under permissive licenses for transparency and
reproducibility.

###### keywords:

Power sector modeling , Open-source modeling , GAMS , Python , Energy storage
, Flexibility options , Sector coupling , Renewable energy integration

††journal: SoftwareX

2.5cm2.5cm1.5cm2cm

## Code metadata

Current code version | v0.3.0
---|---
Permanent link to code/repository used for this code version | https://gitlab.com/diw-evu/dieter_public/dieterpy
Legal Code License | MIT
Code versioning system used | git
Software code languages, tools, and services used | Python, GAMS
Compilation requirements, operating environments & dependencies | Python 3.6, GAMS +24.8
Link to developer documentation/manual | https://diw-evu.gitlab.io/dieter_public/dieterpy
Support email for questions | Carlos Gaete<EMAIL_ADDRESS>

## Software metadata

Current software version | v0.3.0
---|---
Permanent link to executables of this version | https://pypi.org/project/dieterpy/0.3.0/
Legal Code License | MIT
Computing platform/Operating Systems | Linux, Microsoft Windows
Installation requirements | Python 3.6, GAMS +24.8, conda
Link to developer documentation/manual | https://diw-evu.gitlab.io/dieter_public/dieterpy
Support email for questions | Carlos Gaete<EMAIL_ADDRESS>

##  1 Motivation and Significance

Mitigating climate change calls for a decarbonization of economies around the
world. Power sectors are among the most $\mathrm{CO_{2}}$-intensive sectors,
and renewable energy sources play a major role in decarbonizing them [2]. Wind
and solar energy is abundant, but come with specific characteristics, such as
high fixed and low variable costs, and temporally variable production
patterns. Their cost-efficient large-scale integration into energy systems
calls for numerical analyses. As to how they can replace fossil fuels and
become the backbone of future energy systems particularly raises questions on
the role of temporal flexibility options and sector coupling.

DIETER is a power sector model developed to address such questions of temporal
flexibility options and sector coupling in future scenarios with high shares
of variable renewable energy. While the model was first used to investigate
the role of electricity storage, it has subsequently been extended to also
consider various sector coupling options, such as battery-electric vehicles
(BEV), power-to-heat, green hydrogen, as well as solar prosumage.

Here we introduce a new major development of the model, DIETERpy. Its core
model code builds on previous versions of DIETER, written in the General
Algebraic Modeling System (GAMS), to which we refer as DIETERgms from now on.
DIETER has been first introduced to the literature in the context of analyzing
long-term electricity storage needs for variable renewable energy sources [3,
4]. The functionalities added and enhanced by DIETERpy provide new tools for
simpler and more comprehensive scenario runs, facilitate a more convenient
configuration of the model, and enhance accessibility for users. In DIETERpy,
the original algebraic GAMS model is embedded in a Python framework, or
wrapper, that is responsible for the (1) configuration of the model, (2)
definition of the scenarios to be investigated, and (3) pre- and post-
processing of the data.

Python, as an interpreted language, has been used as a wrapper for many highly
efficient programs in their respective fields, such as C/C++, Fortran, or
GAMS. In the literature there are several examples of applications in energy
and climate change, for instance, the Python interface for the Dutch
Atmospheric Large Eddy Simulation, or the Python Wrapper for System Advisor
Model SAM [5, 6]. Other examples for GAMS models with Python wrappers in the
energy modeling space include IIASA’s MESSAGEix modeling framework and the
dispatch model Dispa-SET [7, 8]. To our knowledge, DIETERpy is the first
capacity expansion power sector model that uses the GAMS API for Python. We
also go one step further than previous approaches of Python model wrappers by
developing a tool that enables the creation of scenarios by modifying
parameter values, variable bounds and (de-)activation of constraints without
the need for altering the original model code. DIETERpy also allows running
model instances in parallel by using several processor cores and the
implementation of the GUSS tool, an advanced GAMS feature that reduces the
compilation times of similar scenarios through model instances. Not least,
embedding our legacy model DIETER in a Python framework substantially enhances
the functionalities of the previous pure GAMS-based version, which may be
useful for many current and future users of the model.

DIETERpy can easily be installed via Python package managers, and no extensive
knowledge of GAMS is needed for initial runs. The model can be configured
either by a browser-based graphical user interface or by CSV files. For
standard scenario runs, the GAMS-based core model code does not have to be
altered by the user, but only for more fundamental model changes. DIETERpy has
a data post-processing routine that collects the results of multiple model
runs and makes them accessible for further analysis in different output
formats, allowing users to proceed with their tools of choice. Basic model
results can also be visualized within the browser interface.

##  2 Software Description

DIETER is a power sector capacity expansion model based on linear equations.
It minimizes total system costs in a long-run equilibrium setting under
perfect foresight. In economic terms, it takes a social planner perspective.
Its objective function is the sum of investment costs into various generation
and flexibility technologies as well as transmission, and related variable
costs for a given time period (usually a full year). DIETER aims to minimize
these costs, given exogenous techno-economic input parameters and time series
such as demand and renewable availability which are provided in an hourly
resolution. Hence, the solution is an optimal portfolio of generation and
flexibility technologies such as electricity storage, as well as their optimal
dispatch for the given time period. The model is solved for all consecutive
hours of a target year.

A range of equations implements constraints with respect to generation
capacities, renewable shares, $\mathrm{CO_{2}}$ emissions, renewable
availability, and balancing reserves. Further, there are inter-temporal
restrictions related to various types of storage and sector coupling. The
model does not include a detailed representation of the underlying
transmission grid infrastructure. Within regions, e.g., European countries, it
makes a copper-plate assumption; between regions, DIETER uses a simple
transport model approach with Net Transfer Capacities (NTCs). Different
versions of DIETER have been developed and applied in several research
projects, which has led to a growing number of publications in relevant field
journals and several ongoing working papers (see Section 4).

From the beginning, DIETER was designed as a lean, tractable and flexible
open-source tool. The model applications that were published so far hardly
required high-performance computing resources, but could largely be solved on
a standard computer. The new DIETERpy framework aims to further increase the
model’s accessibility and usefulness also for casual users and practitioners.

DIETERpy includes some basic data in its installation, which the user may have
to adjust, depending on the types of scenario analyses to be investigated. We
provide a range of techno-economic input parameters for the available
technology portfolio. This includes time-invariant costs parameters related to
investment in various generation and flexibility technologies as well as
cross-border transfer capacities, fuel costs, flexibility costs, and variable
costs of different technologies, as well as technology-specific efficiencies,
technical life-times, and upper/lower capacity expansion bounds. Further, we
include geographical characteristics, as well as time series of renewable
availability and demand for electricity and heat. All of the data is freely
available and sources are listed within the respective spreadsheets.

###  2.1 Software Architecture

DIETERpy is a software package written in the programming languages Python and
GAMS. It can be installed via the Python package manager pip. Running the
model requires a license for the GAMS Base Module and an LP solver (we use
CPLEX).222The GAMS Software GmbH told us that potential users who want to
explore DIETERpy can ask for a test license<EMAIL_ADDRESS>The left panel of
Figure 1 provides an overview of the software architecture of DIETERpy. Data
pre- and post-processing as well as the management of different scenario runs
are carried out with Python, only the optimization itself is done within a
GAMS module that is initiated via Python. The user can choose between
different data output formats to further analyze the results.

Figure 1: Graphical overview of DIETERpy (source: own illustration).

The right panel of Figure 1 summarizes the two steps required before running
optimization with DIETERpy. The first step consists of selecting modules. The
basic module contains all variables and constraints for a default power sector
dispatch and investment model. Additional model features, such as demand-side
management (dsm), battery-electric vehicles (features ev_endogenous and
ev_exogenous), balancing reserves (reserves), solar prosumage (prosumage) and
power-to-heat (heat), can be enabled. In a second step, multiple scenario runs
can be specified. Within a scenario run, it is possible to modify parameters,
time series and variable bounds, and select different constraints and sets of
countries. Parameters and variables have to be indicated with their domain
unless it is a scalar or a dimensionless variable. The domain must contain set
names or set elements. Unidimensional and multidimensional parameters and
variables are supported. For variables, we can establish upper and lower
bounds, as well as fixed values.

###  2.2 Software Functionalities

In DIETERpy, the user can select modules and other settings using an easy-to-
access browser-based graphical user interface, or editing the corresponding
configuration CSV files. In order to get access to the configuration files, a
project has to be created. This can be done by calling the create_project
function after typing dieterpy in the command line. This will result in a new
folder that entails all configuration files and input data. Figure 2 shows the
folders and the file tree of a project.

Out-of-the box, we allow the user to alter:

  1. 1.

basic program settings (project_variables.csv),

  2. 2.

modules (features_node_selection.csv), and

  3. 3.

the scenario table (iteration_table.csv).

Basic program settings include, for instance, the definition of input files,
and the output file formats; here, the user can choose between CSV, Pickle,
and VAEX. As DIETERpy can solve scenarios in parallel, we also allow to adapt
specific settings concerning parallelization. In the “basic program settings”,
the user may further switch between an “investment & dispatch model” and a
“dispatch only model”. Cross-border electricity flows can also be easily
switched on and off (see Table 1).

Table 1: Example of the project_variables.csv file (source: own illustration). Variable | Value
---|---
scenarios_iteration | yes
skip_input | no
skip_iteration_data_file | no
base_year | 2030
end_hour | h8760
dispatch_only | no
network_transfer | yes
no_crossover | yes
infeasibility | no
GUSS | yes
GUSS_parallel | yes
GUSS_parallel_threads | 0
data_input_file | static_input.xlsx
time_series_file | timeseries_input.xlsx
iteration_data_file | iteration_data.xlsx
gdx_convert_parallel_threads | 0
gdx_convert_to_csv | no
gdx_convert_to_pickle | yes
gdx_convert_to_vaex | no
report_data | yes

DIETERpy is a generic model which can be adapted to any geographic setting. In
its default version, the calibration is most refined for Germany, yet eleven
other countries (France, Denmark, Belgium, Netherlands, Poland, Czech
Republic, Austria, Switzerland, Spain, Italy, and Portugal) can also be
activated. Adding more countries or applying the model to a different
geographic region can be done relatively easily if respective input data on
electricity demand as well as meaningful bounds for generation and transfer
capacity are available. Different modules can be switched on for different
countries, depending on the research question and model size restrictions, as
shown in Table 2.333By the time of writing, input data is still missing for
several country-module combinations. Further, a green hydrogen module is also
available [9], but only in the pure GAMS version (DIETERgms).

DIETERpy further provides an easy way to change single parameter values or
define and control entire scenario runs. The program has an easy-to-modify
scenario table (iteration_table.csv) that allows the user to edit (a) the set
of countries, (b) specific constraints specifications, (c) entire time series
(such as demand or renewable capacity factors), (d) single parameter values
and (e) variable bounds (either fixing it or providing upper or lower bounds).
The scenario table is an easy-to-use, transparent tool for quickly running the
model multiple times in different specifications, where every row in that
table refers to one scenario (see Table 3). The parametrization is established
by adding column headings to the table that are dedicated to special features.
To modify input parameters, we add a column heading that matches the parameter
name in the model.gms file. For variables, we can set fixed values as well as
upper and lower bounds.

Once the configuration files have been edited and adapted for a desired case
study, the optimization is ready to start. The excel files that contain the
input data and the configuration CSV files are loaded, and then a Python
routine creates the optimization- and GAMS-compatible GDX files. Via the
Python-API, the model (model.gms) as well as scenario table is passed to GAMS.

For solving, DIETERpy uses the Python-API of GAMS to build a model instance.
This model instance exists until a solver in GAMS returns the solutions. We
have developed three options to run optimization problems with DIETERpy. One
option consists of running the scenarios with independent model instances that
compile every time they are built. With this method, the scenarios are solved
sequentially. This may lead to long execution times when several scenarios are
solved due to the compilation time incurred for each model instance. This
problem is solved in part with the second option, the Gather-Update-Solve-
Scatter (GUSS) tool in GAMS. It allows running several scenarios with only one
model instance by updating the variables, parameters and equation values from
one scenario to another. The third option takes advantage of multiprocessing
in Python. It enables to run the GUSS tool in several processor cores, in
which several scenarios are solved in parallel. This option is the fastest
one; yet for complex problems, it may lead to a high usage of memory.
Therefore, we added an option to choose the number of cores that should be
used in the optimization. To provide an indicative idea about the solving
times of DIETERpy, we ran a 4-scenario problem with two countries (Germany &
France) for a full year (8760 hours). All additional modules are deactivated,
thus only investment into power plant capacities, storage and net transfer
capacities are possible. Between the four scenarios, we only vary the share of
renewable energy in both countries (50%-60%-70%-80% in Germany and
40%-50%-60%-70% in France). We used a computer that runs Windows 10, has an
Intel i5-3320M (2 cores, 4 threads), and 6 GB of RAM. The pure solving times
(without any pre- and post-processing of the data) are as follows: sequential
solving (no GUSS) 15.0 min, GUSS (sequential) 9.6 min, GUSS (parallel, 4
threads) 8.4 min 444Practitioners can reproduce this example following the
instruction in the documentation for example2..

for tree= font=, grow’=0, child anchor=west, parent anchor=south, anchor=west,
calign=first, inner ysep=0pt, inner xsep=8pt, edge path= [draw, edge]
(!u.south west) +(7.5pt,0) —- (.child anchor) pic folder edge label; ,
file/.style=edge path=[draw, edge] (!u.south west) +(7.5pt,0) —- (.child
anchor) edge label;, inner xsep=2pt,font=, before typesetting nodes= if n=1
insert before=[,phantom] , fit=band, before computing xy=l=15pt,  [[Project
name [manage.py,file] [projectfiles [data_input [static_input.xlsx,file]
[timeseries_input.xlsx,file] ] [iterationfiles [iteration_table.csv,file]
[iteration_data.xlsx,file] ] [model [model.gms,file] ] [settings
[constraints_list.csv,file] [features_node_selection.csv,file]
[reporting_symbols.csv,file] [project_variables.csv,file] ] ] ]]

Figure 2: Folders and files tree of a project (source: own illustration).

GAMS provides the solutions of individual scenario runs in GDX files, which
contain all resulting symbols (parameters, variables, equations and sets).
When numerous scenario runs have been solved, collecting and combining all
symbols can be computationally intensive. Thus, we have designed three
solutions: i) the user can select the symbols to be extracted from the GDX
files by editing the corresponding file reporting_symbols.csv; ii) the number
of cores can be selected to extract the symbols in parallel; iii) in case many
scenarios and symbols are needed, the VAEX library consists of streaming
algorithms, memory-mapped files and a zero memory copy policy to explore
datasets larger than memory [10]. It is advantageous when dealing with
resulting multidimensional variables, and processing such variables for
several scenarios increases the risk of running out of memory. Hence, VAEX
reduces the amount of memory needed, although it increases physical storage
usage (about 10 times the GDX file size). The selected symbols of each
scenario run are extracted and saved as separate CSV files or in an individual
file per scenario run in case of Pickle and VAEX. As DIETERpy uses Pickle
files to proceed with reporting and visualization, it is the recommended
format.

DIETERpy has been endowed with Python objects that allow the user to make
operations between symbols such as addition, subtraction, multiplication and
division, while taking care of symbols’ dimensions: the SymbolsHandler and
Symbol classes help the users to analyze the results more efficiently.

Finally, DIETERpy provides a browser-based graphical user interface to
interactively visualize the results.555By the time of writing, this interface
is under ongoing development and improvement. Figure 3 shows two exemplary
screenshots. Additional information on how to use the GUI is provided in the
online model documentation.

Figure 3: The graphical user interface. The left panel shows a selection of
possible project settings, the right panel model outcomes (source: own
illustration).

##  3 Illustrative Example

In this section, we provide an exemplary application of DIETERpy, varying the
costs of stationary Li-ion battery storage in a mid-term future central
European setting. In doing so, we highlight some novel Python features
introduced by DIETERpy compared to the previous GAMS-only version DIETERgms.
The example can be reproduced after installing DIETERpy and creating a project
folder by typing in the terminal dieterpy create_project -n $<$project name$>$
-t example1, where -t stands for template.

We adapt project_variables.csv to change some basic options (see Table 1). For
example, we activate the scenario iteration feature (scenario_iteration set to
yes); we decide to run a full “investment and dispatch model” (set
dispatch_only is no) with activated electricity exchange between the nodes
(network_transfer set to yes); and we use the maximum number of processor
cores for the optimization via the GUSS tool with parallel processes (GUSS is
yes, GUSS_parallel is yes and GUSS_parallel_threads is 0).

To (de-)activate certain model-related modules, we edit the file
features_node_selection.csv (Table 2). In our example, we deactivate all
additional modules for simplicity by setting all entries to 0. Accordingly,
only the basic module is used.

Table 2: Example of the features_node_selection.csv file. Zeros (0) deactivate features, ones (1) activate them. Here, we deactivated all optional features. dsm refers to demand side management, ev_endogenous and ev_exogenous to endogenous and exogenous optimization of BEV. For additional information, please refer to the online documentation (source: own illustration) | Node
---|---
Module | DE | FR | DK | BE | NL | PL | CZ | AT | CH | ES | IT | PT
dsm | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
ev_endogenous | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
ev_exogenous | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
reserves | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
prosumage | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
heat | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
Table 3: Example of the iteration_table.csv file with different assumptions on the annualized costs of Li-ion storage (source: own illustration). | c_i_sto_e(n,’Li-ion’) | c_i_sto_p(n,’Li-ion’)
---|---|---
run | [EUR/MWh] | [EUR/MW]
S0 | 20029 | 15021
S1 | 10014 | 7511
S2 | 5007 | 3755

We analyze the effects of lower-cost Li-ion storage with three different
scenario runs. Model run S0 represents baseline storage cost assumptions; the
scenario S1 reflects a cost decrease of both energy- and power-related Li-ion
investments of 50%; and scenario S2 assumes a further storage cost reduction
to 25% of S0 values. We specify Table 3 accordingly. DIETERgms defines these
parameters as c_i_sto_e(n,sto) and c_i_sto_p(n,sto) for energy and power
components, respectively. First, as we do not provide the special features
country_set as a column heading, we choose the entire set of n countries to be
included in the runs. Second, the set sto in the model consists of three
elements: “Li-ion” (stationary battery storage), “PHS” (pumped hydro storage,
which is fixed in this example) and “P2G2P” (power-to-gas-to-power). As we
want to vary only the costs of Li-ion batteries, we provide it literally in
the column heading: c_i_sto_e(n,‘Li-ion’) and c_i_sto_p(n,‘Li-ion’).

Figure 4: Installed capacity and total generation of conventional and
renewable generators (left panel) and storage (right panel) for three
exemplary scenarios (source: own illustration).

Here we only present a snapshot of the results of the exemplary application,
using figures generated by our built-in visualization tool. Cheaper batteries
generally increase the use of solar PV, both regarding installed capacity and
yearly electricity generation (left panel of Figure 4). This is because short-
term battery storage is particularly suited to balance daily PV fluctuations.
If the costs of Li-ion batteries decrease as assumed here, they would be
deployed with comparable energy and power capacity as existing European pumped
hydro storage (right panel of Figure 4).

Figure 5 shows an exemplary residual load duration curve (RLDC), combined with
the generation of various technologies in respective hours. The typical role
of different generation technologies can be seen, e.g., base-load use of
lignite and peak-load use of open cycle gas turbines (OCGT). Storage charging
mainly occurs in periods of renewable surplus generation, but partly also in
other periods.

Figure 5: Residual load duration curve, generation of dispatchable
technologies and storage, and transmission flows. This example represents
scenario S2 for Germany (source: own illustration).

##  4 Impact & Conclusion

DIETER has been designed to investigate research questions that are highly
relevant in current energy transition research. This includes, for example,
the exploration of infrastructure requirements for least-cost integration of
variable renewable energy sources in the power sector, and the effects of
flexibility using wind and solar energy also in other sectors. The model’s
prosumage module further allow investigating specific aspects of decentralized
self-supply with PV-battery systems, which is usually not covered by other
energy models.

The new features of the DIETERpy model version presented here will increase
the efficiency of numerical model analyses applied to respective research
questions. Compared to previous model versions, the new Python implementation
allows to more easily specify, run, and evaluate the outcomes of numerous
scenarios, and to make use of a great variety of Python libraries for data
pre- and post-processing and for visualizing results.

Despite the new Python functionalities, DIETERpy in its core remains a
parsimonious model which can be flexibly applied to different parametrizations
and research questions. Most of the applications we published so far could be
solved on standard desktop computers. Only very large-scale applications
covering many regions and multiple sector coupling options may require larger
computational resources. Accordingly, DIETERpy may not only be used by highly
specialized research groups, but also by students and practitioners.

The Python framework presented here further allows model users without deeper
knowledge of programming in either GAMS or Python to run a large range of
model applications. In particular, the browser-based graphical user interface
increases the ease of use and the accessibility of the model. More expert
users are free to adjust and expand any part of DIETERpy as they wish, given
the open-source nature of the model and the permissive MIT license.

Thus, we expect that the DIETERpy version presented here will contribute to
the further usage and application of the model, especially outside the domain
of the current development team. In the past, most publications based on
DIETER were co-authored by DIW Berlin researchers. Two articles introduce the
basic model version and investigate optimal electrical storage capacity in
scenarios with high shares of renewable energy sources [3, 4]. Reduced model
versions are used for more general reflections of the economics of electrical
storage [11] and its changing role in settings with increasing renewable
penetration [12]. Three papers on solar prosumage focus on power sector
effects for Germany [13] and Western Australia [14], and on how tariff design
impacts PV-battery investments [15]. Further model applications analyze the
power sector impacts of electric vehicles [16], flexible electric heating
[17], and green hydrogen [9]. A demand-side management feature we developed
for DIETER was published separately [18]. Recently. we also noticed spin-off
versions of the model that have been developed without any involvement of the
initial DIETER team. These include, for example, generation cost projections
developed for the Australian Energy Market Operator [19], as well as analyses
of demand-side management in India [20] and methodological aspects of modeling
long-term storage [21]. We expect that the DIETERpy improvements described
here will spur more of such activities.

Because of the permissive license, DIETERpy can also be used in commercial
settings. Yet we assume that it is more likely to be used in academic and not-
for-profit research applications. In fact, the model and its applications have
been the backbone of several research grants acquired by us, including such of
different German federal ministries and the European Commission.

To draw a more general conclusion, with DIETERpy we show how to embed an
existing GAMS-based model into a modern Python framework. Now, the model
combines the best of the two programming languages. On the one hand, GAMS is a
well-established language for energy models which is proofed to work. It
offers a straightforward algebraic formulation and the use of efficient
solvers. Maintaining the GAMS core also allows easier linking with other GAMS-
based models. On the other hand, Python offers more flexibility, a wide choice
of additional libraries, and better opportunities for data pre- and post-
processing as well as visualization of results. Using Python also enables an
easy-to-use and flexible scenario tool which would be difficult to implement
in GAMS. This gives the user the opportunity to run the model in many
different scenarios by flexibly altering the model parametrization or its
constraints. We believe that DIETERpy could serve as an example also for other
established energy models to make them future-proof and more accessible to a
wider audience.

Several model improvements and upgrades are currently ongoing or planned. This
concerns both the algebraic GAMS core, where we aim for a more complete and
more consistent coverage of different sector coupling options, and further
advancements of the Python framework. We particularly aim to improve and
extended the user interface and the post-processing and data visualization
functionalities.

##  5 Conflict of Interest

No conflict of interest exists: we confirm that there are no known conflicts
of interest associated with this work.

## Acknowledgments

This work has been supported by research grants of the German Federal Ministry
of Education and Research via the projects “Future of Fossil Fuels in the wake
of greenhouse gas neutrality”, FKZ 01LA1810B, and “Ariadne”, FKZ 03SFK5NO.

## Author Contributions

Carlos Gaete: Conceptualization; Methodology; Software (Python);
Visualization; Writing - original draft, review and editing. Martin Kittel:
Methodology; Software (Python); Writing - review and editing. Alexander Roth:
Methodology; Software (Python); Writing - original draft, review and editing;
Online documentation. Wolf-Peter Schill: Funding acquisition; Methodology;
Software (GAMS); Writing - original draft, review and editing.

## References

  * [1]
  * [2] H. de Coninck, A. Revi, M. Babiker, P. Bertoldi, M. Buckeridge, A. Cartwright, W. Dong, J. Ford, S. Fuss, J.-C. Hourcade, D. Ley, R. Mechler, P. Newman, A. Revokatova, S. Schultz, L. Steg, T. Sugiyama, Strengthening and implementing the global response, Tech. rep., Intergovernmental Panel on Climate Change (2018).
URL
https://www.ipcc.ch/site/assets/uploads/sites/2/2019/02/SR15_Chapter4_Low_Res.pdf

  * [3] A. Zerrahn, W.-P. Schill, Long-run power storage requirements for high shares of renewables: review and a new model, Renewable and Sustainable Energy Reviews 79 (2017) 1518 – 1534.  doi:https://doi.org/10.1016/j.rser.2016.11.098.
  * [4] W.-P. Schill, A. Zerrahn, Long-run power storage requirements for high shares of renewables: Results and sensitivities, Renewable and Sustainable Energy Reviews 83 (2018) 156 – 171.  doi:10.1016/j.rser.2017.05.205.
  * [5] G. van den Oord, F. Jansson, I. Pelupessy, M. Chertova, J. H. Grönqvist, P. Siebesma, D. Crommelin, A python interface to the dutch atmospheric large-eddy simulation, SoftwareX 12 (2020) 100608.  doi:https://doi.org/10.1016/j.softx.2020.100608.
URL https://www.sciencedirect.com/science/article/pii/S2352711020303216

  * [6] P. Gilman, S. Janzou, D. Guittet, J. Freeman, N. DiOrio, N. Blair, M. Boyd, T. Neises, M. Wagner, U. O. of Energy Efficiency, R. Energy, Pysam (python wrapper for system advisor model ”sam”) (8 2019).  doi:10.11578/dc.20190903.1.
URL https://www.osti.gov/biblio/1559931

  * [7] D. Huppmann, M. Gidden, O. Fricko, P. Kolp, C. Orthofer, M. Pimmer, N. Kushin, A. Vinca, A. Mastrucci, K. Riahi, V. Krey, The messageix integrated assessment model and the ix modeling platform (ixmp): An open framework for integrated and cross-cutting analysis of energy, climate, the environment, and sustainable development, Environmental Modelling & Software 112 (2019) 143–156.  doi:https://doi.org/10.1016/j.envsoft.2018.11.012.
URL https://www.sciencedirect.com/science/article/pii/S1364815218302330

  * [8] K. Kavvadias, I. H. Gonzalez, A. Zucker, S. Quoilin, Integrated modelling of future eu power and heat systems - the dispa-set v2.2 open-source model (eur 29085 en), Tech. rep., Luxembourg: European Commission (2018).  doi:10.2760/860626.
  * [9] F. Stoeckl, W.-P. Schill, A. Zerrahn, Green hydrogen: optimal supply chains and power sector benefits (2020).  arXiv:2005.03464.
  * [10] Breddels, Maarten A., Veljanoski, Jovan, Vaex: big data exploration in the era of gaia, A&A 618 (2018) A13.  doi:10.1051/0004-6361/201732493.
URL https://doi.org/10.1051/0004-6361/201732493

  * [11] A. Zerrahn, W.-P. Schill, C. Kemfert, On the economics of electrical storage for variable renewable energy sources, European Economic Review 108 (2018) 259 – 279.  doi:10.1016/j.euroecorev.2018.07.004.
  * [12] W.-P. Schill, Electricity storage and the renewable energy transition, Joule (2020).  doi:10.1016/j.joule.2020.07.022.
  * [13] W.-P. Schill, A. Zerrahn, F. Kunz, Prosumage of solar electricity: pros, cons, and the system perspective, Economics of Energy and Environmental Policy 6 (2017) 7 – 31.  doi:10.5547/2160-5890.6.1.wsch.
  * [14] K. Say, W.-P. Schill, M. John, Degrees of displacement: The impact of household PV battery prosumage on utility generation and energy storage, Applied Energy 276 (2020) 115466.  doi:10.1016/j.apenergy.2020.115466.
  * [15] C. Günther, W.-P. Schill, A. Zerrahn, Prosumage of solar electricity: tariff design, capacity investments, and power system effects, accepted for publication in Energy Policy (2019).  arXiv:1907.09855.
  * [16] W.-P. Schill, M. Niemeyer, A. Zerrahn, J. Diekmann, Bereitstellung von Regelleistung durch Elektrofahrzeuge: Modellrechnungen für Deutschland im Jahr 2035, Zeitschrift für Energiewirtschaft 40 (2016) 73 – 87.  doi:10.1007/s12398-016-0174-7.
  * [17] W.-P. Schill, A. Zerrahn, Flexible electricity use for heating in markets with renewable energy, Applied Energy 266 (2020) 114571.  doi:10.1016/j.apenergy.2020.114571.
  * [18] A. Zerrahn, W.-P. Schill, On the representation of demand-side management in power system models, Energy 84 (2015) 840 – 845.  doi:10.1016/j.energy.2015.03.037.
  * [19] P. W. Graham, J. Hayward, J. Foster, O. Story, L. Havas, GenCost 2018, Tech. rep., CSIRO, Australia (2018).  doi:10.25919/5c587da8cafe7.
  * [20] A. M. Ershad, R. Pietzcker, F. Ueckerdt, G. Luderer, Managing power demand from air conditioning benefits solar pv in india scenarios for 2040, Energies 13 (9) (2020) 2223.  doi:10.3390/en13092223.
  * [21] P. de Guibert, B. Shirizadeh, P. Quirion, Variable time-step: A method for improving computational tractability for energy system models with long-term storage, Energy 213 (2020) 119024.  doi:10.1016/j.energy.2020.119024.