# Joint Repetition Suppression and Content Moderation of Large Language Models

###### Abstract

Natural language generation (NLG) is one of the most impactful fields in NLP,
and recent years have witnessed its evolution brought about by large language
models (LLMs). As the key instrument for writing assistance applications, they
are generally prone to replicating or extending offensive content provided in
the input. In low-resource data regime, they can also lead to repetitive
outputs (holtzman2019curious, ). Usually, offensive content and repetitions
are mitigated with post-hoc methods, including n-gram level blocklists, top-k
and nucleus sampling. In this paper, we apply non-exact repetition suppression
using token and sequence level unlikelihood loss, and further explore the
framework of unlikelihood training objective in order to jointly endow the
model with abilities to avoid generating offensive words and phrases from the
beginning. Finally, with comprehensive experiments, we demonstrate that our
proposed methods work exceptionally in controlling the repetition and content
quality of LLM outputs.

Keywords: unlikelihood loss, repetition suppression, content moderation

Minghui Zhang, Word + Editor<EMAIL_ADDRESS>
Alex Sokolov, Word + Editor<EMAIL_ADDRESS>
Weixin Cai, Word + Editor<EMAIL_ADDRESS>
Si-Qing Chen, Word + Editor<EMAIL_ADDRESS>

##  1 Introduction

Over the years, large language models have become more impactful as they are
being applied to an increasing range of features and products
(brants2007large, ; brown2020language, ). LLMs have been widely employed in
various writing assistance applications, aiding users in generating high-
quality, human-like text. However, despite their immense potential, LLMs often
struggle with certain limitations that prevent them from further mimicking
actual human-written content. Specifically, generations from LLMs sometimes
contain repetitions (holtzman2019curious, ) and controversial phrases
(political topics, racial topics, etc.). Repetition refers to the tendency of
LLMs to produce sentences or phrases that are either identical or very similar
to each other within the generated text. This can lead to a lack of diversity
in the output and cause the generated content to appear unnatural, monotonous,
or even nonsensical. The problem of repetition can be particularly severe in
low-resource data regimes where the model has limited training data to learn
from, leading to a higher likelihood of generating repetitive content. Another
significant challenge associated with LLMs is the generation of controversial
or offensive phrases. LLMs are trained on vast amounts of text data from the
internet, and as a result, they may inadvertently learn to generate content
that is politically biased, racially insensitive, or otherwise offensive. This
can pose a significant risk for applications that rely on LLMs for content
generation, as it may lead to the dissemination of harmful or inappropriate
content.

Currently, mainstream solutions for both problems are post-hoc, rule-based
methods, including n-gram level blocklists, top-k and nucleus sampling
(holtzman2019curious, ), which are suboptimal. Not only are they not effective
enough - words may go through post-filters if they are not exact matches, but
they also degrade the output by breaking its coherence.

To overcome these limitations, in this paper we first review the effectiveness
of repetition removal method based on sentence embedding, and then we adopt
token and sequence level unlikelihood training objective (welleck2019neural, )
as the non-exact repetition suppression solution. Furthermore, we extend the
unlikelihood training objective and customize it to jointly address a broader
range of problems. Finally, we demonstrate through experiments that our
approach Pareto-dominates the baseline method and can help suppress repetition
and moderate content with minimum impact to model performance.

##  2 Related Work

Various techniques have been proposed to tackle the repetition problem in
language models. Some of these methods include modifying the decoding
algorithm, such as using nucleus sampling (holtzman2019curious, ), top-k
sampling (fan2018hierarchical, ) and diverse beam search
(vijayakumar2016diverse, ). Another approach to suppress repetition is to
penalize repeated n-grams during the decoding process. Holtzman et al.
(holtzman2019curious, ) acknowledge the problem of repetition and propose a
new decoding strategy to mitigate it. Welleck et al. (welleck2019neural, ) try
to tackle this problem by customizing training objectives. Fu et al.
(fu2021theoretical, ) provide a theoretical framework to systematically
analyze the root cause of repetition and the reason behind existing
techniques.

Content moderation in LLMs aims to prevent the generation of offensive or
controversial content. Several methods have been proposed to mitigate this
issue, including the use of blocklists, adversarial training, reinforcement
learning from human feedback (ziegler2019fine, ), or rule-based filters. In
practice, post-processing filters like blocklists and offensiveness
classifiers are still most economic and prevalent.

##  3 Non-Exact Repetition Suppression

Since its inception, BERT (devlin2018bert, ) has been used as a tool for
encoding sentences and generating their representations. However, BERT isn’t
pre-trained to be natively support sentence similarity detection. SentenceBERT
(reimers2019sentence, ), being a solution to this issue, makes structural
changes on top of BERT for training and inference respectively with cosine-
similarity in mind. In practice, we calculate the similarity score for any two
sentences in a paragraph generated by the LLM, and only keep one sentence in
any pair with a score above a pre-determined threshold. This SentenceBERT-
based method is a great representative of repetition detection & removal
approaches. Figure 1 contains the architectures of SentenceBERT during
training (left) and inference (right).

Figure 1: Architecture of SentenceBERT(reimers2019sentence, )

As we discussed above in the introduction, repetition prevention is a more
ideal way to address the issue than post-hoc repetition removal. We adopt the
unlikelihood (UL) training objective in Welleck et al. (welleck2019neural, ).
Specifically, ordinary likelihood training objective minimizes the loss for
ground truth tokens:

$\mathcal{L}_{Likelihood}^{t}(p_{\theta}(\cdot|x_{<t}))=-\log
p_{\theta}(x_{t}|x_{<t})$ (1)

Where $p_{\theta}$ denotes the language model with parameters $\theta$, and
$t$ is the current time step.

In unlikelihood training objective, higher loss is applied to a set of tokens,
called negative candidates, and thus discourages the model from generating
them. Token-level UL objective defines negative candidates $C^{t}_{UL-token}$
as previous tokens within the target (ground truth).

$\mathcal{L}_{Unlikelihood}^{t}(p_{\theta}(\cdot|x_{<t}),C^{t})=\\\
-\alpha\sum_{c\in C^{t}}\log(1-p_{\theta}(c|x_{<t}))-\log
p_{\theta}(x_{t}|x_{<t})$ (2) $C^{t}=C^{t}_{UL-
token}=\\{x_{1},\ldots,x_{t-1}\\}\setminus\\{x_{t}\\}$ (3)

Coefficient $\alpha$ controls the proportion of the unlikelihood loss term.

Sequence-level UL objective follows the same principle, except that it defines
negative candidates as previous duplicate n-grams within the predicted
sequence.

$\begin{gathered}C^{t}=C^{t}_{UL-seq}=\\{x_{t}\\}\text{ if
}(x_{t-i},\ldots,x_{t+j})\in x_{<t-i}\\\ \text{ for any
}i+j+1=n\end{gathered}$ (4)

##  4 Content Moderation

The unlikelihood training objectives, with both token-level UL loss and
sequence-level UL loss, are not standalone loss functions. In fact, they
propose a platform with the concept of negative candidates, and having
repetition-related context can be seen as a special case. Based on this idea,
we further generalize the scope of negative candidates and define a new loss
term called “block loss”. In block loss, the negative candidates are defined
as blocklist phrases $B_{n}$ that we have collected in advance.

$C^{t}=C^{t}_{block}=\bigcup^{10}_{n=2}C^{t}_{block-n}$ (5)
$\begin{gathered}C^{t}_{block-n}=\\{x_{t}\\}\text{ if
}(x_{t-i},\ldots,x_{t+j})\in B_{n}\\\ \text{ for any }i+j+1=n\end{gathered}$
(6)

##  5 Experiments

First, we evaluate the performance of SentenceBERT-based post-processing
methods. Then, we compare different aspects of unlikelihood training
objectives. Lastly, we show the efficacy of our novel block loss in the
setting of sequence-level UL training objective.

Model | S-BERT threshold | Repeated Word Ratio | Repeated 4-word Phrase Ratio | BLEURT
---|---|---|---|---
Baseline | - | 40.553 | 0.017 | 0.501
Baseline + S-BERT | 0.91 | 40.419 | 0.017 | 0.501
Baseline + S-BERT | 0.8 | 39.171 | 0.013 | 0.500
Token-level UL Obj | - | 34.463 | 0.011 | 0.512
Table 1: Results for SentenceBERT and token-level unlikelihood objective

Model | ppl | acc | rep-128 | wrep-128 | seq-rep-1 | seq-rep-4 | uniq | uniq-seq |  human-seq-rep-1 |  human-seq-rep-4
---|---|---|---|---|---|---|---|---|---|---
Baseline | 11.786 | 0.521 | 0.795 | 0.586 | 0.667 | 0.506 | 7332 | 6929 |  |
Token-level UL Obj | 10.201 | 0.533 | 0.390 | 0.182 | 0.585 | 0.394 | 7468 | 7035 |  0.317 |  0.022
Seq-level UL Obj | 11.382 | 0.524 | 0.366 | 0.168 | 0.311 | 0.059 | 7491 | 7152 |  |

Model | ROUGE1-F | ROUGE2-F | ROUGEL-F | BERTScore | BLEURT |  perc-grammar-wrong |  count-grammar-wrong
---|---|---|---|---|---|---|---
Baseline | 0.496 | 0.207 | 0.324 | 0.289 | 0.501 |  0.034 |  0.145
Token-level UL Obj | 0.497 | 0.212 | 0.332 | 0.310 | 0.512 |  0.021 |  0.087
Seq-level UL Obj | 0.486 | 0.212 | 0.340 | 0.325 | 0.509 |  0.023 |  0.093

Table 2: Results for unlikelihood objectives

###  5.1 Experimental Setup

We use a sequence-to-sequence text rewriting task to evaluate the approaches
discussed in the sections above, with bullet points as inputs and paragraphs
as outputs. In practice, this task could translate to writing assistant
products or features capable of generating fluent documents based on user-
provided outlines.

We use pre-trained BART model (lewis2019bart, ) as the common starting point
and apply different training objectives during fine-tuning. The baseline model
is fine-tuned until convergence with regular likelihood loss. Another model is
fine-tuned from the starting point with token-level UL objective. The last
model is fine-tuned with sequence-level UL objective on top of the previous
model. Following Welleck et al. (welleck2019neural, ), sequence-level UL
objective is applied 50% of the time during fine-tuning, with the other 50% of
the time using model’s original token-level training objective.

Inputs are encoded by SentencePiece tokenizer (kudo2018sentencepiece, ).
Teacher forcing (williams1989learning, ) is applied during training to ensure
a faster and more stable convergence. We use beam search as the decoding
strategy with beam size 5 across all experiments. All training is done on an
Azure ML Compute instance with 4 Nvidia V100 16GB GPUs.

###  5.2 Data

