11institutetext: ETH Zürich, Rämistrasse 101, 8092 Zürich, Switzerland
11email<EMAIL_ADDRESS>22institutetext: Università di Bologna, via Zamboni 33, 40126 Bologna, Italy

# Fast Shared-Memory Barrier Synchronization for a 1024-Cores RISC-V Many-Core
Cluster

Marco Bertuletti 11 0000-0001-7576-0803 Samuel Riedel 11 0000-0002-5772-6377
Yichao Zhang 11 0009-0008-7508-599X Alessandro Vanelli-Coralli 1122
0000-0002-4475-5718 Luca Benini 1122 0000-0001-8068-3806

###### Abstract

Synchronization is likely the most critical performance killer in shared-
memory parallel programs. With the rise of multi-core and many-core
processors, the relative impact on performance and energy overhead of
synchronization is bound to grow. This paper focuses on barrier
synchronization for TeraPool, a cluster of 1024 RISC-V processors with non-
uniform memory access to a tightly coupled 4MB shared L1 data memory. We
compare the synchronization strategies available in other multi-core and many-
core clusters to identify the optimal native barrier kernel for TeraPool. We
benchmark a set of optimized barrier implementations and evaluate their
performance in the framework of the widespread fork-join Open-MP style
programming model. We test parallel kernels from the signal-processing and
telecommunications domain, achieving less than 10% synchronization overhead
over the total runtime for problems that fit TeraPool’s L1 memory. By fine-
tuning our tree barriers, we achieve $1.6\times$ speed-up with respect to a
naive central counter barrier and just 6.2% overhead on a typical 5G
application, including a challenging multistage synchronization kernel. To our
knowledge, this is the first work where shared-memory barriers are used for
the synchronization of a thousand processing elements tightly coupled to
shared data memory.

###### Keywords:

Many-Core RISC-V Synchronization 5G.

##  1 Introduction

With the slow-down of Moore’s Law at the turning of the century, multi-core
systems became widespread, to sustain performance increase at an acceptable
power budget in a scenario of diminishing returns for technology scaling [16].
Nowadays, the popularity of many-core systems increases, as they offer huge
parallel computing power to achieve top performance on embarrassingly parallel
workloads, from genomics over computational photography and machine learning
to telecommunications [11, 14, 17]. For example, NIVIDIA’s H100 Tensor Core
graphic processing unit (GPU) features $144$ streaming multiprocessors (SMs)
with $128$ processing elements (PEs) [3], artificial intelligence (AI)
accelerators such as TsunAImi assemble $4$ RunAI200 chiplets [1] with
$250\,000$ PEs within standard SRAM arrays for an at-memory design,
Esperanto’s ET-Soc-1 chip has over a thousand RISC-V processors on a single
chip and more than $160$ MB of on-chip SRAM[5].

As the number of cores increases, scaling up architectures by instantiating
many loosely-coupled clusters is a common architectural pattern adopted by
many-cores to ensure modularity. However, this approach introduces overheads,
including workload distribution, data allocation and splitting, inter-cluster
communication and synchronization. To reduce these costs, increasing the
cluster size is therefore desirable, as a direction space exploration the
physical viability of this direction was demonstrated by MemPool [4, 15],
which couples $256$ RISC-V Snitch[19] PEs to a shared data memory ensuring low
access latency. In this paper we further scale-up MemPool and increase the
core count to $1024$.

MemPool and TeraPool have a fork-join (the abstraction at the base of Open-MP)
programming model: sequential execution forks to a parallel section, where PEs
access concurrently the shared memory. Barriers are used to synchronize and
switch back to the sequential execution. The cost of barrier synchronization
is a relevant factor to determine the performance of a parallel program and
scales with the number of PEs involved [12]. Despite the high core count, the
synchronization overhead in TeraPool must be minimal, as we desire speedup
also for kernels that do not have lots of work in each parallel thread.
Moreover, synchronizing only some cores in the cluster must be possible, to
ease workload distribution, increase the PEs utilization, and ensure more
degrees of freedom in the parallel decomposition of a full application.

In this paper, we challenge the fork-join programming model, implementing fast
barriers for a shared-memory tightly coupled cluster of 1024 cores. Our
contributions include:

  * •

A comparison of the synchronization strategies adopted on other large-scale
many-core systems, with a focus on how the hierarchy of the hardware
architecture affects the barrier implementation.

  * •

The implementation of a central counter barrier and a k-ary tree
synchronization barrier for TeraPool, exploiting hardware support to trigger
the wakeup of all the PEs in the cluster or a fraction of them.

  * •

An in-depth analysis of the performance of TeraPool on shared-memory parallel
kernels synchronized with the implemented barriers, showing that the
granularity of synchronization can be tuned on the basis of the kernel
characteristics and that the barrier selection is an important stage of the
kernel optimization.

A key insight is that tree barriers give up to $1.6\times$ speed-up with
respect to centralized barriers and less than 6.2% impact of synchronization
on the total runtime of a full application from the field of 5G
communications. Focusing on a RISC-V-based open-source many-core system
enables us to provide an in-depth analysis of the synergies between our
barrier implementations and the underlying hardware architecture. This is a
key advantage over proprietary vendor-specific solutions, where an incomplete
disclosure of architecture prevents effective hardware-software co-design.

##  2 Related work

In the following, we survey relevant contributions on the synchronization of
tens to hundreds of PEs. Most of the implementations focused on cached-based
systems, with PEs grouped in hierarchies and sharing only the last-level
cache.

In [13], an extended butterfly barrier was designed for Intel Xeon Phi
Knight’s Landing processor, whose $72$ PEs, each having a private L1 data
cache, are grouped in 32 tiles, connected by a 2D all-to-all mesh
interconnect. The synchronization occurs in multiple stages, whereby a pair of
threads notify each other of their arrival via atomic read and writes to
synchronization variables. The architecture enforces cache coherence and the
synchronization variables must be aligned to the cache boundary to avoid false
sharing. The results indicate that at high core count, in such a fragmented
and tiled many-core system, the butterfly barrier ($\sim 2500$ cycles)
outperforms less hierarchical centralized barriers ($\sim 6500$ cycles) where
a single master thread is responsible for verifying the PEs’ arrival. In [6],
tree barriers are tested on different many-core architectures with up to $64$
ARMv8 cores. Authors focus on tournament barriers with a tree structure that
fit the hierarchical core-cache organization of the underlying architecture,
achieving a synchronization overhead of $642.5$, $618.2$, and $356$ kilo-
cycles on the ThunderX2, the Pythion 2000+, and the Kunpeng920 processors,
respectively. In [18], four barriers (single-master linear barrier, tournament
tree barrier, butterfly barrier, and all-to-all barrier) are tested on the
model of a scalable architecture with $N_{PE}$ simple PEs connected together
with a highly scalable nework on chip (NoC) interconnect. Barriers were tested
on different network topologies for up to $128$ PEs. In highly connected NoC
topologies, such as the Torus, barriers have less than $400$ cycles
synchronization overhead, and the all-to-all barrier, where any PE can
simultaneously send a message to other PEs, performs the best. In a Mesh NoC,
synchronization overhead takes up to $10\,000$ cycles for the all-to-all
barrier but is limited to less than $1000$ cycles for the tree and the
butterfly barriers, as tree barriers become optimal when interconnect
resources are reduced. In [7], the low core count (only $8$ to $16$ cores) of
the multicore architecture makes hardware support for quadratic-complexity PE
to PE signaling feasible and highly energy efficient. For the barriers
implemented, the average length of periods where PEs can work independently
from each other with 10% overhead of barriers corresponds to just 42 cycles.

In the context of GPU programming, the compute unified device architecture
(CUDA) application programmable interface (API) has primitives that enable
cooperative parallelism, including producer-consumer parallelism and
synchronization across a thread group, the entire thread grid or even multiple
GPUs [8]. From the hardware viewpoint, NVIDIA Ampere first added asynchronous
barriers, with a non-blocking arrival phase that allows threads to keep
working on independent data while waiting. When eventually all threads need
data produced by others, they wait until everyone arrives, spinning on a
shared variable. In Hopper GPUs, threads sleep instead of spinning while
waiting, and transaction barriers are introduced to enable asynchronous copies
of data [3]. Due to the proprietary nature of these tools, the behavior in
hardware and the software implementation of GPU barriers is not entirely
transparent.

Figure 1: a) The architecture of the TeraPool cluster and b) scheme of the
implemented wakeup cluster registers and triggers.

TeraPool is the scaled-up version of the MemPool cluster presented in [4, 15].
The TeraPool cluster, represented in Fig. 1, has $1024$ PEs tightly coupled to
a multi-banked shared data memory. The access latency to any memory location
is limited to $5$ cycles, thanks to a hierarchical partition of the PEs and of
the AXI interconnection resources. $8$ PEs are grouped in a Tile, with single-
cycle access latency to $32$ local banks via a local interconnect. $16$ Tiles
are part of a Group. Each PE in a Tile can access the memory banks of another
Tile in the same Group in less than $3$ cycles, thanks to the Group-level
16x16 interconnect. $8$ Groups build a cluster, and each PE can access a bank
of a Tile in another Group in less than $5$ cycles, though point-to-point
connections between Groups. In a Tile, PEs share the interconnection resources
towards another Tile in the same Group, and in a Group, Tiles share the
interconnection resources towards another Group. Contentions may arise when
more than one memory request tries to access the same memory bank or the same
shared interconnection resource, leading to one of them being stalled for one
cycle. The cluster has a non uniform memory access (NUMA) interconnect, but
the low access latency in the case of no contentions makes TeraPool a good
approximation of the parallel random access machine (PRAM) model [10].

In [13, 6, 18] the best performance of a barrier algorithm over another is
strongly dictated by the interconnection topologies and by the clustering of
PEs in hierarchies. In TeraPool, synchronization variables in any bank of the
shared memory can be accessed at an almost equivalent and low cost, allowing
to choose the granularity of barrier synchronization on the basis of the
workload characteristics rather than of the topology of the interconnection
between PEs and of the hierarchical partition of the hardware.

Figure 2: a) Binary tree for the arrival phase of the barrier. Couples of PEs
synchronize by atomically accessing shared synchronization variables. b)
Central counter barrier.

##  3 Barriers implementation

In this section, we describe the implementation of our barrier primitives. A
synchronization barrier algorithm can be divided into three phases: an
arrival, a notification, and a re-initialization phase.

