# MIPE: A Metric Independent Pipeline for Effective Code-Mixed NLG Evaluation

Ayush Garg , Sammed S Kagi††footnotemark:
IIT Gandhinagar, India
<EMAIL_ADDRESS>
Vivek Srivastava
TCS Research, India
<EMAIL_ADDRESS>
Mayank Singh
IIT Gandhinagar, India
<EMAIL_ADDRESS>equal contribution

###### Abstract

Code-mixing is a phenomenon of mixing words and phrases from two or more
languages in a single utterance of speech and text. Due to the high linguistic
diversity, code-mixing presents several challenges in evaluating standard
natural language generation (NLG) tasks. Various widely popular metrics
perform poorly with the code-mixed NLG tasks. To address this challenge, we
present a metric independent evaluation pipeline MIPE that significantly
improves the correlation between evaluation metrics and human judgments on the
generated code-mixed text. As a use case, we demonstrate the performance of
MIPE on the machine-generated Hinglish (code-mixing of Hindi and English
languages) sentences from the HinGE corpus. We can extend the proposed
evaluation strategy to other code-mixed language pairs, NLG tasks, and
evaluation metrics with minimal to no effort.

##  1 Introduction

Code-mixing (hereafter ‘CM’) is a commonly observed communication pattern for
a multilingual speaker to mix words and phrases from multiple languages. CM is
widespread across various language pairs across the globe, such as Spanish-
English (Spanglish) and Hindi-English (Hinglish). Various studies Baldauf
(2004) have predicted the high growth in the number of CM speakers, which
would surpass the number of native speakers in various globally popular
languages (e.g., English).

With the advent of social-media platforms (e.g., Twitter, Facebook, etc.), we
observe a manifold increase in the CM communication by multilingual speakers.
This leads to a large scale availability of CM data for various NLP tasks.
Recently, we witness magnitude of work to address various CM NLP tasks such as
language identification Shekhar et al. (2020); Singh et al. (2018a);
Ramanarayanan et al. (2019); Barman et al. (2014); Gundapu and Mamidi (2018),
POS tagging Singh et al. (2018b); Vyas et al. (2014); Pratapa et al. (2018),
named entity recognition Singh et al. (2018a); Priyadharshini et al. (2020);
Winata et al. (2019), word normalisation Singh et al. (2018c); Parikh and
Solorio (2021), CM metrics Guzmán et al. (2017); Srivastava and Singh (2021a),
sentiment analysis Patwa et al. (2020); Joshi et al. (2016), stance detection
Utsav et al. (2020); Sane et al. (2019), natural language inference Khanuja et
al. (2020), machine translation Srivastava and Singh (2020); Dhar et al.
(2018), and question-answering Chandu et al. (2019); Thara et al. (2020).

We observe a growing interest in the computational linguistic community to
study the CM NLG tasks. Recently, various resources and systems have been
proposed that explore different dimensions of the CM NLG Yang et al. (2020);
Gautam et al. (2021); Gupta et al. (2021); Rizvi et al. (2021); Gupta et al.
(2020); Jawahar et al. (2021). Evaluation of the CM NLG tasks is challenging
due to the high linguistic diversity and lack of standardization. To address
this challenge, Srivastava and Singh (2021b) has proposed HinGE corpus for the
Hinglish CM text generation and evaluation (see Section 2 for details). HinGE
corpus demonstrates the inefficacy of various widely popular metrics on the CM
dataset.

In this paper, we choose five evaluation metrics (see Section 3 for details)
as discussed in Srivastava and Singh (2021b) to demonstrate the efficacy of
MIPE. Our proposed metric independent pipeline (MIPE) augments these metrics
and addresses four major linguistic bottlenecks: (i) spelling variations, (ii)
language switching, (iii) missing words, and (iv) the limited number of
reference sentences associated with the CM NLG systems. The main contributions
are:

  * •

We identify four major reasons for the poor quality performance of various
widely popular evaluation metrics for the code-mixed NLG evaluation.

  * •

We propose a metric independent evaluation pipeline MIPE that addresses the
identified bottlenecks in CM NLG evaluation. Furthermore, we show its efficacy
in generating highly correlated metric scores against human scores.

The rest of the paper is organized as follows. In Section 2, we discuss the
dataset for the CM NLG evaluation task. In Section 3, we present the MIPE
pipeline addressing the four major bottlenecks for effective CM NLG
evaluation. We discuss the results in Section 4. In Section 5, we discuss the
current state and future direction. We conclude the discussion in Section 6.

##  2 Dataset

Recently, we observe various works to address the underlying challenges with
the CM NLG. Numerous resources and systems have been proposed recently to
advance the field. In our experiments, we use the HinGE corpus proposed in
Srivastava and Singh (2021b). The HinGE corpus contains 1,976 English-Hindi
parallel sentences from the IIT-B parallel corpus Kunchukuttan et al. (2018).
Corresponding to each of the English-Hindi parallel sentences, HinGE has two
variants of CM Hinglish sentences:

  * •

Human-generated Hinglish sentences: Srivastava and Singh (2021b) have employed
eight human annotators to generate the Hinglish sentences. Each parallel
sentence pair is annotated by a single human annotator. Human annotators have
generated at least two Hinglish sentences corresponding to each parallel
sentence pair. On average, 2.5 Hinglish sentences are generated for each
parallel sentence pair.

  * •

Machine-generated Hinglish sentences: Srivastava and Singh (2021b) proposes
two rule-based algorithms to generate the CM sentences. They leverage the
matrix-frame theory to generate the Hinglish sentences where Hindi is the
matrix language and English tokens are embedded. The proposed algorithms
differ significantly at the level of granularity (i.e., word and phrase). We
will use the acronyms WAC (word-aligned code-mixing) and PAC (phrase-aligned
code-mixing) for the two algorithm variants in the rest of the paper.

In addition to the machine-generated Hinglish sentences, HinGE has a human
rating corresponding to each generated sentence. The human rating varies
between 1–10, indicating low to high generation quality. Two human annotators
have rated each of the machine-generated CM sentences. Figure 1 shows the
example CM sentences generated by humans and two rule-based algorithms along
with the rating to the machine-generated CM sentences. Figure 2 shows the
distribution of the human ratings to the machine-generated Hinglish sentences.
WAC-generated sentences receive a relatively high rating ($>6$) as compared to
PAC. In addition, WAC showed a low degree of human disagreements than PAC.

Human-generated 1: is another human being saying, “kya aapko samaj aaya?”
Human-generated 2: koi dusra human being yeh kahe, “Do you understand this?”
WAC generated: koee doosra human ye kahe, kya aapko samajh aaya Rating 1: 9
Rating 2: 8 PAC generated: koee doosra manushy ye kahe, kya aapko samajh
understand Rating 1: 7 Rating 2: 8 Figure 1: Example of the CM sentences
generated by the annotator along with WAC and PAC generated CM sentence. Two
human annotators rate the machine-generated sentence on a scale of 1–10.
Figure 2: Distribution of human ratings on the generated Hinglish sentences
using WAC and PAC. The figure is taken from Srivastava and Singh (2021b).

Efficacy of NLG Evaluation Metrics: Srivastava and Singh (2021b) present a
study demonstrating the inefficacy of five widely popular NLG evaluation
metric on the HinGE corpus. The five metrics are: (i) Bilingual Evaluation
Understudy Score (BLEU, Papineni et al. (2002)), (ii) NIST Doddington (2002),
(iii) BERTScore (BS, Zhang et al. (2019)), (iv) Word Error Rate (WER,
Levenshtein (1966)), and (v) Translator Error Rate (TER, Snover et al.
(2006)). Higher BLEU, NIST, or BS values and lower WER or TER values represent
better generation performance. Tables 1 and 2 show the comparison of five
metric scores against the human ratings against WAC and PAC (see scores
present in columns with heading ‘Without MIPE’). In addition, Srivastava and
Singh (2021b) present a correlation study between the human ratings and the
metric scores. For this purpose they divide the ratings into three buckets:

  * •

Bucket 1: Human rating between 2–10.

  * •

Bucket 2: Human rating between 2–5.

  * •

Bucket 3: Human rating between 6–10.

Table 4 shows the correlation between the human ratings and the metric scores
for WAC and PAC (see scores present in columns with heading ‘Without MIPE’).
The correlation scores show a scope to build systems that shows a high
correlation with human judgment.

##  3 MIPE

As discussed in the previous section, the widely used evaluation metrics fail
to capture the linguistic diversity of the CM data. Based on the empirical
observation on the 10 datasets used in Srivastava and Singh (2021a), we
identify four major reasons for the failure of NLG evaluation metrics on the
CM data. We propose a metric independent evaluation pipeline MIPE, for
effective evaluation. Using MIPE, we first reduce the spelling variations (see
Section 3.1) and the language switching (see Section 3.2) in the candidate
Hinglish sentence. Next, we introduce a penalty (see Section 3.3) on the
evaluation score based on the degree of importance of the missing words in the
candidate Hinglish sentence. Finally, we address the challenge of a limited
number of reference sentences (see Section 3.4) by segmenting the candidate
and the reference sentences into phrases and leveraging the paraphrasing
capability. Figure 3 shows the architecture of the proposed evaluation
pipeline.

Figure 3: The architecture of the proposed CM NLG evaluation system MIPE.
Machine-generated candidate CM sentences are generated by two rule-based
algorithms (WAC and PAC). We reduce the spelling variation and language
switching for both the candidate and reference sentences based on phonetics. A
penalty is applied to the words in the candidate sentence which are not
present in any of the reference sentences. We account for limited reference
sentences by chunking the candidate and reference sentences into trigram
phrases. The words in the candidate trigram phrases are assigned a score based
on their presence in the reference phrases. The candidate phrase score is used
to account for the paraphrasing possibilities of the CM reference sentences.

###  3.1 Spelling variations