Our data is in a simple format, as each data sample consists of one paragraph
as ground truth and its corresponding list of bullet points in pure text
format. The bullet is denoted by an asterisk ($*$), and the sub-bullet is
denoted by double asterisk ($**$). The size of the training set, validation
set, and test set are 45k, 6.6k, 1.4k respectively. Bullet points are
summarized by human annotators from paragraphs in public Word documents
corpus, and unqualified samples (too long, offensive, etc.) are removed in
advance. Below is one example sample of the dataset:

    {"bullet_points": "Evans, CMO of Subaru of
    America, Inc. (SOA) * 20+yrs experience *
    oversaw demand generation, brand awareness
    * customer engagement programs * SOA
    revenue increase ** 40% to 65%of parent
    company",

    "paragraph": "Evans boasts over 20 years of
    experience in the automotive industry, most
    recently as CMO of Subaru of America,
    Inc. (SOA). In that position, he oversaw
    demand generation, brand awareness and
    customer engagement programs that directly
    contributed to the company’s highest years
    of sales growth in its history. SOA’s
    revenue increased from 40% to 65% of parent
    company Fuji Heavy Industries’ (FHI)
    overall revenue during Evans’ tenure, with
    FHI’s stock the best performer on the
    Nikkei."}

For the evaluation of sequence-level training objective with block loss, we
use a subset of the original dataset, with 50% samples containing blocklist
phrases & 50% regular samples, in order to better demonstrate the results and
save computational cost.

###  5.3 Evaluation Metrics

We record an extensive range of metrics during evaluation in four categories:
language model metrics, repetition metrics, summarization/translation-based
metrics, and grammatical metrics. Below is a list of itemized metric
descriptions.

Language model metrics measure the basic capabilities of language models,
namely how well they can predict the next token.

  * •

Perplexity (ppl)

  * •

Next-token prediction accuracy (acc)

Repetition metrics measure the duplicativeness and uniqueness of generation on
both token level and sequence level.

  * •

Repetition (rep-$l$): the fraction of next-token prediction that occur in
previous $l$ tokens

  * •

Wrong repetition (wrep-$l$): similar to rep-$l$, but only counts token repeats
that are not equal to gold next token

  * •

Portion of duplicate 1-grams (seq-rep-1)

  * •

Portion of duplicate 4-grams (seq-rep-4)

  * •

Number of unique next-token predictions (uniq)

  * •

Number of unique tokens in the generated paragraph (uniq-seq)

Summarization/translation-based metrics measure the semantic consistency
between model’s input and output.

  * •

ROUGE (lin2004rouge, ): similarity between prediction & ground truth measured
with overlap n-grams & longest common subsequence

  * •

BERTScore (zhang2019bertscore, ): similarity between prediction & ground truth
measured with BERT representations

  * •

BLEURT (sellam2020bleurt, ): a transfer learning-based NLG metric

Grammatical metrics measure the prevalence of grammar mistakes in model
outputs, and thus monitor the impact on grammatical performance.

  * •

Percentage of sentences with grammar mistakes (perc-grammar-wrong)

  * •

Number of grammar mistakes per sentence (count-grammar-wrong)

###  5.4 Results

In table 1, SentenceBERT, as a post-hoc method, is Pareto dominated by
unlikelihood objectives regardless of former’s threshold choice, which
justifies our transition from post processing to custom training objective. In
table 2, token-level UL objective significantly reduces token repetition,
while additional training with sequence-level UL objective further reduces
repetitive n-grams by a huge margin. Overall, unlikelihood training objectives
help suppress repetition with minimum impact to performance.

Table 5 lists a set of generations from different models given the same
outline. Baseline output suffers from severe repetition problem whereas the
outputs of models trained with unlikelihood objectives do not, and thus
provide a better text semantically and syntactically. Outline contains
additional line breaks and indentations for better illustration. Ground truth
(the original paragraph) is also attached for reference.

In terms of training time, as shown in table 3, token-level unlikelihood
objective has a similar result as regular likelihood objective, which is
expected since the former can reduce to the latter when $\alpha=0$ in equation
(2). In contrast, sequence-level UL objectives are much more time-consuming.
This order-of-magnitude difference between two levels can be explained by the
iterative n-gram checks during the identification of sequence-level negative
candidates.

In table 4, sequence-level UL objective with our novel block loss reduces the
number of outputs containing unwanted blocklist phrases. Similarly, a set of
generations from different models as well as corresponding ground truth are
listed in table 6. The word ”abortion” is in the blocklist and successfully
avoided in the output of the model fine-tuned with sequence-level UL objective
with block loss.

Model | Training Time
---|---
Baseline | 25
Token-level UL Obj | 25
Seq-level UL Obj | 729
Seq-level UL Obj with block loss | 530
Table 3: Training time (seconds/100 steps) of unlikelihood objectives Model | beta |  # of outputs with blocklist phrases
---|---|---
Baseline | - |  119
Seq-level UL Obj with block loss | 10 |  84
Table 4: Results for sequence-level unlikelihood objective with block loss Outline |  PAML
* healthcare solutions company focused on diagnostics
** recognized for innovations
* joint venture partnerships leader w/ community hospitals
---|---
Baseline |  PAML is a healthcare solutions company focused on diagnostics and has been recognized for its innovations in diagnostic and diagnostic technology. PAML has been a joint venture partnerships leader with community hospitals in the United States, Canada, Australia, and the United Kingdom. In addition to providing a wide range of diagnostic services to patients and their families, PAML has also been recognized as one of the world’s leading healthcare solutions companies in the field of diagnostic, diagnostic, and diagnostical diagnostic technologies.
Token-level UL Obj |  PAML is a healthcare solutions company focused on diagnostics. PAML has been recognized as one of the world’s leading innovators in the field of medical imaging and medical diagnostic technology. The company’s Joint Venture Partnerships are a leader in partnerships with community hospitals across the United States and internationally. The joint venture partnerships provide a unique opportunity to collaborate with a wide range of healthcare providers across the globe.
Seq-level UL Obj |  PAML is a healthcare solutions company focused on diagnostics. PAML has been recognized as one of the world’s leading innovators in the field of diagnostic technology. The company’s Joint Venture Partnerships is a leader in partnerships with community hospitals across the U.S. and internationally. The joint venture partnerships are designed to provide high-quality, high-performing diagnostic services to patients with complex medical conditions.
Ground Truth |  PAML, LLC, a healthcare solutions company with a focus in diagnostics, is headquartered in Spokane, WA. One of the top reference laboratories in the country, PAML is also nationally recognized for innovations in clinical diagnostics. PAML is also an industry leader in joint venture partnerships with community-based hospitals because of their expertise in developing cutting-edge laboratory management systems, including state-of-the-art automation and support services. PAML is a founding member of PACLAB, with the largest outreach lab market share in the region.
Table 5: Example outputs from models fine-tuned with unlikelihood objectives Outline |  Abortion
* Malta = illegal
** explains increase in deaths due congenital malformations
* where legal
** pregnancies are terminated b4 fetus is delivered
---|---
Baseline |  In Malta, abortion is illegal. This explains the increase in the number of deaths due to congenital malformations. Where legal, pregnancies are terminated b4 the fetus is delivered. In the case of a woman who is pregnant at the time of the abortion, the pregnancy is terminated, and the mother is not able to give birth to the child. The mother is unable to provide the child with a safe, safe, and safe environment for the delivery of the child.
Seq-level UL Obj with
Block Loss |  In the Republic of Malta, it is illegal to carry out an unplanned pregnancy without the consent of the mother. This explains why there has been an increase in deaths due to congenital malformations. However, in other countries where it is legal, pregnancies are terminated after the fetus is delivered. This is not the case in England and Wales, where it has been shown that there are many cases where women who do not have access to medical care are forced to leave the country.
Ground Truth |  The comparability of these figures to those of other countries is undermined by the fact that, in contrast to many other countries, abortion in Malta is illegal. This may partly explain the increase in the proportion of deaths due to congenital malformations, deformations and chromosomal abnormalities (Q00-Q99), which are largely unpreventable. Whereas in countries where abortion is legal these pregnancies are likely to be terminated before the fetus is delivered, in Malta such cases may possibly live for a few minutes, hours or days, after delivery, in which case they are included in the perinatal, neonatal, infant and under-five mortality rates.
Table 6: Example outputs from model fine-tuned with sequence-level
unlikelihood objective with block loss

##  6 Conclusions & Future Work

In this paper, we explored a joint effort of non-exact repetition suppression
and content moderation to address the limitations of LLMs in generating
repetitive and offensive content. We first set up SentenceBERT as a baseline
of repetition detection & post-processing methods. Then, we utilized multiple
levels of unlikelihood training objectives to suppress repetition at the step
of generation. Finally, we exploited and further generalized the unlikelihood
training objective and brought it into the field of content moderation. We
demonstrated that our proposed methods work exceptionally well in controlling
the repetition and content quality of LLM outputs. The results showed that
multi-level unlikelihood training objectives and our novel block loss greatly
reduce token repetition, repetitive n-grams and offensive content while
maintaining minimum impact on model performance.

In the future, we plan to explore more possibilities for the unlikelihood
objective framework and negative candidates, as well as expanding the
potential applications of our proposed methods in more complex NLP scenarios.
Additional investigation could be performed on the impact of the size and
prevalence of the blocklist.

## References

  * (1) A. Holtzman, J. Buys, L. Du, M. Forbes, and Y. Choi, “The curious case of neural text degeneration,” arXiv preprint arXiv:1904.09751, 2019.
  * (2) T. Brants, A. C. Popat, P. Xu, F. J. Och, and J. Dean, “Large language models in machine translation,” 2007.
  * (3) T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al., “Language models are few-shot learners,” Advances in neural information processing systems, vol. 33, pp. 1877–1901, 2020.
  * (4) S. Welleck, I. Kulikov, S. Roller, E. Dinan, K. Cho, and J. Weston, “Neural text generation with unlikelihood training,” arXiv preprint arXiv:1908.04319, 2019.
  * (5) A. Fan, M. Lewis, and Y. Dauphin, “Hierarchical neural story generation,” arXiv preprint arXiv:1805.04833, 2018.
  * (6) A. K. Vijayakumar, M. Cogswell, R. R. Selvaraju, Q. Sun, S. Lee, D. Crandall, and D. Batra, “Diverse beam search: Decoding diverse solutions from neural sequence models,” arXiv preprint arXiv:1610.02424, 2016.
  * (7) Z. Fu, W. Lam, A. M.-C. So, and B. Shi, “A theoretical analysis of the repetition problem in text generation,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, pp. 12848–12856, 2021.
  * (8) D. M. Ziegler, N. Stiennon, J. Wu, T. B. Brown, A. Radford, D. Amodei, P. Christiano, and G. Irving, “Fine-tuning language models from human preferences,” arXiv preprint arXiv:1909.08593, 2019.
  * (9) J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” arXiv preprint arXiv:1810.04805, 2018.
  * (10) N. Reimers and I. Gurevych, “Sentence-bert: Sentence embeddings using siamese bert-networks,” arXiv preprint arXiv:1908.10084, 2019.
  * (11) M. Lewis, Y. Liu, N. Goyal, M. Ghazvininejad, A. Mohamed, O. Levy, V. Stoyanov, and L. Zettlemoyer, “Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension,” arXiv preprint arXiv:1910.13461, 2019.
  * (12) T. Kudo and J. Richardson, “Sentencepiece: A simple and language independent subword tokenizer and detokenizer for neural text processing,” arXiv preprint arXiv:1808.06226, 2018.
  * (13) R. J. Williams and D. Zipser, “A learning algorithm for continually running fully recurrent neural networks,” Neural computation, vol. 1, no. 2, pp. 270–280, 1989.
  * (14) C.-Y. Lin, “Rouge: A package for automatic evaluation of summaries,” in Text summarization branches out, pp. 74–81, 2004.
  * (15) T. Zhang, V. Kishore, F. Wu, K. Q. Weinberger, and Y. Artzi, “Bertscore: Evaluating text generation with bert,” arXiv preprint arXiv:1904.09675, 2019.
  * (16) T. Sellam, D. Das, and A. P. Parikh, “Bleurt: Learning robust metrics for text generation,” arXiv preprint arXiv:2004.04696, 2020.


# Hybrid Non-Binary Repeated Polar Codes

Fariba Abbasi, Member, IEEE, Hessam Mahdavifar, Member, IEEE, and Emanuele
Viterbo, Fellow, IEEE
This paper was presented in part at IEEE International Symposium on
Information Theory (ISIT), Melbourne, Australia, July, 2021, [10].
Fariba Abbasi was with the Department of Electrical and Computer Systems
Engineering (ECSE), Monash University, Melbourne, VIC3800, Australia. She is
now with the Department of Electrical Engineering and Computer Science (EECS),
University of Michigan, Ann Arbor, MI 48104 (E-mail: fabbasia@umich.edu).
Emanuele Viterbo is with the Department of Electrical and Computer Systems
Engineering (ECSE), Monash University, Melbourne, VIC3800, Australia (E-mail:
emanuele.viterbo@monash.edu).
Hessam Mahdavifar is with the Department of Electrical Engineering and
Computer Science (EECS), University of Michigan, Ann Arbor, MI 48104 (E-mail:
hessam@umich.edu).

###### Abstract

Concatenating the state-of-the-art codes at moderate rates with repetition
codes has emerged as a practical solution deployed in various standards for
ultra-low-power devices such as in Internet-of-Things (IoT) networks. In this
paper, we propose a novel concatenation mechanism for such applications which
need to operate at very low signal-to-noise ratio (SNR) regime. In the
proposed scheme, the outer code is a hybrid polar code constructed in two
stages, one with a binary kernel and another also with a binary kernel but
applied over a binary extension field. The inner code is a non-binary
multiplicative repetition code. This particular structure inherits low-
complexity decoding structures of polar codes while enabling concatenation
with an inner non-binary multiplicative repetition scheme. The decoding for
the proposed scheme is done using cyclic redundancy check (CRC) aided
successive cancellation list (SCL) decoder over additive white Gaussian noise
(AWGN) and Rayleigh fading channels. Simulation results demonstrate that the
proposed hybrid non-binary repeated polar code provides performance gain
compared to a polar-repetition scheme with comparable decoding complexity.

Index terms – Polar codes, repetition codes, concatenation codes, low SNR
regime, cyclic redundancy check (CRC) aided successive cancellation list (SCL)
decoder.

##  I Introduction

The Third Generation Partnership Project (3GPP) has recently introduced
Narrow-Band Internet-of-Things (NB-IoT) and enhanced Machine-Type
Communications (eMTC) features into the cellular standard protocols. These two
narrow-band and complementary technologies expand the cellular networks to
support low-power, wide-area (LPWA) cellular connectivity for a wide range of
IoT use cases [4].

In general, IoT devices need to operate under extreme power constraints.
Consequently, they often communicate at very low signal-to-noise ratio (SNR),
e.g., $-13$ dB or $0.03$ bits per transmission (translated to capacity) in NB-
IoT protocols [4]. Also, they are often not equipped with advanced
transceivers due to cost constraints. Therefore, the solution adopted in the
standard is to use the legacy turbo codes or convolutional codes at moderate
rates, e.g., the turbo code of rate $1/3$, together with many repetitions,
e.g., up to $2048$ repetitions in NB-IoT. This implies effective code rates as
low as $1.6\times 10^{-4}$ are supported in such protocols. This repetition
scheme has efficient implementations with computational complexity and latency
effectively reduced to that of the outer code. However, it is expected that
repeating a high-rate code to enable low-rate communication will result in
rate loss and mediocre performance. As a result, studying ultra-low-rate
error-correcting codes for reliable communications in such low-capacity
regimes becomes necessary [1].

In [1], the authors constructed an efficient repetition scheme with outer
polar codes and showed that the proposed polar-repetition scheme outperforms
the Turbo-repetition code, the proposed code design in the eMTC and NB-IoT
(uplink) standards, over additive white Gaussian noise (AWGN) channel. In
another related work, low-rate codes for binary symmetric channels were
constructed by concatenating high-rate polar codes with repetitions [5]. Also,
non-binary LDPC codes concatenated with multiplicative repetition codes were
introduced in [6]. By multiplicatively repeating the $(2,3)$-regular non-
binary LDPC mother code of rate $1/3$, they constructed rate-compatible codes
of lower rates $1/6,1/9,1/12,\ldots$ which outperform the best low-rate binary
LDPC codes at the cost of the increase in decoding complexity. Very recently,
weakly-coded binary LDPC type code combined with polar code has been
introduced in [7], [8] which is shown to outperform uncoded modulation over
high noise memoryless channels. However, the complexity of the proposed scheme
in [7] and [8] is higher than that of a repetition-based scheme.

In [11], we proposed polar coded repetition to improve the asymptotic
achievable rate of the repetition scheme, while ensuring that the overall
encoding and decoding complexity is kept almost the same. A slightly modified
polar codeword is transmitted in each repetition block by deviating from
Arıkan’s standard $2\times 2$ kernel in a certain number of polarization
recursions at each repetition block. It is shown that the polar coded
repetition outperforms the polar-repetition, in terms of the asymptotic
achievable rate, for any given number of repetitions over the binary erasure
channel (BEC).

In this paper, we propose an alternative mechanism for polar-repetition
schemes, referred to as hybrid non-binary multiplicative repetition. In this
scheme, the outer code is a hybrid binary and non-binary polar code
constructed in two stages. The first stage of the outer encoder utilizes
Arıkan’s binary polarization kernel applied recursively, as in original polar
codes [2]. The output bits of the first stage are grouped into $t$-tuples and
are turned into symbols over the extension binary field $GF(2^{t})$. Then
Arıkan’s kernel is again applied recursively. Hence, the output of the outer
encoder consists of symbols over $GF(2^{t})$. The inner code is a non-binary
multiplicative repetition code.

The motivation behind constructing the outer code in two stages is to improve
the decoding performance by capturing the correlation of the bits within each
symbol in the decoding process. The encoded symbols can be either turned into
binary strings for transmission using a binary modulation scheme, e.g., binary
phase shift keying (BPSK) or, alternatively, can be sent using a higher order
modulation. The proposed structure allows for i) benefiting from the
multiplicative repetition over an extension field as opposed to a simple
repetition in a binary polar-repetition scheme, and ii) keeping the complexity
of the encoder/decoder almost the same as that of the polar-repetition scheme.
The simulation results show that with increasing list size in the CRC-aided
SCL decoder, the proposed hybrid non-binary repeated polar code provides
significant performance gain compared to a polar-repetition scheme with
comparable decoding complexity over AWGN and Rayleigh fading channels.
Alternatively, the proposed scheme results in lower decoding complexity
compared to the polar-repetition scheme with the same performance.