For the arrival phase, we adopt a k-ary tree. The $N_{PE}$ cores of the
cluster are divided into $N_{PE}/k$ groups of $k$ PEs. In each group,
synchronization occurs in the form of a central-counter barrier [9]. Each PE
arriving at the barrier updates a shared counter via an atomic fetch&add
operation and goes into a wait for interrupt (WFI) sleeping state. The last PE
reaching the synchronization step, fetches a counter value equal to $k-1$ and
continues with the next steps, where it is further synchronized with the other
$N_{PE}/k-1$ PEs that survived the first step. The last step counts $k$ PEs,
and the very last PE arriving wakes up all the PEs in the cluster. The arrival
tree works best when the $log_{k}(N_{PE})$ is an integer, but it is also
adapted to the case where $k$ is any power of $2$ $<N_{PE}$, by synchronizing
a number of PEs different from the radix of the tree in the first step of the
barrier. Varying $k$, we encounter two extremes, represented in Fig. 2 (a-b):
the left shows a radix-2 logarithmic tree barrier, where each step only
synchronizes pairs of PEs, the right illustrates the central-counter barrier.
The re-initialization phase is implemented concurrently with the arrival
phase, as each PE arriving last in a synchronization step also resets the
shared barrier counter before proceeding to the next step.

The notification phase leverages hardware support in the form of a centralized
wakeup handling unit. The last PE arriving at the barrier and fetching from
the shared barrier counter variable writes in a cluster shared register. The
address of this register is in the cluster global address space and can be
accessed by any core through the hierarchical AXI interconnections. The
written value is detected by the wakeup handling logic that sends a wakeup
signal to each individual PE, triggering $N_{PE}$ hardwired wakeup lines. A
software implementation of the wakeup mechanism is excluded because it would
fall into the single master barrier class [13], whose cost scales linearly
with $N_{PE}$ and is unsuitable for synchronizing more than a few tens of PEs.

We support synchronizing a subset of PEs in the cluster modifying the wakeup
handling unit by adding other memory-addressable shared registers, as shown in
Fig. 1. The core wakeup register is a 32-bit register that can be used to
either trigger a wakeup signal to all the PEs in the cluster, when it is set
to all ones, or to a single PE, by specifying its ID. One 8-bit register is
used to selectively wake up Groups, and a register per Group is added to wake
up Tiles in a Group selectively. A bitmask is used to determine the Groups or
the Tiles to wake up. Depending on the bitmask written by a PE in one of the
synchronization registers, the wakeup logic, asserts a subset of or all the
wakeup triggers hardwired to the cores in the cluster, to trigger a wakeup
signal.

The implemented barriers can be called from the function body through a custom
software API. The radix of the barrier can be tuned through a single
parameter, to ease trials and selection of the best synchronization option.

##  4 Benchmarking strategy

In the following, we describe the benchmarking strategy adopted to evaluate
the performance of our barriers. Software is compiled with GCC 7.1.1 and runs
on the open-source register transfer level (RTL) model of TeraPool, via a
QuestaSim 2021.2 cycle-accurate simulation. In all the cases we assume that
the input data resides in the L1 memory of the cluster.

###  4.1 Benchmarking with random delay

We first test the implemented barriers on the synchronization of PEs with a
synthetic kernel implementing a random execution time for the parallel
threads. The PEs start the execution together and proceed in parallel through
a synchronization-free time interval. At this point, before entering the
barrier, the cores are delayed by a number of cycles drawn from a uniform
distribution between zero and a maximum delay. We track the average time spent
by the PEs in the barrier. Since the result is subjected to the randomness of
the delay, we average it over multiple tests. We also compute the fraction of
the cycles spent in a barrier over the total runtime, as a function of the
initial parallel section of the program only, referred to as synchronization
free region (SFR). The goal is to estimate the minimum SFR for a negligible
overhead, which is important information for the programmer on the granularity
of the workload allocation to PEs.

###  4.2 Benchmarking of kernels

We analyze the performance of the barriers on benchmark kernels with a key
role in the field of signal processing and telecommunications. The kernels are
implemented using a fork-join programming model, in which each PE operates on
separate portions of the input data and accesses memory concurrently with the
others. The final synchronization is achieved through a barrier call after all
PEs completed their tasks. We can identify three classes of kernels:

  * •

The dot-product (DOTP) and the ax plus y (AXPY) are implemented enforcing
local access of the PEs to memory so that all the inputs can be fetched with
one cycle latency. The data to be processed is equally divided between the
PEs. The dot-product implies a reduction, which is implemented via the atomic
addition of each PE’s partial sum to a shared variable.

  * •

In the direct cosine transform (DCT) and matrix-matrix multiplication (MATMUL)
the workload is equally distributed between PEs, but we cannot enforce local
access for all the PEs. Therefore, we expect some memory requests to take on
average more cycles because of the inherent interconnection topology and
contentions arising from concurrent parallel accesses.

  * •

In the 2D-convolution (Conv2D), the workload is not equally distributed
because some PEs are just used to compute the image border, but the access
pattern is locally constrained as seen for AXPY and DOTP.

Figure 3: Scheduling of $N\times 4$ FFTs on TeraPool. Stage by stage, a group
of N independent FFTs is scheduled on the same subset of PE, which are then
partially synchronized.

###  4.3 Benchmarking of a 5G-processing application

Finally, we consider the implementation and performance of a full 5G
application running on TeraPool, evaluating the impact of synchronization
overhead on parallelization. We benchmark the Orthogonal Frequency Division
Multiplexing (OFDM) demodulation stage of the lower Physical Layer (PHY) in 5G
Physical Uplink Shared Channel (PUSCH), followed by a digital beamforming
stage. In this workload, $N_{RX}$ independent antenna streams, consisting of
$N_{SC}$ orthogonal sub-carrier samples, undergo a fast Fourier transform
(FFT). The beamforming process is a linear combination of the antennas’
streams, by known coefficients, producing $N_{B}$ streams of $N_{SC}$ samples.
Between the two steps, there is a strong data dependency, and synchronization
is needed.

The implemented radix-4 decimation in frequency FFT is a challenging multi-
stage synchronization kernel, because PEs need to be synchronized after each
butterfly stage. In a butterfly stage, each PE combines $4$ inputs to produce
$4$ outputs. We can store the inputs locally in the same bank on different
rows. Given the banking factor of $4$, each core can work with the minimum
access latency on $4\times 4$ input data and store the data in the local banks
of PEs that will use them in the next FFT stage. A 4096-points FFT is
therefore stored in the local memory of $256$ PEs and processed by them, as
shown in Fig. 3. Synchronization overhead is kept to the bare minimum: every
FFT stage is run in parallel over a subset of PEs of the cluster. Cores
working on different FFTs are independently synchronized, leveraging the
partial barriers. Since a barrier is needed after each FFT computation stage,
the PEs can load twiddles and work on multiple independent FFTs before
joining, thus reducing the fraction of synchronization overhead over the total
runtime.

Beamforming is implemented as a MATMUL between the $N_{B}\times N_{RX}$ matrix
of beamforming coefficients and the output FFT streams. Each PE computes a
different output element, as the dot-product between a row and a column of the
first and second input matrix respectively. The workload is distributed
column-wise between $1024$ PEs, so that each column goes to a different PE,
while accesses to rows can happen concurrently.

We try different configurations, as proposed in the 3rd Generation Partnership
Project (3GPP) technical specifications [2]. Assuming $N_{SC}=4096$, we
consider a Multiple-Input Multiple-Output (MIMO) systems with $N_{RX}=16$,
$32$ or $64$ antennas and $N_{B}=32$ beams.

##  5 Results

This section discusses the results of our benchmarking experiments. Fig. 4 (a)
represents the cycles between the last PE entering and the last one leaving
the barrier when each PE has a different random delay, extracted from a
uniform distribution between zero and a maximum value. When the delay is zero
for all PEs, the cycles for the barrier call exhibit a scoop behavior
depending on the radix used. Low radix barriers require a longer multi-step
synchronization process. In this sense, the binary-tree logarithmic barrier is
the worst, having $10$ steps where PEs are synchronized in pairs. Barriers
with few centralized synchronization variables require simultaneous access to
the same memory locations by multiple PEs, creating banking conflicts. On this
side, the linear central-counter barrier, where $1024$ PEs conflict for the
same memory location, is the worst. As the maximum delay increases, the PEs’
arrival at the barrier is scattered. Therefore, contentions in accessing the
synchronization variables reduce, and the lower radix barriers start to be
more expensive than the higher radix ones, generating a staircase pattern.
Ultimately, for the $2048$ cycles delay, the central-counter barrier is the
best, because cores requests to the barrier variable are sufficiently
scattered in time to avoid contentions. The time that the last PE arriving at
the barrier needs to traverse all the levels of the k-ary tree is, in this
case, the most relevant part of the barrier runtime.

Figure 4: a) Cycles between the last PE entering and leaving the barrier for
different barrier radices, and maximum delays between the incoming PEs. b)
Fraction of the best-performing barriers’ overhead as a function of the SFR.
Figure 5: CDF of the distributions of the difference between the fastest and
the slowest PE runtimes for different exemplary parallel kernels before
synchronization.

Fig. 4 (b) shows the fraction of the average cycles spent in a barrier by a
PE, over the total runtime cycles, as a function of the SFR. The PEs’ arrival
is scattered as in the previous experiment. We consider different values of
the maximum random delay between the PEs, and for each case, we report the
results on the barrier with the best-performing radix. To achieve a
synchronization overhead of less than 10%, our barriers need a SFR between
$2000$ and $10\,000$ cycles, depending on the scattering of the arriving PEs.

Since the arrival time of PEs is not always uniformly distributed, we measured
the actual distribution for various key kernels and evaluated its impact on
synchronization. Fig. 5 represents the cumulative distribution function (CDF)
of the difference between the runtime cycles of the fastest and the slowest PE
before synchronization for different parallel kernels.

  * •

The local access enforced for the AXPY and the DOTP kernels makes them
conclude their job at the same time, independently of the input dimension.
Contentions in accessing the reduction variable make some PEs slower than
others for the execution of the DOTP.

  * •

The access latency and the contentions in fetching memory locations that are
distributed over the banks make the arrival of the PEs executing DCT, MATMUL,
and Conv2D more scattered. The difference between the arrival time of PEs
depends on the input dimension, because the larger the input data, the more
the contentions. Interestingly the most compact distribution in arrival times
for the DCT kernel is obtained for an input of length $2\times 4096$. In this
case, each PE works on two inputs of $2\times 2$ samples. Since TeraPool has
$1024$ PEs and a banking factor of $4$, and the addresses run sequentially,
the data is always stored locally.

  * •

In the case of the Conv2D, we see a wide gap between the first and the last
PEs arriving, which is caused by work imbalance. Some PEs are indeed assigned
to the calculation of the boundary of the input image, which containing zeros
is resolved in a lower number of instructions with respect to the pixels in
the center of the image.

Figure 6: Colormaps of a) the delay between the last PE leaving and the last
PE entering the barrier, b) the fraction of cycles for a barrier call (average
on all PEs) over the total runtime, for different kernels, input dimensions,
and barrier radices. c) Speed-up of the kernel synchronized with the fastest
barrier on the kernel using the slowest barrier for each input dimension.
Figure 7: a) Execution cycles for the 5G OFDM and beamforming with different
synchronization barriers. b) Speed-up with respect to serial execution on a
Snitch core. c) Speed-up with respect to the baseline using the linear
central-counter barrier.