The first challenge to effective evaluation is the non-standard spellings of
the code-mixed words. E.g., words kanekt, connect, and connekt conveys the
same meaning in a Hinglish sentence. Due to a lack of writing standards for
the code-mixed languages, the speakers often use their phonetic understanding
of the source languages to write the CM sentences. Hence, in most spelling
variations, the addition, omission, and substitution of letters indicate that
the phonetics remains almost the same. Specifically, we observe three major
reasons for spelling variations,

  * •

$R1$: character repetition

  * •

$R2$: replacement with similar-sounding character

  * •

$R3$: vowel omission

To address these problems, we normalize words such that similar-sounding words
are grouped. We leverage the concept of Phonetic Dissimilarity (PDS, Toutanova
and Moore (2002)) to address the spelling variations in the CM language. Our
proposed PDS algorithm is a variant of the popular dynamic programming-based
edit distance algorithm. Similar to edit distance, PDS quantifies the
dissimilarity between two strings by counting the minimum number of edit
operations (addition, deletion, and substitution) required to transform one
string into the other. In PDS, we assign different costs to each edit
operation based on the phonetic characteristics of the corresponding
characters of the two words and the edit operation under consideration. To
access the phonetic characteristics, we use a corpus of all possible
pronunciations of the English
alphabets111https://www.speakmethod.com/alphabet_sounds.html. Algorithm
1describes PDS between a word $w_{1}$ (in candidate CM sentence) and $w_{2}$
(in reference CM sentences). To address $R1$, we remove repeating characters
from both words. By default, we keep addition and deletion cost = 1 and
substitution cost = 2. To address $R2$, we decrease the substitution cost to
$\rho_{sub}$ for similar-sounding characters as substitution of one of these
characters is highly likely. To address $R3$, we decrease the addition cost of
vowels to $\rho_{add}$ and the deletion cost of vowels to $\rho_{del}$, where
$\rho_{add}>\rho_{del}$. This is due to the empirical observation that the
omission of vowels is much more likely than an addition. Further, we decrease
the addition and deletion costs of a possible silent character to
$\rho_{sil}$. We consider the minimum of PDS($w1$, $w2$) and PDS($w2$, $w1$)
as the final PDS score to identify the spelling variation between words $w1$
and $w2$. In our experiments, we keep $\rho_{sub}=\rho_{add}=\rho_{sil}=0.75$,
and $\rho_{del}=0.25$.

###  3.2 Similar Words

Identifying similar words in the same or different languages is a challenging
task in the CM languages. For example, two phrases “in the market” and “in the
bazaar” convey the same semantics, but most automatic evaluation metrics will
fail to identify the semantic similarity. To address the challenge of token-
level similarity, we need a common representation of words across the source
languages. To mitigate this problem, we propose a Similar Word Search (SWS)
procedure. Algorithm 2 shows the description of the SWS procedure. Given a
word from the candidate CM sentence as an input, the SWS procedure returns all
similar words from the corresponding reference sentences. We select that word
from the reference sentences, which yields the minimum PDS value. The SWS
procedure returns a word from the reference set if the minimum PDS value is
less than $\sigma_{thres}$. Otherwise, it computes pairwise cosine distance
(in the cross-lingual word embedding space) between each word in a set of
reference words and the input word. To create the cross-lingual embedding
space, we use the pre-trained word vectors of dimension 300 for English and
Hindi from fastText Bojanowski et al. (2017). For the shared representation,
we use VecMap Artetxe et al. (2018) to learn the mapping in an unsupervised
fashion with the default settings. We use the English and Hindi sentences from
the IIT-B parallel corpus Kunchukuttan et al. (2018). In case the cosine
similarity is greater than $\sigma_{cos}$, the SWS procedure returns the word
from the reference set; else, we assume that no similar word exists in the
reference set. In our experiments, we keep $\sigma_{thres}=2$, and
$\sigma_{cos}=0.5$.

###  3.3 Missing words

Generally, the generated candidate sentence misses some words resulting in a
significant impact on the automatic evaluation scores. Some words are more
important than others, but most metrics consider them equal ($M1$).
Furthermore, most metrics match exact words with no flexibility in spelling
variations and language switching ($M2$). Here, we address both these problems
to apply a missing word penalty to the metric score with some writing style
flexibility. To address $M1$, we use WAC procedure222We employ WAC due to its
capability to generate high-quality sentences (as shown in Srivastava and
Singh (2021b)). Also, the Hinglish sentence generated by WAC has words from
only the source English and Hindi sentences which in turn doesn’t influence
the IDF values of the generated words to a large extent. to generate a large
Hinglish corpus (hereafter ‘ParallelCorp’) of 2,132,184 sentences. For
creating the parallel corpus, we collect English sentences from multiple
sources333https://www.kaggle.com/kazanova/sentiment140,444https://www.kaggle.com/arkhoshghalb/twitter-
sentiment-analysis-hatred-
speech,555http://www.cfilt.iitb.ac.in/iitb_parallel/,666https://www.kaggle.com/columbine/imdb-
dataset-sentiment-analysis-in-csv-format and translate them (if not already
translated) into Hindi language using Google Translate API. We calculate IDF-
values (Inverse Document Frequency) of each word in the Hinglish corpus. The
words with low IDF values occur rarely and hence carry more semantic
information. If a word is not present in the ParallelCorp, we consider it
semantically important. To address $M2$, we relax the exact match condition by
postulating that either the word is present in the candidate sentence or its
variant is present in the sentence. Here, we allow two types of variations (i)
minor spelling variations and (ii) language switch (for more details, see
Sections 3.1 and 3.2). We use the SWS procedure to find a word variant keeping
a maximum distance value of 1. Algorithm 3 shows the description of the
missing word penalty (MWP) in detail. For each word $w$ in a reference
sentence, we check the presence of $w$ and its variants in the candidate
sentence. In case $w$ is not present, we add $w$’s IDF value as the penalty
for the absence. We repeat the procedure for each reference sentence and take
the minimum penalty among all reference sentences. We reduce the MWP score
from the metric score for a given evaluation metric.

###  3.4 Limited Reference Sentences

A sentence can be paraphrased in numerous ways by interchanging subject and
predicate, active and passive voice, and first, second, and third-person
perspectives. With the code-mixed text, the paraphrasing possibilities
significantly increase. For an automatic evaluation, it is infeasible to
generate all possible paraphrases as reference sentences. Even though HinGE
dataset has at least two reference sentences against a candidate sentence but
it is insufficient to include all the possibilities. Thus, paraphrasing
drastically limits the evaluation capabilities of various metrics. To address
this problem, we present an algorithm PhraseScore that captures the
paraphrasing capability of the reference sentences. Algorithm 4 shows the
description of the PhraseScore method. We split the candidate sentence and the
set of reference sentences into trigram phrases. If word w in the candidate
phrase exists in one of the reference phrases, we add the IDF value of the w
in the phrase score for that phrase. Else, we subtract the IDF value as a
penalty. This phrase score is aggregated, normalized over the number of
phrases in the candidate sentence, and divided by the penalty of missing words
in the candidate sentence. To prevent division by zero, we add 0.0001 to the
penalty. In case a word is not present in the IDF dictionary, we assign it a
relatively high value ($\mu_{miss}$) to indicate that it is a rare word of
high importance. Finally, we increase the metric score by adding the candidate
sentence’s PhraseScore. In our experiments, we keep $\mu_{miss}$=20. Due to
the unavailability of a paraphrasing system for a code-mixed language, the
formulation of PhraseScore algorithm depends on the assumption that the
trigram phrases in a sentence can be reordered to create new sentences.

##  4 Results and Evaluation

We evaluate WAC and PAC procedures augmented with MIPE pipeline against all
the five metrics (as discussed in Section 2). Table 1 and 2 shows the effect
of MIPE against the five metrics. As expected, all metrics show better scores
with the MIPE augmentation. The metric scores after the MIPE shows a high
correlation777We experiment with Pearson Correlation Coefficient. against the
metric scores without MIPE (see Table 3). This shows that improvements in the
metric scores is constant throughout and are not by chance.

Table 4 shows the effect of MIPE on the correlation with the human scores. We
use the same criteria to bucket the human ratings as discussed in Section 2.
We observe a higher correlation in all the three buckets for WAC augmented
with MIPE. This improvement is consistent throughout all the metrics. For PAC
augmented with MIPE, we observe a decrease in correlation in the second
bucket, which can be attributed to (i) a relatively large number of poor
quality (low human scores) sentences generated by PAC, and (ii) rating poor
quality CM sentence is a challenging task for humans due to lower readability
of the sentence. For the rest of the buckets, PAC with MIPE shows a higher
correlation with the human scores.

##  5 Current State and Future Directions

Human score | Without MIPE | With MIPE
---|---|---
BLEU | WER | TER | NIST | BS | BLEU | WER | TER | NIST | BS
2 | 0.144 | 0.741 | 0.667 | 0.092 | 0.851 | 0.238 | 0.651 | 0.544 | 0.140 | 0.860
3 | 0.138 | 0.735 | 0.708 | 0.070 | 0.852 | 0.323 | 0.625 | 0.569 | 0.133 | 0.860
4 | 0.133 | 0.695 | 0.666 | 0.103 | 0.849 | 0.391 | 0.536 | 0.480 | 0.184 | 0.906
5 | 0.135 | 0.711 | 0.681 | 0.110 | 0.853 | 0.380 | 0.556 | 0.494 | 0.172 | 0.985
6 | 0.141 | 0.697 | 0.670 | 0.102 | 0.852 | 0.361 | 0.560 | 0.502 | 0.144 | 0.967
7 | 0.161 | 0.663 | 0.630 | 0.111 | 0.856 | 0.398 | 0.522 | 0.453 | 0.168 | 0.947
8 | 0.177 | 0.621 | 0.589 | 0.127 | 0.859 | 0.465 | 0.445 | 0.377 | 0.204 | 0.976
9 | 0.212 | 0.571 | 0.538 | 0.150 | 0.865 | 0.531 | 0.387 | 0.313 | 0.242 | 1.000
10 | 0.291 | 0.509 | 0.493 | 0.157 | 0.878 | 0.572 | 0.318 | 0.252 | 0.291 | 1.000

Table 1: Comparison of metric scores with and without using MIPE for WAC.