The rest of this paper is organized as follows. In Section II, we review some
basics of polar codes as well as repetition codes. In Section III, we discuss
the proposed scheme. The numerical results are discussed in Section IV.
Finally, Section V concludes the paper.

##  II Background

In this section, a brief background on polar codes, their successive
cancellation (SC) and cyclic redundancy check-aided successive cancellation
list (CRC-aided SCL) decoders, as well as some background on repetition
schemes, a simple and efficient scheme for low-capacity applications, are
discussed.

###  II-A Polar Codes

An $(n,k,\mathcal{F})$, with $n=2^{m}$, polar code based on the $2\times 2$
polarization kernel $G_{2}=\footnotesize\begin{pmatrix}1&0\\\
1&1\end{pmatrix}$ is a linear block code generated by $k$ rows of
$G_{n}=G_{2}^{\otimes m}$, where $.^{\otimes m}$ is the $m$-th Kronecker power
of a matrix [2]. The set of frozen bits $\mathcal{F}$, with
$|\mathcal{F}|=n-k$, is the set of the indices of sub-channels with the lowest
reliabilities. Arıkan’s polar codes are constructed by setting entries of the
input vector $u_{0}^{n-1}$111$u_{0}^{n-1}$ is a row vector
$(u_{0},u_{1},\ldots u_{n-1})$ and $u_{0}^{i}$ is its subvector
$(u_{0},u_{1},\ldots u_{i})$. indexed by $\mathcal{F}$ to some pre-defined
values, e.g. zero, and the remaining $k$ bits are used to transmit the
information. At the decoder side, the SC decoder, makes the decision on
$u_{i}$, based on the previously decoded bits, $\hat{u}_{0}^{i-1}$, and
channel output vector, $y_{0}^{n-1}$, according to the following log
likelihood ratio (LLR) rule:

$\hat{u}_{i}=\begin{cases}1,\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \textup{if}\ \ \ i\in\mathcal{F}^{C}\ \&\\\ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \
\ln\frac{W_{n}^{(i)}(\hat{u}_{0}^{i-1},y_{0}^{n-1}|u_{i}=0)}{W_{n}^{(i)}(\hat{u}_{0}^{i-1},y_{0}^{n-1}|u_{i}=1)}<0\\\
\text{the frozen value of $u_{i}$},\ \ \ \ \textup{if}\ \ \
i\in\mathcal{F},\end{cases}$ (1)

where $W_{n}^{(i)}$ is the $i$-th bit-channel [2].

In order to improve the error correction performance of the SC decoder, the
successive cancellation list (SCL) decoding algorithm was proposed by Tal and
Vardy in [3]. In SCL decoding, the $L$ most likely paths $u_{0}^{i-1}$ are
tracked. When decoding $u_{i}$, for $i\in\mathcal{F}^{C}$, the decoder extends
each path into two paths exploring both possibilities $u_{i}=0$ and $u_{i}=1$.
If the number of obtained paths exceeds $L$, the decoder picks $L$ most likely
paths as the surviving ones and prunes the rest based on a certain Path Metric
(PM). Let $\hat{u}_{i}[l]$ denote the estimate of $u_{i}$ in the $l$-th path,
for $l\in\\{1,2,\ldots,L\\}$ and $S_{i}[l]$ denote its corresponding LLR. Then
the corresponding PM is calculated as follows:

