On the potential of permutation-based repetition coding-like symbol level coding

Abstract

The purpose of this thesis is to investigate the potential of transmitting data
symbols alongside permuted copies in a repetition coding-like scheme, called the
permutation scheme. First exhaustive search is conducted for small constellation
sizes to identify possible patterns. The next step was identifying local search
methods for permutations, and other methods for longer chains of permutations.

It was found that as permutations are used, the energy efficiency d2min of the
high-dimensional constellation improves as more and more permutations are used.
It was also found that the union bound of a high-dimensional constellation is still
indicative of the constellations respective bit error rate performance. Bit error
rate was evaluated for the Gaussian channel.

Another seminal investigation was if, and how the permutation scheme could be
used alongside binary coding schemes such as block codes. The results show that
the block codes do work in conjunction with the permutation scheme, and that
random interleaving still functions as expected.

Another property of permutations examined is how optimal permutations for 8-
PSK constellations are affected when the constellation points are normalized with
respect to different p-norms. We show that energy efficiency (as well as spectral
efficiency) is invariant with respect to norm, and a by only using one permutation
the scheme outperforms binary signaling with respect to both these metrics.

In terms of future work, a more thorough study is suggested on other methods for
finding optimal or near-optimal permutations, including relaxations of optimiza-
tion problems and heuristics. Furthermore, additional verification of the scheme
under different channel models, for example, would be an interesting line of
research to pursue.

Popular Abstract

In our modern world it is preferable that wireless communication is as reliable and
energy efficient as possible, to which efficient error correcting codes are desirable.
In this project, these codes take the form of high-dimensional constellations, and
have their symbol alternatives in such locations that the energy efficiency of the
transmission can be improved in comparison to underlying uncoded modulation
schemes. These symbols are essentially the interface between data bits and physi-
cal signals, where the more symbol alternatives a constellation has, the more bits
can be packed into a single symbol. In this thesis high-dimensional constellations
are investigated, alongside their corresponding symbol error probability bounds
and theoretical bit error rates.

These high-dimensional symbol constellations are constructed from an underly-
ing or regular constellation. We refer to the high-dimensional constellation as
the counterpart of the regular constellation. When the symbol alternatives in the
counterpart are permuted just right, the distance between the symbol alternatives
becomes large, meaning that it becomes easier to separate them or detect them,
when the physical signal is affected by random noise in a wireless channel.

To actually find these good permutations or the optimal one in the first place,
exhaustive search is first conducted for the pulse amplitude modulating scheme
(PAM) and the phase shift keying modulating scheme (PSK) in order the identify
any and all possible patterns. For constellations with a "too large" number of
symbol alternatives, e.g, sixteen, then there are simply too many possible permu-
tations to go through them all. For such cases, when the number of permutations
was too large for exhaustive search, we used a greedy local search strategy using
randomly selected subsets of permutations.

It was found that such a strategy can be used to improve the energy efficiency
of constellations. Like expected, simulations verify that the theoretic increase of
energy efficiency resulted in lower bit error rate. In the simulations, the channel
was modeled as a signal sent plus additive wide sense stationary Gaussian noise.

The simulations show that the introduced permutation scheme is seemingly com-
patible with previously established error correcting codes.

• author: Larsson, Linus
• supervisor: Johan Thunberg; Juan Vidal Alegria
• organization: Department of Electrical and Information Technology
• course: EITM01 20251
• year: 2025
• type: H2 - Master's Degree (Two Years)
• subject: Technology and Engineering
• keywords: Channel coding, repetition coding, symbol level coding, permutations, energy efficiency, spectral efficiency
• report number: LU/LTH-EIT 2025-1084
• language: English
• id: 9200670
• date added to LUP: 2025-07-02 09:57:00
• date last changed: 2025-07-02 09:57:00