Human score | Without MIPE | With MIPE
---|---|---
BLEU | WER | TER | NIST | BS | BLEU | WER | TER | NIST | BS
2 | 0.126 | 0.672 | 0.698 | 0.176 | 0.8603 | 0.338 | 0.474 | 0.500 | 0.318 | 0.997
3 | 0.146 | 0.765 | 0.696 | 0.086 | 0.851 | 0.425 | 0.603 | 0.526 | 0.120 | 0.883
4 | 0.143 | 0.744 | 0.703 | 0.100 | 0.8464 | 0.419 | 0.598 | 0.523 | 0.130 | 0.888
5 | 0.153 | 0.726 | 0.680 | 0.114 | 0.8515 | 0.407 | 0.589 | 0.508 | 0.154 | 0.894
6 | 0.164 | 0.689 | 0.646 | 0.124 | 0.8558 | 0.449 | 0.525 | 0.456 | 0.171 | 0.912
7 | 0.176 | 0.661 | 0.618 | 0.121 | 0.8581 | 0.475 | 0.485 | 0.411 | 0.198 | 0.936
8 | 0.177 | 0.639 | 0.605 | 0.128 | 0.8598 | 0.498 | 0.437 | 0.370 | 0.200 | 0.938
9 | 0.184 | 0.614 | 0.590 | 0.129 | 0.8638 | 0.545 | 0.387 | 0.321 | 0.230 | 0.967
10 | 0.242 | 0.551 | 0.543 | 0.146 | 0.8731 | 0.600 | 0.314 | 0.262 | 0.280 | 0.997

Table 2: Comparison of metric scores with and without using MIPE for PAC. | BLEU | WER | TER | NIST | BS
---|---|---|---|---|---
WAC | 0.948 | 0.988 | 0.984 | 0.961 | 0.8326
PAC | 0.830 | 0.986 | 0.982 | 0.944 | 0.8843
Table 3: Correlation between the evaluation metric scores with and without
using MIPE pipeline.

|  | Correlation with human scores
---
(Without MIPE)
| Correlation with human scores
---
(With MIPE)
Bucket 1 | Bucket 2 | Bucket 3 | Bucket 1 | Bucket 2 | Bucket 3
WAC | PAC | WAC | PAC | WAC | PAC | WAC | PAC | WAC | PAC | WAC | PAC
BLEU | 0.810 | 0.910 | -0.861 | 0.878 | 0.941 | 0.844 | 0.942 | 0.950 | 0.910 | 0.643 | 0.994 | 0.981
WER | -0.936 | -0.822 | -0.785 | 0.457 | -0.993 | -0.973 | -0.949 | -0.780 | -0.880 | 0.713 | -0.995 | -0.993
TER | -0.891 | -0.963 | 0.000 | -0.610 | -0.998 | -0.970 | -0.932 | -0.937 | -0.737 | 0.229 | -0.998 | -0.997
NIST | 0.913 | 0.127 | 0.642 | -0.559 | 0.986 | 0.846 | 0.851 | 0.246 | 0.769 | -0.671 | 0.993 | 0.952
BS | 0.844 | 0.710 | 0.227 | -0.689 | 0.953 | 0.937 | 0.924 | 0.400 | 0.922 | -0.720 | 0.895 | 0.972

Table 4: Comparison of correlation between evaluation metrics and human scores
for WAC and PAC with and without MIPE pipeline.

The results discussed in Section 4 demonstrate a need to build metrics,
theories, and experiments for better CM NLG evaluation. Some of the challenges
and limitations of the proposed MIPE pipeline for effective CM NLG includes:

  * •

Due to the unavailability of resources in other CM language pairs, the MIPE
pipeline is tested on a single CM language. We need to extend the proposed
evaluation strategy to other CM language pairs.

  * •

The presence of two different languages in a single CM sentence increases the
paraphrasing possibility to a much larger extent. We need metrics that attend
to the CM sentences beyond the bag of words model. These metrics should also
be able to account for paraphrasing.

  * •

There are various other reasons (beyond the four reasons discussed in this
paper) that influence the evaluation of CM NLG tasks such as named-entities,
transliteration, etc. The MIPE pipeline doesn’t currently account for these
limitations.

  * •

The code-mixed sentences in the HinGE dataset are not collected from the
social media platforms. The code-mixed data from the social media platform
tends to be more noisy and distorted which could influence the performance of
MIPE pipeline.

As discussed, currently there are several limitations with the CM NLG
evaluation which need to be addressed in order to build effective CM NLG
systems for multilingual societies. Some of the lessons learned and the future
directions for the CM NLG evaluations are:

  * •

The limited resource availability is one of the major bottlenecks in the CM
NLG tasks and evaluation. Currently, the available resources are smaller in
size compared to the monolingual NLG tasks.

  * •

In contrast to the MIPE augmentation pipeline, we need systems that can
leverage the noisy nature of the code-mixed text. The currently proposed MIPE
pipeline addresses the various challenges independently and attempts to
reconstruct the noisy CM text for effective evaluation.

  * •

The two languages participating in CM influence the various constructs of the
target CM sentence such as grammar, syntax, etc. The current experimentation
with only one CM language needs to be explored with other CM languages.

  * •

Recently, we observe a rise in the availability of multilingual language
models (LMs). These LMs could be used to build effective CM NLG evaluation
systems.

  * •

The current evaluation metrics seem to perform poorly with the CM languages.
We need to build dedicated metrics for the CM NLG evaluation tasks that can
leverage the linguistic diversity of the CM data.

##  6 Conclusion

In this paper, we present a metric independent evaluation pipeline for
efficient code-mixed NLG evaluation. The proposed pipeline shows a high
correlation between the human scores and the underlying evaluation metrics.
Besides the four significant challenges to CM NLG evaluation, in the future,
we also plan to address other challenges such as code-mixed existence of
named-entities, informal writing style, and missing context.