$PM_{l}^{(i)}=\begin{cases}PM_{l}^{(i-1)}+|S_{i}[l]|\ \ \textup{if}\
\hat{u}_{i}[l]\neq\frac{1}{2}(1-\textup{sgn}(S_{i}[l]))\\\ PM_{l}^{(i-1)}\ \ \
\ \ \ \ \ \ \ \ \ \ \textup{otherwise},\end{cases}$ (2)

where $PM_{l}^{(-1)}$ is set to $0$. Finally, the path with the smallest PM is
selected as the estimated bits $\hat{u}_{0}^{n-1}$. As the list size $L$ grows
large, the SCL decoder approaches the maximum-likelihood (ML) decoding
performance. To further improve the performance of the SCL decoder, $p$-bits
cyclic redundancy check (CRC) are appended to the information bits as an outer
code. The SCL decoder outputs the decoding path with the smallest PM among the
paths which pass the CRC [9]. Remarkably, Polar-CRC schemes have been adopted
for control channels in the fifth generation of wireless networks (5G) due to
demonstrating the state-of-the-art performance for a wide range of code
parameters [13]. Polar codes and polarization phenomenon have been also
successfully applied to a wide range of problems including data compression
[14, 15], broadcast channels [16, 17], multiple access channels [18, 19],
joint detection and decoding [24], physical layer security [20]–[23], fading
channels [25]–[27], and coded modulation [28, 29].

###  II-B Repetition Schemes

In low-capacity applications, a straightforward way of designing practical
low-rate codes, that is also adopted in the standard, is through repetition
schemes. Let $r$ denote the number of the repetitions and $N$ denote the total
length of the code. For constructing a repetition scheme, first, a smaller
outer code (e.g., a polar code) of length $n=N/r$ is designed and then each of
its coded bits is repeated $r$ times. The main advantage of repetition schemes
is the relatively low computational complexity of their encoding and decoding
algorithms, especially when $r$ is large. This is because the
encoding/decoding complexity is effectively reduced to that of the outer code.
Once the outer code is constructed, at the encoder, one just needs to repeat
each of the coded bits $r$ times. At the decoder, the LLR of a coded bit
repeated $r$ times is equal to the sum of the $r$ LLRs of the individual
transmission. While this looks promising, one should note that the main
drawback of repetition schemes is the loss in capacity. In general, we have
$C(W^{r})\leq rC(W)$, where $W^{r}$ is the channel resulting from repeating
$r$ times transmission across $W$, and $C(\cdot)$ is the channel capacity.
Note also that the ratio $C(W^{r})/rC(W)$ vanishes as $r$ grows large.
Consequently, for very large $r$, the repetition code might suffer from an
unacceptable rate loss [1].

##  III The Proposed Scheme

As mentioned in Section II-B, the polar-repetition code is a practical scheme
for low-capacity scenarios due to its low encoding/decoding complexity.
However, from a channel coding prospective, repeating a high rate polar code
to enable low-rate communication is sub-optimal [1]. To improve the
performance of the polar-repetition scheme in low-capacity regime, we propose
the hybrid non-binary repeated polar code scheme: the concatenation of a
binary polar code with a non-binary random multiplicative repetition code. In
this scheme, the codewords are not generated by simple repetitions of the
polar code but by random multiplicative repetitions of the non-binary symbols.
Our simulation analysis of the proposed scheme under SC and CRC-aided SCL
decoders shows that concatenating with random non-binary multiplicative
repetition code improves the polarization rate of the code and reduces the
number of the low-weight codewords (see Sec. IV).

A potential solution to benefit from the random non-binary multiplicative code
would be to concatenate it with non-binary polar codes. A similar solution is
proposed in the context of LDPC coding, where gains are observed with
multiplicative random non-binary LDPC codes compared to binary LDPC codes in
the low-rate regime [7]. However, in the context of polar coding, the decoding
complexity of non-binary polar codes is often very high for practical
scenarios such as IoT, where the devices are required to be low complexity and
low cost. Therefore, in this paper, we consider the binary polar codes as the
outer code. In general, a straightforward way of concatenating a binary polar
code with a non-binary one would result in a loss of the correlation
information between the bits in a symbol and render the advantage of the non-
binary outer code. However, our proposed scheme overcomes this problem by
splitting the outer code into two stages to capture such correlation in the
decoding process.

Owing to the recursive structure of the polar codes, one can consider the
polarization transform kernel $G_{n}$ as the concatenation of $G_{n/t}$ and
$G_{t}$, with $G_{n}=G_{n/t}\otimes G_{t}$, where
$t=2^{m^{\prime}},m^{\prime}=\\{1,2,3,\ldots,\\}$, [31]. Figure 1 (a) shows
the block diagram of the encoder of the polar code with this structure, where
$x_{0}^{n-1}$ is the output of the transformation $G_{t}$. Figure 1 (c) shows
the structure of the polar-repetition. In this scheme, the outer code is the
polar code depicted in Figure 1 (a) and the inner code is the repetition code
which repeats the output of the outer polar code, $z_{0}^{n-1}$, $r$ times and
generates code $C_{r}$ as follows.

$\displaystyle C_{r}$ $\displaystyle=\\{c_{0}^{rn-1}|c_{(r-1)n+v}=z_{v},$ (3)
for $\displaystyle\ \ v=\\{0,\ldots,n-1\\},\ \ c_{0}^{(r-1)n-1}\in
C_{r-1}\\}.$

To improve the performance of the polar-repetition, the scheme depicted in
Figure 1 (b) and (d) is proposed. The encoder and decoder of the proposed
hybrid non-binary repeated polar codes are as follows.

Figure 1: (a) Layered factor graph representation of a polar code (b) Layered
factor graph representation of the proposed hybrid non-binary polar code (c)
Polar-repetition scheme (d) Hybrid non-binary repeated polar codes scheme.

###  III-A Encoding of the Proposed Hybrid Non-Binary Repeated Polar Codes

For encoding the proposed scheme, in the first stage, the binary input bits
$u_{0}^{n-1}$ are divided into subsets of bits of size $t$. Then, each of
these $n/t$ $t$-tuples are encoded with binary polarization kernel $G_{t}$
over $GF(2)$ and the output is $x_{0}^{n-1}$. In the second stage, each of
these outputs are grouped together as a $2^{t}$-bit symbol $a_{i}$,
$a_{i}=(x_{it},x_{it+1},\ldots x_{(i+1)t-1})\in GF(2^{t})$,
$i=\\{0,1,\ldots,n/t-1\\}$. Then, the symbols $a_{0}^{n/t-1}$ are encoded with
the binary polarization kernel $G_{n/t}$ over $GF(2^{t})$ and generate code
$C_{1}=\\{z_{0}^{n/t-1}\in GF{(2^{t})}\\}$. Finally, coefficients
$\rho_{n/t}^{rn/t-1}$ are chosen at random from $GF(2^{t})\setminus\\{0\\}$
and are multiplied by $z_{0}^{n/t-1}$ to generate the code $C_{r}$, $r>1$, as
follows.

$\displaystyle C_{r}$
$\displaystyle=\\{c_{0}^{rn/t-1}|c_{(r-1)n/t+v}=\rho_{(r-1)n/t+v}z_{v},$ (4)
for $\displaystyle\ \ v=\\{0,\ldots,n/t-1\\},\ \ c_{0}^{(r-1)n/t-1}\in
C_{r-1}\\}.$

Note that the coefficients $\rho_{(j-1)n/t}^{jn/t-1}$, $j=\\{2,3,\ldots,r\\}$
are the random multiplication coefficients for the $j$-th repetition.
Algorithm 1 shows the process of encoding the proposed scheme. The inputs to
this algorithm are binary input bits $u_{0}^{n-1}$, $t$, $n$ and $r$. The
outputs is the code $C_{r}$. The $\leftarrow$ symbol denotes appending an
element to a list.

1

input : $u_{0}^{n-1},t,n,r$

output : Code $C_{r}$

2 Divide $u_{0}^{n-1}$ into sets of $t$ bits, $u_{it}^{(i+1)t-1}$,
$i=\\{0,1,\ldots,n/t-1\\}$.

3

4for  _$i=0$ to $n/t-1$_ do

5 $x_{it}^{(i+1)t-1}=$ Encode each sets of bits, $u_{it}^{(i+1)t-1}$, with
binary kernel $G_{t}$ over $GF(2)$.

6 Group $x_{it}^{(i+1)t-1}$ together to make a $t$-bit symbol $a_{i}$.

7 end for

8$C_{r}=\\{z_{0}^{n/t-1}\\}\leftarrow$ Encode $a_{0}^{n/t-1}$ symbols with
binary kernel $G_{n/t}$ over $GF(2^{t})$.

9

10for  _$j=2$ to $r$_ do

11 $C_{r}\leftarrow$ Choose $n/t$ coefficients $\rho_{(j-1)n/t}^{jn/t-1}$
uniformly at random from $GF(2^{t})\setminus\\{0\\}$, multiply them with
$z_{0}^{n/t-1}$.

12 end for

return $C_{r}$

Algorithm 1 Encoding Algorithm of the Proposed Hybrid Non-binary Repeated
Polar Codes

The outer encoding only requires standard binary polar encoding followed by
binary to $2^{t}$-ary conversion. In the decoding process, and in order to
capture the correlation of the bits in a symbol, the conversion from binary to
$2^{t}$-ary is done between Stage 1 and Stage 2 of decoding.

Note that the authors in [30] constructed mixed kernels over alphabets of
different sizes and improved the polarization properties of the kernel
$G_{n}$. However, in this paper, by using the structure of the kernel $G_{n}$,
we group the binary bits into symbols without modifying the polarization
kernel $G_{n}$.

Example 1: Figure 2 (a) shows an example for $n=8$, $r=3$, and $t=4$. The
polarization kernels of stage 1 and 2 are $G_{4}=B_{4}G_{2}^{\otimes 2}$ and
$G_{2}$, respectively, where $B_{4}$ is the bit-reversal permutation matrix.
By choosing the primitive $\alpha\in GF(2^{4})$ with
$\pi(\alpha)=\alpha^{4}+\alpha+1=0$, the output codewords of this example are
$c_{0}^{5}=(1,\alpha^{13},\alpha^{8},\alpha^{4},\alpha^{4},\alpha^{14})$.

Figure 2: Equivalent encoders for the proposed scheme for $n=8$, $r=3$, $t=4$
based on (a) Algorithm 1 and (b) Algorithm 2.

The encoded symbols $c_{i}$ are turned into binary strings for transmission
over AWGN and Rayleigh fading channels using the BPSK modulation scheme, with
the received signals for these two channels given by