Fig. 6 (a) reports the delay between the last PE leaving the barrier and the
last PE entering the barrier for different exemplary kernels, input
dimensions, and radices of the k-ary tree barrier. The AXPY and the DCT find
their sweet spot around radices $32$ and $16$ because the scattering in the
arrival of PEs is moderate and the use-case falls in the scoop region on the
plot in Fig. 4 (a). The arrival of the PEs in the Conv2D kernel is split
between the fast cores computing the border of the input image and the slow
cores computing the inner pixels, which are predominant, resulting in similar
behavior to AXPY and DCT. The arrival of the PEs working on the DOTP kernel is
scattered because of the reduction process. In this case, the lower-radix
barriers have the worst performance, and the central counter barrier shows the
best performance. We identify a behavior that is close to the staircase
pattern on the right-hand side of Fig. 4 (a). The sparsity in the arrival of
PEs strongly depends on the input dimension for the MATMUL kernel. Therefore,
we find a small delay behavior for the very steep distribution obtained in the
case of the input $128\times 32\times 128$ and a large delay behavior for the
smooth distribution obtained in the case of the input $256\times 128\times
256$. The intermediate dimension has an intermediate behavior with some
outlier points, caused by a peculiar feature of our barrier implementation:
the synchronization of subsets of PEs in the leaves nodes of the tree barriers
is initially performed on PEs with a contiguous index, therefore, mostly
between PEs in the same Tile or in the same Group. These PEs share the
interconnection resources, which are under stress during the execution of the
MATMUL, and have a delay between them that slows down the first phase of the
tree synchronization.

Fig. 6 (b) shows the average over all the PEs of the ratio between the barrier
cycles and the total runtime for the selected kernels. The AXPY has a hot loop
with few operations per input. Therefore, the problem dimension to achieve
$\sim 10\%$ overhead of the barriers is large. The DOTP, the MATMUL, and the
Conv2D having a higher ratio of computations per input and steep CDFs of the
PEs’ arrival times, benefit of our tree barriers from small data dimensions.
The SFR of the DOTP is large due to the PE scattering produced by reduction.
This also requires large input vectors to make the barrier overhead
negligible.

Fig. 6 (c) reports the speed-up on the total runtime obtained synchronizing
with the fastest barrier option for every input dimension and kernel, compared
to the slowest. Speed-up decreases as the input dimension grows because the
barrier fraction on the total runtime reduces. For the DOTP speed-up is
limited, because, as clearly shown on the right-hand side of Fig. 4, the gap
between barriers is small when cores arrive scattered at synchronization. For
all the other kernels, even in the case of large inputs, when synchronization
consists of less than 10% of the total runtime, we report speed-up between
$1.1\times$ and $1.72\times$. This analysis proves that choosing the barrier
radix based on the parallel kernel characteristics provides significant
advantages.

Finally, in Fig. 7 we compare the performance of the central counter barrier,
the tree barriers, and the partial barriers on the 5G OFDM and beamforming
workload. Overheads account for the multi-stage synchronization required by
FFT and the synchronization enforced by data dependencies between FFT and
MATMUL. Fig. 7 (a) shows the execution cycles of the 5G application under exam
for different numbers of antenna streams, and Fig. 7 (b) reports the speed-ups
with respect to a sequential execution on a single Snitch core. The radix-4
$4096$ points FFTs are scheduled on the cluster as described in Fig. 3. We
notice that using tree barriers greatly reduces the runtime with respect to
using a central counter barrier, improving the serial speed-up. Constraining
memory access to local addresses avoids a scattered arrival of the cores due
to contentions, which explains the benefit obtained from tree synchronization.
Further improvement can be obtained by fine-tuning the radix of the tree
barrier through the provided API and by introducing partial synchronization.
The speed-ups with respect to synchronization using a central-counter barrier
are reported in Fig. 7 (b). The best result of $1.6\times$ is obtained using a
radix-32 barrier and synchronizing only groups of $256$ PEs working on
independent FFTs. The overall speed-up reduces as the number of independent
FFTs run between barriers increases. The inefficiency of the central-counter
barrier slowly fades away as synchronization becomes a negligible part of the
runtime. On our best benchmark, corresponding to the run of $4\times 16$ FFTs
of $4096$ points and of a MATMUL between a $32\times 64$ and a $64\times 4096$
matrix, the synchronization overhead accounts for just 6.2% of the total
runtime. In this last case, we observe a speed-up of $1.2\times$.

##  6 Conclusions

This work challenged the fork-join programming model by scaling it to the
$1024$ cores of the TeraPool architecture. To leverage TeraPool’s full
parallel workforce for parallel workloads, we focused on optimizing a key
synchronization primitive: the shared memory barrier. We developed and
optimized different software implementations of these barriers and added
hardware support for the partial synchronization of groups of PEs in the
cluster. We then tested our synchronization primitives on kernels of paramount
importance in the field of signal processing. The average of the cycles spent
by cores in a barrier over the total runtime cycles for the AXPY, DOTP, DCT,
MATMUL, and Conv2D kernels is respectively as low as $7$%, $10$%, $2$%, $5$%,
and $4$%. On the sequence of OFDM and beamforming, a full 5G processing
workload, which includes a multi-stage synchronization kernel (FFT),
logarithmic tree barriers and the use of partial synchronization outperform
the central-counter synchronization with a $1.6\times$ speed-up. Our
scheduling policy allows reducing the fraction of synchronization cycles over
the total cycles to less than 6.2%.

Our results demonstrate that despite its high core count, the TeraPool many-
core cluster behaves as a good approximation of the PRAM model with low
synchronization overhead. This result relies on a tuned selection of the
barrier flavor for a given target kernel.

####  6.0.1 Acknowledgements

This work was supported by Huawei Technologies Sweden AG.

## References

  * [1] runAI200 The Most Efficient AI Compute Engine Available. https://www.untether.ai/products1, accessed: 03.31.2023
  * [2] 3GPP: 5G; NR; Physical layer procedures for data (3GPP TS 38.214 version 17.5.0 Release 17). Technical Specification (TS) 38.214, 3rd Generation Partnership Project (3GPP) (03 2023), version 17.5.0
  * [3] Andersch, M., Palmer, G., Krashinsky, R., Stam, N., Mehta, V., Brito, G., Ramaswamy, S.: NVIDIA Hopper Architecture In-Depth. https://developer.nvidia.com/blog/nvidia-hopper-architecture-in-depth/ (mar 2022), accessed: 2023-03-31
  * [4] Cavalcante, M., Riedel, S., Pullini, A., Benini, L.: MemPool: A Shared-L1 Memory Many-Core Cluster with a Low-Latency Interconnect. In: 2021 Design, Automation & Test in Europe Conference & Exhibition (DATE). pp. 701–706 (2021). https://doi.org/10.23919/DATE51398.2021.9474087
  * [5] Ditzel, D., Espasa, R., Aymerich, N., Baum, A., Berg, T., Burr, J., Hao, E., Iyer, J., Izquierdo, M., Jayaratnam, S., Jones, D., Klingner, C., Kim, J., Lee, S., Lupon, M., Magklis, G., Maric, B., Nath, R., Neilly, M., Northcutt, D., Orner, B., Renau, J., Reves, G., Reves, X., Riordan, T., Sanchez, P., Samudrala, S., Sole, G., Tang, R., Thorn, T., Torres, F., Tortella, S., Yau, D.: Accelerating ML Recommendation with over a Thousand RISC-V/Tensor Processors on Esperanto’s ET-SoC-1 Chip. In: 2021 IEEE Hot Chips 33 Symposium (HCS). pp. 1–23 (2021). https://doi.org/10.1109/HCS52781.2021.9566904
  * [6] Gao, W., Fang, J., Huang, C., Xu, C., Wang, Z.: Optimizing Barrier Synchronization on ARMv8 Many-Core Architectures. In: 2021 IEEE International Conference on Cluster Computing (CLUSTER). pp. 542–552 (2021). https://doi.org/10.1109/Cluster48925.2021.00044
  * [7] Glaser, F., Tagliavini, G., Rossi, D., Haugou, G., Huang, Q., Benini, L.: Energy-Efficient Hardware-Accelerated Synchronization for Shared-L1-Memory Multiprocessor Clusters. IEEE Transactions on Parallel and Distributed Systems 32(3), 633–648 (2021). https://doi.org/10.1109/TPDS.2020.3028691
  * [8] Harris, M., Perelygin, K.: Cooperative Groups: Flexible CUDA Thread Programming. https://developer.nvidia.com/blog/cooperative-groups/ (oct 2017), accessed: 03.31.2023
  * [9] Hoefler, T., Mehlan, T., Mietke, F., Rehm, W.: A Survey of Barrier Algorithms for Coarse Grained Supercomputers. Chemnitzer Informatik Berichte (jan 2004)
  * [10] JaJa, J.F.: PRAM (Parallel Random Access Machines), pp. 1608–1615. Springer US, Boston, MA (2011). https://doi.org/10.1007/978-0-387-09766-4_23
  * [11] Li, H., Homer, N.: A survey of sequence alignment algorithms for next-generation sequencing. Brief. Bioinform. 11(5), 473–483 (may 2010). https://doi.org/10.1093/BIB/BBQ015
  * [12] Mellor-Crummey, J.M., Scott, M.L.: Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. ACM Trans. Comput. Syst. 9(1), 21–65 (feb 1991). https://doi.org/10.1145/103727.103729
  * [13] Mohamed El Maarouf, A.K., Giraud, L., Guermouche, A., Guignon, T.: Combining reduction with synchronization barrier on multi-core processors. Concurrency and Computation: Practice and Experience 35(1), e7402 (2023). https://doi.org/10.1002/cpe.7402
  * [14] Muralidhar, R., Borovica-Gajic, R., Buyya, R.: Energy Efficient Computing Systems: Architectures, Abstractions and Modeling to Techniques and Standards. ACM Comput. Surv. 54(11s), 1–37 (sep 2022). https://doi.org/10.1145/3511094
  * [15] Riedel, S., Cavalcante, M., Andri, R., Benini, L.: MemPool: A Scalable Manycore Architecture with a Low-Latency Shared L1 Memory (2023). https://doi.org/10.48550/arXiv.2303.17742
  * [16] Theis, T.N., Wong, H..P.: The End of Moore’s Law: A New Beginning for Information Technology. In: Computing in Science Engineering. vol. 19, pp. 41–50 (2017). https://doi.org/10.1109/MCSE.2017.29
  * [17] Venkataramani, V., Kulkarni, A., Mitra, T., Peh, L.S.: SPECTRUM: A Software-Defined Predictable Many-Core Architecture for LTE/5G Baseband Processing. ACM Trans. Embed. Comput. Syst. 19(5) (sep 2020). https://doi.org/10.1145/3400032
  * [18] Villa, O., Palermo, G., Silvano, C.: Efficiency and Scalability of Barrier Synchronization on NoC Based Many-Core Architectures. In: Proceedings of the 2008 International Conference on Compilers, Architectures and Synthesis for Embedded Systems. p. 81–90. CASES ’08, Association for Computing Machinery, New York, NY, USA (2008). https://doi.org/10.1145/1450095.1450110
  * [19] Zaruba, F., Schuiki, F., Hoefler, T., Benini, L.: Snitch: A Tiny Pseudo Dual-Issue Processor for Area and Energy Efficient Execution of Floating-Point Intensive Workloads. IEEE Transactions on Computers 70(11), 1845–1860 (2021). https://doi.org/10.1109/TC.2020.3027900