## References

  * Artetxe et al. (2018) Mikel Artetxe, Gorka Labaka, and Eneko Agirre. 2018.  A robust self-learning method for fully unsupervised cross-lingual mappings of word embeddings.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 789–798.
  * Baldauf (2004) Scott Baldauf. 2004.  A hindi-english jumble, spoken by 350 million.  [Online; accessed 23-May-2020].
  * Barman et al. (2014) Utsab Barman, Amitava Das, Joachim Wagner, and Jennifer Foster. 2014.  Code mixing: A challenge for language identification in the language of social media.  In _Proceedings of the first workshop on computational approaches to code switching_ , pages 13–23.
  * Bojanowski et al. (2017) Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. 2017.  Enriching word vectors with subword information.  _Transactions of the Association for Computational Linguistics_ , 5:135–146.
  * Chandu et al. (2019) Khyathi Chandu, Ekaterina Loginova, Vishal Gupta, Josef van Genabith, Günter Neumann, Manoj Chinnakotla, Eric Nyberg, and Alan W Black. 2019.  Code-mixed question answering challenge: Crowd-sourcing data and techniques.  In _Third Workshop on Computational Approaches to Linguistic Code-Switching_ , pages 29–38. Association for Computational Linguistics (ACL).
  * Dhar et al. (2018) Mrinal Dhar, Vaibhav Kumar, and Manish Shrivastava. 2018.  Enabling code-mixed translation: Parallel corpus creation and mt augmentation approach.  In _Proceedings of the First Workshop on Linguistic Resources for Natural Language Processing_ , pages 131–140.
  * Doddington (2002) George Doddington. 2002.  Automatic evaluation of machine translation quality using n-gram co-occurrence statistics.  In _Proceedings of the second international conference on Human Language Technology Research_ , pages 138–145.
  * Gautam et al. (2021) Devansh Gautam, Prashant Kodali, Kshitij Gupta, Anmol Goel, Manish Shrivastava, and Ponnurangam Kumaraguru. 2021.  Comet: Towards code-mixed translation using parallel monolingual sentences.  In _Proceedings of the Fifth Workshop on Computational Approaches to Linguistic Code-Switching_ , pages 47–55.
  * Gundapu and Mamidi (2018) Sunil Gundapu and Radhika Mamidi. 2018.  Word level language identification in english telugu code mixed data.  In _Proceedings of the 32nd Pacific Asia Conference on Language, Information and Computation_.
  * Gupta et al. (2021) Abhirut Gupta, Aditya Vavre, and Sunita Sarawagi. 2021.  Training data augmentation for code-mixed translation.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 5760–5766.
  * Gupta et al. (2020) Deepak Gupta, Asif Ekbal, and Pushpak Bhattacharyya. 2020.  A semi-supervised approach to generate the code-mixed text using pre-trained encoder and transfer learning.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: Findings_ , pages 2267–2280.
  * Guzmán et al. (2017) Gualberto A Guzmán, Joseph Ricard, Jacqueline Serigos, Barbara E Bullock, and Almeida Jacqueline Toribio. 2017.  Metrics for modeling code-switching across corpora.  In _INTERSPEECH_ , pages 67–71.
  * Jawahar et al. (2021) Ganesh Jawahar, Muhammad Abdul-Mageed, VS Laks Lakshmanan, et al. 2021.  Exploring text-to-text transformers for english to hinglish machine translation with synthetic code-mixing.  In _Proceedings of the Fifth Workshop on Computational Approaches to Linguistic Code-Switching_ , pages 36–46.
  * Joshi et al. (2016) Aditya Joshi, Ameya Prabhu, Manish Shrivastava, and Vasudeva Varma. 2016.  Towards sub-word level compositions for sentiment analysis of hindi-english code mixed text.  In _Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers_ , pages 2482–2491.
  * Khanuja et al. (2020) Simran Khanuja, Sandipan Dandapat, Sunayana Sitaram, and Monojit Choudhury. 2020\.  A new dataset for natural language inference from code-mixed conversations.  In _Proceedings of the The 4th Workshop on Computational Approaches to Code Switching_ , pages 9–16.
  * Kunchukuttan et al. (2018) Anoop Kunchukuttan, Pratik Mehta, and Pushpak Bhattacharyya. 2018.  The iit bombay english-hindi parallel corpus.  In _Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018)_.
  * Levenshtein (1966) Vladimir I Levenshtein. 1966.  Binary codes capable of correcting deletions, insertions, and reversals.  In _Soviet physics doklady_ , volume 10, pages 707–710.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th annual meeting on association for computational linguistics_ , pages 311–318. Association for Computational Linguistics.
  * Parikh and Solorio (2021) Dwija Parikh and Thamar Solorio. 2021.  Normalization and back-transliteration for code-switched data.  In _Proceedings of the Fifth Workshop on Computational Approaches to Linguistic Code-Switching_ , pages 119–124.
  * Patwa et al. (2020) Parth Patwa, Gustavo Aguilar, Sudipta Kar, Suraj Pandey, PYKL Srinivas, Björn Gambäck, Tanmoy Chakraborty, Thamar Solorio, and Amitava Das. 2020\.  Semeval-2020 task 9: Overview of sentiment analysis of code-mixed tweets.  In _Proceedings of the Fourteenth Workshop on Semantic Evaluation_ , pages 774–790.
  * Pratapa et al. (2018) Adithya Pratapa, Monojit Choudhury, and Sunayana Sitaram. 2018.  Word embeddings for code-mixed language processing.  In _Proceedings of the 2018 conference on empirical methods in natural language processing_ , pages 3067–3072.
  * Priyadharshini et al. (2020) Ruba Priyadharshini, Bharathi Raja Chakravarthi, Mani Vegupatti, and John P McCrae. 2020.  Named entity recognition for code-mixed indian corpus using meta embedding.  In _2020 6th International Conference on Advanced Computing and Communication Systems (ICACCS)_ , pages 68–72. IEEE.
  * Ramanarayanan et al. (2019) Vikram Ramanarayanan, Robert Pugh, Yao Qian, and David Suendermann-Oeft. 2019.  Automatic turn-level language identification for code-switched spanish–english dialog.  In _9th International Workshop on Spoken Dialogue System Technology_ , pages 51–61. Springer.
  * Rizvi et al. (2021) Mohd Sanad Zaki Rizvi, Anirudh Srinivasan, Tanuja Ganu, Monojit Choudhury, and Sunayana Sitaram. 2021.  Gcm: A toolkit for generating synthetic code-mixed text.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: System Demonstrations_ , pages 205–211.
  * Sane et al. (2019) Sushmitha Reddy Sane, Suraj Tripathi, Koushik Reddy Sane, and Radhika Mamidi. 2019\.  Stance detection in code-mixed hindi-english social media data using multi-task learning.  In _Proceedings of the Tenth Workshop on Computational Approaches to Subjectivity, Sentiment and Social Media Analysis_ , pages 1–5.
  * Shekhar et al. (2020) Shashi Shekhar, Dilip Kumar Sharma, and MM Sufyan Beg. 2020.  Language identification framework in code-mixed social media text based on quantum lstm—the word belongs to which language?  _Modern Physics Letters B_ , 34(06):2050086.
  * Singh et al. (2018a) Kushagra Singh, Indira Sen, and Ponnurangam Kumaraguru. 2018a.  Language identification and named entity recognition in hinglish code mixed tweets.  In _Proceedings of ACL 2018, Student Research Workshop_ , pages 52–58.
  * Singh et al. (2018b) Kushagra Singh, Indira Sen, and Ponnurangam Kumaraguru. 2018b.  A twitter corpus for hindi-english code mixed pos tagging.  In _Proceedings of the Sixth International Workshop on Natural Language Processing for Social Media_ , pages 12–17.
  * Singh et al. (2018c) Rajat Singh, Nurendra Choudhary, and Manish Shrivastava. 2018c.  Automatic normalization of word variations in code-mixed social media text.  _arXiv preprint arXiv:1804.00804_.
  * Snover et al. (2006) Matthew Snover, Bonnie Dorr, Richard Schwartz, Linnea Micciulla, and John Makhoul. 2006.  A study of translation edit rate with targeted human annotation.  In _Proceedings of association for machine translation in the Americas_ , volume 200. Cambridge, MA.
  * Srivastava and Singh (2020) Vivek Srivastava and Mayank Singh. 2020.  Phinc: a parallel hinglish social media code-mixed corpus for machine translation.  _arXiv preprint arXiv:2004.09447_.
  * Srivastava and Singh (2021a) Vivek Srivastava and Mayank Singh. 2021a.  Challenges and limitations with the metrics measuring the complexity of code-mixed text.  In _Proceedings of the Fifth Workshop on Computational Approaches to Linguistic Code-Switching_ , pages 6–14.
  * Srivastava and Singh (2021b) Vivek Srivastava and Mayank Singh. 2021b.  Hinge: A dataset for generation and evaluation of code-mixed hinglish text.  _arXiv preprint arXiv:2107.03760_.
  * Thara et al. (2020) S Thara, E Sampath, Phanindra Reddy, et al. 2020.  Code mixed question answering challenge using deep learning methods.  In _2020 5th International Conference on Communication and Electronics Systems (ICCES)_ , pages 1331–1337. IEEE.
  * Toutanova and Moore (2002) Kristina Toutanova and Robert C Moore. 2002.  Pronunciation modeling for improved spelling correction.  In _Proceedings of the 40th Annual Meeting on Association for Computational Linguistics_ , pages 144–151.
  * Utsav et al. (2020) Jethva Utsav, Dhaiwat Kabaria, Ribhu Vajpeyi, Mohit Mina, and Vivek Srivastava. 2020\.  Stance detection in hindi-english code-mixed data.  In _Proceedings of the 7th ACM IKDD CoDS and 25th COMAD_ , CoDS COMAD 2020, page 359–360, New York, NY, USA. Association for Computing Machinery.
  * Vyas et al. (2014) Yogarshi Vyas, Spandana Gella, Jatin Sharma, Kalika Bali, and Monojit Choudhury. 2014.  Pos tagging of english-hindi code-mixed social media content.  In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 974–979.
  * Winata et al. (2019) Genta Indra Winata, Zhaojiang Lin, and Pascale Fung. 2019.  Learning multilingual meta-embeddings for code-switching named entity recognition.  In _Proceedings of the 4th Workshop on Representation Learning for NLP (RepL4NLP-2019)_ , pages 181–186.
  * Yang et al. (2020) Zhen Yang, Bojie Hu, Ambyera Han, Shen Huang, and Qi Ju. 2020.  Csp: Code-switching pre-training for neural machine translation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 2624–2636.
  * Zhang et al. (2019) Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q Weinberger, and Yoav Artzi. 2019\.  Bertscore: Evaluating text generation with bert.  _arXiv preprint arXiv:1904.09675_.


# Decoding of Variable Length PLH Codes

Marco Morini, Alessandro Ugolini, and Giulio Colavolpe This work has been
supported by MIUR under the PRIN Liquid_Edge contract. This research benefits
from the HPC (High Performance Computing) facility of the University of Parma,
Italy. The authors are with University of Parma, Department of Engineering and
Architecture, and CNIT Research Unit, Parma, Italy (E-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS>giulio.colavolpe@unipr.it).

###### Abstract

In this paper, we address the problem of the decoding of variable length
physical layer header (PLH) codes. We take as a case study the DVB-S2X
standard, and, after selecting a suitable PLH code with variable codeword
length, we propose two alternative noncoherent decoding strategies. The
proposed decoding strategies allow to estimate the length of the transmitted
PLH field, which is unknown at the receiver, jointly with the decoding of the
PLH code. We demonstrate that it is possible to achieve an excellent decoding
performance while significantly reducing the overhead due to the transmission
of the PLH field with respect to a standard fixed-length PLH.

###### Index Terms:

DVB-S2X, PLH decoding, decoding design

##  I Introduction

Many communication standards, for both broadcast and unicast applications,
foresee the use of a physical layer header (PLH) field at the beginning of
each transmitted frame. This is a control field which is usually exploited to
mark the start of frames and for synchronization purposes. Moreover, PLH
fields contain information on the content of the subsequent frame, like the
indication of the modulation and coding formats (ModCod) adopted for the
transmission. For example, the extension of the second generation of the
digital video broadcasting via satellite (DVB-S2X) standard [1] adopts a
$90$-bit PLH in each of the transmitted frames, which includes an invariant
$26$-bit start-of-frame (SoF) sequence, followed by a $64$-bit PLH codeword,
which contains the ModCod information. The PLH is then modulated by means of a
$\pi/2-$binary phase-shift keying (BPSK). DVB-S2X adopts constellations with
sizes from $4$ to $256$, and a wide variety of coding rates to encode
information by means of low-density parity-check (LDPC) codes, which define a
set of $39$ ModCods (see [1]). The constellation size and the code rate
represent the information that is encoded by means of a PLH code and enclosed
in the PLH field at the beginning of each frame. Hence, it is mandatory to
successfully retrieve the information enclosed in the PLH before attempting
the decoding of the transmitted information; in fact, the LDPC decoder needs
to know the adopted modulation and coding formats, and this information can be
achieved only if the PLH field is correctly decoded. A representation of the
DVB-S2X frame structure is reported in Fig. 1, where the division of the
header in SoF and PLH code is highlighted.

Figure 1: Frame structure for the DVB-S2X standard [1].

Received signals are usually affected by unknown amplitude and phase offsets,
which are detrimental for the decoding performance. These impairments can be
estimated by means of pilot symbols, which are distributed in blocks at
regular intervals in the frame. However, a variation of these effects over
time can result in an imprecise pilot-based estimation, which would negatively
affect the PLH decoding performance. A solution to this problem has been
proposed by designing PLH codes which allow for noncoherent detection, which
can be successfully decoded even in presence of a phase offset. It is known
that the performance of noncoherent detection is almost equivalent to those
obtained with a coherent receiver, so the risk of incurring in a performance
loss is negligible [2, 3].