$y_{i}=(c_{i})_{M}+w_{i},\ \ \ i=\\{1,2,\ldots,N\\}$

and

$y_{i}=h_{i}(c_{i})_{M}+w_{i},\ \ \ i=\\{1,2,\ldots,N\\},$

respectively, where $(c_{i})_{M}$ is the modulated codeword, $h_{i}$ is the
channel gain with Rayleigh distribution and $w_{i}$ is a zero mean Gaussian
noise, $w_{i}\sim\mathcal{N}(0,\sigma^{2})$. Here, we assume that $h_{i}$ and
$w_{i}$ are independent, the receiver knows the channel state information
(CSI) and the transmitter knows only the distribution of the CSI.

In the block fading channel model, a transmission frame of $N$ symbols is
affected by $1\leq B\leq N$ dependent fading realizations, resulting in a
block of $\tau=N/B$ symbols being affected by the same fading realization.
Different values $B$ represents different types of fading, e.g., $B=1$ is
referred to fast fading and $B=N$ is referred to slow fading.

###  III-B SCL Decoding of the Proposed Hybrid Non-Binary Repeated Polar Codes

For decoding the proposed scheme, we use CRC-aided LLR-based SCL decoder.
Algorithm 3 shows the details of the process. The SCL decoding of the proposed
scheme involves mainly 4 parts, i.e. the initial LLRs, the LLRs of the
multiplicative repetition, the LLRs of Stage $1$ and the LLRs of Stage $2$ of
the outer polar code. The details of the LLRs calculations are as follow.

Initial LLRs: The initial LLRs of the $i$-th symbol,
$i\in\\{0,1,\ldots,rn/t-1\\}$, with symbol value $s\in GF(2^{t})$ for AWGN and
block fading channels are defined as

${S}_{in,i}^{(s)}=\ln{\frac{W(y_{i}|(c_{i})_{M}=0_{M})}{W(y_{i}|(c_{i})_{M}=s_{M})}},$
(5)

and

${S}_{in,i}^{(s)}=\ln{\frac{W(y_{i}|(c_{i})_{M}=0_{M},h_{i})}{W(y_{i}|(c_{i})_{M}=s_{M},h_{i})}},$
(6)

respectively. Let us denote ${S}_{in,i}=\\{S_{in,i}^{(s)}\\}_{s\in
GF(2^{t})}$, the vector of the $i$-th initial LLRs for all possible symbols
$s$ over $GF(2^{t})$.

LLRs of the multiplicative repetition: Since $GF(2^{t})$ is a finite field,
the non-zero elements can be expressed as powers of a primitive element
$\alpha$ in the field, i.e., $1,\alpha,\dots,\alpha^{2^{t}-2}$. Therefore,
multiplication by an arbitrary non-zero symbols $\rho_{j}=\alpha^{\tau}$,
$j=\\{n/t,\ldots,rn/t-1\\}$, can be regarded as a cyclic shift of the field
elements by $\tau$. As a result, the decoder permutes the LLR vector
${S}_{in,i}$ and outputs the vector $\pi_{\rho_{j}}({S}_{in,i})$.

Finally, the LLR of an $r$-tuple consisting of $r$ independent transmissions
of symbols is equal to sum of the LLRs of the individual channel outcomes
after the permutations (see lines 2-8 of the Algorithm 3).

LLRs update of Stage $2$: In general, the LLR of the $i$-th symbol,
$i\in\\{0,1,\ldots,n-1\\}$ , with symbol value $s$ over kernel $G_{n}$, can be
calculated according to the following formula, [2]:

$\displaystyle S_{i}^{(s)}$
$\displaystyle\overset{\Delta}{=}\ln\frac{\sum_{u_{i+1}^{n-1}}R_{G_{n}}(\hat{u}_{0}^{i-1},0,u_{i+1}^{n-1})}{\sum_{u_{t+1}^{n-1}}R_{G_{n}}(\hat{u}_{0}^{i-1},s,u_{i+1}^{n-1})},$
(7)

where $R_{G_{n}}(u)=\exp(-\sum_{j=0}^{n-1}S_{j}^{(x_{j})})$ and $x_{j}$ is the
$j$-th index of the vector $x_{0}^{n-1}=u_{0}^{n-1}G_{n}$ and $s$ is an
element from $GF(2^{t})$. One can use the following equation for simplifying
eq. (7).

$\ln(\sum_{i}e^{-f_{i}})\approx-\min_{i}(f_{i}).$

Now, for our binary kernel $G_{2}$, consider two input LLR vectors ${S}_{+}$
and ${S}_{-}$ of size $2^{t}$. Then, the output LLR vectors $\hat{S}_{+}$ and
$\hat{S}_{-}$ can be derived from (7), as:

$\displaystyle\hat{S}_{+}^{(s)}\approx$ $\displaystyle\min_{u_{1}\in
GF(2^{t})}{(S_{+}^{(s+u_{1})}+S_{-}^{(u_{1})})}$ (8)
$\displaystyle-\min_{u_{1}\in GF(2^{t})}{(S_{+}^{(u_{1})}+S_{-}^{(u_{1})})},$
$\displaystyle\hat{S}_{-}^{(s)}\approx$ $\displaystyle\leavevmode\nobreak\
S_{+}^{(\hat{u}_{0}+s)}+S_{-}^{(s)}-S_{+}^{(\hat{u}_{0})}-S_{-}^{(0)}.$

where $S_{+}^{(i)}$ and $S_{-}^{(j)}$ are the $i$-th and $j$-th index of the
vectors ${S}_{+}$ and ${S}_{-}$, respectively and $\hat{u}_{0}$ is the
previously decoded symbol, while $u_{1}$ is the yet to be decoded symbol.

LLRs update of Stage $1$: For updating the LLRs of Stage $1$, consider the
input non-binary LLR vector $\hat{S}$. The output binary LLRs
$\hat{S}_{b_{i}}$, $i=\\{1,2,\ldots,t\\}$, derived from eq. (7), are as
follows.

$\displaystyle\hat{S}_{b_{i}}$
$\displaystyle\approx\min_{u_{i+1}^{t-1}}\hat{S}^{([v^{(1)}]_{2^{t}})}-\min_{u_{i+1}^{t-1}}\hat{S}^{([v^{(0)}]_{2^{t}})},$
(9)

where $[v^{(\beta)}]_{2^{t}}$ is the representation of the binary vector
$v^{(\beta)}=(\hat{u}_{0}^{i-1},\beta,u_{i+1}^{t-1})G_{t}$ as element of
$GF(2^{t})$ for $\beta=\\{0,1\\}$ and $\hat{S}^{([v_{\beta}]_{2^{t}})}$ is the
$[v^{(\beta)}]_{2^{t}}$-th index of the vector $\hat{S}$.

In Eq. (9) we show how to calculate the output binary LLRs $\hat{S}_{b_{i}}$
given the input non-binary LLR $\hat{S}$ in one step. However, updating the
LLRs of Stage 1 can be done recursively as well. To this end, Stage 1 of the
encoder in Figure 1 (b) needs to be modified. Instead of encoding $t$ bits
with binary polarization kernel $G_{t}$ over $GF(2)$, $G_{2}$ is applied
recursively on the inputs symbols over $GF(2^{2^{k^{\prime}-1}})$ in
$k^{\prime}$ levels ($1\leq k^{\prime}\leq m^{\prime}$). Then the obtained
symbols are grouped into $2^{k^{\prime}}$-bit symbols
$a_{0}^{(n/2^{k^{\prime}})-1}$. Finally, the output of the last level, $t$-bit
symbol $a_{i}$, $i=\\{0,1,\ldots(n/t)-1\\}$, is fed into Stage $2$. Part of
Stage 1 for this modified encoder is demonstrated in Figure 3. The process of
the encoding for this structure is presented in Algorithm 2.

1

input : $u_{0}^{n-1},m^{\prime},t,n,r$

output : Code $C_{r}$

2

3Define List $\text{A}=\\{\\}$

$\text{A}\leftarrow u_{0}^{n-1}$

// Init.

4 for  _$k^{\prime}=1$ to $m^{\prime}$_ do

5 for  _$i=0$ to $(n/2^{k^{\prime}})-1$_ do

6 $x_{2i}^{2(i+1)-1}=$ Encode each sets $(A[2i],A[2(i+1)-1])$ with binary
kernel $G_{2}$ over $GF(2^{2^{k^{\prime}-1}})$.

7 Group $x_{2i}^{2(i+1)-1}$ together to make a $2^{k^{\prime}}$-bit symbol
$a_{i}$.

8 end for

$A=\\{\\}$

// empty List $A$

9 $A\leftarrow a_{0}^{(n/2^{k^{\prime}})-1}$

10 end for

11lines 6-9 of Algorithm 1.

return $C_{r}$

Algorithm 2 Encoding of the Proposed Hybrid Non-binary Repeated Polar Codes
for Stage $1$

Example 2: Figure 2 (b) demonstrates a encoder structure for the code
discussed in Example 1 based on Algorithm 2. The polarization kernels of Stage
1 (Layer 1 and Layer 2) and Stage 2 is $G_{2}$. The output codewords in this
example are
$c_{0}^{5}=(1,\alpha^{7},\alpha^{8},\alpha^{13},\alpha^{4},\alpha^{8})$ over
$GF(16)$.

Figure 3: Part of Stage 1 of the encoder based on Algorithm 2.

In order to update the LLRs of the layers of Stage 1, based on Algorithm $2$,
the following recursive formulas can be used for calculating $\hat{S}_{+}$ and
$\hat{S}_{-}$ from $\hat{S}$.

$\displaystyle\hat{S}_{+}^{(s)}$ $\displaystyle\approx\min_{u_{1}\in
GF(2^{t^{\prime}})}\hat{S}^{([v^{(s)}]_{2^{t^{\prime}}})}-\min_{u_{1}\in
GF(2^{t^{\prime}})}\hat{S}^{([v^{(0)}]_{2^{t^{\prime}}})}$ (10)
$\displaystyle\hat{S}_{-}^{(s)}$
$\displaystyle\approx\hat{S}^{([\hat{v}^{(s)}]_{2^{t^{\prime}}})}-\hat{S}^{([\hat{v}^{(0)}]_{2^{t^{\prime}}})},$

where $0\leq j\leq m^{\prime}-1$, $t^{\prime}=2^{j}$,
$[v^{(\beta)}]_{2^{t^{\prime}}}$ is the representation of the binary vectors
$v^{(\beta)}=(\beta,u_{1})G_{2}$ as elements of $GF(2^{t^{\prime}})$, and
$[\hat{v}^{(\beta)}]_{2^{t^{\prime}}}$ is the representation of the binary
vectors $\hat{v}^{(\beta)}=(\hat{u}_{0},\beta)G_{2}$ as elements of
$GF(2^{t^{\prime}})$ for $\beta=\\{0,s\\}$.