#  Group LCD and Group Reversible LCD Codes

Steven T. Dougherty
Department of Mathematics
University of Scranton
Scranton, PA 18510
USA
Joe Gildea
Adrian Korban
Adam M. Roberts
University of Chester
Chester, UK

###### Abstract

In this paper, we give a new method for constructing LCD codes. We employ
group rings and a well known map that sends group ring elements to a subring
of the $n\times n$ matrices to obtain LCD codes. Our construction method
guarantees that our LCD codes are also group codes, namely, the codes are
ideals in a group ring. We show that with a certain condition on the group
ring element $v,$ one can construct non-trivial group LCD codes. Moreover, we
also show that by adding more constraints on the group ring element $v,$ one
can construct group LCD codes that are reversible. We present many examples of
binary group LCD codes of which some are optimal and group reversible LCD
codes with different parameters.

Key Words: Group rings; LCD codes; codes over rings.

##  1 Introduction

In this paper, we shall study Linear Complementary Dual codes (LCD codes),
which are linear codes that have a trivial intersection with their orthogonal.
LCD codes were first introduced by Massey in [16] and were used to give an
optimum linear coding solution for the two user binary adder channel. These
codes are also used in counter measures for passive and active side channel
analyses on embedded crypto-systems. For a detailed description of this
application please see [4]. LCD codes are asymptotically good, it is shown in
[17] that they meet the asymptotic Gilbert-Varshamov bound. One of the main
goals is to construct LCD codes over finite fields that also have good error
correcting properties. A result of Carlet et al. in [5] gives that over any
finite field of order $q>3,$ the existence of an $[n,k,d]_{q}$ linear code
implies the existence of an $[n,k,d]_{q}$ LCD code. In general, the limits to
error correction may be more restrictive for binary and ternary LCD codes than
for linear codes, as LCD codes do satisfy extra conditions.

Finding methods for constructing LCD codes, classifying LCD $[n,k]$ codes and
determining the largest minimum weight among all LCD $[n,k]$ codes are open
problems in coding theory. Many researchers have employed different techniques
to construct LCD codes. In [15], the authors consider $k$-covers to construct
binary LCD codes with and they give a complete classification of these codes
with the largest minimum weight for $1\leq k\leq n\leq 16.$ In the paper by D.
Crnkovic et al. ([7]), LCD codes are constructed from weighing matrices and a
connection between LCD codes and self-dual codes is drawn. In [18], M. Shi et
al. construct LCD codes from tridiagonal Toeplitz matrices. In this paper, the
authors construct optimal and quasi-optimal examples of binary and ternary LCD
codes. Recently in [1], the authors determine the largest minimum weight of
LCD $[n,4]$ codes for $n\equiv 2,3,5,6,9,10,13\pmod{15}$ and the largest
minimum weight of LCD $[n,5]$ codes for $n\equiv
3,4,5,7,11,19,20,22,26\pmod{31}.$ In another recent paper by S. Bouyuklieva
([3]), optimal binary LCD $[n,k]$ codes are given for $k\leq 32$ and $n\leq
40.$

In this work, we present a new method for constructing LCD codes over any
finite commutative ring. We employ group rings and a very well known matrix
construction to study and construct LCD codes. In particular, we construct LCD
codes that are group codes generated from group ring elements. We show that
for a specific choice of a group element $v$ in the group ring $RG,$ one can
obtain LCD codes. We specifically show that if we let the coefficient of the
group element $g_{i}$ be the same as the coefficient of the group element
$g_{i}^{-1}$ in the group ring element $v,$ then one can construct a non-
trivial group LCD code over any finite commutative ring $R.$ Moreover, by
further restricting the choice of the group in the group ring $RG,$ and by
fixing the listing of the elements of that group, we show that one can
construct group reversible LCD codes. We give many examples of group LCD and
group reversible LCD codes of different lengths.

The paper is organized as follows. In Section 2, we give the standard
definitions and notations for linear codes, LCD codes, the alphabet that we
use in this work, group rings and group codes. In Section 3, we present our
main method for constructing group LCD codes. We also give an example of how
our method works. Next, in Section 4, we describe generator matrices for
various groups in the the group ring $RG$ with the condition for obtaining
group LCD codes with. In Section 5, we further amend our construction method
so that one can construct group reversible LCD codes. Then, in Section 6, we
give many examples of group LCD codes and group reversible LCD codes. We
finish with concluding remarks and directions for possible future research.

##  2 Definitions and Notations

###  2.1 Linear codes and LCD codes

Our main aim in this paper is to construct binary LCD codes. However, we shall
make use of linear codes over rings to construct such codes. Therefore, we
shall make a very broad definition of linear codes. That is, we assume that
the alphabet of a code can be any finite commutative ring. Note that we assume
that a ring has a multiplicative unity. A code $C$, of length $n$, over a
finite ring $R$ is a subset of $R^{n}.$ If the code is a submodule then the
code is said to be linear. We attach to the ambient space the standard inner-
product, namely $[\mathbf{v},\mathbf{w}]=\sum v_{i}w_{i}.$ The orthogonal is
defined by $C^{\perp}=\\{\mathbf{v}\in R^{n}\ |\ [\mathbf{v},\mathbf{w}]=0,\
\forall\mathbf{w}\in C\\}.$ If the ring is Frobenius, then we have that for
linear codes $|C||C^{\perp}|=|R|^{n}$. For a complete description of codes
over rings and this fact about their cardinality, see [8].

The automorphism group of a code $C$, denoted by $Aut(G)$, is the group of all
permutations of the coordinates of the code that fix the code.

An LCD code satisfies $C\cap C^{\perp}=\\{{\bf 0}\\}$. The following are well
known results. Let $G$ be a generator matrix for a code over a finite field.
If $GG^{T}=I_{n}$ then $G$ generates an LCD code. Let $G$ be a generator
matrix for a code over a field. Then $det(GG^{T})\neq 0$ if and only if $G$
generates an LCD code.

There is a particular family of finite commutative Frobenius rings that we
shall use later in our work to prove some results with, which is a commutative
ring with characteristic 2. The ring $R_{k}$ is defined as $R_{k}=\mbox{\msbm
F}_{2}[u_{1},u_{2},\dots,u_{k}]/\langle
u_{i}^{2},u_{i}u_{j}-u_{j}u_{i}\rangle.$ We have that $R_{k}$ has size
$|R_{k}|=2^{2^{k}}$ and it is a non-chain ring which has characteristic $2$
with maximal ideal ${\bf M}=\langle u_{1},u_{2},\ldots,u_{k}\rangle$ and
$Soc(R_{k})=\langle u_{1}u_{2}\cdots u_{k}\rangle.$

A linear Gray map from $R_{k}$ to $\mbox{\msbm F}_{2}^{2^{k}}$ is constructed
as follows. Let $\phi_{1}$ be the map defined on $R_{1}$, namely
$\phi_{1}(a+bu)=(b,a+b)$. Then let ${{c}}\in R.$ We can write
${{c}}={{c}}_{1}+u_{k}{{c}}_{2}$ where ${{c}}_{1},{{c}}_{2}$ are elements of
the ring $R_{k-1}$ of order $2^{2^{k-1}}$, then we define

$\phi_{k}({{c}})=(\phi_{k-1}({{c}}_{2}),\phi_{k-1}({{c}}_{1})+\phi_{k-1}({{c}}_{2})).$
(1)

The map $\phi_{k}$ is a weight preserving map which we then expand
coordinatewise to $R^{n}$.

In [12] it is shown that the map $\phi_{k}:R_{k}\rightarrow\mbox{\msbm
F}_{2}^{2^{k}}$ is a linear bijection and we have that
$\phi(C^{\perp})=\phi(C)^{\perp}.$

It follows immediately that if $C$ is an LCD code of length $n$ over $R_{k}$
then $\phi(C)$ is a binary LCD code of length $2^{k}n.$ For a complete
description of codes over $R_{k}$, see [12], [13] and [14].

###  2.2 Special Matrices and Group Rings

In this section, we recall the definitions of some special matrices that we
use later in this work. We also give the basic definitions of group rings.

A circulant matrix is one where each row is shifted one element to the right
relative to the preceding row. We label the circulant matrix as
$circ(\alpha_{1},\alpha_{2},\dots,\alpha_{n}),$ where $\alpha_{i}$ are the
ring elements appearing in the first row. A reverse-circulant matrix is one
where each row is shifted one element to the left relative to the preceding
row. We label the reverse-circulant matrix as
$revcirc(\alpha_{1},\alpha_{2},\dots,\alpha_{n}),$ where $\alpha_{i}$ are ring
elements appearing in the first row. The transpose of a matrix $A,$ denoted by
$A^{T},$ is a matrix whose rows are the columns of $A,$ i.e.,
$(A^{T})_{ij}=A_{ji}.$

Our interest is to construct codes that are not only LCD but also that are
ideals inside of a group ring, where the ring is the alphabet of the code. We
shall now give the definitions for group rings. We let $G$ be a finite group
or order $n$, the group ring $RG$ consists of $\sum_{i=1}^{n}\alpha_{i}g_{i}$,
$\alpha_{i}\in R$, $g_{i}\in G.$

Addition in the group ring is done by coordinate addition, namely

$\sum_{i=1}^{n}\alpha_{i}g_{i}+\sum_{i=1}^{n}\beta_{i}g_{i}=\sum_{i=1}^{n}(\alpha_{i}+\beta_{i})g_{i}.$

The product of two elements in a group ring is given by

$\left(\sum_{i=1}^{n}\alpha_{i}g_{i}\right)\left(\sum_{j=1}^{n}\beta_{j}g_{j}\right)=\sum_{i,j}\alpha_{i}\beta_{j}g_{i}g_{j}.$

It follows immediately that the coefficient of $g_{k}$ in the product is
$\sum_{g_{i}g_{j}=g_{k}}\alpha_{i}\beta_{j}.$

When the ring is a field the group ring is generally referred to as a group
algebra. While group rings are defined for groups and rings of arbitrary
cardinality, we shall only consider when both the group and the ring are
finite. Moreover, we shall assume that the ring $R$ is commutative but we let
$G$ be an arbitrary group and make no assumption about its commutativity.
Throughout this paper we use $e$ to refer to the identity element of the group
$G$.

###  2.3 Code construction

The following map was used in [9] to study group codes over a finite
commutative Frobenius ring.

Let $R$ be a finite commutative Frobenius ring and let
$G=\\{g_{1},g_{2},\dots,g_{n}\\}$ be a group of order $n$. Let
$v=\alpha_{g_{1}}g_{1}+\alpha_{g_{2}}g_{2}+\cdots+\alpha_{g_{n}}g_{n}\in RG.$
Define the matrix $\sigma(v)\in M_{n}(R)$ to be