Another example of the need of PLH codes allowing noncoherent detection has
arisen from recent studies showing that precoding can ensure significant
performance gains in a multibeam satellite system [4, 5, 6]. In a precoded
system, the precoding matrix is computed at the transmitter in order to
minimize the interference from other co-frequency signals, but it is unknown
at the receiver. Hence, the received signals can be affected by a constant
unknown amplitude and phase, that cannot be estimated by means of pilot
symbols, which are not precoded. After successful noncoherent detection of the
PLH, it is possible to estimate the amplitude and phase of the subsequent
information block transmitted in that frame, which is precoded with the same
precoding matrix.

Typically, PLH codes have short length, as the above mentioned $64$-bit
codewords included in the DVB-S2X standard. The design of short codes robust
to noncoherent detection has been object of several research works, see for
example[7, 8, 9, 10]. Generally, communication standards foresee the use of
constant length PLH headers. However, it has been proved that significant
gains can be obtained by adopting variable length codes for the PLH [11].
This, however, makes the decoding of the PLH field especially challenging
because the receiver needs to estimate also the length of the received PLH.
Furthermore, when the PLH has a variable length, the position of pilot symbols
is not known at the receiver prior to PLH decoding, so pilots cannot be used
for phase estimation, thus further emphasizing the need for noncoherent
detection. The short codeword length, however, makes PLH decoding performance
practically unaffected by the presence of phase noise because the phase offset
on the PLH field can be considered constant.

In order to successfully adopt variable length PLH codes in a realistic
scenario, it is necessary to design a decoding scheme able to ensure good
performance when the PLH codeword length is unknown at the receiver. In this
paper, we adopt the strategy proposed in [10] to design a variable length code
suitable for noncoherent detection, and we apply it to the DVB-S2X case study.
We associate to each of the DVB-S2X ModCods a PLH codeword, with the aim of
reducing the length of the PLH field with respect to the standard. We then
design two alternative decoding strategies to jointly estimate the length of
the PLH field and to successfully decode the transmitted codeword, which is
the main contribution of the paper. We select the DVB-S2X scenario as an
example to demonstrate the proposed strategies, but the same framework can be
easily applied to other communication systems with different characteristics.

The paper is organized as follows. In Section II we provide a general system
model, and in Section III we briefly describe the adopted code. Section IV
represents the core of the paper, as it describes the designed decoding
strategies, whose effectiveness is proved by a set of numerical simulations
reported in Section V. Finally, Section VI concludes the paper.

##  II System Model

The system considers the transmission of a sequence of information symbols
with associated a PLH field of length $L$, belonging to a finite set of
lengths, as specified in Table I, where the first column represents the
signal-to-noise ratio (SNR) convergence threshold of the LDPC code for each
ModCod, as specified in the DVB-S2X standard [1]. The details of the selected
code design will be reported in the next section, while the meaning of the
third and fourth columns of Table I will be clear at the end of this section.

TABLE I: PLH code details. SNR range [dB] | PLH Length $L$ | $N_{L}$ | $P(L)$
---|---|---|---
-2.85 | 64 | 1 | 0.0256
-2.03 | 58 | 1 | 0.0256
[0.22, 4.73] | 48 | 3 | 0.0769
[5.13, 19.57] | 26 | 34 | 0.8718

Let us define by $L_{\mathrm{max}}$ the maximum value that $L$ can assume. It
is always possible to consider the transmission of a vector of symbols of
length $L_{\mathrm{max}}$, regardless of the true value of $L$. The vectors
can be thus represented as divided in two distinct parts: the first one,
indicated with subscript 1, of length $L$, contains the PLH symbols, while the
second one, indicated with subscript 2, of length $\Delta
L=L_{\mathrm{max}}-L$, contains unknown information symbols, which are drawn
from a constellation with cardinality $M$, which depends on the selected
ModCod.

Let us assume to transmit a vector of symbols
$\boldsymbol{c}=[\boldsymbol{c}_{1},\boldsymbol{c}_{2}]^{T}$ with length
$L_{\mathrm{max}}$ such that $\boldsymbol{c}_{1}$ contains the PLH symbols and
$\boldsymbol{c}_{2}$ contains randomly generated symbols of an unknown
constellation. We can define the received vector $\boldsymbol{r}$, of length
$L_{\mathrm{max}}$, as

$\boldsymbol{r}=A\boldsymbol{c}e^{j\theta}+\boldsymbol{w}$

where $\theta$ is an unknown channel phase, assumed constant and uniformly
distributed in $[0,2\pi)$, $A$ is the unknown amplitude and $\boldsymbol{w}$
is a vector of i.i.d. complex Gaussian noise samples, whose real and imaginary
components have variance $\sigma^{2}$. This is the scenario specified in the
DVB-S2X implementation guidelines for broadcast applications [12].

All LDPC ModCods are considered equally likely. Since the number of ModCods
associated to an arbitrary length $L$ is, in general, different, the
probability to choose a PLH of length $L$ can take different values. Assuming
that the number of ModCods is $N$, the probability to select a PLH of length
$L$ is

$P(L)=\frac{N_{L}}{N},$

where $N_{L}$ is the number of possible ModCods with PLH of length $L$. For
the DVB-S2X standard and the adopted PLH code, described in the next section,
the values of $N_{L}$ and $P(L)$ are reported in Table I, while $N=39$.

##  III Adopted PLH Code

We used the method presented in [10] for generating short codes that are
robust to noncoherent detection for BPSK. We generate codes with length $V$,
code size $K$ and minimum distance $d_{\mathrm{{min}}}$. The main idea behind
the proposed algorithm is to add, at each step, a new column to the generator
matrix $\mathbf{G}$, with dimension $K\times V$, such that the minimum
distance $d_{\mathrm{{min}}}$ of the resulting new code is increased as much
as possible. At each step, the column added to the generator matrix is checked
to be different from all the existing columns. The algorithm stops when a
target $d_{\mathrm{min}}$ is achieved.

We associate to each of the DVB-S2X ModCods a PLH codeword whose length is
reported in the second column of Table I, with the aim of reducing the length
of the PLH field with respect to the standard. We try to reduce as much as
possible the code length by selecting the code with minimal length achieving
the desired decision error rate at a target SNR.

In the design problem for PLH, given the desided error probability and the
channel SNR, we need to construct the code with the shortest possible length.
Therefore, a relation between these parameters is needed in order to correctly
design the code. It can be demonstrated (see for example [2]) that a
conservative upper bound for the codeword error probability $P_{E}$ when using
noncoherent detection is given by

$P_{E}\leq\left(2^{K}-1\right)\frac{1}{2}\mathrm{erfc}\left(\sqrt{Bd_{\mathrm{min}}\frac{E_{\mathrm{s}}}{N_{0}}}\right)\,,$

with $B=1$ and $B=1/2$ for BPSK and QPSK, respectively. This bound provides a
relation between the desired codeword error probability, minimum distance, and
SNR of the channel.

In our considered scenario, we need $K=6$ bits to distinguish among all the
codewords. Assuming a target codeword error rate (CER) equal to $10^{-5}$ and
considering that, in the worst case condition,
$\frac{E_{\mathrm{s}}}{N_{0}}=-2.85$ dB (see [1]), we can obtain a lower bound
for the minimum distance equal to $d_{\mathrm{min}}=26$. The corresponding PLH
code with $K=6$ and $d_{\mathrm{min}}=26$ has length $V=64$ [10]. This
corresponds to the longest codeword in Table I. By repeating the procedure
with the other target SNRs, we can obtain the other values of $L$ in the
table.

##  IV Designed PLH Decoding Strategies

In this section, we propose two alternative strategies for the decoding of a
variable length PLH code as the one described in Section III.

The decoding strategy, when both the PLH and its length are unknown, can be
based on the generalized likelihood criterion

$\left(\hat{A},\hat{L},\hat{\boldsymbol{c}}\right)=\operatorname*{arg\,max}_{(A,L,\boldsymbol{c})}P(\boldsymbol{c},L,A|\boldsymbol{r})\,.$
(1)

Equation (1) gives an estimation of both the transmitted PLH codeword and its
length. It also provides an estimation of the amplitude $A$. Clearly, it is

$P(\boldsymbol{c}|L)=\begin{cases}\frac{1}{N_{L}}&\text{if $\boldsymbol{c}$ is
a codeword of length }L\\\ 0&\text{otherwise.}\end{cases}$

Hence, with $\boldsymbol{c}$ a codeword of length $L$,

$P(\boldsymbol{c}|L)P(L)=\frac{1}{N_{L}}\frac{N_{L}}{N}=\frac{1}{N}$

and, because $N$ does not depend on $L$, the decoding strategy in (1)
simplifies to

$\left(\hat{A},\hat{L},\hat{\boldsymbol{c}}\right)=\operatorname*{arg\,max}_{(A,L,\boldsymbol{c})}\frac{p(\boldsymbol{r}|\boldsymbol{c},L,A)}{p(\boldsymbol{r})}\,.$

Since we are considering a vector of length $L_{\mathrm{max}}$, thus
independent of $L$, $p(\boldsymbol{r})$ is irrelevant in the maximization and
it can be ignored. The generalized likelihood function can be rewritten as

$\begin{split}\left(\hat{A},\hat{L},\hat{\boldsymbol{c}}_{1}\right)&=\operatorname*{arg\,max}_{(A,L,\boldsymbol{c}_{1})}P(\boldsymbol{c}_{1},L,A|\boldsymbol{r})\\\
&=\operatorname*{arg\,max}_{(A,L,\boldsymbol{c}_{1})}p(\boldsymbol{r}|\boldsymbol{c}_{1},L,A)P(L)\\\
&=\operatorname*{arg\,max}_{(A,L,\boldsymbol{c}_{1})}p(\boldsymbol{r}|\boldsymbol{c}_{1},L,A)\,.\end{split}$
(2)

By exploiting the fact that vector $\boldsymbol{r}$ can be divided in two
parts, the last probability density function (PDF) in (2) can be expressed as