The CRC-aided SCL decoder after updating the LLRs and calculating the PM for
different paths based on the values of the $\hat{S}_{b_{i}}$ chooses the path
with the smallest PM which passes the CRC.

1

input : List size $L$, $r$, $n$, $t$, $\rho_{n/t}^{rn/t-1}$ and
$y_{0}^{rn/t-1}$

output : The estimated bits $\hat{u}_{0}^{n-1}$

2 ${S}_{in,i}=$ Calculate the initial LLRs with eq. (5) or eq. (6) for all
$i=\\{0,1,\ldots,rn/t-1\\}$ by using $y_{0}^{rn/t-1}$.

3

${S}_{\textup{inner},i}={S}_{in,i},i=\\{0,\ldots,n/t-1\\}$

// Init.: Pick the first $n/t$ elements of ${S}_{in,i}$.

4

5for  _$i=n/t$ to $rn/t-1$_ do

$\pi_{\rho_{i}}({S}_{in,i})$

// Permute the vector ${S}_{in,i}$ based on the random coefficient $\rho_{i}$.

6

7 end for

8for  _$j=2$ to $r$_ do

${S}_{\textup{inner},i}={S}_{\textup{inner},i}+\pi_{\rho_{i}}({S}_{in,i})[(j-1)n/t:jn/t-1]$.

// Output LLRs of the inner code

9

10 end for

11

12for  _$k^{\prime}=0$ to $n-1$ by $t$_ do

13 Using the LLRs ${S}_{\textup{inner},i}$, for $i=\\{0,\ldots,n/t-1\\}$,
update the LLRs for Stage $2$ with eq. (8).

14 for  _$j=1$ to $t$_ do

15

16 Using the updated LLRs from Stage $2$, update the LLRs for Stage $1$ with
eq. (9) and obtain $\hat{S}_{b_{j}}$.

17 Calculate the PM for $\hat{S}_{b_{j}}$ with eq. (2) for each of the $L$
paths.

18 Update bits for Stage $1$.

19

20 end for

21 Update the symbols for Stage $2$.

22

23 end for

24CRC-aided SCL decoder with list size $L$ chooses the path with the smallest
PM which passes the CRC and outputs $\hat{u}_{0}^{n-1}$.

25 return $\hat{u}_{0}^{n-1}$

Algorithm 3 List Decoding Algorithm for the Proposed Hybrid Non-binary
Repeated Polar Codes

##  IV Analysis and Numerical Results

In this section, we first provide complexity analysis of the proposed scheme
and compare it with those of the polar-repetition scheme and the scheme in
[7]. Then, we analyze the numerical result of the proposed scheme given
certain underlying binary field extensions in the construction, i.e., over
GF($4$) and GF($16$), and compare it with the polar-repetition scheme and the
scheme in [7] over AWGN and Rayleigh fading channels. Finally, we analyze the
performance of the hybrid non-binary repeated polar code.

###  IV-A Complexity Analysis

In this subsection, we count the exact number of operations needed for
calculating the LLRs of the proposed scheme, polar-repetition, and the scheme
in [7] to show the performance-complexity trade-off in subsection IV-B. Note
that to demonstrate the computational complexity, we used the total number of
the summation and comparison operations for calculating the LLRs of the outer
and inner codes for the SC decoder. The complexity advantages of the entire
system using CRC-aided SCL decoder will be shown in Sec. IV-B.

Polar-repetition code: To update the LLRs of the polar-repetition, one needs
to compute

  * •

$(n-1)r$ operations for decoding the inner repetition code of size $r$.

  * •

$(\frac{n}{2}\times 4+\frac{n}{2}\times 1)\log n$ operations for decoding the
outer polar code of size $n$.

Consequently, the total complexity is $nr+2.5n\log n$ operations.

Hybrid non-binary repeated polar code: Since the two methods proposed in
Algorithms 1 and 2 have the same computational complexities, we only count the
number of the operations of the first method as follows.

  1. 1.

Inner multiplicative repetition code: According to (5) or (6), the size of the
initial LLR vector of the proposed scheme, $S_{in,i}$, is $2^{t}$ and
$S_{in,i}^{(0)}=0$. Consequently $(2^{t}-1)rn/t$ operations are needed for
computing lines 6-8 of Algorithm 3 for decoding the inner multiplicative
repetition code.

  2. 2.

Stage2: For updating the LLRs of Stage 2, one need to compute
$\hat{S}_{+}^{(s)}$ and $\hat{S}_{-}^{(s)}$ given in (8).

To obtain $\hat{S}_{+}^{(s)}$, one should compute

     * •

$S_{+}^{(s+u_{1})}+S_{-}^{(u_{1})}$, $\forall s,u_{1}\in GF(2^{t})$, with
$(2^{t}-1)\times(2^{t}-1)$ operations. 222Note that
$S_{+}^{(u_{1})}+S_{-}^{(u_{1})}$ is a special case of
$S_{+}^{(s+u_{1})}+S_{-}^{(u_{1})}$ for $s=0$ and $\hat{S}_{+}^{(0)}=0$,
$\hat{S}_{-}^{(0)}=0$.

     * •

$\min_{u_{1}\in GF(2^{t})}(S_{+}^{(s+u_{1})}+S_{-}^{(u_{1})})$, $\forall s\in
GF(2^{t})$, with $2^{t}\times(2^{t}-1)$.

     * •

$\hat{S}_{+}^{(s)}$ with $2^{t}-1$ operations for $s\in
GF(2^{t})\setminus\\{0\\}$.

Therefore, the total number of the operations for computing
$\hat{S}_{+}^{(s)}$ is $(2^{t}-1)\times 2^{(t+1)}$.

To obtain $\hat{S}_{-}^{(s)}$, one should compute

     * •

$S_{+}^{(\hat{u}_{0}+s)}+S_{-}^{(s)}$, $\forall s\in GF(2^{t})$, with
$2^{t}-2$ operations.

     * •

$\hat{S}_{-}^{(s)}$ with $2^{t}-1$ operations for $s\in
GF(2^{t})\setminus\\{0\\}$.

Therefore, in total $2^{t+1}-3$ operations are needed for computing
$\hat{S}_{-}^{(s)}$.

Finally, for the Arıkan’s kernel of size $n/t$,
$(\log\frac{n}{t})[\frac{n}{2t}((2^{t}-1)\times
2^{(t+1)})+\frac{n}{2t}(2^{t+1}-3)]$ operations are needed for updating the
LLRs of Stage $2$.

  3. 3.

Stage 1: According to (9), for each $b_{i},i\in\\{1,2,\ldots,t\\}$, one needs
to compute

     * •

$\min_{u_{i+1}^{t-1}}\hat{S}^{([v^{(\beta)}]_{2^{t}})}$, $\beta=\\{0,1\\}$
with $2^{t-i}-1$ operations.

     * •

$\hat{S}_{b_{i}}$ with $1$ operation.

As a result, in total, $\frac{n}{t}\sum_{i=1}^{t}(2(2^{t-i}-1)+1)$ operations
are needed to update the LLRs of the ${n}/{t}$ kernel $G_{t}$ of size $t$.

Scheme proposed in [7]: This scheme is the concatenation of the
$(n_{l},k_{l})=(8192,128)$ LDPC with $(n_{p},k_{p})=(128,80)$ polar code. In
this scheme, one needs $8192(8\log(128)+32)=720896$ operations for decoding
the LDPC code and $110469$ operations for decoding the polar code under SCL
with list size $L=32$. As a result the total number of operations for this
scheme is $831365$.

In a nutshell, we conclude that the complexity of the total decoding process
of the polar-repetition and the proposed schemes are $O(nr+n\log n)$ and
$O(2^{t}rn/t+2^{2t}(n/t)\log(n/t)+2^{t}n/t)$, respectively. Here, if $t$ and
$r$ be constants, the complexity of both schemes will be $O(n\log n)$.
Moreover, the complexity of the scheme proposed in [7] is $O(n_{l}(\log
n_{p}+L)+Ln_{p}\log n_{p})$. However, for numerical comparison purposes, we
use the aforementioned exact number of operations for the different schemes.
The complexity comparison of the three discussed schemes is shown in Table I
for $N=8192$ and three different values $r=16,32,64$.

Parameters |  Repetition Scheme
---|---
|  Inner rep. $n(r-1)$ |  Outer polar code $2.5\times n\log n$ |  Total
$n=512$, $r=16$ |  $7680$ |  $11520$ |  $19200$
$n=256$, $r=32$ |  $7936$ |  $5120$ |  $13056$
$n=128$, $r=64$ |  $8064$ |  $2240$ |  $10304$
Parameters |  Proposed Scheme over GF(4)
|  Inner rep. $\frac{n(r-1)}{t}(2^{t}-1)$ |  Stage 2 $(2^{2t}-3/2)\frac{n}{t}\log\frac{n}{t}$ |  Stage 1 $2n$ |  Total
$n=512$, $r=16$, $t=2$ |  $11520$ |  $29696$ |  $1024$ |  $42240$
$n=256$, $r=32$, $t=2$ |  $11904$ |  $12992$ |  $512$ |  $25408$
$n=128$, $r=64$, $t=2$ |  $12096$ |  $5568$ |  $256$ |  $17920$
Parameters |  Proposed Scheme over GF(16)
|  Inner rep. $\frac{n(r-1)}{t}(2^{t}-1)$ |  Stage 2 $(2^{2t}-3/2)\frac{n}{t}\log\frac{n}{t}$ |  Stage 1 $\frac{n}{t}\sum_{i=1}^{t}(2(2^{t-i}-1)+1)$ |  Total
$n=512$, $r=16$, $t=4$ |  $28800$ |  $228032$ |  $3328$ |  $260160$
$n=256$, $r=32$, $t=4$ |  $29760$ |  $97728$ |  $1664$ |  $129152$
$n=128$, $r=64$, $t=4$ |  $30240$ |  $40720$ |  $832$ |  $71792$

Table I:  Complexity comparison of different schemes

###  IV-B Numerical Analysis

In this subsection, we provide numerical results for the proposed scheme given
$GF(4)$ and $GF(16)$ as the underlying binary field extension in the
construction333For the simulation, Algorithm 1 is used. Although both
Algorithm 1 and 2 show the same performance.. The communication is assumed
over AWGN and Rayleigh fading channels with BPSK modulation, where encoded
symbols are turned into binary strings and then modulated. Also, the decoding
is performed under the SC and CRC-aided SCL decoding algorithms. Then, we
compare the performance of the proposed scheme with those of the polar-
repetition scheme as well as the scheme proposed in [7]. Note that the SCL
decoder is implemented using the randomized order statistic algorithm for the
selection of the $L$ most likely paths in each stage, which has the complexity
$O(L)$, where $L$ is the list size. Moreover, the construction for the
proposed hybrid non-binary repeated polar code and polar-repetition schemes is
based on the Monte-Carlo simulation at an optimized design SNR, denoted by
$\gamma$, to be specified separately for each case.