$\sigma(v)=\left(\begin{array}[]{ccccc}\alpha_{g_{1}^{-1}g_{1}}&\alpha_{g_{1}^{-1}g_{2}}&\alpha_{g_{1}^{-1}g_{3}}&\dots&\alpha_{g_{1}^{-1}g_{n}}\\\
\alpha_{g_{2}^{-1}g_{1}}&\alpha_{g_{2}^{-1}g_{2}}&\alpha_{g_{2}^{-1}g_{3}}&\dots&\alpha_{g_{2}^{-1}g_{n}}\\\
\vdots&\vdots&\vdots&\vdots&\vdots\\\
\alpha_{g_{n}^{-1}g_{1}}&\alpha_{g_{n}^{-1}g_{2}}&\alpha_{g_{n}^{-1}g_{3}}&\dots&\alpha_{g_{n}^{-1}g_{n}}\end{array}\right).$
(2)

We note that the elements $g_{1}^{-1},g_{2}^{-1},\dots,g_{n}^{-1}$ are simply
the elements of the group $G$ in some order.

Define the following code over the ring $R$ for a given element $v\in RG$.

$C(v)=\langle\sigma(v)\rangle.$ (3)

Specifically, the code is formed by taking the row space of $\sigma(v)$ over
the ring $R$. Given that it is the span of a set of vectors, the code is
necessarily linear. Given the structure of the matrix it follows immediately
that the code is held invariant by the action of the group $G$. Therefore, we
have that $C(v)$ is a $G$-code, namely a code that corresponds to an ideal in
$RG$.

We do not claim that the rows of the matrix $\sigma(v)$ are necessarily
linearly independent, in general, they will not be. If they are then the
generated code is the ambient space.

######  Example 1.

As a very simple example, let $G$ be any finite group of odd order, $R$ be a
finite Frobenius ring with characterisitc $2$, and let $v=\sum_{g\in
G}v_{g}\in RG$. Then $C=\langle\sigma(v)\rangle$ is the code generated by the
all-one vector. Since the length is odd, this code has a trivial intersection
with its orthogonal, giving that $C$ is an LCD $G$-code.

For an element $v=\sum\alpha_{i}g_{i}\in RG$, define the element $v^{T}\in RG$
as $v^{T}=\sum\alpha_{i}g_{i}^{-1}.$ This is sometimes known as the canonical
involution for the group ring.

In [12], the following is proven. Let $R$ be a finite commutative Frobenius
ring and let $G$ be a group of order $n$. For an element $v\in RG$, we have
that $\sigma(v)^{T}=\sigma(v^{T}).$

From [12], we have the following. Let $R$ be a finite commutative Frobenius
ring and let $G$ be a group of order $n$. Then the map $\sigma:RG\rightarrow
M_{n}(R)$ is an injective ring homomorphism.

Given that we have the map $\sigma:RG\rightarrow M_{n}(R)$ is an injective
ring homomorphism one may be tempted to find elements in $RG$ that satisfy
$vv^{T}=1$, so that $\sigma(v)\sigma(v^{T})=\sigma(v)\sigma(v)^{T}=I_{n}.$
However, in this case, given the structure of $\sigma(v)$ this will only give
trivial LCD codes. Therefore, the approach is that we need to find $v$ so that
$\sigma(v)$ does not have a full rank but still produces an LCD code.

##  3 Construction of group LCD codes

In this section, we show what one needs in terms of the group ring element
$v,$ so that $\sigma(v)$ does not have a full rank but still produces an LCD
code.

Let $Hull(v)=C(v)\cap C(v)^{\perp}.$

######  Lemma 3.1.

Let $v\in RG$, then $Hull(v)$ is a $G$-code.

###### Proof.

We know from [9], that $C(v)^{\perp}$ is a $G$-code. Then if $\mathbf{v}\in
C(v)$, then $\sigma\mathbf{v}\in C(v)$ for all $\sigma\in G$ and if
$\mathbf{v}\in C(v)^{\perp}$, then $\sigma\mathbf{v}\in C(v)^{\perp}$ for all
$\sigma\in G$. This gives that if $\mathbf{v}\in Hull(v)$, then
$\sigma\mathbf{v}\in Hull(v)$ for all $\sigma\in G$ ∎

For an LCD code we have that $Hull(v)=\\{\bf 0\\}.$

Let $I$ be an ideal in a group ring $RG$. Define ${\cal R}(I)=\\{w\ |\
vw=0,\forall v\in I\\}.$ It follows immediately that ${\cal R}(I)$ is an ideal
of $RG.$

Let $v=a_{g_{1}}g_{1}+a_{g_{2}}g_{2}+\dots+a_{g_{n}}g_{n}\in RG$ and $C(v)$.
Let $\Psi:RG\rightarrow R^{n}$ be the canonical map defined by

$\Psi(a_{g_{1}}g_{1}+a_{g_{2}}g_{2}+\dots+a_{g_{n}}g_{n})=(a_{g_{1}},a_{g_{2}},\dots,a_{g_{n}}).$

It is shown in [9], that $\Psi^{-1}(C(v))$ is an ideal of $RG.$

######  Lemma 3.2.

Let $\mathbf{w}=\Psi(w).$ Then ${w^{T}}\in{\cal R}(I(v))$ if and only if
$\mathbf{w}\in C(v)^{\perp}.$

###### Proof.

Let $I(v)$ be the ideal $\Psi^{-1}(C(v))$. Let
$\mathbf{w}=(w_{1},w_{2},\dots,w_{n})\in C^{\perp}.$ Then

$[(a_{g_{j}^{-1}g_{1}},a_{g_{j}^{-1}g_{2}},\dots,a_{g_{j}^{-1}g_{n}}),(w_{1},w_{2},\dots,w_{n})]=0,\forall
j.$ (4)

This gives that

$\sum_{i=1}^{n}a_{g_{j}^{-1}g_{i}}w_{i}=0,\ \forall j.$ (5)

Then

$\sum_{i=1}^{n}a_{g_{j}^{-1}g_{i}}w_{i}=0\implies\sum_{i=1}^{n}a_{g_{j}^{-1}g_{i}}b_{g_{i}^{-1}}=0.$
(6)

Then $g_{j}^{-1}g_{i}g_{i}^{-1}=g_{j}^{-1}$, hence this is the coefficient of
$g_{j}^{-1}$ in the product of $w^{T}$ and $g_{j}^{-1}v$. This gives that
$w^{T}\in{\cal R}(I(v))$ if and only if $\mathbf{w}\in C(v)^{\perp}.$ ∎