$\begin{split}&p(\boldsymbol{r}|\boldsymbol{c}_{1},L,A)=p(\boldsymbol{r}_{1},\boldsymbol{r}_{2}|\boldsymbol{c}_{1},L,A)\\\
&=\left(\frac{1}{M}\right)^{\Delta
L}\sum_{\boldsymbol{c}_{2}}p(\boldsymbol{r}_{1},\boldsymbol{r}_{2}|\boldsymbol{c}_{1},\boldsymbol{c}_{2},L,A)\\\
&=\left(\frac{1}{M}\right)^{\Delta
L}\frac{1}{2\pi}\int\left[\sum_{\boldsymbol{c}_{2}}p(\boldsymbol{r}_{1},\boldsymbol{r}_{2}|\boldsymbol{c}_{1},\boldsymbol{c}_{2},L,A,\theta)\right]\mathrm{d}\theta\,.\end{split}$
(3)

Note that, in (3), the average with respect to $\boldsymbol{c}_{2}$, that is
necessary to obtain the marginal PDF in (2), and the average w.r.t. the
unknown phase $\theta$, are exploited. Given the fact that
$\boldsymbol{r}_{1}$ and $\boldsymbol{r}_{2}$ are uncorrelated, it is possible
to write

$p(\boldsymbol{r}_{1},\boldsymbol{r}_{2}|\boldsymbol{c}_{1},\boldsymbol{c}_{2},L,A,\theta)=p(\boldsymbol{r}_{1}|\boldsymbol{c}_{1},L,A,\theta)p(\boldsymbol{r}_{2}|\boldsymbol{c}_{2},L,A,\theta)\,.$
(4)

Hence, the two PDFs in (4) can be computed separately. For the first one, we
can write

$\begin{split}&p(\boldsymbol{r}_{1}|\boldsymbol{c}_{1},L,A,\theta)=\prod_{k=1}^{L}p(r_{k}|c_{k},A,\theta)\\\
&=\prod_{k=1}^{L}\left(\frac{1}{2\pi\sigma^{2}}\right)\exp\left\\{-\frac{1}{2\sigma^{2}}|r_{k}|^{2}\right\\}\exp\left\\{-\frac{A^{2}}{2\sigma^{2}}|c_{k}|^{2}\right\\}\\\
&\exp\left\\{\frac{A}{\sigma^{2}}\Re\left[r_{k}c_{k}^{*}e^{-j\theta}\right]\right\\}\,.\end{split}$
(5)

As we will demonstrate in the next two subsections, because of some of the
approximations involved in the derivation of the algorithms, the dependence on
the channel phase $\theta$ will only appear in the first part of the right
hand side of (4). Hence, we can average (5) over $\theta$ to obtain

$\begin{split}&p(\boldsymbol{r}_{1}|\boldsymbol{c}_{1},L,A)=\frac{1}{2\pi}\int_{0}^{2\pi}p(\boldsymbol{r}_{1}|\boldsymbol{c}_{1},L,A,\theta)\mathrm{d}\theta\\\
&=\left(\frac{1}{2\pi\sigma^{2}}\right)^{L}\exp\left\\{-\frac{1}{2\sigma^{2}}\sum_{k=1}^{L}|r_{k}|^{2}\right\\}\\\
&\exp\left\\{-\frac{A^{2}}{2\sigma^{2}}\sum_{k=1}^{L}|c_{k}|^{2}\right\\}\mathrm{I}_{0}\left(\frac{A}{\sigma^{2}}\left|\sum_{k=1}^{L}r_{k}c_{k}^{*}\right|\right)\,,\end{split}$
(6)

in which $\mathrm{I}_{0}(\cdot)$ is the modified Bessel function of the first
kind of order zero. For the second term in (4), instead, we can write

$p(\boldsymbol{r}_{2}|L,A,\theta)=\prod_{k=L+1}^{L_{\mathrm{max}}}\left[\frac{1}{M}\sum_{c_{k}}p(r_{k}|c_{k},A,\theta)\right]\,.$
(7)

The term in square brackets in (7) cannot be computed in closed form, so some
approximations are needed. In the following two subsections, we derive two
alternative decoding rules based on different approximations.

###  IV-A Strategy 1

Let us consider one term of the summation in (7). It can be written as

$\begin{split}&p(r_{k}|c_{k},A,\theta)=\left(\frac{1}{2\pi\sigma^{2}}\right)\exp\left\\{-\frac{1}{2\sigma^{2}}|r_{k}|^{2}\right\\}\\\
&\exp\left\\{-\frac{A^{2}}{2\sigma^{2}}|c_{k}|^{2}+\frac{A}{\sigma^{2}}\Re\left[r_{k}c_{k}^{*}e^{-j\theta}\right]\right\\}\,.\end{split}$

By using a first order Taylor approximation for the second exponential, we get

$\begin{split}&p(r_{k}|c_{k},A,\theta)\simeq\left(\frac{1}{2\pi\sigma^{2}}\right)\exp\left\\{-\frac{1}{2\sigma^{2}}|r_{k}|^{2}\right\\}\\\
&\left[1-\frac{A^{2}}{2\sigma^{2}}|c_{k}|^{2}+\frac{A}{\sigma^{2}}\Re\left[r_{k}c_{k}^{*}e^{-j\theta}\right]\right]\,.\end{split}$

Moreover, by averaging out terms with zero mean, we obtain that

$\begin{split}\frac{1}{M}\sum_{c_{k}}p(r_{k}|c_{k},A,\theta)\\\
&\simeq\left(\frac{1}{2\pi\sigma^{2}}\right)\exp\left\\{-\frac{1}{2\sigma^{2}}|r_{k}|^{2}\right\\}\left[1-\frac{A^{2}}{2\sigma^{2}}\right]\end{split}$

and, hence, we can write

$\begin{split}p(\boldsymbol{r}_{2}|L,A,\theta)\simeq\left(\frac{1}{2\pi\sigma^{2}}\right)^{\Delta
L}\\\
&\exp\left\\{-\frac{1}{2\sigma^{2}}\sum_{k=L+1}^{L_{\mathrm{max}}}|r_{k}|^{2}\right\\}\left[1-\frac{A^{2}}{2\sigma^{2}}\right]^{\Delta
L}\,,\end{split}$ (8)

where we notice that the dependence on $\theta$ has disappeared. Finally, we
can compute (3) by combining (6) and (8):

$\begin{split}&p(\boldsymbol{r}|\boldsymbol{c}_{1},L,A)=\left(\frac{1}{2\pi\sigma^{2}}\right)^{L_{\mathrm{max}}}\exp\left\\{-\frac{1}{2\sigma^{2}}\sum_{k=1}^{L_{\mathrm{max}}}|r_{k}|^{2}\right\\}\\\
&\exp\left\\{-\frac{A^{2}}{2\sigma^{2}}\sum_{k=1}^{L}|c_{k}|^{2}\right\\}\mathrm{I}_{0}\left(\frac{A}{\sigma^{2}}\left|\sum_{k=1}^{L}r_{k}c_{k}^{*}\right|\right)\left[1-\frac{A^{2}}{2\sigma^{2}}\right]^{\Delta
L}\,.\end{split}$

Being $L_{\mathrm{max}}$ constant, the first two terms are irrelevant. For the
last one we assume to make the following approximation, which is good if
$\sigma^{2}\gg 1$:

$\left[1-\frac{A^{2}}{2\sigma^{2}}\right]^{\Delta L}\simeq 1\,.$

Hence, by exploiting the approximation $\mathrm{I}_{0}(x)\simeq e^{x}$ and
taking the logarithm, the decision rule becomes

$\left(\hat{A},\hat{L},\hat{\boldsymbol{c}}_{1}\right)=\operatorname*{arg\,max}_{(A,L,\boldsymbol{c}_{1})}\left(A\left|\sum_{k=1}^{L}r_{k}c_{k}^{*}\right|-\frac{A^{2}L}{2}\right)\,.$
(9)

By performing the maximization with respect to $A$ first, we obtain that the
amplitude estimate is

$\hat{A}=\frac{\left|\sum_{k=1}^{L}r_{k}c_{k}^{*}\right|}{L}\,.$ (10)

Substituting (10) in (9), we have

$\left(\hat{L},\hat{\boldsymbol{c}}_{1}\right)=\operatorname*{arg\,max}_{(L,\boldsymbol{c}_{1})}\frac{\left|\sum_{k=1}^{L}r_{k}c_{k}^{*}\right|^{2}}{L}\,.$
(11)

Considering that we used several approximations in the derivation of this
decision rule, some of them involving the PLH length, it can be convenient to
correct the metric as follows

$\left(\hat{L},\hat{\boldsymbol{c}}_{1}\right)=\operatorname*{arg\,max}_{(L,\boldsymbol{c}_{1})}\frac{\left|\sum_{k=1}^{L}r_{k}c_{k}^{*}\right|^{2}}{L^{\alpha}}\,,$
(12)

where $\alpha$ is a coefficient to be optimized.

###  IV-B Strategy 2

An alternative decoding scheme can be derived by considering the following
approximation

$c_{k}\simeq E\left\\{|c_{k}|\right\\}e^{j\psi_{k}}=e^{j\psi_{k}}\,,$

where $\\{\psi_{k}\\}$ are independent random variables with uniform
distribution in $[0,2\pi)$. By averaging with respect to $\psi_{k}$, we can
rewrite (7) as

$\begin{split}&p(\boldsymbol{r}_{2}|L,A,\theta)\\\
&=\prod_{k=L+1}^{L_{\mathrm{max}}}\frac{1}{2\pi}\int_{0}^{2\pi}\left[\frac{1}{M}\sum_{c_{k}}p(r_{k}|c_{k},A,\theta)\right]\mathrm{d}\psi_{k}\\\
&=\left(\frac{1}{2\pi\sigma^{2}}\right)^{\Delta
L}\exp\left\\{-\frac{1}{2\sigma^{2}}\sum_{k=L+1}^{L_{\mathrm{max}}}|r_{k}|^{2}\right\\}\exp\left\\{-\frac{A^{2}}{2\sigma^{2}}\Delta
L\right\\}\\\
&\prod_{k=L+1}^{L_{\mathrm{max}}}\frac{1}{2\pi}\int_{0}^{2\pi}\exp\left\\{\frac{A}{\sigma^{2}}\Re\left[r_{k}e^{-j\psi_{k}}e^{-j\theta}\right]\right\\}\mathrm{d}\psi_{k}\\\
&=\left(\frac{1}{2\pi\sigma^{2}}\right)^{\Delta
L}\exp\left\\{-\frac{1}{2\sigma^{2}}\sum_{k=L+1}^{L_{\mathrm{max}}}|r_{k}|^{2}\right\\}\exp\left\\{-\frac{A^{2}}{2\sigma^{2}}\Delta
L\right\\}\\\
&\prod_{k=L+1}^{L_{\mathrm{max}}}\frac{1}{2\pi}\int_{0}^{2\pi}\exp\left\\{\frac{A}{\sigma^{2}}|r_{k}|\cos\left(\psi_{k}+\theta-\angle{r_{k}}\right)\right\\}\mathrm{d}\psi_{k}\,.\end{split}$