It is worth noting that in each instance of the simulation, a different set of
the random coefficients $\rho_{(j-1)n/t}^{jn/t-1}$, $j=\\{2,3,\ldots,r\\}$ is
used. At the end, the average is taken over all the instances. An alternative
approach is to choose the set of the coefficients in a certain way and then
use them in all the instances of the simulation. The choice of such
coefficients could be optimized, however, solving such a combinatorial
optimization problem is complex and beyond the scope of this paper.

Figures 4(a), 4(c), and 4(e) compare the performance of the proposed scheme
for $N=8192$, $k=80$, and over $GF(4)$ and $GF(16)$ with that of the
straightforward polar-repetition scheme over AWGN channel. To illustrate the
trade-off between the rate of the outer polar code and the number of the
repetitions, we consider three different values $r=16,32,64$. The optimized
design SNR $\gamma$ for each simulated case is specified in the legend of the
corresponding plot.

It can be seen that the proposed scheme over $GF(16)$ outperforms the one over
$GF(4)$ and the repetition scheme, under SC and CRC-aided SCL decoder with the
same list size and $6$-bit CRC. For $r=16$ under CRC-aided SCL, the
performance of the proposed scheme over $GF(16)$ with $L=8$ is almost the same
as that of the proposed scheme over $GF(4)$ with $L=32$ and the polar-
repetition scheme with $L=128$. For $r=32$ under CRC-aided SCL, the proposed
scheme over $GF(16)$ with $L=8$ outperforms the proposed scheme over $GF(4)$
with $L=32$ and that one outperforms the repetition scheme with $L=128$.
Moreover, the performance of the proposed scheme over $GF(16)$ with $L=4$ is
almost the same as that of the repetition scheme with $L=128$. As we increase
the number of the repetitions to $64$, due to the loss in the asymptotic
achievable rate, the performance of polar-repetition scheme degrades. As a
result, the performance of the proposed scheme over $GF(4)$ with $L=8$
outperforms that of the repetition scheme with $L=128$.

For comparison, the performance of the scheme proposed in [7] for low-SNR
regime is also considered. It can be seen that for $r=16$, the proposed
schemes over $GF(4)$ under CRC-aided SCL with $L=32$ and $GF(16)$ with $L=8$
outperform the scheme in [7]. Moreover, the performance of the scheme in [7]
is the same as that of the proposed scheme over $GF(4)$ with $L=8$ and
repetition scheme with $L=32$. For $r=32$, the proposed scheme over $GF(16)$
with $L=8$ outperforms the scheme in [7]. On the other hand, the performance
of the proposed scheme over $GF(4)$ with $L=32$ is almost the same as that of
[7]. However, for $r=64$, the scheme in [7] outperforms the proposed scheme
over $GF(16)$ with $L=32$.

Figures 4(b), 4(d), and 4(f) compare the performance of the proposed scheme
over $GF(4)$ and $GF(16)$ with that of the straightforward polar-repetition
scheme over AWGN channel for $N=8192$, $k=40$. Similarly, the proposed scheme
over $GF(16)$ outperforms the one over $GF(4)$ and repetition scheme under
both SC and CRC-aided SCL decoder. The scheme in [7] can not be realized for
these parameters.

(a) $N=8192$, $n=512$, $k=80$, $r=16$, $t=2,4$.

(b) $N=8192$, $n=512$, $k=40$, $r=16$, $t=2,4$.

(c) $N=8192$, $n=256$, $k=80$, $r=32$, $t=2,4$.

(d) $N=8192$, $n=256$, $k=40$, $r=32$, $t=2,4$.

(e) $N=8192$, $n=128$, $k=80$, $r=64$, $t=2,4$.

(f) $N=8192$, $n=128$, $k=40$, $r=64$, $t=2,4$.

Figure 4: Performance comparison of the proposed scheme with the polar-
repetition scheme and the scheme in [7] over AWGN channel for different values
of $n$, $r$ and $k$.

(a) Performance

(b) Complexity

Figure 5: CRC-aided SCL decoding over AWGN channel at $Eb/No=1.5$ dB for
$N=8192$, $n=512$, $r=16$, $k=80$.

(c) Performance

(d) Complexity

Figure 6: CRC-aided SCL decoding over AWGN channel at $Eb/No=1.5$ dB for
$N=8192$, $n=256$, $r=32$, $k=80$.

(a) Performance

(b) Complexity

Figure 7: CRC-aided SCL decoding over AWGN channel at $Eb/No=1.5$ dB for
$N=8192$, $n=128$, $r=64$, $k=80$.

Figures 5(a), 5(c) and 6(a) present the simulation results of the hybrid non-
binary repeated polar code and the polar repetition scheme under CRC-aided SCL
decoder as a function of $L$ over AWGN channel at $Eb/N0=1.5$ dB for $N=8192$,
$k=80$ and three different number of repetitions, $r=16,32,64$, respectively.
It can be seen that the hybrid non-binary repeated polar code over $GF(16)$
requires significantly lower list size $L$ to achieve the same performance as
the polar-repetition scheme over $GF(4)$. Moreover, this gap grows with $L$.
For comparison, the performance of the scheme proposed in [7] with $L=32$ is
also provided.

Figure 5(b) presents the performance of the CRC-aided SCL decoding of the
schemes in Figure 5(a) in terms of the decoding complexity. Observe that the
proposed scheme over $GF(4)$ can provide better performance than polar-
repetition scheme with the same decoding complexity for FER $\leq 6\times
10^{-3}$ ($L>4$ for the proposed scheme over $GF(4)$ and $L>8$ for polar-
repetition scheme). This is due to the higher slope of the corresponding curve
in Figure 5(a), which eventually enables one to compensate for the relatively
high complexity of the LLR computation presented in Table I. The proposed
scheme over $GF(16)$ has greater processing complexity than the one over
$GF(4)$, so that its curve intersects the polar-repetition scheme at FER
$=2\times 10^{-3}$ ($L\geq 4$ for the proposed scheme over $GF(16)$ and $L\geq
64$ for polar-repetition scheme). Moreover, the proposed schemes over $GF(4)$
and $GF(16)$ have the same FER $=8\times 10^{-4}$ for $L\geq 64$ and $L>8$,
respectively. Similar behaviour is observed for $r=32$ repetitions in Figure
5(d). However, as we increase $r$ from $16$ to $32$, the decoding complexity
decreases, while the performance of all the schemes degrades. As a result, the
intersections of the curves happen at lower FER and smaller number of the
operations. For $r=64$ repetitions in Figure 6(b), a significant degradation
in the performance occurs due to the reduced achievable rate of the outer
polar code due to having a shorter length. For any $L$, the hybrid non-binary
repeated polar code over $GF(16)$ provides the best performance for the same
decoding complexity.

It can be observed that for $r=16$ repetitions (see Figure 5(b)), the hybrid
non-binary repeated polar code and polar-repetition scheme outperform the
scheme in [7] with the same decoding complexity. For $r=32$ repetitions (see
Figure 5(d)), the scheme in [7] slightly outperforms the polar-repetition, but
not the proposed scheme for the same decoding complexity. Only for $64$
repetitions (see Figure 6(b)), the scheme in [7] outperforms the others with
the same decoding complexity.

Figure 8 compares the performance of the proposed scheme for $N=8192$, $k=80$,
$r=16$ over $GF(4)$ and $GF(16)$ with that of the straightforward polar-
repetition scheme over Rayleigh fading channel. For each repetition block, we
consider one distinct fading coefficient. As a result, in each frame of size
$8192$, there are $16$ distinct fading coefficients and each block of length
$512$ symbols in each repetition will be affected by the same fading
coefficient.

Figure 8: Performance comparison of the proposed scheme with the polar-
repetition over Rayleigh fading channel for $N=8192$, $n=512$, $k=80$, $r=16$,
$t=2,4$.

Similar to AWGN channel, it can be seen that the proposed scheme over $GF(16)$
outperforms the one over $GF(4)$ and the repetition scheme, under SC and CRC-
aided SCL decoder with the same list size and $6$-bit CRC.

###  IV-C Performance Analysis

In this subsection, we analyze the performance of the proposed scheme to gain
insight into its better performance under the CRC-aided SCL decoder. Since the
SCL decoder with large list size achieves performance very close to that of
the ML decoder, we study the performance of the proposed scheme under ML
decoding to have better analytical understanding.

The block error probability under ML decoding can be estimated via the
truncated union bound as follows, [33].

$P_{e}^{\textup{ML}}\leq\sum_{i=d}^{n}A_{i}Q(\sqrt{2iRE_{b}/N_{o})},$ (11)

where $A_{i}$ is the number of the codewords of weight $i$ and $d$ is the
minimum distance of the code. At high SNR, upper bound on
$P_{e}^{\textup{ML}}$ depends primarily on $d$ and $A_{d}$. Hence, to obtain a
good performance under ML decoding, one needs to eliminate low-weight non-zero
(LWNZ) codewords from the code.

To enumerate the LWNZ codewords, we transmit the all-zero codeword in the
extremely high SNR regime under SCL decoder with very large list size, [32].
In this case, it is expected that the list most likely contains only the
codewords with the least Hamming weights.

Table II compares the number of low-weight codewords of the proposed scheme
with the polar-repetition ones over AWGN channel for $N=8192$, $n=512$,
$r=16$, $k=40$. As it is expected the number of LWNZ codewords for the
proposed scheme over $GF(4)$ is less than that of the polar-repetition scheme.
For $GF(16)$, although the minimum distance is slightly reduced, the number of
low-weight codewords is still much smaller compared to the polar-repetition
scheme.

Parameters |  Schemes |  $A_{1000}-A_{1024}$ |  $A_{64\times 16}$ |  $A_{1329}-A_{2047}$ |  $A_{128\times 16}$ |  $A_{2049}-A_{3071}$ |  $A_{192\times 16}$ |  $A_{3073}-A_{4095}$ |  $A_{256\times 16}$
---|---|---|---|---|---|---|---|---|---
$n=512$, $r=16$ |  Prop. Sch., $t=2$ |  $0$ |  $0$ |  $<10$ |  $0$ |  $<30$ |  $3$ |  $<230$ |  $230$
$k=40$ |  Prop. Sch., $t=4$ |  $2$ |  $0$ |  $32766$ |  $0$ |  $0$ |  $0$ |  $0$ |  $0$
|  Rep. Sch. |  $0$ |  $105$ |  $0$ |  $1365$ |  $0$ |  $5005$ |  $0$ |  $22819$
|  |  $A_{4097}-A_{5119}$ |  $A_{320\times 16}$ |  $A_{5121}-A_{6143}$ |  $A_{384\times 16}$ |  $A_{6145}-A_{7167}$ |  $A_{448\times 16}$ |  $>A_{7169}$ |
|  Prop. Sch., $t=2$ |  $<230$ |  $0$ |  $<20$ |  $0$ |  $0$ |  $0$ |  $0$ |
|  Prop. Sch., $t=4$ |  $0$ |  $0$ |  $0$ |  $0$ |  $0$ |  $0$ |  $0$ |
|  Rep. Sch. |  $0$ |  $3003$ |  $0$ |  $455$ |  $0$ |  $15$ |  $0$ |