Let ${\cal R}(I(v))^{T}=\\{w^{t}\ |\ w\in{\cal R}(I(v))$ and let ${\cal
H}(v)=I(v)\cap{\cal R}({\cal H}(v))^{T}.$

######  Lemma 3.3.

Let $v\in RG$, then $\Psi({\cal R}(I(v))^{T})=C^{\perp}$ and $\Psi({\cal
H}(v))=Hull(v)$.

###### Proof.

Follows from a direct application of Lemma 3.2. ∎

We have the following diagrams.

${Hull(v)^{\perp}}$${C(v)}$${C(v)^{\perp}}$${Hull(v)}$${{\cal R}({\cal
H}(v))}$${I(v)}$${{\cal R}(I(v))}$${{\cal H}(v)}$

We now state our main result.

######  Theorem 3.4.

Let $v\in RG.$ If $C(v)$ is a non-trivial LCD code then $v=v^{T}.$

###### Proof.

Let $R(I(v))^{T}=\langle w_{1}^{T},w_{2}^{T},\dots,w_{s}^{T}\rangle.$ Assume
$C(v)$ is an LCD code. Then $\langle
w_{1}^{T},w_{2}^{T},\dots,w_{s}^{T}\rangle=RG.$ Hence no element divides $v$
and each $w_{i}^{T}.$ If $w_{i}^{T}\in{\cal R}(I)^{T}$ then $w_{i}\in{\cal
R}(I)$ which gives that $vw_{i}=0$ for all $i$. It follows that
$v^{T}w_{i}^{T}=0$ for all $i$.

If $vw_{i}^{T}=\alpha\neq 0$ then $\alpha\in I(v)$ and $\alpha\in{\cal
R}(I(v))^{T}$ which gives $\alpha\in{calH}(v)$ which is a contradiction since
this ideal is trivial by Lemma 3.3. This gives that $vw_{i}^{T}=0$ for all
$i$.

Then we have that $vw_{i}^{T}=v^{T}w_{i}^{T}$ which gives
$v(w_{1}^{T}+w_{2}^{T}+\dots+w_{s}^{T})=v^{T}(w_{1}^{T}+w_{2}^{T}+\dots+w_{s}^{T})$
and $v$ and $(w_{1}^{T}+w_{2}^{T}+\dots+w_{s}^{T})$ can have no common factor.
This gives that $v=v^{T}.$ ∎

This result allows us to reduce the search for LCD codes significantly.
Namely, we need only search through $v$ with $v=v^{T}.$

It follows then that if $C(v)$ is an LCD code then $C(v)=C(v^{T}).$

We note that the theorem is not a biconditional. Consider the vector
$v=1+1g_{1}+1g_{2}+1g_{3}\in\mbox{\msbm F}_{2}C_{4}$. Then $v=v^{T}$ but
$Hull(v)=C(v)$ and so $C(v)$ is not an LCD code.

We now present an example.

######  Example 2.

Let
$v=\alpha_{1}1+\alpha_{a}a+\alpha_{a^{2}}+\alpha_{b}b+\alpha_{ab}ab+\alpha_{a^{2}b}a^{2}b\in\mathbb{F}_{2}D_{6},$
where $D_{6}=\\{1,a,a^{a},b,ab,a^{2}b\\}$ is the dihedral group with $6$
elements. Then

$\sigma(v)=\begin{pmatrix}\alpha_{1}&\alpha_{a}&\alpha_{a^{2}}&\alpha_{b}&\alpha_{ab}&\alpha_{a^{2}b}\\\
\alpha_{a^{2}}&\alpha_{1}&\alpha_{a}&\alpha_{a^{2}b}&\alpha_{b}&\alpha_{ab}\\\
\alpha_{a}&\alpha_{a^{2}}&\alpha_{1}&\alpha_{ab}&\alpha_{a^{2}b}&\alpha_{b}\\\
\alpha_{b}&\alpha_{a^{2}b}&\alpha_{ab}&\alpha_{1}&\alpha_{a^{2}}&\alpha_{a}\\\
\alpha_{ab}&\alpha_{b}&\alpha_{a^{2}b}&\alpha_{a}&\alpha_{1}&\alpha_{a^{2}}\\\
\alpha_{a^{2}b}&\alpha_{ab}&\alpha_{b}&\alpha_{a^{2}}&\alpha_{a}&\alpha_{1}\end{pmatrix}.$

Now, if we add the condition $v=v^{T}$ in, that is, we want the coefficient of
the group element $g_{i}$ to be the same as the coefficient of the group
element $g_{i}^{-1}$, the above matrix becomes:

$\sigma^{\prime}(v)=\begin{pmatrix}\alpha_{1}&\alpha_{a}&\alpha_{a}&\alpha_{b}&\alpha_{ab}&\alpha_{a^{2}b}\\\
\alpha_{a}&\alpha_{1}&\alpha_{a}&\alpha_{a^{2}b}&\alpha_{b}&\alpha_{ab}\\\
\alpha_{a}&\alpha_{a}&\alpha_{1}&\alpha_{ab}&\alpha_{a^{2}b}&\alpha_{b}\\\
\alpha_{b}&\alpha_{a^{2}b}&\alpha_{ab}&\alpha_{1}&\alpha_{a}&\alpha_{a}\\\
\alpha_{ab}&\alpha_{b}&\alpha_{a^{2}b}&\alpha_{a}&\alpha_{1}&\alpha_{a}\\\
\alpha_{a^{2}b}&\alpha_{ab}&\alpha_{b}&\alpha_{a}&\alpha_{a}&\alpha_{1}\end{pmatrix},$

since $1^{-1}=1,a^{-1}=a^{2},(a^{2})^{-1}=a,b^{-1}=b,(ab)^{-1}=ab$ and
$(a^{2}b)^{-1}=a^{2}b.$

One can see that the search field in the matrix $\sigma(v)$ is $2^{6}$ and
$2^{5}$ in the matrix $\sigma^{\prime}(v).$ We now search for dihedral LCD
group codes of length 6 using both matrices; $\sigma(v)$ and
$\sigma^{\prime}(v)$ and we obtain the following:

$C_{1}=\begin{pmatrix}0&0&0&0&0&0\\\ 0&0&0&0&0&0\\\ 0&0&0&0&0&0\\\
0&0&0&0&0&0\\\ 0&0&0&0&0&0\\\
0&0&0&0&0&0\end{pmatrix},C_{2}=\begin{pmatrix}0&0&0&0&0&1\\\ 0&0&0&1&0&0\\\
0&0&0&0&1&0\\\ 0&1&0&0&0&0\\\ 0&0&1&0&0&0\\\
1&0&0&0&0&0\end{pmatrix},C_{3}=\begin{pmatrix}0&0&0&0&1&1\\\ 0&0&0&1&0&1\\\
0&0&0&1&1&0\\\ 0&1&1&0&0&0\\\ 1&0&1&0&0&0\\\ 1&1&0&0&0&0\end{pmatrix}$

and

$C_{4}=\begin{pmatrix}0&0&0&1&1&1\\\ 0&0&0&1&1&1\\\ 0&0&0&1&1&1\\\
1&1&1&0&0&0\\\ 1&1&1&0&0&0\\\ 1&1&1&0&0&0\end{pmatrix}.$

The same 4 dihedral LCD codes were obtained from both matrices; $\sigma(v)$
and $\sigma^{\prime}(v).$ Of course, there were fewer calculations needed with
the second matrix $\sigma^{\prime}(v)$ which highlights the importance of
Theorem 3.4.

##  4 Construction of $\sigma(v)$ with $v=v^{T}$ for various groups

In this section, we want to generalize the forms of the matrices $\sigma(v)$
with the condition $v=v^{T}$ for various groups. That is, in this section, we
present a number of matrices $\sigma(v),$ where
$v=\alpha_{g_{1}}g_{1}+\alpha_{g_{2}}g_{2}+\dots+\alpha_{g_{n}}g_{n}\in RG$
with the coefficient of $g_{i}$ being the same as the coefficient of
$g_{i}^{-1}.$ This will enable us to calculate group LCD codes of different
lengths for different groups in less and more practical time.

  1. 1.

Let $C_{n}=\langle a\ |\ a^{n}=e\rangle$ be the cyclic group of order $n$ with
$n=2k,$ for $k\in\mathbb{Z}^{+}.$ Let
$v=\sum_{i=1}^{n}\alpha_{a^{i-1}}a^{i-1}\in RC_{n}.$ Then

$\sigma(v)=circ(\alpha_{e},\alpha_{a},\alpha_{a^{2}},\dots,\alpha_{a^{\frac{n}{2}}},\alpha_{a^{\frac{n}{2}-1}},\alpha_{a^{\frac{n}{2}-2}},\dots,\alpha_{a^{2}},\alpha_{a}).$
(7)

  2. 2.

Let $C_{n}=\langle a\ |\ a^{n}=e\rangle$ be the cyclic group of order $n$ with
$n=2k+1,$ for $k\in\mathbb{Z}^{+}.$ Let
$v=\sum_{i=1}^{n}\alpha_{a^{i-1}}a^{i-1}\in RC_{n}.$ Then

$\sigma(v)=circ(\alpha_{e},\alpha_{a},\alpha_{a^{2}},\dots,\alpha_{a^{\frac{n-1}{2}}},\alpha_{a^{\frac{n-1}{2}}},\alpha_{a^{\frac{n-1}{2}-1}},\alpha_{a^{\frac{n-1}{2}-2}},\dots,\alpha_{a^{2}},\alpha_{a}).$
(8)

  3. 3.

Let $D_{2n}=\langle a,b\ |\ a^{n}=b^{2}=e,a^{b}=a^{-1}\rangle$ be the dihedral
group of order $2n$ with $n=2k,$ for $k\in\mathbb{Z}^{+}.$ Let
$v=\sum_{i=0}^{n}\sum_{j=0}^{1}\alpha_{a^{i}b^{j}}a^{i}b^{j}\in RD_{2n}.$ Then

$\sigma(v)=\begin{pmatrix}A&B\\\ B^{T}&A^{T}\end{pmatrix},$ (9)

where

$A=circ(\alpha_{e},\alpha_{a},\alpha_{a^{2}},\dots,\alpha_{a^{\frac{n}{2}}},\alpha_{a^{\frac{n}{2}-1}},\alpha_{a^{\frac{n}{2}-2}},\dots,\alpha_{a^{2}},\alpha_{a}),$
$B=circ(\alpha_{b},\alpha_{ab},\alpha_{a^{2}b},\dots,\alpha_{a^{n-1}b}).$

  4. 4.

Let $D_{2n}=\langle a,b\ |\ a^{n}=b^{2}=e,a^{b}=a^{-1}\rangle$ be the dihedral
group of order $2n$ with $n=2k+1,$ for $k\in\mathbb{Z}^{+}.$ Let
$v=\sum_{i=0}^{n}\sum_{j=0}^{1}\alpha_{a^{i}b^{j}}a^{i}b^{j}\in RD_{2n}.$ Then

$\sigma(v)=\begin{pmatrix}A&B\\\ B^{T}&A^{T}\end{pmatrix},$ (10)

where

$A=circ(\alpha_{e},\alpha_{a},\alpha_{a^{2}},\dots,\alpha_{a^{\frac{n-1}{2}}},\alpha_{a^{\frac{n-1}{2}}},\alpha_{a^{\frac{n-1}{2}-1}},\alpha_{a^{\frac{n-1}{2}-2}},\dots,\alpha_{a^{2}},\alpha_{a}),$
$B=circ(\alpha_{b},\alpha_{ab},\alpha_{a^{2}b},\dots,\alpha_{a^{n-1}b}).$

  5. 5.

Let $D_{2n}=\langle a,b\ |\ a^{n}=b^{2}=e,a^{b}=a^{-1}\rangle$ be the dihedral
group of order $2n$ with $n=2k,$ for $k\in\mathbb{Z}^{+}.$ Let
$v=\sum_{i=0}^{n}\sum_{j=0}^{1}\alpha_{b^{j}a^{i}}b^{j}a^{i}\in RD_{2n}.$ Then

$\sigma(v)=\begin{pmatrix}A&B\\\ B&A\end{pmatrix},$ (11)

where

$A=circ(\alpha_{e},\alpha_{a},\alpha_{a^{2}},\dots,\alpha_{a^{\frac{n}{2}}},\alpha_{a^{\frac{n}{2}-1}},\alpha_{a^{\frac{n}{2}-2}},\dots,\alpha_{a^{2}},\alpha_{a}),$
$B=revcirc(\alpha_{b},\alpha_{ba},\alpha_{ba^{2}},\dots,\alpha_{ba^{n-1}}).$

  6. 6.

Let $D_{2n}=\langle a,b\ |\ a^{n}=b^{2}=e,a^{b}=a^{-1}\rangle$ be the dihedral
group of order $2n$ with $n=2k+1,$ for $k\in\mathbb{Z}^{+}.$ Let
$v=\sum_{i=0}^{n}\sum_{j=0}^{1}\alpha_{b^{j}a^{i}}b^{j}a^{i}\in RD_{2n}.$ Then

$\sigma(v)=\begin{pmatrix}A&B\\\ B&A\end{pmatrix},$ (12)

where

$A=circ(\alpha_{e},\alpha_{a},\alpha_{a^{2}},\dots,\alpha_{a^{\frac{n-1}{2}}},\alpha_{a^{\frac{n-1}{2}}},\alpha_{a^{\frac{n-1}{2}-1}},\alpha_{a^{\frac{n-1}{2}-2}},\dots,\alpha_{a^{2}},\alpha_{a}),$
$B=revcirc(\alpha_{b},\alpha_{ba},\alpha_{ba^{2}},\dots,\alpha_{ba^{n-1}}).$

##  5 Construction of group reversible LCD codes

In this section, we show that for certain groups and with a fixed listing of
their elements in the group ring $RG,$ one can construct group reversible LCD
codes with our method. We start with a definition from [6].

######  Definition 1.

A code $C$ is said to be reversible of index $\alpha$ if $\mathbf{a}_{i}$ is a
vector of length $\alpha$ and
$\mathbf{c}^{\alpha}=(\mathbf{a}_{0},\mathbf{a}_{1},\dots,\mathbf{a}_{s-1})\in
C$ implies that
$(\mathbf{c}^{\alpha})^{r}=(\mathbf{a}_{s-1},\mathbf{a}_{s-2},\dots,\mathbf{a}_{1},\mathbf{a}_{0})\in
C.$

Also in [6], the following is shown.

######  Theorem 5.1.

Let $R$ be a finite ring. Let $G$ be a finite group of order $n=2\ell$ and let
$H=\\{e,h_{1},h_{2},\dots,h_{\ell-1}\\}$ be a subgroup of index 2 in $G.$ Let
$\beta\notin H$ be an element in $G$ with $\beta^{-1}=\beta.$ List the
elements of $G$ as

$\\{e,h_{1},\dots,h_{\ell-1},\beta h_{\ell-1},\beta h_{\ell-2},\beta
h_{2},\beta h_{1},\beta\\},$

then any linear $G$-code in $R^{n}$ (a left ideal in $RG$) is a reversible
code of index 1.

Combining the above result with Theorem 3.4, we get the following

######  Theorem 5.2.

Let $R$ be a finite ring. Let $G$ be a finite group of order $n=2\ell$ and let
$H=\\{e,h_{1},h_{2},\dots,h_{\ell-1}\\}$ be a subgroup of index 2 in $G.$ Let
$\beta\notin H$ be an element in $G$ with $\beta^{-1}=\beta.$ Let $v\in RG$
with $v=v^{T}$ such that the elements of $G$ in $v$ are listed as

$\\{e,h_{1},\dots,h_{\ell-1},\beta h_{\ell-1},\beta h_{\ell-2},\beta
h_{2},\beta h_{1},\beta\\}.$

Then $C(v)$ is a non-trivial reversible LCD code of index 1.

###### Proof.

The reversibility follows from Theorem 3.4 and the second part follows from
Theorem 5.1. ∎

The above result shows that with a careful selection of the element $v$ in the
group ring $RG,$ one can construct a group code that is both, reversible and
LCD.

######  Theorem 5.3.

Let $G$ be a finite group of order $n=2\ell$ and let
$H=\\{e,h_{1},h_{2},\dots,h_{\ell-1}\\}$ be a subgroup of index 2 in $G.$ Let
$\beta\notin H$ be an element in $G$ with $\beta^{-1}=\beta.$ Let $v\in RG$
with $v=v^{T}$ such that the elements of $G$ in $v$ are listed as

$\\{e,h_{1},\dots,h_{\ell-1},\beta h_{\ell-1},\beta h_{\ell-2},\beta
h_{2},\beta h_{1},\beta\\}.$

If $C(v)$ is a linear $G$-code in $R_{k}^{n}$ (a left ideal in $R_{k}G$), then
$\phi(C(v))$ is a non-trivial reversible LCD code of index $2^{k}.$

###### Proof.

By Theorem 5.2, we have that $C$ is a non-trivial reversible LCD code of index
1. Therefore, if $(c_{0},c_{1},\dots,c_{n-1})\in C(v)$ we have that
$(c_{n-1},c_{n-2},\dots,c_{1},c_{0})\in C(v),$ where $c_{i}\in R_{k}.$ Then
$\phi(c_{i})$ is a vector of length $2^{k}.$ This gives that

$(\phi(c_{0}),\phi(c_{1}),\dots,\phi(c_{n-1}))\in\phi(C)$

and then

$(\phi(c_{n-1}),\phi(c_{n-2}),\dots,\phi(c_{1}),\phi(c_{0}))\in\phi(C).$

This gives the result. ∎

##  6 Computational Results

In this section, we construct many group LCD and group reversible LCD codes
using the code construction $\langle\sigma(v)\rangle,$ given in Equation (2),
where $\sigma(v)$ are some of the $n\times n$ matrices described in Section 4.
The searches are performed in the software package MAGMA ([2]). We only
tabulate the lengths, dimensions and the largest minimum distance of the codes
that we construct. Codes with the largest minimum distance that are optimal
(according to [3]) are written in bold. The generator matrices of these codes
and their corresponding weight enumerators can be found at [10].

###  6.1 Group LCD Codes

In this section we search for group LCD codes using the code construction
$\langle\sigma(v)\rangle,$ given in Equation (2), where $\sigma(v)$ are some
of the $n\times n$ matrices described in Section 4.

  1. 1.

Let $v\in\mathbb{F}_{2}C_{n}$ and let
$\mathcal{G}_{1}=\langle\sigma(v)\rangle,$ where $\sigma(v)$ is the matrix
given in Equation (7). We set $n$ to be $28,30,34,36$ and $38.$ We list the
results in Table 1, Table 2, Table 3, Table 4 and Table 5 respectively.

Table 1: Group LCD Codes from $\mathcal{G}_{1}\ (n=28)$ over $\mathbb{F}_{2}$

$\mathcal{C}_{i}$ | $[n,k,d]$ | $\mathcal{C}_{i}$ | $[n,k,d]$
---|---|---|---
$\mathcal{C}_{1}$ | $[28,4,7]$ | $\mathcal{C}_{2}$ | $[28,24,2]$

Table 2: Group LCD Codes from $\mathcal{G}_{1}\ (n=30)$ over $\mathbb{F}_{2}$

$\mathcal{C}_{i}$ | $[n,k,d]$ | $\mathcal{C}_{i}$ | $[n,k,d]$
---|---|---|---
$\mathcal{C}_{1}$ | $[30,2,15]$ | $\mathcal{C}_{8}$ | $[30,16,4]$
$\mathcal{C}_{2}$ | $[30,4,10]$ | $\mathcal{C}_{9}$ | $[30,18,4]$
$\mathcal{C}_{3}$ | $[30,6,5]$ | $\mathcal{C}_{10}$ | $[30,20,2]$
$\mathcal{C}_{4}$ | $[30,8,6]$ | $\mathcal{C}_{11}$ | $[30,22,2]$
$\mathcal{C}_{5}$ | $[30,10,3]$ | $\mathcal{C}_{12}$ | $[30,24,2]$
$\mathcal{C}_{6}$ | $[30,12,6]$ | $\mathcal{C}_{13}$ | $[30,26,2]$
$\mathcal{C}_{7}$ | $[30,14,3]$ | $\mathcal{C}_{14}$ | $[30,28,2]$

Table 3: Group LCD Codes from $\mathcal{G}_{1}\ (n=34)$ over $\mathbb{F}_{2}$

$\mathcal{C}_{i}$ | $[n,k,d]$ | $\mathcal{C}_{i}$ | $[n,k,d]$
---|---|---|---
$\mathcal{C}_{1}$ | $[34,2,17]$ | $\mathcal{C}_{3}$ | $[34,18,5]$
$\mathcal{C}_{2}$ | $[34,16,6]$ | $\mathcal{C}_{4}$ | $[34,32,2]$

Table 4: Group LCD Codes from $\mathcal{G}_{1}\ (n=36)$ over $\mathbb{F}_{2}$

$\mathcal{C}_{i}$ | $[n,k,d]$ | $\mathcal{C}_{i}$ | $[n,k,d]$
---|---|---|---
$\mathcal{C}_{1}$ | $[36,4,9]$ | $\mathcal{C}_{4}$ | $[36,24,2]$
$\mathcal{C}_{2}$ | $[36,8,6]$ | $\mathcal{C}_{5}$ | $[36,28,2]$
$\mathcal{C}_{3}$ | $[36,12,3]$ | $\mathcal{C}_{6}$ | $[36,32,2]$

Table 5: Group LCD Codes from $\mathcal{G}_{1}\ (n=38)$ over $\mathbb{F}_{2}$

$\mathcal{C}_{i}$ | $[n,k,d]$ | $\mathcal{C}_{i}$ | $[n,k,d]$
---|---|---|---
$\mathcal{C}_{1}$ | $[38,2,19]$ | $\mathcal{C}_{2}$ | $[38,36,2]$

  2. 2.

Let $v\in\mathbb{F}_{2}C_{n}$ and let
$\mathcal{G}_{2}=\langle\sigma(v)\rangle,$ where $\sigma(v)$ is the matrix
given in Equation (8). We set $n$ to be $29,31,33,35,37$ and $39.$ We list the
results in Table 6, Table 7, Table 8, Table 9, Table 10 and Table 11
respectively.

Table 6: Group LCD Codes from $\mathcal{G}_{2}\ (n=29)$ over $\mathbb{F}_{2}$

$\mathcal{C}_{i}$ | $[n,k,d]$
---|---
$\mathcal{C}_{1}$ | $[29,28,2]$

Table 7: Group LCD Codes from $\mathcal{G}_{2}\ (n=31)$ over $\mathbb{F}_{2}$

$\mathcal{C}_{i}$ | $[n,k,d]$ | $\mathcal{C}_{i}$ | $[n,k,d]$
---|---|---|---
$\mathcal{C}_{1}$ | $\mathbf{[31,10,10]}$ | $\mathcal{C}_{4}$ | $\mathbf{[31,21,5]}$
$\mathcal{C}_{2}$ | $\mathbf{[31,11,10]}$ | $\mathcal{C}_{5}$ | $[31,30,2]$
$\mathcal{C}_{3}$ | $\mathbf{[31,20,6]}$ |  |

Table 8: Group LCD Codes from $\mathcal{G}_{2}\ (n=33)$ over $\mathbb{F}_{2}$

$\mathcal{C}_{i}$ | $[n,k,d]$ | $\mathcal{C}_{i}$ | $[n,k,d]$
---|---|---|---
$\mathcal{C}_{1}$ | $[33,2,22]$ | $\mathcal{C}_{12}$ | $\mathbf{[33,20,6]}$
$\mathcal{C}_{2}$ | $[33,3,11]$ | $\mathcal{C}_{13}$ | $[33,21,3]$
$\mathcal{C}_{3}$ | $[33,10,6]$ | $\mathcal{C}_{14}$ | $[33,21,4]$
$\mathcal{C}_{4}$ | $\mathbf{[33,10,12]}$ | $\mathcal{C}_{15}$ | $[33,22,2]$
$\mathcal{C}_{5}$ | $[33,11,3]$ | $\mathcal{C}_{16}$ | $\mathbf{[33,22,6]}$
$\mathcal{C}_{6}$ | $\mathbf{[33,11,11]}$ | $\mathcal{C}_{17}$ | $[33,23,2]$
$\mathcal{C}_{7}$ | $[33,12,6]$ | $\mathcal{C}_{18}$ | $[33,23,3]$
$\mathcal{C}_{8}$ | $\mathbf{[33,12,10]}$ | $\mathcal{C}_{19}$ | $[33,30,2]$
$\mathcal{C}_{9}$ | $[33,13,3]$ | $\mathcal{C}_{20}$ | $[33,31,2]$
$\mathcal{C}_{10}$ | $\mathbf{[33,13,10]}$ | $\mathcal{C}_{21}$ | $[33,32,2]$
$\mathcal{C}_{11}$ | $[33,20,4]$ |  |

Table 9: Group LCD Codes from $\mathcal{G}_{2}\ (n=35)$ over $\mathbb{F}_{2}$

$\mathcal{C}_{i}$ | $[n,k,d]$ | $\mathcal{C}_{i}$ | $[n,k,d]$
---|---|---|---
$\mathcal{C}_{1}$ | $[35,4,14]$ | $\mathcal{C}_{8}$ | $\mathbf{[35,25,4]}$
$\mathcal{C}_{2}$ | $[35,5,7]$ | $\mathcal{C}_{9}$ | $[35,28,2]$
$\mathcal{C}_{3}$ | $[35,6,10]$ | $\mathcal{C}_{10}$ | $[35,29,2]$
$\mathcal{C}_{4}$ | $[35,7,5]$ | $\mathcal{C}_{11}$ | $[35,30,2]$
$\mathcal{C}_{5}$ | $[35,10,10]$ | $\mathcal{C}_{12}$ | $[35,31,2]$
$\mathcal{C}_{6}$ | $[35,11,5]$ | $\mathcal{C}_{13}$ | $[35,34,2]$
$\mathcal{C}_{7}$ | $[35,24,4]$ |  |

Table 10: Group LCD Codes from $\mathcal{G}_{2}\ (n=37)$ over $\mathbb{F}_{2}$

$\mathcal{C}_{i}$ | $[n,k,d]$
---|---
$\mathcal{C}_{1}$ | $[37,36,2]$

Table 11: Group LCD Codes from $\mathcal{G}_{2}\ (n=39)$ over $\mathbb{F}_{2}$

$\mathcal{C}_{i}$ | $[n,k,d]$ | $\mathcal{C}_{i}$ | $[n,k,d]$
---|---|---|---
$\mathcal{C}_{1}$ | $[39,2,26]$ | $\mathcal{C}_{8}$ | $[39,25,4]$
$\mathcal{C}_{2}$ | $[39,3,13]$ | $\mathcal{C}_{9}$ | $[39,26,2]$
$\mathcal{C}_{3}$ | $[39,12,6]$ | $\mathcal{C}_{10}$ | $[39,27,2]$
$\mathcal{C}_{4}$ | $[39,13,3]$ | $\mathcal{C}_{11}$ | $[39,36,2]$
$\mathcal{C}_{5}$ | $[39,14,6]$ | $\mathcal{C}_{12}$ | $[39,37,2]$
$\mathcal{C}_{6}$ | $[39,15,3]$ | $\mathcal{C}_{13}$ | $[39,38,2]$
$\mathcal{C}_{7}$ | $[39,24,4]$ |  |

  3. 3.

Let $v\in\mathbb{F}_{2}D_{24}$ and let
$\mathcal{G}_{3}=\langle\sigma(v)\rangle,$ where $\sigma(v)$ is the matrix
given in Equation (11). We list our results in Table 12.

Table 12: Group LCD Codes from $\mathcal{G}_{3}$ over $\mathbb{F}_{2}$

$\mathcal{C}_{i}$ | $[n,k,d]$ | $\mathcal{C}_{i}$ | $[n,k,d]$
---|---|---|---
$\mathcal{C}_{1}$ | $[24,8,3]$ | $\mathcal{C}_{2}$ | $[24,16,2]$

  4. 4.

Let $v\in\mathbb{F}_{2}D_{30}$ and let
$\mathcal{G}_{4}=\langle\sigma(v)\rangle,$ where $\sigma(v)$ is the matrix
given in Equation (12). We list our results in Table 13.

Table 13: Group Reversible LCD Codes from $\mathcal{G}_{4}$ over
$\mathbb{F}_{2}$

$\mathcal{C}_{i}$ | $[n,k,d]$ | $\mathcal{C}_{i}$ | $[n,k,d]$
---|---|---|---
$\mathcal{C}_{1}$ | $[30,2,15]$ | $\mathcal{C}_{8}$ | $[30,16,4]$
$\mathcal{C}_{2}$ | $[30,4,10]$ | $\mathcal{C}_{9}$ | $[30,18,4]$
$\mathcal{C}_{3}$ | $[30,6,5]$ | $\mathcal{C}_{10}$ | $[30,20,2]$
$\mathcal{C}_{4}$ | $[30,8,6]$ | $\mathcal{C}_{11}$ | $[30,22,2]$
$\mathcal{C}_{5}$ | $[30,10,3]$ | $\mathcal{C}_{12}$ | $[30,24,2]$
$\mathcal{C}_{6}$ | $[30,12,6]$ | $\mathcal{C}_{13}$ | $[30,26,2]$
$\mathcal{C}_{7}$ | $[30,14,3]$ | $\mathcal{C}_{14}$ | $[30,28,2]$

###  6.2 Group Reversible LCD Codes

In this section we search for group reversible LCD codes using Theorem 5.2. In
particular, we employ the matrices $\sigma(v)$ given in Equation (9) and
Equation (10) but with the listing of the group elements in the group ring
element $v$ as given in Theorem 5.2. That is, since the group used in the
group ring element $v$ in both equations; Equation (9) and Equation (10), is
the dihedral group of even order, we list the elements of this group
(according to Theorem 5.2) as follow:

$\\{e,a,a^{2},\dots,a^{n-1},ba^{n-1},ba^{n-2},\dots,ba,b\\}.$ (13)

This approach, as shown in Theorem 5.2 guarantees that the codes are group
reversible LCD codes.

  1. 1.

Let $v\in\mathbb{F}_{2}D_{22}$ and let
$\mathcal{G}_{5}=\langle\sigma(v)\rangle,$ where $\sigma(v)$ is the matrix
given in Equation (10). We list our results in Table 14.

Table 14: Group Reversible LCD Codes from $\mathcal{G}_{5}$ over
$\mathbb{F}_{2}$

$\mathcal{C}_{i}$ | $[n,k,d]$ | $\mathcal{C}_{i}$ | $[n,k,d]$
---|---|---|---
$\mathcal{C}_{1}$ | $[22,2,11]$ | $\mathcal{C}_{2}$ | $[22,20,2]$

  2. 2.

Let $v\in\mathbb{F}_{2}D_{24}$ and let
$\mathcal{G}_{6}=\langle\sigma(v)\rangle,$ where $\sigma(v)$ is the matrix
given in Equation (9). We list our results in Table 15.

Table 15: Group Reversible LCD Codes from $\mathcal{G}_{6}$ over
$\mathbb{F}_{2}$

$\mathcal{C}_{i}$ | $[n,k,d]$ | $\mathcal{C}_{i}$ | $[n,k,d]$
---|---|---|---
$\mathcal{C}_{1}$ | $[24,8,3]$ | $\mathcal{C}_{2}$ | $[24,16,2]$

  3. 3.

Let $v\in\mathbb{F}_{2}D_{30}$ and let
$\mathcal{G}_{7}=\langle\sigma(v)\rangle,$ where $\sigma(v)$ is the matrix
given in Equation (10). We list our results in Table 16.

Table 16: Group Reversible LCD Codes from $\mathcal{G}_{7}$ over
$\mathbb{F}_{2}$

$\mathcal{C}_{i}$ | $[n,k,d]$ | $\mathcal{C}_{i}$ | $[n,k,d]$
---|---|---|---
$\mathcal{C}_{1}$ | $[30,2,15]$ | $\mathcal{C}_{8}$ | $[30,16,4]$
$\mathcal{C}_{2}$ | $[30,4,10]$ | $\mathcal{C}_{9}$ | $[30,18,4]$
$\mathcal{C}_{3}$ | $[30,6,5]$ | $\mathcal{C}_{10}$ | $[30,20,2]$
$\mathcal{C}_{4}$ | $[30,8,6]$ | $\mathcal{C}_{11}$ | $[30,22,2]$
$\mathcal{C}_{5}$ | $[30,10,3]$ | $\mathcal{C}_{12}$ | $[30,24,2]$
$\mathcal{C}_{6}$ | $[30,12,6]$ | $\mathcal{C}_{13}$ | $[30,26,2]$
$\mathcal{C}_{7}$ | $[30,14,3]$ | $\mathcal{C}_{14}$ | $[30,28,2]$

##  7 Conclusion

In this work, we presented a new method for constructing LCD codes over any
finite commutative ring. We showed that the LCD codes constructed with our
method are ideals in a group ring $RG,$ i.e., our LCD codes are also group
codes. We proved that with a certain condition on the group ring element $v,$
one can construct non-trivial group LCD codes with our method. Moreover, we
also proved that under some more restrictions on the group ring element $v,$
one can construct group reversible LCD codes with our method. We presented
many examples of group LCD codes and group reversible LCD codes with different
parameters. A possible direction for future research is to consider our
approach but with groups of orders higher than we used in this paper to obtain
more group LCD and group reversible LCD codes of lengths greater than we
constructed in this paper.

## References

  * [1] M. Araya, M, Harada, On the minimum weights of binary linear complementary dual codes, Cryptography and Communications, 12, (2020), 285–300.
  * [2] W. Bosma, J. Cannon and C. Playoust, “The Magma algebra system. I. The user language”, J. Symbolic Comput., 24, (1997), 235–265.
  * [3] S. Bouyuklieva, Optimal Binary LCD Codes, arXiv:2010.13399.
  * [4] C. Carlet and S. Guilley, Complementary dual codes for counter-measures to side-channel attacks, Proceedings of the 4th ICMCTA Meeting, Palmela, Portugal, (2014).
  * [5] C. Carlet, S. Mesnager, C. Tang, Y. Qi, Linear codes over $\mathbb{F}_{q}$ are equivalent to LCD codes for $q>3,$ IEEE Trans. Inform. Theory, 64, (2018), 3010–3017.
  * [6] Y. Cengellenmis, A. Dertli, S.T. Dougherty, A. Korban and S. Sahinkaya, “Reversible $G$-Codes over the Ring $\mathcal{F}_{j,k}$ with Applications to DNA Codes”, in submission.
  * [7] D. Crnkovic, R. Egan, B. G. Rodrigues, A. Svob, LCD codes from weighing matrices, Applicable Algebra in Engineering, Communication and Computing, 32, (2021), 175–189.
  * [8] Dougherty, S.T., Algebraic Coding Theory Over Finite Commutative Rings, Springer-Verlag, Springer Briefs in Mathematics (ISBN 978-3-319-59805-5), (2017).
  * [9] Dougherty, S.T., Gildea, J., Taylor, R., Tylshchak, A., Group Rings, $G$-Codes and Constructions Of Self-Dual and Formally Self-Dual Codes, Designs, Codes and Cryptography, 10.1007/s10623-017-0440-7.
  * [10] S.T. Dougherty, J. Gildea, A. Korban, A. M. Roberts, Generator Matrices for the manuscript entitled “Group LCD and Group Reversible LCD Codes”, available at https://sites.google.com/view/adriankorban/generator-matrices.
  * [11] S.T. Dougherty, J. L. Kim, B. Ozkaya, L. Sok, P. Sole, The combinatorics of LCD codes: linear programming bound and orthogonal matrices. Int. J. Inf. Coding Theory, 4, (2017), 116–128.
  * [12] S. T. Dougherty, B. Yildiz, S. Karadeniz, Codes over $R_{k}$, Gray maps and their Binary Images, Finite Fields and their Applications, 17, (2011), 205–219.
  * [13] S. T. Dougherty, B. Yildiz, S. Karadeniz, Cyclic Codes over $R_{k}$, Designs, Codes and Cryptography, 63, (2012), 113–126.
  * [14] S. T. Dougherty, B. Yildiz, S. Karadeniz, Self-dual codes over $R_{k}$ and binary self-dual codes. Eur. J. Pure Appl. Math. 6, (2013), 89– 106.
  * [15] M. Harada, K. Saito, Binary linear complementary dual codes, Cryptography and Communications, 11, (2019), 677–696.
  * [16] J.L. Massey, Linear codes with complementary duals, Discrete Mathematics, 106/107, (1992), 337–342.
  * [17] N. Sendrier, Linear codes with complementary duals meet the Gilbert-Varshamov bound, Discrete Math., 304, (2004), 345–347.
  * [18] M. Shi, F. Ozbudak, L. Xu, P. Sole, LCD codes from tridiagonal Toeplitz matrices, Finite Fields and Their Applications, (2021).