text:
\section{Introduction}
	BCH codes were introduced in \cite{Hoc, BCHa,BCHb} and are a well known
	class of block codes with various practical applications.
	There exist many hard and soft decision decoding methods for them which can be classified into
	algebraic methods using the Berlekamp-Massey or the Euclidean algorithm,
	methods based on the dual code, and information set based methods. Many algorithms are already included in textbooks, see e.g. \cite{McWSl, Boss, Blahut}.
	While the algebraic decoding works up to half the designed minimum distance which is determined by the construction of BCH codes.
	Interpolation based decoding \cite{guruswami} can be used to extend the decoding radius.
	Some non algebraic decoding methods can also decode beyond half the minimum distance.

	Shortly after the introduction of BCH codes, it was shown in
	\cite{Kolesnik, Kasami} that Reed-Muller (RM) codes are equivalent to
	BCH codes with a particular choice of cyclotomic cosets for their construction, extended
	by a parity bit (see also \cite{McWSl, infoset}).
	This implies that the hard and soft decision decoding methods for RM codes
	can also be applied to BCH codes and vice versa.
	This fact is particularly interesting since there exist many examples for BCH codes that have a larger minimum distance than the RM codes at the same coderate.
	In addition for RM codes the Plotkin construction \cite{Plotkin}
	allows low complexity decoding \cite{Schnabl, Boss}.
	Further, in \cite{RmPolar_Mondelli, RmPolar_Arikan} the relations of
	polar codes and RM codes are shown.
	Note that the construction of polar codes was given earlier in \cite{stolte}
	as a modification of the RM construction.
	Therefore, the use of BCH codes has, besides the cyclic property, the advantage
	of better code parameters than RM and polar codes which possibly leads to a better decoding performance.

	In \cite{ferdi}, minimal weight dual codewords are used for decoding beyond half the minimum distance and the decoding methods presented
	in this work are based on this approach which was also used in \cite{haeger}.
	We will show that information set decoding of BCH codes without channel reliability
	based on minimal weight dual codewords
	performs in many cases as good as hard decision maximum likelihood decoding.
	The presented decoding method works also for Reed--Solomon and q-ary BCH codes \cite{jiongyue}
	but this will not be discussed here.

	For soft decision decoding of BCH codes, three principles which make use of the reliability
	information from the channel, are known. The first \cite{Chase} uses the most unreliable positions
	which contain more likely errors and constructs flip-patterns for these positions. For all
	of these flip-patterns, a classical decoder is applied.
	The idea is that if a flip-pattern reduces the number of errors to a value less or equal to half the minimum distance,
	it can be decoded by a classical decoder.
	The second \cite{Dorsch} uses the most reliable positions as information set and re-encodes
	with these positions. Also here flip-patterns are used in case the information set contains erroneous
	positions. In \cite{linfos} both methods are studied under the name ordered statistics.
	The third method uses dual codewords to calculate extrinsic information and reduces
	the number of errors iteratively.
	Various variants are known and
	some recent results can be found in \cite{Wu, Khamy, haeger, Liva}.
	Also, the determination of an information set after applying the extrinsic idea is known \cite{BP_ISD}.
	We will extend the hard decision information set decoding to soft decision decoding
	which uses channel reliability information.
	Since in all studied examples the decoding methods based on unreliable positions
	show worse results than those based on the most reliable positions,
	we will restrict to the latter case here.

	\paragraph{Contributions}
	We compare BCH codes of the same rate with different choices of cyclotomic cosets and
	analyze their properties.
	Based on the minimal weight dual codewords the results from \cite{ferdi,arxivboss, SCC2019} are
	extended and three decoding algorithms are derived, namely,
	the error reduction, the information set, and the redundancy set decoding.
	The information set decoding in case of a binary symmetric channel, which does not provide any reliability
	information, shows in many cases the same decoding performance as
	hard decision maximum likelihood decoding.
	The redundancy set decoding makes use of the fact that for cyclic codes any consecutive
	positions equal to the dimension of the code can be used for encoding.
	The error reduction decoding based on unreliable positions shows inferior performance compared to the methods based on the most reliable positions.
	We recall a known result that every RM code is a BCH code extended by a parity bit and show examples where
	BCH codes have better parameters than RM codes.
	A soft decision decoding based on hard decision information set decoding is presented.
	We show that using the dual codewords improves the reliability of the channel.
	A novel choice of the flip-patterns is given which is able to predict the decoding performance.
	Comparisons to selected literature are provided.

	\paragraph{Structure}
	In Section~\ref{sec:bch} we give a short introduction to BCH codes and their dual codes.
	The choice of the cyclotomic cosets is described and illustrated with several examples.
	Then we recall an old result that punctured RM codes are equivalent to BCH codes.
	Finally, we discuss a systematic basis.
	In Section~\ref{sec:decdual} we describe the main idea of the decoding
	based on codewords of the dual code.
	We show the inherent reliability contained in the introduced measure
	and relate the measure to classical concepts, namely bit flipping, majority logic decoding, and
	extrinsic information.
	In the end, we describe three possible decoding concepts.

	The results of the three different decoding methods are discussed in Section~\ref{sec:hardec}.
	The performance of BCH codes with different lengths and rates is presented and analyzed.
	A maximum likelihood bound is introduced in order to compare the obtained word error rates.
	Also, the decoding complexity is addressed.

	In Section~\ref{sec:softdec} we will describe and analyze the
	soft decision extension of information set decoding.
	The results are compared to known results from \cite{Liva}.
	Conclusions will be given in the last section and the
	proof of the equivalence of BCH and RM codes, including the permutation, can be found in the appendix.

	\section{BCH codes}\label{sec:bch}
	We restrict ourselves to binary BCH codes and refer to \cite{McWSl, Boss, Blahut}
	for further details.
	Let $\alpha$ be a primitive element of the field $\mathbb F_{2^m}$.
	$\mathbb F_{2^m} [x]$ denotes
	the polynomials $\mod (x^n -1)$, with $n=2^m-1$.

	\begin{definition}[Cyclotomic coset] For $n=2^m-1$ the cyclotomic cosets are
		\[K_i = \{i \cdot 2^j\mod n, j= 0,1, \ldots, m-1\},\  i=0, \ldots, n-1.\]
	\end{definition}
	Two cyclotomic cosets $K_i$ and $K_j$ with $i \neq j$  are either disjoint or identical.
	Their cardinality is $|K_i| \leq m$ and $|K_0| =1$.
	The cyclotomic cosets define the irreducible polynomials $m_{\ell}(x)$  which
	are the product of the linear factors $m_{\ell}(x)=\prod_{j \in K_\ell}(x-\alpha^{-j})$. The irreducible polynomials
	have only coefficients from $\mathbb F_{2}$.

	\begin{theorem}[BCH Code]\label{th:bch}
		Let $\mathcal M = \cup K_i$ be a union of some cyclotomic cosets for $n=2^m-1$.
		The binary BCH code with generator polynomial
		\[
		g(x)= \prod_{j \in \mathcal M} (x-\alpha^{j}).
		\]
		has length $n=2^m-1$, dimension $k=n-|\mathcal M|$, and designed minimum distance
		$d$ when $\mathcal M$ contains   $d-1$ consecutive integers.
		The true minimum distance $\delta$ can be larger than $d$.
	\end{theorem}
	The generator polynomial $g(x)$ is a product of some irreducible polynomials.
	The BCH$(n,k,d)$ code has the parity check polynomial $h(x)$ with $g(x)h(x)=x^n-1$.
	The dual code of a BCH$(n,k,d)$
	code is also a BCH$(n,n-k,d^\perp)$ code with generator polynomial
	$h(x) =(x^n-1)/g(x)$.
	The codewords of the dual code are $c^\perp(x)= a(x) h(x)$ where $a(x)$
	is some information polynomial of degree less than $n-k$.
	As a consequence, the product of any codeword and any dual codeword is zero, i.e.,
	\begin{equation}\label{eq:cwtimesdual}
	c(x) c^\perp(x)= 0\mod (x^n-1)
	\end{equation}
	which is the main property we will use for decoding.

	\subsection{Choice of cyclotomic cosets}
	Algebraic decoding of BCH codes works up to half the minimum designed distance.
	Therefore, given the rate, the cyclotomic cosets have to be chosen such that the designed distance of the BCH code is maximized. For other decoding algorithms
	different criteria for the selection of the cyclotomic cosets might be applied,
	for example the weight distribution of the resulting code.
	The presented decoding methods depend on minimum weight codewords of the dual code,
	hence their weight and their number are influencing the decoding performance and complexity.

	When considering minimal weight dual codewords it may happen that these codewords belong to a subcode of the
	dual code as explained in the following.
	Any dual codeword $b(x)$ can be described as the multiplication of some information
	polynomial $i(x)$ with the parity check polynomial $h(x)$,
	\begin{equation}
	b(x) = i(x) \cdot h(x).
	\end{equation}
	It is possible that the information polynomial has an irreducible polynomial $m_{\ell}(x)$ as factor which means
	$m_{\ell}(x) | i(x)$.
	When this factor does not divide the parity check polynomial,
	$m_{\ell}(x) \, \not| \, h(x)$,
	it can be seen as factor of another parity check polynomial $h_\ell(x)= m_{\ell}(x) h(x)$ with larger degree,
	\begin{equation}
	b(x) = i(x) \cdot h(x) = \underbrace{(i_\ell(x) \cdot m_{\ell}(x))}_{=i(x)} \cdot h(x) = i_\ell(x) \cdot \underbrace{(m_{\ell}(x) \cdot h(x))}_{h_\ell(x)}.
	\end{equation}
	Since $\deg(h_\ell(x)) > \deg(h(x))$, the described code has a smaller dimension, thus, is a subcode.
	However, the dual code of this subcode is a supercode of the code with generator polynomial
	$g(x) = (x^n-1)/h(x)$  since this supercode has generator polynomial $g(x)/ m_{\ell}(x)$ and thus, a larger dimension and possibly a smaller minimum distance.
	Nevertheless, there exist dual codewords $a(x)$, maybe of larger weight, for which
	$h(x) | a(x)$ and also $h_\ell(x) \, \not| \, a(x)$ hold.

	In the following, we present several examples for parameters and characteristics of BCH codes for different choices of cyclotomic cosets.
	Since the presented decoder uses codewords from the dual code the decoding performance will
	depend on the particular choice of cyclotomic cosets.
	Note that the number of possible choices of cyclotomic cosets is exponentially growing with the length $n$.
	All parameters in the examples are found by computer using SageMath \cite{sage}.

	\begin{example}[BCH$(63,31,d)$ Code]\label{ex:ratehalbcode}
		For $n=63$ there exist $13$ cyclotomic cosets $K_i, i \in \{0,1,3,5,7,9,11,\\13,15,21,23,27,31 \}$.
		The usual construction of BCH codes to maximize the designed minimum distance would choose the cosets $K_i, i \in \{1,3,5,7,9,11\}$
		and the resulting code is BCH$(63,30,13)$.
		But fixing the dimension to $31$ with the $13$ cosets, $252$ different BCH codes can be constructed and
		several of them are monomially equivalent. Even if the number and weight of minimum weight dual codewords are identical, differences in the weight distribution of the codes may exist.
		The largest designed minimum distance which was found among them was $d=11$ for
		$K_i, i \in \{1,3,5,7,9,21,27\}$ and we will use this code for bounded minimum distance decoding later
		when comparing the decoding performances.
		For $217$ different codes the minimum weight dual codewords are from a subcode.
		We select four codes for further investigation and their parameters, the designed distances  $d$, $d^\perp$,
		the true distances $\delta$, $\delta^\perp$, the number of minimal weight dual codewords $L$, and
		the chosen cyclotomic cosets are listed in Table~\ref{table_chosenCodes_params_63_31}.
		It should be noted that only the cyclically different codewords are counted and therefore, the number of minimal weight codewords is $\leq n L$.
		\begin{table}[h!]
			\centering
			\begin{tabular}{l|l|l|l|l|l|l}
				$\mathcal{C}$ & $\delta$ & $\delta^\perp$ & $L$ & $d$ & $d^\perp$ & $\{i : K_i \subset \mathcal{M}\}$\\\hline\hline
				$\mathcal{C}_{63,31}^{1}$ & 12 & 10 & 5 & 8 & 6 & $\{5, 9, 11, 13, 21, 23, 27\}$\\
				$\mathcal{C}_{63,31}^{2}$ & 12 & 12 & 35 & 7 & 10 & $\{1, 3, 5, 9, 13, 21, 27\}$\\
				$\mathcal{C}_{63,31}^{3}$ & 12 & 12 & 44 & 7 & 8 & $\{1, 5, 7, 9, 13, 21, 27\}$\\
				$\mathcal{C}_{63,31}^{4}$ & 9 & 12 & 52 & 7 & 12 & $\{11, 13, 15, 21, 23, 31\}$\\
			\end{tabular}
			\caption{Parameters of selected codes with $n = 63$ and $k = 31$}
			\label{table_chosenCodes_params_63_31}
		\end{table}
	\end{example}

	\begin{example}[BCH$(63,22,d)$ Code]\label{ex:rmcode}
		Here $168$ BCH codes can be constructed.
		However, several of them are equivalent. In total only $13$ different codes have minimum weight dual codewords
		which are not only in the subcode.
		Four codes are selected for further investigations and their parameters are listed in Table~\ref{table_chosenCodes_params_63_22}.
		For the first two codes, we had to add $19$, respectively $25$ dual codewords of weight $8$ which
		are not in a subcode.
		Three codes have a different designed and true minimum distance.
		The fourth code has the same designed and true distance and has the most minimum weight dual codewords.
		\begin{table}[h!]
			\centering
			\begin{tabular}{l|l|l|l|l|l|l|l|l|l}
				$\mathcal{C}$ & $\delta$ & $\delta^\perp$ & $L_{\delta^\perp}$ & $w_{add}$ & $L_{add}$ & $L$ & $d$ & $d^\perp$ & $\{i : K_i \subset \mathcal{M}\}$\\\hline\hline
				$\mathcal{C}_{63,22}^{1}$ & 16 & 6 & 1 & 8 & 19 & 20 & 11 & 4 & $\{3, 5, 7, 9, 11, 13, 15, 21\}$\\
				$\mathcal{C}_{63,22}^{2}$ & 15 & 6 & 1 & 8 & 25 & 26 & 11 & 6 & $\{1, 3, 5, 7, 9, 13, 21, 23\}$\\
				$\mathcal{C}_{63,22}^{3}$ & 15 & 8 & 30 & & 0 & 30 & 11 & 4 & $\{1, 5, 7, 15, 21, 23, 27, 31\}$\\
				$\mathcal{C}_{63,22}^{4}$ & 15 & 8 & 155 & & 0 & 155 & 15 & 8 & $\{1, 3, 5, 7, 9, 11, 13, 21\}$\\
			\end{tabular}
			\caption{Parameters of selected codes with $n = 63$ and $k = 22$}
			\label{table_chosenCodes_params_63_22}
		\end{table}
	\end{example}
	The next example shows the case when the minimal weight dual codeword belongs to a subcode.
	\begin{example}[Dual codewords of BCH$(63,22,d)$]
		The BCH code $\mathcal{C}_{63,22}^{2}$ has the parity check polynomial $h(x) = x^{22} + x^{21} + x^{20} + x^{19} + x^{18} + x^{14} + x^{13} + x^{10} + x^9 + x^7 + x^2 + 1$.
		The minimum weight dual codewords are $b(x) = x^{56} + x^{51} + x^{23} + x^{17} + x^3 + 1$
		and all cyclic shifts.
		However, $b(x)$ has a factor $m_\ell(x)$ which does not divide  $h(x)$ and is a product of irreducible polynomials since
		the greatest common divisor of $x^n-1$ and $b(x)$ is
		$h_\ell(x) = \gcd(b(x), x^n-1) = x^{31} + x^{27} + x^{25} + x^{23} + x^{21} + x^{19} + x^{17} + x^{15} + x^{13} + x^9 + x^8 + x^5 + x^4 + 1$. Thus, the factor
		$m_\ell(x) = h_\ell(x) / h (x)$ divides $b(x)$ and any cyclic shift
		and thus, $b(x)$ belongs to a subcode.
		Since $h_\ell(x)$ is the parity check polynomial of
		the $BCH(63,31,d)$ code which is a supercode of $\mathcal{C}_{63,22}^{2}$ and
		with $b(x)$ this supercode is checked which has a smaller minimum distance.
	\end{example}
	The number 127 is prime, hence for this codelength, all corresponding cosets (except for $K_0$) have the same cardinality. This increases the number of possible combinations to achieve a certain dimension, however, it decreases the possible choices of dimensions since $|\mathcal M|$ or $|\mathcal M|-1$ is divisible by $7$.

	\begin{example}[BCH$(127,64,d)$ Code]\label{bch127_64}
		The cyclotomic cosets corresponding to $n = 127$ are $K_i, i \in \{0, 1, 3, 5, \\ 7, 9, 11, 13, 15, 19, 21, 23, 27, 29, 31, 43, 47, 55, 63,\}$. Since all cyclotomic cosets but $K_0$ contain $7$ numbers, any combination of 9 of these will result in a BCH code with $k = 64$. In total, $\binom{18}{9} = 48620$ different codes can be constructed. Here we select four codes to be examined in detail and their parameters (same notation as in the previous examples) are given in Table~\ref{table_chosenCodes_params_127_64}.
		\begin{table}[h!]
			\centering
			\begin{tabular}{l|l|l|l|l|l|l}
				$\mathcal{C}$ & $\delta$ & $\delta^\perp$ & $L$ & $d$ & $d^\perp$ & $\{i : K_i \subset \mathcal{M}\}$\\\hline\hline
				$\mathcal{C}_{127,64}^{1}$ & 21 & 20 & 28 & 19 & 8 & $\{1, 3, 5, 7, 9, 11, 13, 15, 63\}$\\
				$\mathcal{C}_{127,64}^{2}$ & 20 & 20 & 119 & 13 & 12 & $\{1, 3, 5, 7, 9, 11, 23, 29, 43\}$\\
				$\mathcal{C}_{127,64}^{3}$ & 21 & 21 & 1\,590 & 21 & 8 & $\{1, 3, 5, 7, 9, 11, 13, 15, 19\}$\\
				$\mathcal{C}_{127,64}^{4}$ & 15 & 16 & 651 & 15 & 16 & $\{1, 3, 5, 7, 9, 11, 13, 19, 21\}$\\

			\end{tabular}
			\caption{Parameters of selected codes with $n = 127$ and $k = 64$}
			\label{table_chosenCodes_params_127_64}
		\end{table}
	\end{example}

	\subsection{Equivalence of RM and extended BCH codes}\label{subsec:equivalence}

	Reed-Muller codes are denoted by $\mathcal{R}(r,m)$ where $r$ is the order and $n=2^m$ is the length.
	The dimension is $k=\sum_{i=0}^r {m \choose i}$ and the minimum distance is $d=2^{m-r}$, see \cite{Boss,McWSl}.
	RM codes can be described by various constructions [\citefirst{Schnabl, RmPolar_Arikan, RmPolar_Mondelli}.
	In the following, we will define RM codes as permuted extended BCH codes.
	A proof can be found in \cite{McWSl} Ch.13, \S 5, Th. 11, where the explicit permutation is not given.
	However, we give the explicit permutation and a proof that RM codes punctured by one position are cyclic in the appendix.
	For a BCH code corresponding to a RM code we select a cyclotomic coset of length $n=2^m-1$ if the weight of the binary number $a_0 \ldots a_{m-1}$ of its index $i$
	is between $0$ and $m-r$.
	Formally, the set $I$ is
	\begin{equation}\label{eq:coset_choice_RM}
	I=\left\{i=\sum_{j=0}^{m-1}a_{j}\cdot 2^j: 0 <\sum_{j=0}^{m-1}a_{j} < m-r, \ a_i \in \{0,1\}\right\}.
	\end{equation}
	The union of cyclotomic cosets is $\mathcal M = \cup_{i\in I} K_i$. In other words, the factors of $g(x)$
	are the irreducible polynomials $m_i(x), i \in I$.
	\begin{example}[$\mathcal{R}(2,6)$ and  BCH$(63,22,15)$]
		The code $\mathcal{C}_{63,22}^{4}$ from Example~\ref{ex:rmcode} corresponds to the punctured Reed-Muller code $\mathcal{R}(2,6)$ since the binary representation  of the number of the selected cyclotomic cosets $1 \leftrightarrow 00001$,
		$3 \leftrightarrow 00011$,
		$5 \leftrightarrow 00101$,
		$7 \leftrightarrow 00111$,
		$9 \leftrightarrow 01001$,
		$11 \leftrightarrow 01011$,
		$13 \leftrightarrow 01101$,
		$21 \leftrightarrow 10101$
		have all weight larger than $0$ and less than $m-r=4$.
		The cyclotomic coset
		$15 \leftrightarrow 01111$ was not selected since the weight is $4$.

	\end{example}
	The BCH code  $\mathcal{C}_{127,64}^{4}$ from Example~\ref{bch127_64} is equivalent to a punctured Reed-Muller code $\mathcal{R}(3,7)$. It can be observed that the minimum distance is smaller than those of the other codes.

	Let  $(c_{0},\ldots,c_{n-1})$ be a codeword of the BCH code.
	The permutation of the codeword coordinates to obtain a codeword of the RM code is given by
	\begin{equation}\label{eq:permutation_func}
	\pi(i) = \log_\alpha \left( \sum_{j=0}^{m-1}\alpha^{j}a_j \right) \mbox{ where } i= \sum_{j=0}^{m-1}2^{j}a_j, i =1 \ldots n, \ a_j \in \mathbb F_2.
	\end{equation}
	and $ \log_\alpha (\alpha^\ell) = \ell$.
	Further, a parity bit $p=\sum_{i=0}^{n-1}c_i$ has to be prepended and the codeword of the $r$-th order Reed-Muller code is
	\begin{equation}\label{eq:extended_cw}
	\left(p,c_{\pi(1)},\ldots,c_{\pi(2^m-1)} \right) \in \mathcal{R}(r,m).
	\end{equation}

	\begin{example}[Permutation for $\mathcal{R}(1,3)$ and BCH$(7,4,3)$]
		According to Eq.~(\ref{eq:coset_choice_RM}), the only chosen cyclotomic coset is $K_1$, since
		$I=\left\{2 i_1+i_0: 0 < i_0+i_1 < 2\right\}=\left\{1,2\right\}$
		and $K_1$ includes $1$ and $2$.
		Using $p(x)=x^3+x+1$ as primitive polynomial of $\mathbb F_{2^3}$, the
		generator polynomial of the BCH code is $g(x) = x^3+x+1$.
		With the same $p(x)$  the permutating function according to Eq.~(\ref{eq:permutation_func}) 		can be calculated, for example consider
		\begin{equation*}
		\pi(5)=\pi(1\cdot2^2+0\cdot2^1+1\cdot2^0)=\log_\alpha(1\alpha^2+0\alpha^1+1\alpha^0)=\log_					\alpha(\alpha^6)=6.
		\end{equation*}
		Using Eq.~(\ref{eq:extended_cw}), the codewords of $\mathcal{R}(1,3)$ are given by
		$\left(p,c_{0},c_{1},c_{3},c_{2},c_{6},c_{4},c_{5}\right)$ where
		$p=\sum_{i=0}^{6}c_i$.
	\end{example}
	In general, the special choice of cyclotomic cosets is suboptimal with respect to maximizing the designed distance.
	Therefore, the minimum distance of a RM code is often smaller than
	the true minimum distance of a comparable extended BCH code.
	An example for this statement are the BCH codes $\mathcal{C}_{127,64}^{3}(127,64,21)$ and $\mathcal{C}_{127,64}^{4}(127,64,15)$ from Example~\ref{bch127_64} where the latter corresponds to an RM code.
	This observation is especially interesting due to the close relation of RM and polar codes [\citefirst{RmPolar_Arikan, RmPolar_Mondelli}.

	\subsection{Calculation of a Systematic Basis}\label{subsec:sytematic}
	Let $g(x)$ be the generator polynomial of a BCH$(n,k,d)$ code. The degree of $g(x)$ is $n-k$.
	One possible generator matrix $\mathbf G$ consists of the $k$ rows $x^j g(x), j =0, \ldots, k-1$
	and this is a $k \times n$ matrix.
	Let $\mathcal S \subset \{0,1, \ldots, n-1 \}$ be a set of $k$ distinct positions.
	If the submatrix $\mathbf G_S$ which consists of the columns $\ell \in \mathcal S $ has full rank
	$k$ then $\mathcal S$ is called information set and these positions uniquely determine the remaining $n-k$ positions of any codeword. Since  $\mathbf G_S$ has full rank by
	Gaussian elimination of  $\mathbf G$ it is possible to calculate the matrix $\mathbf G_I$
	which has the unity matrix at the positions $\mathcal S$.
	It is known that for BCH codes not any $k$ positions are an information set.
	Which $k$ positions form an information set is a code property and not a property of the chosen generator matrix.

	If the submatrix $\mathbf G_S$ has not full rank, the linear dependent
	columns must be substituted by other columns of $\mathbf G$ which are linear independent.
	Since $\mathbf G$ has rank $k$ a full rank $\mathbf G_S$ can always be found.

	Cyclic codes have the property that any $k$ consecutive positions $\mathcal S_c$ are an information set.
	Let $\mathcal S_c = \{k_0,k_0+1, \ldots, k_0+k-1 \mod n \}$.
	These position can be cyclically shifted by $x^j, j=n-k-k_0$ such that
	$\mathcal S_s = \{n-k, \ldots, n-1 \}$. Encoding of the information symbols
	$c_I(x)= c_{n-k}x^{n-k} + \ldots + c_{n-1}x^{n-1}$  is done by calculating the remainder $c_R(x)$
	when dividing $c_I(x)$ by
	the generator polynomial $g(x)$ denoted by $\mathrm{rem} (g(x),c_I(x))$. The codeword is then
	$c(x)=c_I(x)+c_R(x)$.
	Obviously the remainder has degree $< n-k$ and its $n-k$ coefficients are the redundancy
	part of the codeword. If necessary one can shift back $c(x)$ such that the information
	positions are at  $\{k_0,k_0+1, \ldots, k_0+k-1 \mod n \}$ again.

	In case of an information set of consecutive positions we can calculate the generator matrix $\mathbf G_C$
	which consist of the $k$ rows
	\begin{equation}
	c_\ell (x) +x^\ell, \ \ell= n-k, \ldots, n-1
	\end{equation}
	where $c_\ell (x)=\mathrm{rem}(g(x),x^\ell)$ is the remainder of the division $x^\ell :g(x)$.
	This matrix $\mathbf G_C$ has the form
	\begin{equation}\label{eq:sysmatrix}
	\mathbf G_C = (\mathbf G_R | \mathbf I_k)
	\end{equation}
	were $\mathbf I_k$ is the $k \times k$ identity matrix.

	\section{Decoding Based on the Dual Code}\label{sec:decdual}

	In case of a BSC we receive $r(x)=c(x)+e(x)$ where $e(x)=x^{e_0} +  x^{e_1} + \ldots + x^{e_{\tau-1}} $ is the error polynomial of weight $\tau$
	and $c(x)$ is the transmitted codeword. We can calculate
	\begin{equation}\label{eq:rectimesdual}
	r(x) c^\perp(x)=   (c(x)+e(x)) c^\perp(x) =  e(x) c^\perp(x)\mod (x^n-1)
	\end{equation}
	where we have used Eq.~(\ref{eq:cwtimesdual}). Since the dual code is cyclic, we can choose a dual codeword $c^\perp(x)=b(x)$ of minimal weight $d^\perp$
	of the form $b(x)=1 + x^{b_1} + \ldots + x^{b_{d^\perp-1}}$.
	We calculate $w(x)=r(x) b(x)\mod (x^n-1)$
	which is equal to
	$w(x)= e(x) b(x)\mod (x^n-1)$, according to Eq.~(\ref{eq:rectimesdual}). The polynomial $w(x)$  can be written as sum of cyclic shifts of $e(x)$, namely
	\[
	\begin{array}{rcl}
	w(x)
	&=& x^{e_0} +  x^{e_1} + \ldots + x^{e_{\tau-1}} +\\
	& & x^{e_0+ b_1} +  x^{e_1 + b_1} + \ldots + x^{e_{\tau-1} +b_1} +\\
	& \vdots & \\
	& & x^{e_0+ b_{d^\perp-1}} +  x^{e_1 + b_{d^\perp-1}} + \ldots + x^{e_{\tau-1} +b_{d^\perp-1}},
	\end{array}
	\]
	where the exponents $ e_i + b_j$ are calculated$\mod n$.
	Every coefficient of $w(x)$ equal $1$ is either an error  $x^{e_i}$ or a shifted
	error  $x^{e_i+b_j}$. The $1$ could also come from an addition of an error and an even
	number of shifted errors.
	Similarly, for coefficients equal $0$ the position is error free and also no shifted error at this position or an error and an odd number of shifted errors are added, or an even
	number of shifted errors is added.

	The main idea \cite{arxivboss} is to shift back
	the shifted errors to their original positions using
	$x^{-b_i} w(x) \mod (x^n-1), i=0, \ldots, d^{\perp}-1$.
	Recall that $x^{-b_0} w(x) =w(x)$.
	Then it is counted how often position $j$ is
	equal to $1$
	in all $d^\perp$ shifts of $w(x)$. This number is called $\Phi_j$ and calculated by
	\begin{equation}
	{ \Phi_j} =  \sum\limits_{i \in \mathrm{supp} \, b(x)} \  w_{j+i\mod n},\ j=0, 1, \ldots, n-1.
	\end{equation}
	Obviously, using a polynomial $b'(x)$ which is a cyclic shift of $b(x)$ where the
	zero coefficient is $1$
	would result in the same $\Phi_j$. Therefore, we can use cyclically different polynomials only.
	In case of $L$ cyclically different minimal weight polynomials $b^{(\ell)}(x), \ell=0, \ldots, L-1$
	we can do this counting for each of these and add them.
	The calculation of $\Phi_j$ using only the coefficients of $r(x)$ is
	\begin{equation}\label{eq:phi_coeff}
	\Phi_j= \sum\limits_{\ell=0}^{L-1} \sum\limits_{i=0}^{d^\perp-1}  \left(\sum\limits_{l=0}^{d^\perp-1}
	r_{(j+ b^{(\ell)}_i - b^{(\ell)}_l\mod n)}\mod 2 \right).
	\end{equation}

	\subsection{Inherent reliability}
	In order to give plausibility arguments for the inherent reliability we
	calculate the expected value of the weight $\omega$ of $w(x)$ and follow
	the ideas in \cite{ferdi}.
	The coefficient $w_i$ is $1$ if an odd number of the $\tau$ error positions
	overlap with the $d^\perp$ nonzero positions of $b(x)$.
	However, we only can calculate how often this happens when considering all possible
	errors of weight $\tau$.
	This number $W \in \mathbb N$ dependents only on $ \tau, d^\perp$, and $n$ and is
	\begin{equation}
	W=  { d^\perp \choose 1} {n- d^\perp \choose \tau- 1} +{ d^\perp \choose 3} {n- d^\perp \choose \tau- 3} + \ldots +q,
	\end{equation}
	where
	\[
	q= \left\{ \begin{array}{ll}
	{ d^\perp \choose \tau} {n- d^\perp \choose 0}, & \tau \ \mathrm{odd}\\
	{ d^\perp \choose \tau-1} {n- d^\perp \choose 1}, & \tau \ \mathrm{even}.\end{array}
	\right.
	\]
	Thus, the expected contribution of one error of weight $\tau$ to one
	coefficient $w_i$ is
	$W/ {n \choose \tau}$. Therefore, the expected
	weight $\omega$ of $w(x)$ is
	\begin{equation}\label{DA}
	E[\omega] =  \frac{n W}{{n \choose \tau}}.
	\end{equation}
	Now we follow the ideas in \cite{arxivboss} in order to calculate the expected values for
	$\Phi_j$ in case of an error and a non-error position.
	At an error position $j$,
	the frequency of occurrence $\Phi_j$
	has the expected  value
	\begin{equation}\label{eq:expected_phierror}
	E[\Phi_e(\tau)] =  \frac{E[\omega]}{\tau} L.
	\end{equation}
	Since the expected weight $\omega$  is for  $\tau$ errors
	for each
	polynomial $b^{(\ell)}(x)$ we have to divide by $\tau$ and multiply by $L$
	because we have $L$ different polynomials.
	For a non-error position the expected value of  $\Phi_j$
	is
	\begin{equation}\label{eq:expected_phicorrect}
	E[\Phi_c(\tau)] =   \frac{E[\omega] (d^\perp-1)}{n-\tau}   L.
	\end{equation}
	An error position contributes to $d^\perp-1$ positions of the $n-\tau$ non-error positions. Thus,
	we multiply the expected weight by  $d^\perp-1$ and divide by the number of non-error positions.
	Again we have $L$ polynomials.
	\begin{figure}[h]
		\centering
		\subfloat[Expected and average values of $\Phi$ dependent on $\tau$
		\label{fig_ValsOfPhi_Hard}]
		{\includegraphics[]{bossert1.pdf}}
		\hfil
		\subfloat[Statistics of non-error and error positions
		\label{fig_ErrorStatistics_63-24}]
		{\includegraphics{bossert2}}
		\caption{Aspects of $\Phi$ for BCH(63,24,15)}

	\end{figure}

	\begin{example}[Comparison of  Expected Values and Simulated Averages]
		We use the $35$ different dual codewords of minimum weight $d^\perp = 8$ of $BCH(63,24,15)$. The simulation uses 20000 random errors of weight $\tau$ and calculates the corresponding values of $\Phi$. The calculated values together with simulation results are shown in Fig.~\ref{fig_ValsOfPhi_Hard}. The mean of all occurred values for error positions is $AVG[\Phi_e(\tau)]$. The expected weight $E[\Phi_e(\tau)]$ is calculated according to Eq.~(\ref{eq:expected_phierror}). Respectively, $AVG[\Phi_c(\tau)]$ gives the average values of $\Phi(\tau)$ for correct positions, while $E[\Phi_c(\tau)]$ is predicted by Eq.~(\ref{eq:expected_phicorrect}) and gives the expected value for $\Phi(\tau)$ for non-error positions. For $\tau < 6$ the smallest occurred value for an error position is larger than the largest value for a correct position. In this case, erroneous and correct values are clearly separated.
		It can be observed that the estimated values for non-error positions are
		closer to the simulated averages than those for the
		error positions. This is due to the above-mentioned effect that a $w_j=1$,
		which corresponds to a shifted error at one position can, in addition, be
		shifted to other error positions.
	\end{example}

	The values of $\Phi_j$ contain inherent reliability information
	because the smaller values are more likely error free and the larger values are
	more likely erroneous.
	This implies decoding concepts for different
	decoding strategies based on the unreliable positions
	or based on the reliable positions or based on both.

	\begin{example}[Distribution of error and non-error values of $\Phi$]
		According to the description in Section~\ref{sec:decdual}, higher reliability is indicated by a smaller value of $\Phi$ of the corresponding position.
		A smaller reliability corresponds to a larger value, respectively.
		For a decoding concept based on reliable or based on unreliable positions,
		it is interesting how many error positions have a smaller reliability than all correct positions or how many correct positions have a larger reliability than all error positions.
		Fig.~\ref{fig_ErrorStatistics_63-24} shows the answer to this question
		for the same code BCH(63,24,15) that was used before.
		For each error weight, we simulated $20000$ errors and examined the values of $\Phi$ corresponding to error and non-error positions. The red curve corresponds to the average percentage of error positions that show a smaller reliability than all correct positions. Respectively, the average percentage of correct positions with larger reliability than all errors is depicted in green. For $\tau < 7$ both curves yield values of $100\%$, thus in these cases the $\tau$ error positions correspond to the $\tau$ largest values of $\Phi$. With increasing error weight the values of both curves decrease. Still, the non-error positions correspond on average in $20-30\%$ more cases to the largest reliability values than it is the case for error positions and the smallest reliabilities.
	\end{example}

	Before we describe the decoding concepts we will show that the measure $\Phi_j$
	can be related to known decoding methods.

	\subsection{Relation to known decoding concepts}
	There exist two classical decoding methods based on codewords of the dual code.
	The bit flipping decoding \cite{Gallager}, introduced for low-density
	parity-check codes
	and the majority logic decoding  \cite{Massey} for arbitrary codes.
	Further, the concept of extrinsic information is also based
	on codewords of the dual code.
	For short, we will call them BiFl, MaLo, and ExIn, respectively.
	We will follow the derivation in \cite{arxivboss}.
	Given the dual codeword $b(x)=1 + x^{b_1} + \ldots + x^{b_{d^\perp-1}}$ the vector  $\mathbf p$ with support $\{n-1,n-1-b_1, \ldots, n-1-b_{d^\perp-1}\}$ is a codeword of the dual code. The reverse operation
	relates the polynomial multiplication to the scalar product (compare Eq.~(\ref{eq:phi_coeff})).
	The scalar product of $\mathbf p$ with the received vector $\mathbf r$ is called a parity check
	$\langle \mathbf p, \mathbf r \rangle =  r_{n-1}+ r_{n-1-b_1}+ \ldots
	+ r_{n-1-b_{d^\perp-1}}$
	and results in $0$ or $1$.
	Each coefficient $w_i$ of $w(x)=r(x) b(x)$ corresponds to the scalar product of the
	shifted dual codeword $\mathbf p$ with $\mathbf r$,
	for example $w_{n-1}= r_{n-1}+ r_{n-1-b_1}+ \ldots + r_{n-1-b_{d^{\perp-1}}}$.
	By cyclic shifting the  $L$ codewords, we can create $n L$
	different minimum weight codewords, and thus,  $\mathbf p_t, t =0, \ldots, nL-1$ parity checks.
	Clearly, the $nL$ coefficients of $w^{(\ell)}(x), \ell =0, \ldots, L-1$ are the results of the
	parity checks $\langle \mathbf p_t, \mathbf r \rangle, t =0, \ldots, nL-1$.

	\paragraph{Relation to MaLo}
	In MaLo decoding, each position $j$ is decoded separately
	using a set of parity checks ($\mathbf p_i, i=1, \ldots, J$) with
	the following property \cite{Boss}:
	at position $j$ all checks are $1$ and at
	all other positions  only one of the checks has a $1$.
	In other words $\cap_i \mathrm{supp}(\mathbf p_i )=j$.
	If the majority of the checks is
	not fulfilled ($=1$), position $j$ is decided to be erroneous.
	Note that for $\mathrm{wt} (\mathbf p_i)= d^\perp$ it follows that the number $J$ of checks which can exist, is bounded by $J\leq \lfloor (n-1)/(d^\perp-1) \rfloor$.
	If we restrict the calculation of $\Phi_j$ by using only those polynomials
	$b^{\ell}(x)$ with $b^{\ell}_j=1$ and all the other coefficients are only $1$
	in one of the polynomials, this is identical
	to MaLo decoding.
	Therefore, the calculation of $\Phi_j$ is an extension of MaLo by using for
	position $j$ more checks and violating the restriction that the other positions
	should have ones at disjoint positions.
	Since we use all cyclic shifts of the $L$ polynomials $b^{\ell}(x)$
	for any position $j$ there are  $d^\perp L$ checks  with a
	$1$ at this position. However, the other positions are
	$1$ in more than one check, since $d^\perp L> \lfloor (n-1)/(d^\perp-1) \rfloor$.
	The $\Phi_j$ represent the voting if position $j$ is an error or not.
	Using more checks for this voting about position $j$ turns out as an advantage.

	\paragraph{Relation to BiFl}
	In BiFl position $j$ in the received vector $\mathbf r$ is flipped resulting in the vector
	$\mathbf r_j$ and
	the scalar products $\langle \mathbf p_t, \mathbf r \rangle$  are compared
	with $\langle \mathbf p_t, \mathbf r_j \rangle$. The position $j$
	for which the number of scalar products with result
	$1$ is reduced most is considered as error.
	Flipping position $j$ is the addition of $x^j b^{(\ell)}(x) \mod (x^n-1)$ to $w^{(\ell)}(x)$.
	Note, that this is equivalent to the correlation
	between $x^j b^{(\ell)}(x) \mod (x^n-1)$ and $w^{(\ell)}(x)$.
	In order to measure the change in the scalar products for BiFl we define the value $\Delta_j$ by
	\begin{equation}\label{delta}
	\Delta_j = \sum\limits_{\ell=1}^L \mathrm{wt} (w^{(\ell)}(x) + x^j b^{(\ell)}(x)) - \mathrm{wt} (w^{(\ell)}(x)).
	\end{equation}
	\begin{lemma}[\cite{arxivboss} Relation between $\Phi$ and $\Delta$]\label{bfmalo}
		\[L d^\perp - 2\Phi_j= \Delta_j.\]
	\end{lemma}
	\begin{proof}
		We use only one polynomial $w(x) = e(x) b(x)\mod (x^n-1)$.
		The value  of $\Delta_j$ only depends on the non-zero positions of
		$x^j b(x)$ which are $\mathcal J =\{j, j+b_1, j+ b_2, \ldots, j+ b_{d^\perp-1}\}$.
		If the value of $w_i,\  i \in \mathcal J$ is $1$, $-1$ is added to $\Delta_j$ and if the value is $0$,
		$1$ is added.
		$\Phi_j$ is calculated by shifting $w(x)$
		by $0,-b_1, \ldots, -b_{d^\perp-1}$, which is $\Phi_j= \sum_{j \in \mathcal J} w_j$
		and corresponds to the number of ones in these $d^\perp$ positions.
		The number of zeros is then $d^\perp -\Phi_j$ and
		$\Delta_j$ is the number of zeros minus the number of ones
		thus, $\Delta_j =  (d^\perp -\Phi_j) - \Phi_j $.
		This is valid for each of the $L$ polynomials, which completes the proof.
	\end{proof}

	The concept of low-density parity-check codes is to create
	minimal weight dual codewords. However, only $n-k$ codewords are used as checks
	to get a parity check matrix where $n-k$ is in general much smaller than $nL$.

	\paragraph{Relation to ExIn}
	Assume the check $r_j + r_{t_1} + \ldots +r_{t_{d^\perp-1}}=s_j \in \{0,1\}$.
	With this check equation we can calculate the information of $d^\perp-1$ positions
	about the remaining position.
	This information of the positions $t_1, \ldots, t_{d^\perp-1}$ about position $j$ is
	called extrinsic information. Note that the name extrinsic information is also used
	in a different meaning assuming statistical independence.
	Here we use extrinsic information to describe the collection
	of the information of various combinations of other positions about one position. This exploits the weak law of large numbers
	rather than statistical independence.
	$\Phi_j$ can be interpreted as the extrinsic information for position $j$.
	The calculation of $\Phi_j$ uses $L d^\perp$ checks therefore,  $n(L d^\perp)$ checks
	are used for all $n$ positions. There are $n L$ checks for BiFl, however, for each check, $d^\perp$ extrinsic informations are calculated which results in  $d^\perp(n L)$ checks
	which is the same number.
	Using the extrinsic information to update the reliabilities of positions is known as belief propagation which can be done in the same way with the $\Phi_j$.

	\subsection{Decoding Concepts}
	At the receiver we calculate $\Phi_j, j=0, \ldots, n-1$ and sort
	the positions according to the value  $\Phi_j$  which corresponds to their reliability.
	The order $\Phi_{i_0} \leq \Phi_{i_1} \leq \ldots \leq \Phi_{i_{n-1}}$
	assigns the index set $\mathcal S =\{ i_0, i_1, \ldots, i_{n-1}\}$.
	The most reliable position is $i_{0}$ and the most unreliable is  $i_{n-1}$.
	Here we restrict to a BSC and hard decision decoding.
	Based on these reliabilities we can use the unreliable positions and reduce the number of errors iteratively by flipping these positions.
	However, we also can use the most reliable positions as an information set and it is also possible to use
	both, reliable and unreliable positions.

	The first concept is called {\em error reduction decoding} and is an iterative method. In the first step the
	most unreliable position is flipped.
	Note that the values  $\Phi_j$ have not to be sorted here but only the position $max$ with the maximum value $\Phi_{max}$ must be determined.
	After flipping this position in the received polynomial the values $\Phi_j$ are recalculated.
	Then again the most unreliable position is flipped and the $\Phi_j$ are recalculated and so on.
	The decoding is either stopped when a valid codeword is found or when a maximum number of iterations is reached. In the latter case, a decoding failure is declared.

	In {\em information set decoding} the positions $i_0, \ldots, i_{k-1}$
	are used to calculate a systematic basis according Section~\ref{subsec:sytematic}.
	If this positions contain linear dependent columns the positions
	$i_k, i_{k+1}, \ldots$ are used until a systematic basis
	$\mathcal B = \{\ell_0, \ell_1, \ldots, \ell_{k-1}\}$ is found.
	Then encoding with the received bits $r_{\ell_0}, r_{\ell_1}, \ldots, r_{\ell_{k-1}}$
	as information is done. Here a decoding failure is not possible.
	This can be extended to a list decoder by flipping each $r_{\ell_i}, i=0, \ldots, k-1$
	information symbol and encode. The list size is then $k$ and the codeword which has the smallest Hamming distance to the received polynomial is chosen.
	In case of several codewords with the same distance, one of them is chosen at random.
	The list size could possibly be enlarged by including flips of the unreliable positions of the basis.
	Note that the inherent reliability of the
	$\Phi_j$ makes information set decoding possible.
	Without this reliability, only a trial and error search for an error free systematic basis could be done.

	The third decoding concept is the
	{\em redundancy set decoding}.
	It uses the fact that for cyclic codes any $k$ coherent positions are systematic positions
	as shown in Section~\ref{subsec:sytematic}.
	We will use the positions $n-k, \ldots, n-1$
	as systematic positions in the following.
	Let $\overline r (x) = c(x) + e(x)$ be received. The addition of a codeword $c_w(x)$
	to  $\overline r (x) $ does not change the error positions.
	If we choose the information part $c_I(x)= \overline r_{n-k} x^{n-k}+ \ldots + \overline r_{n-1} x^{n-1}$
	and the redundancy part $c_R(x) = \mathrm{rem}(g(x), c_I(x))$
	then $r(x) = \overline r (x) + c_w(x) = r_0 + r_1 x + \ldots + r_{n-k-1} x^{n-k-1}$.
	The $k$ positions $r_{n-k} = r_{n-k+1} = \ldots =r_{n-1}=0$ are zero,
	however, some of these positions may be erroneous. We will illustrate all
	steps of this new decoding concept with examples.
	\begin{example}[BCH$(15,7,5)$]
		The generator polynomial is $g(x)=x^8 + x^7 + x^6 + x^4 + 1 $
		and the parity check polynomial is $h(x)= x^7 + x^6 + x^4 + 1$.
		The dual code has only one cyclically different minimal weight polynomial $b(x)= x^{11} + x^3 + x^2 + 1$.
		In fact we could use also other cyclic shifts of this polynomial
		for which the coefficient at $x^0$ is $1$.
		In particular $x^4 b(x) = h(x) \mod (x^n-1)$.
		Let the codeword $c(x)= x^{14} + x^{12} + x^{11} + x^{10} + x^{9} + x^{6} + x^{4} + x^{3} + x $
		be transmitted and the error be
		$e(x)= x^{14} + x^2+1$
		which has a weight beyond half the minimum distance.
		Then the received polynomial is
		$\overline{r}(x) = x^{12} + x^{11} + x^{10} + x^{9} + x^{6} + x^{4} + x^{3} + x^{2} + x + 1$
		From the systematic part of the received polynomial $x^{12} + x^{11} + x^{10} + x^{9}$
		we calculate the codeword
		$c_w(x)=x^{12} + x^{11} + x^{10} + x^9 + x^7 + x^5 + x^4 + x$
		and then
		$r(x)= x^7 + x^6 + x^5 + x^3 + x^2 + 1$.
	\end{example}
	Clearly, the $\Phi_j$ are identical when calculated with $\overline r (x) $ or $ r (x) $
	according to Eq.~(\ref{eq:phi_coeff}) since they only depend on the error and the dual codewords.
	The value $\Phi_j$ corresponds to the reliability of position $j$.
	Let $\mathcal B = \{\ell_0, \ell_1, \ldots, \ell_{k-1}\}$ be the index set of the
	sorted reliabilities of the positions $n-k, n-k+1, \ldots, n-1$ and $\ell_0$ is the
	most unreliable one which corresponds to the largest value $\Phi_j$.
	The remaining $n-k$ positions $0,1, \ldots, n-k-1$ are also
	sorted as the index set  $\mathcal G = \{j_0, j_1, \ldots, j_{n-k-1}\}$ and
	$j_0$ is the most reliable symbol. Note that the sets  $\mathcal B$ and $\mathcal G$
	are sorted in opposite order.
	The errors in the systematic part are more likely in the first positions of the set $\mathcal B$ while the first part of $\mathcal G$ is likely error free.
	We take $\mu$ unreliable positions from the systematic
	part and $\mu$ reliable from the redundancy part.
	The choice of $\mu$ is influencing the decoding performance
	and here we choose $\mu \approx k/2$.
	The idea is that the unreliable positions of
	the systematic part contain all errors which are in this systematic part while the reliable positions of the
	redundancy part are error free.
	\begin{example}[$\Phi$ for BCH$(15,7,5)$]
		We calculate $w(x)=r(x) b(x)=  x^{14} + x^{13} + x^{11} + x^{10} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1$.
		In addition we need the three cyclic shifts by $-2,-3$ and $-11$ of $w(x)$. Now we count the ones at the positions and
		get the values

		\[\Phi=
		\left(4,\,3,\,4,\,3,\,2,\,2,\,1,\,2,\,3,\,2,\,2,\,3,\,2,\,3,\,4\right).
		\]
		The index sets are $\mathcal B =\{6, 0, 3, 5, 1, 2, 4\}$ which means the positions
		$\{14, 8, 11, 13, 9, 10, 12\}$,
		and $\mathcal G= \{6, 4, 5, 7, 1, 3, 0, 2\}$.
		We choose $\mu=3$ and verify that the three positions of $\mathcal B$, $\{6, 0, 3\}$ contain
		the error in the systematic part in position $14$.
		Further, the three positions of $\mathcal G$, $ \{6,4,5\}$ of the redundancy part contain no errors.
	\end{example}
	The matrix $\mathbf G_R$ according Eq.~(\ref{eq:sysmatrix}) has $k$ rows and $n-k$ columns.
	From this matrix we extract a $\mu \times \mu$ square matrix $\mathbf D$
	by taking $\mu$ rows  $\ell_0, \ell_1, \ldots,\ell_{\mu-1}$ according
	the index set  $\mathcal B$ and  $\mu$ columns $j_0, \ldots,  j_{\mu-1}$
	according the index set  $\mathcal G$.
	Then from the received values a vector $\mathbf r_G=(r_{ j_{n-k-1}}, \ldots, r_{ j_{n-k-\mu}})$ is determined.
	Assuming that $\mathbf r_G$ is error free as well as the positions $\ell_\mu, \ell_{\mu+1}, \ldots,\ell_{k-1}$
	and $\mathbf D$ is invertible, then the vector $\mathbf \varepsilon = \mathbf r_G \mathbf D^{-1}$
	are the errors in the systematic part.

	We consider a simple case, where only one error is in $\ell_0$ and all other systematic positions $\ell_1, \ldots,\ell_{k -1}$ are error free.
	Then the redundancy part $\mathrm{rem}(g(x), x^{\ell_0})$ should be identical to the redundancy
	part $\mathbf r_G$ at those positions of $j_0, \ldots ,j_{n-k -1}$ which are error free.
	Because of linearity, this holds for any number of errors as long as all errors are in the
	$\mu$ of the $k$ systematic positions.

	\begin{example}[Matrix for decoding BCH$(15,7,5)$]
		The matrix $\mathbf G_R$ from which we select the three rows  $ \mathcal B = \{6,0,3\}$ and three columns
		$\mathcal G = \{6,4,5\}$ gives the matrix $\mathbf D$ and their inverse
		\begin{equation}
		\mathbf G_R=\left(\begin{array}{rrrrrrrr}
		1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\
		1 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \\
		0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\
		1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\
		0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\
		0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 \\
		0 & 0 & 0 & 1 & 0 & 1 & 1 & 1
		\end{array}\right)
		\mathbf D=
		\left(\begin{array}{rrr}
		1 & 0 & 1 \\
		1 & 1 & 0 \\
		0 & 1 & 0
		\end{array}\right)
		\mathbf D^{-1}=
		\left(\begin{array}{rrr}
		0 & 1 & 1 \\
		0 & 0 & 1 \\
		1 & 1 & 1
		\end{array}\right)
		\end{equation}
		The vector $\mathbf r_G=  \left(1,\,0,\,1\right) $
		and the error in the systematic part is $\mathbf e=(0,0,0,0,0,0,1)$.
		With this the decoded codeword is
		$\hat c(x) = c_w(x) + \mathrm{rem}(x^{14}, g(x)) + x^{14}$
		which is the transmitted one.
	\end{example}
	Two extensions of this
	decoding concept to list decoding are possible.
	The first one is to
	use cyclic shifts of the received polynomial $\overline r$.
	With these shifts
	any $k$ consecutive positions can be shifted to the consecutive systematic positions
	$n-k, \ldots, n-1$. With this shifted received polynomial $\overline r_s$
	the same decoding can be done. The $\Phi_j$ has not to be calculated again
	but only shifted accordingly.
	However, a different codeword $c_w(x)$  has to be calculated and added
	and the sorting of the new sets $\mathcal B$ and $\mathcal G$ must be done again.
	With these shifts the Dirichlet principle is used implicitely. If $\tau$
	random errors are in $n$ positions
	the principle says that splitting the $n$ positions into $\nu$ disjoint parts
	there is at least one part which contains $\leq \tau/\nu$ errors.
	But, there is also at least one part which contains $\geq \tau/\nu$ errors. Therefore,
	we can shift the different parts to the fixed systematic positions and have different error
	constellations in the systematic part and in the redundancy part.

	The second possible extension to list decoding is the flipping  of
	the used positions of the redundancy part which is the vector $\mathbf r_G$.
	For any of these vectors with flipped positions,
	as in information set decoding, the multiplication
	$\mathbf \varepsilon = \mathbf r_G \mathbf D^{-1}$ must be calculated.

	\section{Hard Decision Decoding}\label{sec:hardec}
	In this section, we describe three different decoding algorithms
	and analyze their complexity.
	Then we show the decoding performance for selected BCH codes of
	different lengths and rates based on simulations.
	Let $p_\tau$ be the probability that $\tau$ errors can not be decoded by the used decoding algorithm, where $p_\tau$ is determined by simulations.
	Then the  word error rate (WER) can be calculated according a BSC channel
	with error probability $p$,
	using the
	binomial distribution by
	\[ \mathrm{WER}(p) =\sum\limits_{\tau=1}^{n} p_\tau {n \choose \tau} p^\tau (1-p)^{n-\tau}.\]
	The simulation results will be discussed and comparisons will be made.
	But first, we derive a maximum-likelihood (ML) bound, which is used
	to relate the achieved performance to ML decoding.

	For the remainder of this section, a BSC with error probability $p$ is assumed.
	All the algorithms have been implemented in SageMath \cite{sage}.

	\subsection{Maximum Likelihood Bound}
	Since ML decoding is not feasible for many codes, we use a lower bound
	from \cite{Boss} Th. 9.28, p. 384.
	The idea is based on the fact that in simulations we know the transmitted
	codeword $c(x)$ as well as the error $e(x)$.
	In addition we have the decision $\hat c (x)$ of the used hard decision decoding algorithm
	when $r(x)=c(x) + e(x)$ was received.
	An ML decoder decides for
	the codeword with smallest Hamming distance $c_m(x) = \arg \min_c \dist{r,c}$.
	If $\dist{r, \hat c} \geq \dist{r, c}$ we assume that the ML decoder
	decodes  correctly $c_m(x)=c(x)$, which is not guaranteed.
	If $\dist{r, \hat c} < \dist{r, c}$, we assume that the ML decoder makes a decoding error because it will find the same codeword or another one
	with the same or smaller distance.
	In addition, if the outcome of the decoding algorithm is a failure and the decoder gives no estimation we assume that the ML decoder would decode correctly.
	The calculated WER is therefore a lower bound and an ML decoder can not perform better.
	If the performance of the decoding algorithm is identical to the bound,
	it has the same performance as ML decoding.

	This bound can be tightened in case of a
	list-decoder when the output consists of multiple codewords possibly with equal distance to the received sequence.
	Let $\tau = \dist{r, c}$ be the true number of errors and $\hat{\tau}$ the minimum estimated number of errors.
	Furthermore, let the list $\mathcal{L}$ of codewords found by the decoder only contain codewords with corresponding error weight $\hat{\tau}$.
	Then, the number of error events which are relevant for the ML bound can be updated based on this decoding result by
	\begin{equation}
	\text{\# errors for  ML bound} \pluseq \begin{cases}
	0                                           &\text{if } \hat{\tau} > \tau \\
	1-\frac{1}{\left|\mathcal{L}\right|}   = \frac{\left|\mathcal{L}\right|-1}{\left|\mathcal{L}\right|}    &\text{if } \hat{\tau} = \tau \text{ and } c\in \mathcal{L} \\
	1-\frac{1}{\left|\mathcal{L}\right|+1} = \frac{\left|\mathcal{L}\right|}{\left|\mathcal{L}\right|+1}    &\text{if } \hat{\tau} = \tau \text{ and } c\notin \mathcal{L} \\
	1                                           &\text{if } \hat{\tau} < \tau.
	\end{cases}
	\end{equation}
	The update rule for the cases with $\tau = \hat{\tau}$ is based on the following considerations.
	Let $s$ be the number of codewords with distance $\tau$ to the received sequence.
	Then, an ML decoder will choose a wrong codeword with probability $1-\frac{1}{s}$.
	While $s$ is unknown, it can be lower bounded by $\left|\mathcal{L}\right|$, i.e., the number of found codewords, which also lower bounds the error probability of the ML decoder.
	In the case that $c$ is not in the list, an even tighter bound can be obtained, as it is known that at least $\left|\mathcal{L}\right|+1$ codewords with distance $\tau$ exist.

	\subsection{Decoding Algorithms}
	For all decoding algorithms the reliability information $\Phi$ according Eq.~(\ref{eq:phi_coeff})
	has to be calculated. This can be done by Algorithm~\ref{calcphi} where $L$ dual minimal weight codewords are used which are cyclically different and have a one at position $x^0$.

	\medskip
	\begin{algorithm}[H]
		\DontPrintSemicolon
		\SetKwInput{Input}{input}\SetKwInput{Output}{output}
		\Input{$r$, cyclically different minimum weight checks $\mathcal{W}$}
		\Output{$\Phi$}
		\For{$b \in \mathcal{W}$}{
			$w = r \cdot b \mod x^n-1$\;
			\For{cyclic shifts $w_{shifted}$ of $w$}{
				\For{$exp \in \mathrm{exponents}(w_{shifted})$}{
					$\Phi_{exp} \pluseq 1$
				}
			}
		}

		\caption{Calculation of $\Phi$}\label{calcphi}
	\end{algorithm}

	\medskip
	For binary codes, the polynomial multiplication is the XOR of $d^\perp$ cyclic shifts of the
	received vector. The complexity to calculate $\Phi$ is $L$ polynomial multiplications and $L d^\perp$ cyclic shifts. Then these $L d^\perp$ binary vectors are added.
	Each coordinate of $\Phi$ is an integer between $0$ and $L d^\perp$.

	\subsubsection{Error Reduction Decoding}
	The error reduction is an iterative decoding method, where in each iteration
	the unreliable positions according to $\Phi$ are flipped to calculate a new received vector,
	see Algorithm~\ref{eredec}.
	With this new received vector $\Phi$ is recalculated which can be done by modifying
	$w^{(\ell)}(x)$ as follows.
	Let $j_1, \ldots, j_\mu$ be the flipped positions
	then $w^{(\ell)}_{new}(x)= w^{(\ell)}(x) + x^{j_1} b^{(\ell)}(x) + \ldots + x^{j_\mu} b^{(\ell)}(x)$.
	Therefore, the complexity is the number of iterations times the calculation of $\Phi$.
	In addition, a sorting operation in each iteration has to find the $\mu$ largest values
	of $\Phi$ which takes not more than  $\mu$ times $n$ comparisons.
	There exist several variants, which and how many unreliable positions are flipped in each iteration.
	Further, a list decoding variant is given as follows: if more than $maxflip$ positions possess the maximum value of $\Phi$, multiple subsets of these values can be chosen. For each of these subsets, an iterative decoder can be started.

	\subsubsection{Information Set Decoding}

	For this decoding, the values of $\Phi$ have to be calculated only once and a sorting has to be done to find the $k$ most reliable positions. There exist several possibilities to find the  $k$ most reliable positions which are a systematic. Here we sort the columns of the generator matrix according to their reliability and choose the linearly independent pivot columns as information set.
	Therefore, the complexity is the calculation of $\Phi$, the sorting, and the pivot calculation.
	Since we have a systematic encoding matrix we can do list decoding
	by flipping some of the $k$ systematic positions. The flip-pattern
	is a binary vector that contains ones at the positions which are flipped. We choose the list size $1+k + k(k-1)/2$ which means we try all flip-patterns of weight one and two, corresponding to single and double errors.

	\medskip
	\begin{algorithm}[H]
		\DontPrintSemicolon
		\SetKwInput{Input}{input}\SetKwInput{Output}{output}
		\Input{$r$, minimum weight checks $\mathcal{W}$}
		\Output{$\hat{c}$}

		$\hat{c} = r$\;

		\For{$\mathrm{iter}<\mathrm{max iter}$}{
			\If{$\hat{c} \in \mathcal{C}$}{
				break\;
			}
			calculate $\Phi$\;

			$J = \{j \in \{0,1,\dots, n-1\}: \Phi_j = \max(\Phi)\}$\;
			\If{$|J| > \mathrm{maxflip}$}{
				$J = $ choose $maxflip$ random positions of $J$
			}
			flip $\hat{c}_j \quad \forall j \in J$
		}
		\caption{Error Reduction}\label{eredec}
	\end{algorithm}

	\medskip
	\begin{algorithm}[H]
		\DontPrintSemicolon
		\SetKwInput{Input}{input}\SetKwInput{Output}{output}
		\Input{$r$, $\Phi$, generator matrix $G$}
		\Output{$\hat{c}$}

		\tcp{find Information set from most reliable positions according to $\Phi$}
		$G_{sorted} = $sort columns of $G$ according to reliability of $\Phi$\;
		$I = $ pivot columns of $G_{sorted}$

		\tcp{apply flip-patterns}
		\For{$\forall e \in \mathbb{F}_2^k, 0 \leq  \mathrm{\, wt \,} (e)\leq2$}{
			$r_I = r|_I + e$\;
			$\hat{c} = r_I \cdot G_I^{-1} \cdot G$\;
		}
		\Return $\hat{c} = \mathrm{argmin}(\mathrm{dist}(\hat{c}, r))$

		\caption{Information set decoding}
	\end{algorithm}

	\medskip
	\subsubsection{Redundancy Set Decoding}
	This decoding algorithm
	makes use of the fact that for cyclic codes $k$ consecutive positions
	are an information set. Because the code is cyclic we can fix the systematic positions
	and use a precalculated systematic encoding matrix. In order to exploit the Dirichlet principle,
	we can use cyclic shifts of the received vector. The values of $\Phi$ do not have to be recalculated but can also be shifted. Only the sorting in the systematic and in the redundancy part has to be done again.
	Since this decoding was described in detail with examples in the last section we omit a formal description here.

	\subsection{Decoding Performance}
	We start with simulation results of the four BCH$(63,31)$ codes from Example~\ref{ex:ratehalbcode}
	using transmission over a BSC channel.
	Because a BSC channel does not provide reliability information the selection of the information set
	is based on the inherent reliability of the $\Phi$ values only.
	Fig.~\ref{fig_Hard_63_31}
	shows that the performances of information set decoding for the codes $1$, $2$, and $3$ are the same and all are equal to the ML bound
	which means it has the same performance as ML decoding.
	The true minimum distance of all three codes is $\delta=12$.
	Code $4$ has a true minimum distance of  $\delta=9$
	which leads to a different performance,
	as expected, especially for smaller channel error probabilities.
	Nevertheless, the performance of Code $4$ is also equal to the corresponding ML bound.
	The weight of the decoding polynomials is $12$ for all codes except for code
	$1$ where it is $10$. The number $L$ of cyclically different decoding polynomials
	is $5,35,44$, and $52$, respectively.
	Therefore, code $1$ has the smallest decoding complexity.
	With error reduction decoding, Code $4$, which has
	$52$ and thus the most decoding polynomials, has  the best performance.
	It can be observed that information set decoding outperforms error reduction decoding for all codes.
	For comparison, the curve for bounded minimum distance decoding of a BCH code with
	designed minimum distance $d=11$
	is included which is described in Example~\ref{ex:ratehalbcode}.

	\begin{figure}[h]
		\centering
		\subfloat[Hard decision decoding of BCH(63,31)	\label{fig_Hard_63_31}]
		{\includegraphics[]{bossert3}}
		\hfil
		\subfloat[Hard decision decoding of BCH(63,22)	\label{fig_Hard_63_22}]
		{\includegraphics[]{bossert4}}

		\caption{Hard decision decoding of multiple codes with codelength 63}
	\end{figure}

	The simulation results of the four BCH$(63,22)$ codes from Example~\ref{ex:rmcode}
	are visualized in Fig.~\ref{fig_Hard_63_22}, where Code $4$ is the punctured RM code
	which has $155$, thus the most decoding polynomials. For codes $1$ and $2$
	the true minimal weight of the dual code is $6$ and we have to add
	$19$, respectively $25$ dual codewords with a larger weight of $8$.
	The code $3$ has $30$ decoding polynomials.
	For information set decoding, code $1$ shows the best performance
	which is close to the ML bound.
	The second best performance has code $3$ which is identical to the ML bound.
	Code $2$ has a worse performance which is also identical to the ML bound.
	The information set decoding of the punctured RM code $4$ shows the worst performance
	even though the performance is on the ML bound.
	This is an example for which the decoding of a BCH code performs better than the one for the RM code.
	The error reduction decoding of code $3$ performs better than
	the information set decoding of RM code $4$ but worse than all other codes.
	The BMD decoding is more than a factor of $100$ worse than code $1$.

	For the performance of redundancy set decoding, we simulate two codes.
	There exists a BCH code of dimension $24$ and minimum distance $15$ which was already used above.
	For this code the cyclotomic coset
	$21$  is exchanged by the coset  $15$ in Code $4$ of Example~\ref{ex:rmcode}.
	This increases the coderate at the same minimum distance.
	Fig.~\ref{fig_CohHard_63_24} shows the decoding performance of redundancy set decoding for this code in dependence on the number of cyclic shifts used by the decoder. The number $\mu$
	is chosen to be $17$.
	Using four shifts of the received vector, the decoding performance is very close to
	the ML bound.
	For comparison, the performance of information set decoding of code $1$ from Example~\ref{ex:rmcode}
	is included.
	As expected, the ML decoding of a code with fewer codewords, i.e. smaller coderate, should have a better performance, and  Fig.~\ref{fig_CohHard_63_24} shows this effect.
	In general, the redundancy set decoding has a worse performance
	than information set decoding. We use redundancy set decoding for a BCH code of length $n = 127$ and dimension $k=43$.
	The chosen cyclotomic cosets are $K_i, i \in \{1,3,5,7,9,11,13,15,19,27,29,43 \}$, which provides a designed minimum distance of $d = 21$ and a true minimum distance of $\delta = 31$.
	In this case, there are $63$ cyclically different minimum weight codewords of weight $12$.
	As Fig.~\ref{fig_CohHard_127_43} shows, without shifts there is almost no performance loss due to selecting a fixed number of the most reliable positions of the systematic and the redundancy part for $n=127$.
	This can be explained with the weak law of large numbers.
	By using up to eight shifts and no flip-patterns, one can obtain a performance close to information set decoding with $k$ flip-patterns (ISD($1$)) in a channel with high error probability.
	The performance of the redundancy set decoder is better than decoding all error patterns of weight $\leq 16$, which is $(\delta-1)/2 +1$.
	For channels with smaller error probability, the shifts enable a decoding performance similar to that of bounded minimum distance decoding, which cannot be achieved by information set decoding without flip-patterns (ISD($0$)).
	It has to be emphasized that algebraic decoding of the used code can only correct up to $10$ errors as it is limited by the designed minimum distance.
	As the performance of the decoding algorithms based on the dual code is not determined by the designed minimum distance directly, they can improve upon algebraic decoding by a factor of up to $10^6$ at $p=10^{-2}$.

	The redundancy set decoding for the rate one half code was simulated for different $\mu$ and different shifts.
	However, the performance could not reach those of information set decoding
	as in the case of lower rate codes. If no or only a few flip-patterns
	are used the performance can compete. Nevertheless, there remain many open problems for further research,
	especially the choices of the shifts in combination with $\mu$.
	There might be advantages in case of longer codes that are not studied yet.

	\begin{figure}[h]
		\centering
		\subfloat[Redundancy set decoding of BCH(63,24,15) \label{fig_CohHard_63_24}]
		{\includegraphics[]{bossert5}}
		\hfil
		\subfloat[Redundancy set decoding of BCH(127,43,21) \label{fig_CohHard_127_43}]
		{\includegraphics[]{bossert6}}

		\caption{Redundancy set decoding of codes with different codelengths and rate $R \approx 0.35$}
	\end{figure}

	\begin{figure}
		\centering

		\subfloat[Information set decoding of BCH(127,64) \label{fig_Hard_127_64}]
		{\includegraphics[]{bossert7}}
		\hfil
		\subfloat[Comparison BCH and RM \label{fig_Hard_ISD_127_64}]
		{\includegraphics[]{bossert8}}

		\caption{Information set decoding of BCH(127,64)}
	\end{figure}
	Next, we look at the performances of the four BCH codes $(127,64)$ from Example~\ref{bch127_64}
	which have $28$, $119$, $1590$, and $651$  decoding polynomials, respectively.
	First, we compare the three BCH codes which are not equivalent to an RM code
	and then we compare the RM equivalent code $4$ to code $3$.
	While code $1$ shows the same performance as BMD decoding for information set decoding,  codes
	$2$ and $3$ show better performances,
	see Fig. ~\ref{fig_Hard_127_64}.
	The performances are quite different and seem to be related to the number of decoding polynomials.
	For these codes, the performances are not close to the ML bounds and as expected
	the worse a decoder performs the larger is the distance to the ML bound.
	The performance of the punctured RM code $4$ is compared with the performance
	of the BCH code $3$ in Fig.~\ref{fig_Hard_ISD_127_64}.
	Both codes have the same dimension, but
	the RM equivalent BCH code has minimum distance $d=15$ while the
	BCH code has $d=21$.
	In case of a large channel error probability,
	there is hardly any difference in the performance of these codes.
	However, at small error probabilities, the larger minimum distance of the BCH code becomes obvious
	by a performance improvement up to a factor of $100$.
	A surprising result is that the performance of the information set
	decoding of the RM equivalent BCH code is independent of the number of flip-patterns used.
	Here, {\em wt j} means all possible subsets of the $k$
	systematic positions with cardinality $\leq j$ are flipped and the list size
	is $\sum_{i=0}^j {k \choose i}$.

	\begin{figure}[h]
		\centering
		\includegraphics[]{bossert9}
		\caption{Hard decision decoding of BCH(127,92)}
		\label{fig_Hard_127_92}
	\end{figure}

	The last example is a BCH code of higher rate, namely  $(127,94,11)$.
	Code $1$ uses the cyclotomic cosets $\{1,3,5,31,63\}$ and has $21$ decoding polynomials,
	code $2$ uses $\{1,3,5,7,9\}$ and has $155$ polynomials, and
	code $3$ uses $\{1,3,7,23,55\}$ and has $429$ polynomials.
	Fig.~\ref{fig_Hard_127_92} shows the identical decoding performance which is for codes $2$ and $3$ and rather close to the ML bound.
	Code $1$ which has only $21$ decoding polynomials is slightly better than BMD decoding.

	\section{Soft Decision Decoding}\label{sec:softdec}
	For the AWGN channel we use the usual mapping of the binary code symbols  $c_i=0 \leftrightarrow x_i = 1$
	and $c_i=1 \leftrightarrow x_i = -1$ which corresponds to binary phase shift keying (BPSK).
	We receive $y_i = x_i + n_i$ where $n_i$ denotes the Gaussian noise.
	The signal to noise ratio for information bits in dB is called $E_b/N_0$.
	Then the signal to noise ratio  for a codebit is $E_s/N_0 = E_b/N_0 - 10 \cdot \log_{10}(1/R)$
	where $R$ is the coderate of the used code.
	The variance of the noise is then $\sigma^2=1/(2 \cdot 10^{E_s/(10 N_0)})$.

	First, we will describe the intrinsic reliability information from the channel.
	We show a method to predetermine flip-patterns which are used for list information set decoding. An example that this method allows to predict the performance
	of the word error rate of the decoding is given.
	Then the used information set decoder is described.
	We give no results of the soft decision error reduction decoder since the performance
	is worse than with the information set decoding.
	The simulation results show that the reliability from the Gaussian channel can be improved by the inherent
	reliability from the minimal weight dual codewords.
	However, when taking only one minimal weight codeword the decoding performance gets worse than using only the intrinsic reliability from the channel.
	Note that one polynomial means $n$ instead of $n-k$  checks when using a parity check matrix.
	From all checks, only some may be selected according to a criterion which leads to an improvement
	that was also observed in \cite{haeger}.
	We also compare methods for choosing the flip-patterns as well as the choice of different numbers of flip-patterns.
	We did not use stopping criteria from the literature in order to reduce the average decoding time, however, this could be included straight forward into the algorithms.

	\subsection{Aspects of Reliability Information}
	While the binary symmetric channel (BSC) offers no information about the reliability of the received symbols,
	the AWGN channel with its real-valued output alphabet
	allows the calculation of the a posteriori probability $p$ that $x_j=1$ was transmitted as
	\begin{equation*}
	p = P(x_j=1|y_j) = \left(1+\exp\left(\frac{-2y_j}{\sigma^2}\right)\right)^{-1}.
	\end{equation*}
	This probability may be transformed into a log-likelihood ratio (LLR)
	\begin{equation*}
	L_j = \log\left(\frac{p}{1-p}\right) = \frac{2y_j}{\sigma^2}.
	\end{equation*}
	For our simulations we use two different reliability measures, namely,
	\begin{equation}\label{Aexp}
	L_j = \exp{\frac{2|y_j|}{\sigma^2}}
	\end{equation}
	and the absolute value
	\begin{equation}\label{Alin}
	L_j = |y_j|.
	\end{equation}
	For list decoding, there exist several strategies for choosing flip-patterns given a fixed list size.
	In \cite{flippattern} several strategies are compared.
	In this work, we consider an approach that gives very similar flip-patterns
	as the predetermined flip-patterns from \cite{flippattern} which are based on the so called elliptic weight.
	For our method, we simulate codewords and corresponding noise and
	use the knowledge of the error positions to construct a matrix
	$A$ which counts the relative frequency of occurrence of errors at certain positions. A similar approach is used in \cite{wu2008soft} to select flip-patterns.
	The positions are ordered according to their reliability and the $k$ most reliable ones are the
	information set.
	Each element $a_{i,j}$ of $A$ gives the relative frequency of $i$ errors in this information set and $j$
	denotes the position in the information set where the error with the largest reliability value is located.
	With this matrix $A$, the expected WER of a simulation can be predicted by
	the sum over all elements $a_{i,j}$, which are not within the flip-patterns
	\begin{equation}\label{expwer}
	\text{WER}_{est} = \sum_{i}\sum_{j=0}^{k-1} a_{i,j}.
	\end{equation}
	This estimation can, on the other hand, also be used to calculate how many flip-patterns have to be used in order to reach a certain performance.
	Fig.~\ref{fig_Matrix_FlipPattern} shows the simulated values for the code \codename{3}{127,64}.
	For example in case of two errors the relative frequency that the more reliable one
	of these two is at position $30$ in the information set is about $10^{-3}$.
	It can be observed that the relative frequency of $3$ errors in positions $50$ to $64$,
	which are the unreliable positions among the $k$ most reliable ones,
	is higher than for $2$ errors with the larger reliability in the positions $0$ to $14$.
	Eq.~(\ref{expwer}) can also be used to minimize the expected WER under the condition that a fixed number of flip-patterns is used.
	The following example compares the WER simulation with the estimation using the preselected flip-patterns.
	\begin{example}[Estimated WER]
		The matrix is constructed according to simulations using the code $\codename{3}{127,64,21}$. In the following, we limit the maximum amount of flip-patterns to 1000. According to the optimization using the constructed matrix, we use all patterns of weight 1 which include the least reliable 62 positions of the information set. Additionally, all combinations of the least reliable 43 positions of weight 2 and all combinations of the least reliable 7 positions of weight 3 are used in the flip-patterns. We calculate the estimated WER as $\text{WER}_{est} = 0.034$. The WER obtained using simulations of the desired flip-pattern is $\text{WER} = 0.036$.
	\end{example}

	\begin{figure}
		\centering
		{\includegraphics[]{bossert10}}
		\caption{Relative frequency of errors in the $k$ positions that are contained in the information set for code \codename{127,64}{3}. 0 corresponds to the most reliable position and 63 is the position with the smallest reliability.}
		\label{fig_Matrix_FlipPattern}
	\end{figure}

	\subsection{Decoding Algorithm}
	This section describes the soft decision list information set decoding algorithm.
	We assume that the vector $y = (y_0, y_1, \dots, y_{n-1})$ has been received after transmission over the AWGN channel. There are two variants of this algorithm, which use different reliability measures.
	In the first variant, the value of $y_j$ is used directly $L_j=y_j$,  and in the
	second variant
	$
	L_j = \mathrm{sign}(y_j) \cdot \exp(\frac{2|y_j|}{\sigma^2})$.
	For both, the sign of $L_j$ gives the hard decision of the corresponding position, while the absolute value $|L_j|$ indicates the reliability. For the calculation of the extrinsic reliability, the minimum weight dual codewords are used. Let $b$ be a dual codeword with support $\sup(b) = \{b_0,b_1, \dots, b_{\delta^\perp-1}\}$. We discovered that the
	decoding performance can be improved if not all checks are used.
	For this, we examine
	\begin{equation}
	L_{\sup(b)} = \{L_{b_0}, L_{b_1}, \dots, L_{b_{\delta^\perp-1}}\}.
	\end{equation}
	If there are multiple unreliable positions within one check, the knowledge gathered from this check on the reliability of each position is unreliable. Hence, the check is only chosen, if the second smallest value in $L_{\sup(b)}$ is larger than a predefined threshold. In our simulations, we found the twentieth smallest value of $L_j$ to be a suitable value for \codename{3}{127,63,21}.
	Thus, all but one position of the check must belong to the twentieth most reliable positions.
	If the check is chosen, it is evaluated using \begin{equation}
	s = \prod_{j \in \sup(b)} \mathrm{sign}(L_j).
	\end{equation}
	If $s$ is positive, the check is fulfilled, hence no or an even amount of errors is contained within the positions defined by $\sup(b)$. In order to keep track of the number of times each position has been used in a check, we increment the corresponding count of $checks$\begin{equation}
	checks_{j} \pluseq 1 \quad \forall j \in \sup(b).
	\end{equation}
	For each of the positions included in the check we use the minimum of $L_j$ of all other positions of this check as a reliability measure. If the check is fulfilled, the value is added to the current value of $\Phi_j$, else subtracted, \begin{equation}
	\Phi_j \pluseq s\cdot \min_{\ell\in\sup(b)\setminus{j}} \{|L_\ell|\}, \quad \forall j \in \sup(b).
	\end{equation} These calculations are performed for all chosen checks and all their cyclic shifts.

	Before performing information set decoding, the calculated extrinsic reliability $\Phi$ is combined with the intrinsic information $L$. For this purpose we describe two variants. The first is an additive combination. The updated value of $L$ is obtained by \begin{equation}
	L_j \pluseq \mathrm{sign}(L_j) \cdot \frac{\Phi_j}{checks_j} \quad \forall j: checks_j > 0.
	\end{equation}
	The other variant uses a multiplicative combination, which varies depending on the sign of $\Phi_j$,
	\begin{equation}
	L_j = \begin{cases}
	L_j\cdot(1+\frac{3\Phi_j}{\max\Phi}), \Phi_j > 0\\
	L_j\cdot(1-\frac{3\Phi_j}{4\min\Phi}), \Phi_j < 0 .\\
	\end{cases}
	\end{equation}With the updated values $L_j$, information set decoding is performed as in the case of hard decision decoding. In Algorithm~\ref{LISD} the decoding steps are described.

	\begin{algorithm}[H]
		\DontPrintSemicolon
		\SetKwInput{Input}{input}\SetKwInput{Output}{output}
		\Input{$y$, minimum weight checks $\mathcal{W}$, $t\in \mathbf{N}$, flip-patterns $\mathcal{F}$}
		\Output{$\hat{c}$}

		\tcp{intrinsic information}
		$\begin{cases}
		L_j = y_j\quad\forall j $\tcp*{\textcolor{Alin}{Alin}}$\\
		L_j = \mathrm{sign}(y_j)\cdot \exp{\frac{2|y_j|}{\sigma^2}}\quad\forall j 	$\tcp*{\textcolor{Aexp}{Aexp}}$
		\end{cases}$\\
		\tcp{calculate $\Phi$}
		$\mathrm{checks}_j = 0 \quad\forall j$\;
		$\Phi_j = 0 \quad \forall j$\;
		$\mathrm{threshold}=sorted(L)_{t}$\;
		\For{$\forall\mathcal{H}\in\mathcal{W}$}{
			\If{second smallest $|L_j|$ in $\mathcal{H} \geq \mathrm{threshold}$ }{
				$s = \prod_{l\in\mathcal{H}}\mathrm{sign}(L_l)$\;
				\For{$h\in\mathcal{H}$}{
					$\mathrm{checks}_h \pluseq 1$\;
					$\Phi_h \pluseq (-1)^s \min_{\ell\in\mathcal{H}\setminus\{h\}}|L_\ell|$ \tcp*{extrinsic information}
				}
			}
		}
		\tcp{update intrinsic information}
		$\begin{cases}
		L_j \pluseq \mathrm{sign}(L_j)\cdot \frac{\Phi_j}{\mathrm{checks}_j} \quad\forall j \ \mathrm{s.t.}\ \mathrm{checks}_j\neq0$	\tcp*{\textcolor{Alin}{Add}}$\\
		L_j = L_j\cdot(1+\frac{3\Phi_j}{\max\Phi}) \text{, if } \Phi_j>0 \quad\forall j; \quad	L_j = L_j\cdot(1-\frac{3\Phi_j}{4\min\Phi}) \text{, if } \Phi_j<0 \quad\forall j$\tcp*{\textcolor{Aexp}{Mult}}$\\
		\end{cases}
		$

		\tcp{perform information set decoding}
		$G_{sorted} = $sort columns of $G$ according to reliability of $L_j$\;
		$I = $ pivot columns of $G_{sorted}$\;
		$r = \mathrm{hard}(L)$\;

		\tcp{apply flip-patterns}
		\For{$\forall e \in \mathcal{F}$}{
			$r_I = r|_I + e$\;
			$\hat{c} = r_I \cdot G_I^{-1} \cdot G$\;
		}
		\Return $\hat{c} = \mathrm{argmin}\left(\sum_j \left(r_j-(-1)^{\hat{c}_j}\right)^2\right)$
		\caption{Soft list information set decoding\label{LISD}}
	\end{algorithm}

	\subsection{Decoding Performance}

	\begin{figure}
		\centering
		{\includegraphics[]{bossert11}}
		\caption{Comparison LISD reliability estimation $\codename{3}{127,63,21}$ }
		\label{fig:BCH1}
	\end{figure}

	In Fig.~\ref{fig:BCH1} we show the simulation results of soft decision list information set
	decoding (LISD) of the BCH code $\codename{3}{127,64,21}$ with $1000$ flip-patterns, which are predetermined
	to minimize the WER. The reliability according to Eq.~(\ref{Aexp}) was used.
	The performance using only the intrinsic reliability from the channel (LISD Chan)
	is better than using the extrinsic reliability from one minimal weight dual codeword (LISD H)
	which corresponds to $n$ checks (instead of $n-k$ when using a parity check matrix H).
	The performance when using all minimal weight dual codewords for the extrinsic reliability (LISD)
	has not only a better performance than (LISD Chan) but also a steeper slope.
	The performance can be improved
	(LISD TH) when choosing out of all minimal weight dual codewords only those
	which have all but one checked positions within the $T$ best.
	The shown result is for $T=20$.

	In Fig.~\ref{fig:BCHRM1} the BCH code $\codename{3}{127,64,21}$ and the punctured RM code
	$\codename{4}{127,63,15}$
	are compared with soft decision list information set decoding (LISD). The reliability according to Eq.~(\ref{Aexp})
	and $1000$ flip-patterns are used. The latter are again selected such that the expected WER is minimized.
	The RM code (LISD RM) shows a performance close to the ML bound (ML Bound RM) and performs better than the BCH code (LISD BCH). Note that the decoding of the RM code can not be improved by using
	more flip-patterns since it is already close to the ML bound.
	However, using a threshold to select only the best checks
	(LISD BCH TH), the performance curve is crossing the ML bound of the RM code
	which is due to the different minimum distance of the codes.
	For comparison, the BMD hard decision curve (BMD hard BCH) is given.
	Using the reliability from the channel only (LISD Chan) the performance is
	worse as well as the slope.

	\begin{figure}
		\centering
		\subfloat[Different variants]
		{\includegraphics[]{bossert12}}
		\hfil
		\subfloat[Flip-patterns of size 100, 1000 ,2080, 10000 and 100000 \label{fig:BCH2}]
		{\includegraphics[]{bossert13}}

		\caption{Soft decision list information set decoding of $\codename{3}{127,64,21}$ and $\codename{4}{127,64,15}$\label{fig:BCHRM1}}
	\end{figure}

	Now we show that increasing the list size considerably improves the decoding performance.
	Different list sizes are compared in Fig.~\ref{fig:BCH2}.
	Again  the BCH code $\codename{3}{127,64,21}$ with the reliability according Eq.~(\ref{Aexp}) is simulated.
	As expected the performance improves with the list size. The performance of all one and two error patterns
	(LISD Combi) which are $2080$ flip-patterns
	is between $1000$ and $2080$ which shows that the selection of the patterns is improving the performance.
	We have added two points from \cite{Liva} at $2.5$ dB which are for decoding a polar code
	of length $128$ and $k=64$ and the worse performance is
	for successive cancellation (SC) decoding and the better is for list decoding.

	We compare information set decoding when using the damped Belief Propagation algorithm \cite{Gallager} to include extrinsic information before sorting the reliabilities.
	The updated reliabilities are calculated as
	\begin{equation}
	\left| \frac{2y_i}{\sigma^2} +2\alpha \sum_{j \in J(i)} \tanh^{-1} \left(\prod_{\ell \in I(j)\setminus\{i\}}\tanh\left(\frac{y_\ell}{\sigma^2}\right) \right) \right|,
	\end{equation}
	where $J(i)$ enumerates all check equations which include position $i$ and $I(j)$ enumerates all positions included in the $j$-th check equation.
	For regular BP decoding, the parity check matrix constitutes the check equations, however for our simulations we proceed in a slightly different manner:
	For the curves labeled with $h(x)$ we use $n$ shifts of the check polynomial, while the parity check matrix only consists of $n-k$ shifts.
	For the simulations labeled with $b(x)$ we use $n$ shifts of a minimum weight polynomial and for the $\mathcal{W}$-simulations all minimum weight dual codewords, i.e. $n$ shifts of all cyclically different minimum weight polynomials.
	Having optimized $\alpha$ empirically, we only show the results for the best tested value of $\alpha$.
	As flip-patterns, we use all patterns up to a certain Hamming weight, no optimization is applied.
	For both, $BCH(63,24,15)$ and $\codename{3}{127,64,21}$, preprocessing the LLRs with BP using the check polynomial leads to no improvement in WER over ISD without preprocessing.
	The same holds for $\codename{3}{127,64,21}$ when using a minimum weight polynomial.
	Here, however, a slight WER improvement is noticeable for $BCH(63,24,15)$: including the extrinsic information which can be generated with a single minimum weight polynomial and its shifts decreases the WER by a factor of two at $3\,$dB.

	For $BCH(63,24,15)$, using all minimum weight polynomials and their shifts provides a performance close to ISD($2$) despite only testing patterns of weight $\leq1$.
	In case of $\codename{3}{127,64,21}$, the use of the minimum weight polynomials provides a remarkable increase in steepness over the curve with ISD($2$), but no preprocessing.
	For higher SNRs, a performance close to ISD($3$) is attainable by testing only patterns of weight $\leq2$.
	This reduction in flip-patterns by a factor of $20$ is paid for by having to evaluate $1590\cdot 22 = 34980$ check equations per position prior to the information set decoding.

	\begin{figure}[h]
		\centering

		\subfloat[Results for $BCH(63,24,15)$ \label{fig_Soft_63_24_SPA}]
		{\includegraphics[]{bossert14}}
		\hfil
		\subfloat[Results for $\codename{3}{127,64,21}$ \label{fig_Soft_127_64_SPA}]
		{\includegraphics[]{bossert15}}

		\caption{Decoding with BP in conjunction with ISD.}
	\end{figure}

	\section{Conclusions}
	We have shown that erroneous codewords can be checked by minimal weight dual codewords and these checks
	provide reliability information for the received symbols.
	This reliability can be used for information set decoding even in a case of a BSC, which does not provide any reliability information.
	In many examples the decoding has the same performance as hard decision ML decoding
	which we have shown using an ML bound.
	Of the three decoding concepts, which are possible with the inherent reliability information,
	the information set decoding was superior.
	However, for the concept of redundancy set decoding, many open questions remain. But it has
	the advantage that a precalculated systematic generator matrix can be used.
	For soft decision list information set decoding
	we have derived that the use of the inherent reliability in addition to the channel reliability can improve the decoding performance.
	We recalled that any RM code can be described as a particular BCH code extended by a parity bit.
	We presented examples where the BCH codes show better performance than
	the punctured RM codes.

	\begin{appendix}
		Reed--Muller codes can be defined recursively using the Plotkin construction \cite{Plotkin}, however, the same set of codewords can also be obtained from a definition based on Boolean functions.
		We refer to a function $\mathrm{f}(v_0,\ldots,v_{m-1})$ as a Boolean function if it takes on the values $0$ and $1$ for any input tuple in $\mathbb{F}_{2}^m$.
		A Reed--Muller code of length $2^m$ is then the set of all Boolean functions of degree up to $r$ evaluated at all $2^m$ input $m$-tuples:
		\begin{equation*}
		\mathcal{R}(r,m) = \left\{\left(\mathrm{f}(i_0,\ldots,i_{m-1})\right)_{i=0}^{2^m-1} \mid
		\mathrm{f}(i_0,\ldots,i_{m-1}) = \sum_{\boldsymbol s} C_{\boldsymbol s} (i_0)^{s_0}\cdot\ldots\cdot(i_{m-1})^{s_{m-1}}\right\},
		\end{equation*}
		where $i = i_0 + i_1\cdot2+\ldots+i_{m-1}2^{m-1}$, the sum runs over all $\boldsymbol s=(s_0,\ldots,s_{m-1}) \in \{0,1\}^m$ such that $0\leq\sum_{t=0}^{m-1} s_t \leq r $ and $C_{\boldsymbol s} \in \mathbb F_{2}$.

		In the definition of the Reed--Muller code the Boolean functions were evaluated at $(i_0,\ldots,i_{m-1})$, where each $m$-tuple corresponded to the binary expansion of the respective code coordinate.
		However, now, we change the evaluation order and evaluate a Boolean function at $(a^{(i)}_{0},\ldots,a^{(i)}_{m-1})$, the coefficients of $\alpha^i \in \mathbb{F}_{2^m}^*$ when expressed through the polynomial basis $\{\alpha^0,\ldots,\alpha^{m-1}\}$, in order to obtain the value of the codeword at position $i$.
		Let $\alpha^{i}=a^{(i)}_{0}+a^{(i)}_{1}\alpha+\ldots+a^{(i)}_{m-1}\alpha^{m-1}$, the code
		\begin{equation*}
		\mathcal{R}(r,m)^* = \left\{\left(\mathrm{f}(a^{(i)}_{0},\ldots,a^{(i)}_{m-1})\right)_{i=0}^{2^m-2} \mid \mathrm{f}(a^{(i)}_{0},\ldots,a^{(i)}_{m-1}) = \sum_{\boldsymbol s} C_{\boldsymbol s} (a^{(i)}_{0})^{s_0}\cdot\ldots\cdot(a^{(i)}_{m-1})^{s_{m-1}}\right\}
		\end{equation*}
		is then a punctured and permuted RM code.
		First, we show that $\mathcal{R}(r,m)^*$ is cyclic.
		This is equivalent to showing that for all $\mathrm{f}(v_0,\ldots,v_{m-1})$, there exists a $\tilde{\mathrm{f}}(v_0,\ldots,v_{m-1})$, which satisfies
		\begin{equation}
		\mathrm{f}(a^{(i)}_{0},\ldots,a^{(i)}_{m-1}) = \tilde{\mathrm{f}}(a^{(i+1)}_{0},\ldots,a^{(i+1)}_{m-1})\quad
		\forall i \in \{0,\ldots,2^m-2\}.
		\end{equation}
		In $\mathbb{F}_{2^m}$, the multiplication of $\alpha^{i}$ with $\alpha$ is carried out modulo a primitive polynomial $\mathrm{p}(x)= x^m+\sum_{\ell=1}^{m-1} \mathrm{p}_{\ell}\cdot x^{\ell}+1$ with coefficients in $\mathbb{F}_{2}$. Therefore, we arrive at
		\begin{equation}
		\mathrm{f}(a^{(i)}_{0},\ldots,a^{(i)}_{m-1}) =
		\mathrm{\tilde{f}}(a^{(i)}_{m-1},a^{(i)}_{0}+\mathrm{p}_{1}a^{(i)}_{m-1},a^{(i)}_{1}+\mathrm{p}_{2}a^{(i)}_{m-1},\ldots,a^{(i)}_{m-2}+\mathrm{p}_{m-1}a^{(i)}_{m-1}).
		\end{equation}
		By applying substitution, one sees that a $\mathrm{\tilde{f}}(v_0,\ldots,v_{m-1})$ which satisfies this for all $i$ is given by
		\begin{equation}
		\mathrm{\tilde{f}}(v_0,\ldots,v_{m-1}) =
		\mathrm{f}(v_1+\mathrm{p}_1v_0,v_1+\mathrm{p}_2v_0,\ldots,v_1+\mathrm{p}_{m-1}v_0,v_0)
		\end{equation}
		and is of the same degree as $\mathrm{f}(v_0,\ldots,v_{m-1})$.
		Hence, $\mathcal{R}(r,m)^*$ is indeed cyclic.
		For $\mathcal{R}(r,m)$ the order of the evaluation tuples is given by the natural representation of the respective position as binary number.
		For the cyclic code $\mathcal{R}(r,m)^*$ the order is the vector representation of $\alpha^{i}$ using the polynomial basis.
		This proves the permutation given in \ref{subsec:equivalence}: $\pi$ maps $i$ to $j$ such that the binary expansion of $i$ is identical to the coefficients of $\alpha^j$ under the polynomial basis.

		Now, we find a generator polynomial of $\mathcal{R}(r,m)^*$.
		We need to find the roots of $\sum_{i=0}^{2^m-2} \mathrm{f}(a^{(i)}_{0},\ldots,a^{(i)}_{m-1})\ \alpha^{h\cdot i}$.

		Let $h = \sum_{t=0}^{m-1}h_t 2^t$ with $1\leq \sum_{t=0}^{m-1}h_t \leq m-r-1$ and $h_t\in\{0,1\}$, then
		\begin{equation}
		\alpha^{h\cdot i}
		=\left(\sum_{j=0}^{m-1} a^{(i)}_{j}\alpha^{j} \right)^{\sum_{t=0}^{m-1}h_t 2^t}
		=\prod_{t=0}^{m-1}\left(\sum_{j=0}^{m-1} a^{(i)}_{j}\alpha^{j} \right)^{h_t2^t}
		=\prod_{\{t:\ h_t=1\}} \sum_{j=0}^{m-1} a^{(i)}_{j}\alpha^{j2^t}
		\end{equation}
		Following \cite{Kasami}, we can expand the product as
		\begin{equation}
		\alpha^{h\cdot i} = \sum_{\boldsymbol \ell}\left(a^{(i)}_0\right)^{\ell_0}\cdot\ldots\cdot\left(a^{(i)}_{m-1}\right)^{\ell_{m-1}} \alpha^{\beta(h,\boldsymbol \ell)},
		\end{equation}
		where the sum runs over all $\boldsymbol \ell=(\ell_0,\ldots,\ell_{m-1})$ s.t. $1\leq\sum_{t=0}^{m-1} \ell_t = \sum_{t=0}^{m-1}h_t \leq m-r-1$.
		Utilizing that $\beta(h,\boldsymbol \ell)$ does not depend of $j$, we can reorder the sums and obtain
		\begin{equation}
		\sum_{i=0}^{2^m-2} \mathrm{f}(a^{(i)}_{0},\ldots,a^{(i)}_{m-1})\ \alpha^{h\cdot i}
		= \sum_{\boldsymbol \ell} \alpha^{\beta(h,\boldsymbol \ell)} \sum_{\boldsymbol s} C_{\boldsymbol s} \sum_{j=0}^{2^m-2} (a^{(i)}_{0})^{s_{0}+\ell_{0}}\cdot\ldots\cdot(a^{(i)}_{m-1})^{s_{m-1}+\ell_{m-1}},
		\end{equation}
		which is $0$ as the innermost sum is $0$:
		Due to the restrictions on $\boldsymbol \ell$ and $\boldsymbol s$, there is at least one $\gamma$ such that $s_\gamma+\ell_\gamma=0$.
		The sum goes through all $m$-tuples $(a^{(i)}_{0},\ldots,a^{(i)}_{m-1})$ in $\mathbb{F}_{2^m}^*$.
		Therefore, the summands $(a^{(i)}_{0})^{s_{0}+\ell_{0}}\cdot\ldots\cdot(a^{(i)}_{\gamma})^0\cdot\ldots\cdot(a^{(i)}_{m-1})^{s_{m-1}+\ell_{m-1}}$ and $(a^{(i)}_{0})^{s_{0}+\ell_{0}}\cdot\ldots\cdot(a^{(i)}_{\gamma}+1)^0\cdot\ldots\cdot(a^{(i)}_{m-1})^{s_{m-1}+\ell_{m-1}}$ add up to $0$.
		The $m$-tuple which has only a $1$ in position $\gamma$ would correspond to the all-zero tuple which is not in $\mathbb{F}_{2^m}^*$, note however that its summand is already $0$, as there is at least one $\theta$ s.t. $s_\theta+\ell_\theta\neq0$, because $h>0$ (in other words, $h=0$ has to be excluded as there would be a sum of an odd number of ones for $\ell=(0,\ldots,0)$).
		Hence, we have seen that all $\alpha^h$ with $1\leq\sum_{t=0}^{m-1}h_t \leq m-r-1$ are<<< roots of all codepolynomials respectively the generator polynomial.
		The number of $h$ which satisfy this restriction is
		\begin{align*}
		\binom{m}{1} +\ldots+ \binom{m}{m-r-1}
		= \binom{m}{m-1} +\ldots+ \binom{m}{r+1} \\
		= 2^m - 1 -\left[\binom{m}{0} +\ldots+ \binom{m}{r}\right]
		= 2^m -1 - \dim{\mathcal{R}(r,m)^*}.
		\end{align*}
		Hence, there can be no further roots of the generator polynomial.

	\end{appendix}

	\vspace{.2cm}

redpajama_set_name: RedPajamaArXiv


text:
\section{Introduction}

 \input{introduction-kurz.tex}

 \section{Background}

 \input{basics-kurz.tex}

\section{Rule Application on Shape Graphs}
 \label{sec:method}
 \input{rules-kurz.tex}

\section{Soundness of Technique}
 \label{sec:result}
 \input{results-kurz.tex}

\section{Implementation}
 \input{impl-kurz.tex}

\section{Conclusion and Related Work}

\label{sec:conclusion}
\input{conclusion-kurz.tex}

\bibliographystyle{alphaabb}