Table II: Number of Low-Weight Codewords

##  V Conclusion

In this paper, we proposed a new concatenation scheme to improve upon the
performance of the polar-repetition scheme in the low-SNR regime. The proposed
scheme is the concatenation of a hybrid non-binary polar code with a
multiplicative repetition code. Extensive simulation and numerical results
show that the proposed scheme provides a better trade-off between the decoding
complexity and performance compared with the polar-repetition scheme, under
CRC-aided SCL decoder over AWGN and Rayleigh fading channels.

There are several directions for the future research. Finding the best
permutation for the inner non-binary multiplicative repetition code is an
interesting problem. Reducing the decoding complexity of our proposed
constructions by pruning the decoding trellis and simplifying it [34], and
reducing the latency to become sub-linear [35] are other interesting
directions. Also, analyzing the polarization properties of the proposed scheme
with the optimal permutation in terms of error exponent, [36], and scaling
exponent, [37], [38], and comparing them with polarization based on kernels
constructed in [39]–[41], are other interesting open problems.

## Acknowledgment

The authors would like to thank Navid Gharavi and Prof. Ilya Dumer for
providing the simulation results of their proposed scheme in [7].

## References

  * [1] M. Fereydounian, M. V. Jamali, H. Hassani, and H. Mahdavifar, ”Channel coding at low capacity,” Available at https://arxiv.org/abs/1811.04322, Mar. 2020.
  * [2] E. Arıkan, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,” IEEE Transactions on Information Theory, vol. 55, no. 7, pp. 3051–3073, Jul. 2009.
  * [3] I. Tal, and A. Vardy, “List decoding of polar codes,” IEEE Transactions on Information Theory, vol. 61, no. 5, pp. 2213–2226, May 2015.
  * [4] R. Ratasuk, N. Mangalvedhe, Y. Zhang, M. Robert, and J.-P. Koskinen, “Overview of narrowband IoT in LTE Rel-13,” in Proc. IEEE Conf. Standard Communication Network (CSCN), Berlin, Germany, Oct./Nov. 2016, pp. 1–7.
  * [5] I. Dumer, “Polar codes with a stepped boundary,” in Proc. IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, Jun. 2017, pp. 2613–2617.
  * [6] K. Kasai, D. Declercq, C. Poulliat, and K. Sakaniwa, “Multiplicatively repeated nonbinary LDPC codes,” IEEE Transactions on Information Theory, vol. 57, no. 10, pp. 6788–6795, Oct. 2011.
  * [7] I. Dumer and N. Gharavi, “Codes for high-noise memoryless channels”, in Proc. International Symposium on Information Theory and Its Applications (ISITA), Kapolei, HI, USA, Oct. 2020, pp. 101–105. (Extended version is available at https://www.researchgate.net/publication/340726241.)
  * [8] I. Dumer, and N. Gharavi, “Codes approaching the Shannon limit with polynomial complexity per information bit”, Available at https://arxiv.org/pdf/2101.10145.pdf.
  * [9] K. Niu and K. Chen, “CRC-Aided Decoding of Polar Codes,” IEEE Communications Letters, vol. 16, no. 10, pp. 1668-1671, Oct. 2012.
  * [10] F. Abbasi, H. Mahdavifar and E. Viterbo, ”Hybrid Non-Binary Repeated Polar Codes For Low-SNR Regime,“ in Proc. IEEE International Symposium on Information Theory (ISIT), 2021, pp. 1742–1747.
  * [11] F. Abbasi, H. Mahdavifar, and E. Viterbo, “Polar Coded Repetition for Low-Capacity Channels”, in Proc. IEEE Information Theory Workshop (ITW), Riva del Garda, Italy, April, 2021. Available at https://arxiv.org/abs/2010.16144.
  * [12] Y. Li, L. Yang, X. Wang, and F.Y. Wang, “When LPWAN Meets ITS: Evaluation of Low Power Wide Area Networks for V2X Communications,” in Proc. 21st International Conference on Intelligent Transportation Systems (ITSC), Maui, HI, USA, Dec. 2018, pp. 473–478.
  * [13] “5G NR multiplexing and channel coding ,” 3GPP Technical Specification 38.212, Release 15, 2018.
  * [14] E. Arıkan, “Source polarization,” in Proc. of IEEE International Symposium on Information Theory (ISIT), Texas, US, pp. 899–903, Jun. 2010.
  * [15] E. Abbe, “Polarization and randomness extraction,” in Proc. of IEEE International Symposium on Information Theory (ISIT), St.Petersburg, Russia, pp. 184–188, Jul./Aug. 2011.
  * [16] M. Mondelli, S. H. Hassani, I. Sason, and R. L. Urbanke, “Achieving Marton’s region for broadcast channels using polar codes,” IEEE Transactions on Information Theory, vol. 61, no. 2, pp. 783–800, Feb. 2015.
  * [17] N. Goela, E. Abbe, and M. Gastpar, “Polar codes for broadcast channels,” IEEE Transactions on Information Theory, vol. 61, no. 2, pp. 758–782, Feb. 2015.
  * [18] E. Şaşoğlu, E. Telatar, and E. Yeh, “Polar Codes for the Two-User Multiple-Access Channel,” IEEE Transactions on Information Theory, vol. 59, no. 10, pp. 6583–6592, 2013.
  * [19] H. Mahdavifar, M. El-Khamy, J. Lee, and I. Kang, “Achieving the uniform rate region of general multiple access channels by polar coding,” IEEE Transactions on Communications, vol. 64, no. 2, pp. 467–478, Feb. 2016.
  * [20] H. Mahdavifar and A. Vardy, “Achieving the secrecy capacity of wiretap channels using polar codes,” IEEE Transactions on Information Theory, vol. 57, no. 10, pp. 6428–6443, Oct. 2011.
  * [21] M. Andersson, V. Rathi, R. Thobaben, J. Kliewer, and M. Skoglund, “Nested polar codes for wiretap and relay channels,” IEEE Communications Letters, vol. 14, no. 8, pp. 752–754, Aug. 2010.
  * [22] R. A. Chou, M. R. Bloch, and E. Abbe, “Polar coding for secret-key generation,” IEEE Transactions on Information Theory, vol. 61, no. 11, pp. 6213–6237, Nov. 2015.
  * [23] Y.-P. Wei and S. Ulukus, “Polar coding for the general wiretap channel with extensions to multiuser scenarios,” IEEE Journal on Selected Areas in Communications, vol. 34, no. 2, pp. 278–291, Feb. 2016.
  * [24] A. Jalali and Z. Ding, “Joint Detection and Decoding of Polar Coded 5G Control Channels,” IEEE Transactions on Wireless Communications, vol. 19, no. 3, pp. 2066–2078, Mar. 2020.
  * [25] H. Si, O. O. Koyluoglu, and S. Vishwanath, “Polar coding for fading channels: binary and exponential channel cases,” IEEE Transactions on Communications, vol. 62, no. 8, pp. 2638–2650, 2014.
  * [26] S. Liu, Y. Hong, and E. Viterbo, “Polar codes for block fading channels,” in Proc. IEEE Wireless Communications and Networking Conference Workshops (WCNCW), San Francisco, CA, USA, Mar. 2017, pp. 1–6
  * [27] P. Trifonov, “Design of polar codes for Rayleigh fading channel,” in Proc. International Symposium on Wireless Communication Systems (ISWCS’15), Aug. 2015, pp. 331–335.
  * [28] M. Seidl, A. Schenk, C. Stierstorfer, and J. B. Huber, “Polar-coded modulation,” IEEE Transactions on Communications, vol. 61, no. 10, pp. 4108–4119, Oct. 2013.
  * [29] H. Mahdavifar, M. El-Khamy, J. Lee, and I. Kang, “Polar coding for bit-interleaved coded modulation,” IEEE Transactions on Vehicular Technology., vol. 65, no.5, pp. 3115–3127, May 2016.
  * [30] N. Presman, O. Shapira, and S. Litsyn, “Mixed-kernels constructions of polar codes,” IEEE Journal on Selected Areas in Communications, vol. 34, no. 2, pp. 239–253, Feb. 2016.
  * [31] H. Mahdavifar, M. El-Khamy, J. Lee, and I. Kang, “Fast multidimensional polar encoding and decoding,” in Proc. Information Theory Application Workshop, San Diego, CA, USA, Feb. 2014, pp. 1–5.
  * [32] B. Li, H. Shen, and D. Tse, “An adaptive successive cancellation list decoder for polar codes with cyclic redundancy check”, IEEE Communications Letters, vol. 16, no. 12, pp. 2044–2047, Dec. 2012.
  * [33] I. Sason, and S. Shamai, “Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial”, now, 2006.
  * [34] A. Alamdar-Yazdi and F. R. Kschischang, “A simplified successive cancellation decoder for polar codes,” IEEE Communications Letters, vol. 15, no. 12, pp. 1378–1380, Dec. 2011.
  * [35] M. Mondelli, S. A. Hashemi, J. M. Cioffi and A. Goldsmith, “Sublinear Latency for Simplified Successive Cancellation Decoding of Polar Codes,” IEEE Transactions on Wireless Communications, vol. 20, no. 1, pp. 18–27, Jan. 2021.
  * [36] E. Arıkan and E. Telatar, “On the rate of channel polarization”, in Proc. IEEE International Symposium on Information Theory (ISIT), Seoul, South Korea, Jun./Jul. 2009, pp. 1493–1495.
  * [37] S. H. Hassani, K. Alishahi, and R. L. Urbanke, “Finite-length scaling for polar codes”, IEEE Transactions on Information Theory, vol. 60, no. 10, pp. 5875–5898, Oct. 2014.
  * [38] H. Mahdavifar, “Polar Coding for Non-Stationary Channels”, IEEE Transactions on Information Theory, vol. 66, no. 11, pp. 6920–6938, Nov. 2020.
  * [39] H. Lin, S. Lin, and K. A. S. Abdel-Ghaffar, “Linear and nonlinear binary kernels of polar codes of small dimensions with maximum exponents,” IEEE Transactions on Information Theory, vol. 61, no. 10, pp. 5253–5270, Oct. 2015.
  * [40] G. Trofimiuk and P. Trifonov, “Construction of polarization kernels of size 16 for low complexity processing,” in Proc. Fourth Conference on Software Engineering and Information Management (SEIM), 2019.
  * [41] F. Abbasi and E. Viterbo, “Large Kernel Polar Codes with Efficient Window Decoding,” IEEE Transactions on Vehicular Technology, vol. 69, no. 11, pp. 14031–14036, Nov. 2020.