Using second order Taylor approximation for the last exponential, we obtain

$\begin{split}&p(\boldsymbol{r}_{2}|L,A,\theta)\\\
&\simeq\left(\frac{1}{2\pi\sigma^{2}}\right)^{\Delta
L}\exp\left\\{-\frac{1}{2\sigma^{2}}\sum_{k=L+1}^{L_{\mathrm{max}}}|r_{k}|^{2}\right\\}\exp\left\\{-\frac{A^{2}}{2\sigma^{2}}\Delta
L\right\\}\\\
&\prod_{k=L+1}^{L_{\mathrm{max}}}\frac{1}{2\pi}\int_{0}^{2\pi}\left[1+\frac{1}{\sigma^{2}}|r_{k}|\cos\left(\psi_{k}+\theta-\angle{r_{k}}\right)\right.\\\
&\left.+\frac{1}{2\sigma^{4}}|r_{k}|^{2}\cos^{2}\left(\psi_{k}+\theta-\angle{r_{k}}\right)\right]^{A}\mathrm{d}\psi_{k}\,.\end{split}$

Adopting now the approximation $(1+x)^{r}\simeq 1+rx$ for $|x|\ll 1$, we get

$\begin{split}&p(\boldsymbol{r}_{2}|L,A,\theta)\\\
&\simeq\left(\frac{1}{2\pi\sigma^{2}}\right)^{\Delta
L}\exp\left\\{-\frac{1}{2\sigma^{2}}\sum_{k=L+1}^{L_{\mathrm{max}}}|r_{k}|^{2}\right\\}\exp\left\\{-\frac{A^{2}}{2\sigma^{2}}\Delta
L\right\\}\\\
&\prod_{k=L+1}^{L_{\mathrm{max}}}\frac{1}{2\pi}\int_{0}^{2\pi}\left[1+\frac{A}{\sigma^{2}}|r_{k}|\cos\left(\psi_{k}+\theta-\angle{r_{k}}\right)\right.\\\
&\left.+\frac{A}{2\sigma^{4}}|r_{k}|^{2}\cos^{2}\left(\psi_{k}+\theta-\angle{r_{k}}\right)\right]\mathrm{d}\psi_{k}\\\
&=\left(\frac{1}{2\pi\sigma^{2}}\right)^{\Delta
L}\exp\left\\{-\frac{1}{2\sigma^{2}}\sum_{k=L+1}^{L_{\mathrm{max}}}|r_{k}|^{2}\right\\}\exp\left\\{-\frac{A^{2}}{2\sigma^{2}}\Delta
L\right\\}\\\
&\prod_{k=L+1}^{L_{\mathrm{max}}}\left(1+\frac{A}{8\pi\sigma^{4}}|r_{k}|^{2}\right)\,.\end{split}$
(13)

Note that this expression is independent of $\theta$. Hence, we can compute
(3) by using (6) and (13) as

$\begin{split}&p(\boldsymbol{r}|\boldsymbol{c}_{1},L,A)=\left(\frac{1}{2\pi\sigma^{2}}\right)^{L_{\mathrm{max}}}\exp\left\\{-\frac{1}{2\sigma^{2}}\sum_{k=1}^{L_{\mathrm{max}}}|r_{k}|^{2}\right\\}\\\
&\mathrm{I}_{0}\left(\frac{A}{\sigma^{2}}\left|\sum_{k=1}^{L}r_{k}c_{k}^{*}\right|\right)\exp\left\\{-\frac{A^{2}}{2\sigma^{2}}L_{\mathrm{max}}\right\\}\\\
&\prod_{k=L+1}^{L_{\mathrm{max}}}\left(1+\frac{A}{8\pi\sigma^{4}}|r_{k}|^{2}\right)\,.\end{split}$

By removing the first two irrelevant terms, applying the approximation
$\mathrm{I}_{0}(x)\simeq e^{x}$, and taking the logarithm, the likelihood
function can be written as

$\begin{split}&\left(\hat{A},\hat{L},\hat{\boldsymbol{c}}_{1}\right)=\operatorname*{arg\,max}_{(A,L,\boldsymbol{c}_{1})}\left(\frac{A}{\sigma^{2}}\left|\sum_{k=1}^{L}r_{k}c_{k}^{*}\right|\right.\\\
&\left.+\sum_{k=L+1}^{L_{\mathrm{max}}}\log\left(1+\frac{A}{8\pi\sigma^{4}}|r_{k}|^{2}\right)-\frac{A^{2}L_{\mathrm{max}}}{2\sigma^{2}}\right)\,.\end{split}$

Approximating $\log(1+x)\simeq x$ for $|x|\ll 1$, we get

$\begin{split}&\left(\hat{A},\hat{L},\hat{\boldsymbol{c}}_{1}\right)=\operatorname*{arg\,max}_{(A,L,\boldsymbol{c}_{1})}\left(A\left|\sum_{k=1}^{L}r_{k}c_{k}^{*}\right|\right.\\\
&\left.+\frac{A}{8\pi\sigma^{2}}\sum_{k=L+1}^{L_{\mathrm{max}}}|r_{k}|^{2}-\frac{A^{2}L_{\mathrm{max}}}{2}\right)\,.\end{split}$
(14)

Also in this case, we perform the maximization with respect to $A$ first to
obtain the following amplitude estimate value,

$\hat{A}=\frac{\left|\sum_{k=1}^{L}r_{k}c_{k}^{*}\right|+\frac{1}{8\pi\sigma^{2}}\sum_{k=L+1}^{L_{\mathrm{max}}}|r_{k}|^{2}}{L_{\mathrm{max}}}\,.$
(15)

Finally, by replacing (15) in (14), we obtain the decision rule

$\begin{split}\left(\hat{L},\hat{\boldsymbol{c}}_{1}\right)&=\operatorname*{arg\,max}_{(L,\boldsymbol{c}_{1})}\left(\left|\sum_{k=1}^{L}r_{k}c_{k}^{*}\right|+\frac{1}{8\pi\sigma^{2}}\sum_{k=L+1}^{L_{\mathrm{max}}}|r_{k}|^{2}\right)^{2}\\\
&=\operatorname*{arg\,max}_{(L,\boldsymbol{c}_{1})}\left|\sum_{k=1}^{L}r_{k}c_{k}^{*}\right|+\frac{1}{8\pi\sigma^{2}}\sum_{k=L+1}^{L_{\mathrm{max}}}|r_{k}|^{2}\,.\end{split}$

Also in this case, we can apply a correction factor $\beta$ to the metric, to
be optimized, in order to take into account the approximations involved in the
derivation. Hence, the final metric is

$\left(\hat{L},\hat{\boldsymbol{c}}_{1}\right)=\operatorname*{arg\,max}_{(L,\boldsymbol{c}_{1})}\left|\sum_{k=1}^{L}r_{k}c_{k}^{*}\right|+\frac{\beta}{\sigma^{2}}\sum_{k=L+1}^{L_{\mathrm{max}}}|r_{k}|^{2}\,.$
(16)

We can notice that this strategy requires knowledge of the noise variance
$\sigma^{2}$.

##  V Numerical Results

In this section, we show the performance of the proposed decoding schemes
derived in Sections IV-A and IV-B in the considered DVB-S2X scenario. For each
possible length of the PLH, we select the ModCod associated with the lowest
SNR, in order to test the decoder in the worst working conditions. This
corresponds to ModCods 1, 2, 3, and 6, as can be observed from Table I. The
performance is compared with that achievable with the code adopted by the
DVB-S2X standard [1]. We remind that the standard uses a fixed-length
$64$-bits PLH code, designed to guarantee reliable performance in all working
conditions. A receiver for the standard code operates according to the
following decoding rule

$\boldsymbol{\hat{c}}=\operatorname*{arg\,max}_{\boldsymbol{c}}\left|\sum_{k=1}^{L_{\mathrm{max}}}r_{k}c_{k}^{*}\right|\,,$
(17)

and its performance will be labeled as _standard_ in this section. We also
compare the proposed decoding strategies with another benchmark strategy,
denoted as _simple_ in this section. This decoder does not know the codeword
length and it simply computes the likelihood function of each codeword with
the received signal, assuming always the maximum length $L_{\mathrm{max}}$,
and it operates according to decoding rule (17). This is representative of the
performance achievable in a system adopting a variable length PLH, but using a
conventional detection scheme.

###  V-A Strategy 1

The performance of the first proposed strategy is reported in Figs. 2 and 3 as
a function of the ratio between the average energy per symbol and the noise
power spectral density, $E_{\mathrm{s}}/N_{0}$, for ModCods 1 and 6,
respectively. Different values of the parameter $\alpha$ in (12) are compared.
We can see that for ModCod $1$ all tested values of $\alpha$ provide
relatively similar performance, and that increasing the value of $\alpha$ the
performance tends to degrade. We also notice that, in this case, the standard
and the simple receivers reach similar performance. This is not surprising,
because in our proposed scheme ModCod 1 adopts a $64$-bits PLH codeword, which
is the same length considered by both the standard and simple schemes.

If we look at ModCod 6, instead, first of all we notice the poor performance
of the simple receiver scheme. Also in this case, this was expected, recalling
that this scheme attempts decoding on $64$ bits, but the PLH codeword for
ModCod 6 is only 26 bits long, so the decoder tries to use also part of the
information symbols, which are encoded and modulated with the code and
modulation specific to the ModCod. We can also notice the large gap between
the standard decoder and our proposed solution. This is also unsurprising,
considering that the standard code needs to work properly for all ModCods,
including those operating at low SNR, so it has to be robust to the worst case
scenario. Adopting a variable length code, and a corresponding decoding
strategy, allows us to relax this robustness constraint for ModCods operating
at higher SNR, like ModCod 6 and those above. If we compare the curves for
different values of $\alpha$, we see that the performance improves by
increasing $\alpha$. This is exactly the opposite of the behavior we observed
for ModCod 1, so the problem arises of how to select $\alpha$ to guarantee a
good trade-off in all cases.

Figure 2: PLH CER for ModCod 1 using Strategy 1. Figure 3: PLH CER for ModCod
6 using Strategy 1.

In order to allow for a correct decoding of the transmitted information, it is
important that the PLH is reliably decoded at SNR values that are lower than
the working conditions of the ModCods. Fig. 4 shows the gap from the ModCod
convergence threshold, as reported in [1], for several values of $\alpha$, at
a target ${\mathrm{CER}=10^{-5}}$.

Figure 4: Gap in dB from the ModCod convergence threshold for several values
of $\alpha$ at ${\mathrm{CER}=10^{-5}}$, using Strategy 1.

From the figure, we can notice that the maximum gap is minimized for
$\alpha=0.5$. Moreover, we can see that for $0.3\leq\alpha\leq 0.7$ the gaps
are negative, which means that the PLH is decoded with a CER below $10^{-5}$
for SNR values which are lower than the ModCod convergence threshold. This is
fundamental to guarantee the correct decoding of all ModCods. Considering the
probability of occurrence of the different PLH lengths, we notice that
choosing $\alpha=0.7$ is a value which mostly favors the most probable length
and still keeps the PLH decoding performance below the LDPC convergence
threshold for all ModCods. Values of $\alpha$ higher than $0.7$ will reduce
the gap for ModCod $6$ but also increase the gap for the other ModCods, so
they should not be considered.

###  V-B Strategy 2

The results obtained using Strategy 2 in Section IV-B are presented in this
section. Through simulation, we verified that the metric shows the best
performance for $\beta=0.2$ for all ModCods; the gaps from the ModCods
convergence threshold are presented in Table II.

TABLE II: Gap in dB from the ModCod convergence threshold at ${\mathrm{CER}=10^{-5}}$ using Strategy 2 with $\beta=0.2$. ModCod | Gap from LDPC threshold
---|---
1 | -0.86
2 | -1.04
3 | -1.67
6 | -4.35

We see that for all the ModCods the PLH is decoded reliably at SNR values that
are lower than the ModCods convergence threshold; in particular, for ModCod 6,
a very large gap can be ensured.

As mentioned, Strategy 2 requires knowledge of the noise variance. The results
reported in Table II assume perfect knowledge of the variance, but this
parameter can be estimated [13]. We resort to the algorithm proposed in [14],
which is based on the second and fourth order moments of the received signal,
and does not need pilot symbols to perform estimation, so it is independent of
the adopted frame structure. Fig. 5 reports the CER curves for ModCods 1 and 6
assuming ideal knowledge of the noise variance and using the variance
estimator [14] ($\hat{\sigma}^{2}$ curves). We notice that we can achieve the
same performance with the variance estimator as in case of perfect knowledge
of the variance.

Figure 5: PLH CER comparison for Strategy 2 using a noise variance estimator.

###  V-C Comparison and Discussion

We have proposed two alternative decoding strategies, with different
complexity and performance. Clearly, the best decoding strategy depends on the
probability distribution of the PLH length over the ModCods, as well as on the
number of ModCods and on the adopted PLH code. However, both proposed decoding
strategies can ensure very good performance using a PLH with length
significantly lower than that used in the DVB-S2X standard. In fact, if we
compare the proposed design with the standard, where all $39$ ModCods adopt a
fixed length $64$-bit code, and taking into account the probability
distribution of the codeword length reported in Table I, we can notice that
the average codeword length is $30$ bits, so less than half the value adopted
in the standard.

If we compare Strategy 1 and Strategy 2, we notice that Strategy 2 has
slightly better performance, in terms of larger gaps from LDPC convergence
threshold, at the cost of an increased complexity. In fact, Strategy 1 (12)
operates only on the first $L$ symbols, while Strategy 2 (16) takes all
$L_{\mathrm{max}}$ symbols into account. A standard fixed length PLH decoding
strategy would operate with the metric (17) on all $L_{\mathrm{max}}$ symbols,
and the same would happen for the described simple receiver. Table III reports
the complexity of the different strategies, in terms of number of real
operations. To evaluate the complexity, we have to keep in mind that the PLH
uses $\pi/2-$BPSK symbols, so multiplications with preamble symbols only
results in a change of the sign of the real or the imaginary part. Hence,
multiplications by preamble symbols are not accounted for. Look-up table (LUT)
accesses are necessary to evaluate square roots to compute absolute values.
For Strategy 1 and 2 we have used the average codeword length, $30$, to
evaluate the complexity. We notice that Strategy 1 has a largely inferior
complexity with respect to both Strategy 2 and a standard decoding scheme,
while Strategy 2 is comparable to the standard scheme in terms of additions
and it requires more multiplications. Hence, Strategy 1 is clearly desirable
from an implementation complexity point of view. We have to keep in mind,
however, that the performance and complexity may vary depending on the PLH
length distribution, number of PLH codewords and the channel conditions.
Hence, while the general decoding framework remains valid, performance must be
evaluated according to the characteristics of the considered communication
system.

TABLE III: Complexity comparison of the proposed decoding strategies. Strategy | # additions | # multiplications | # LUT
---|---|---|---
Standard (17) | $2L_{\mathrm{max}}-1=127$ | $2$ | $1$
Strategy 1 (12) | $2L-1=59$ | $2$ | $0$
Strategy 2 (16) | $2L_{\mathrm{max}}-4=124$ | $2L_{\mathrm{max}}-2L=68$ | $1$

##  VI Conclusions

We proposed two decoding strategies to decode a PLH code with variable length
codewords. The use of a variable length code for the PLH field allows for a
significant reduction of the overhead in each of the transmitted frames, but
makes decoding harder because the codeword length is unknown at the receiver.
We took the DVB-S2X standard as a test case, and showed that excellent
decoding performance can be achieved by estimating the unknown length of the
PLH field, together with the decoding of the PLH code. The proposed decoding
strategies ensure that a very low error rate can be reached at SNR values
which allow for a successful decoding of the information enclosed in the
frames. The proposed decoders rely on the tuning of a parameter, which takes
into account the approximations involved in the derivation. The optimal value
of this parameter, clearly, depends on the investigated scenario and on the
adopted PLH code, but the general strategy can be easily applied to different
cases and applications.

## References

  * [1] ETSI EN 302 307-2 Digital Video Broadcasting (DVB), Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications, Part II: S2-Extensions (DVB-S2X).  Available on ETSI web site (http://www.etsi.org).
  * [2] G. Colavolpe and R. Raheli, “Theoretical analysis and performance limits of noncoherent sequence detection of coded PSK,” IEEE Trans. Inform. Theory, vol. 46, pp. 1483–1494, July 2000.
  * [3] G. Colavolpe and R. Raheli, “The capacity of the noncoherent channel,” European Trans. Telecommun., vol. 12, pp. 289–296, July/August 2001.
  * [4] P.-D. Arapoglou, A. Ginesi, S. Cioni, S. Erl, F. Clazzer, S. Andrenacci, and A. Vanelli-Coralli, “DVB-S2X-enabled precoding for high throughput satellite systems,” International Journal of Satellite Communications and Networking, vol. 34, pp. 439–455, May/June 2016.
  * [5] M. A. Vazquez, M. Caus, and A. Perez-Neira, “Performance analysis of joint precoding and MUD techniques in multibeam satellite systems,” in Proc. IEEE Global Telecommun. Conf., (Washington, DC, USA), Dec. 2016.
  * [6] A. Guidotti and A. Vanelli-Coralli, “Clustering strategies for multicast precoding in multibeam satellite systems,” International Journal of Satellite Communications and Networking, vol. 38, pp. 85–104, March/April 2020\.
  * [7] R. Knopp and H. Leib, “$M$-ary phase coding for the noncoherent AWGN channel,” IEEE Trans. Inform. Theory, vol. 40, no. 6, pp. 1968–1984, 1994\.
  * [8] H. Jin and T. Richardson, “Design of low-density parity-check codes for noncoherent MPSK communication,” in Proc. IEEE International Symposium on Information Theory, (Lausanne, Switzerland), p. 169, June-July 2002\.
  * [9] Ruey-Yi Wei, “Noncoherent block-coded MPSK,” IEEE Trans. Commun., vol. 53, no. 6, pp. 978–986, 2005.
  * [10] F. Kayhan and G. Montorsi, “Short-length rate-compatible code design for noncoherent detection,” International Journal of Satellite Communications and Networking, 2019.
  * [11] F. Kayhan and G. Montorsi, “Code design for adaptive coding and modulation indicator in broadcast systems,” International Journal of Satellite Communications and Networking, vol. 34, no. 6, pp. 771–785, 2016.
  * [12] ETSI TR 102 376-2, Implementation guidelines for the second generation system for Bradcasting, Interactive Service, News Gathering and other broadband satellite applications, Part 2: S2 Extensions (DVB-S2X).  Available on ETSI web site (http://www.etsi.org).
  * [13] D. R. Pauluzzi and N. C. Beaulieu, “A comparison of SNR estimation techniques for the AWGN channel,” IEEE Trans. Commun., vol. 48, pp. 1681–1691, Oct. 2000.
  * [14] N. Kamel and V. Jeoti, “A linear prediction based estimation of signal-to-noise ratio in AWGN channel,” Etri Journal - ETRI J, vol. 29, pp. 607–613, 10 2007.