Kjell Winblad 0 To appear in 2017 Imperial College Computing Student Workshop
(ICCSW 2017) 3 1 1 10.4230/OASIcs.xxx.yyy.p

# Faster Concurrent Range Queries with Contention Adapting Search Trees Using
Immutable Data

Kjell Winblad  Department of Information Technology, Uppsala University,
Sweden
<EMAIL_ADDRESS>
###### Abstract.

The need for scalable concurrent ordered set data structures with linearizable
range query support is increasing due to the rise of multicore computers, data
processing platforms and in-memory databases. This paper presents a new
concurrent ordered set with linearizable range query support. The new data
structure is based on the contention adapting search tree and an immutable
data structure. Experimental results show that the new data structure is as
much as three times faster compared to related data structures. The data
structure scales well due to its ability to adapt the sizes of its immutable
parts to the contention level and the sizes of the range queries.

###### Key words and phrases:

linearizability, concurrent data structures, treap

###### 1991 Mathematics Subject Classification:

D.2.8 Performance measures, E.1 Trees, H.2.4 Concurrency

##  1\. Introduction

The use of concurrent ordered set data structures111A concurrent ordered set
data structure represents a set of items that can be manipulated concurrently
by several threads and where an item consists of an ordered key and optionally
some additional data. with support for linearizable222A linearizable operation
appears to happen instantly between the operation’s invocation and return
[10]. range queries333A range query operation returns all items with keys
within the given range (specified by two keys). is increasing as multicores
are becoming more readily available and due to the rise of big scale data
processing platforms and in-memory databases such as Google’s F1 [22] and
Yahoo’s Flurry [1]. Both of these require set data structures with fast
updates444An update operation is an insert operation or a remove operation
where the former inserts an item (replacing an existing item if one with an
equal key already exists) and the latter removes an item with the given key if
such an item exists. to store incoming data while concurrently serving
(typically large) linearizable range queries for analytics [3]. Although there
are many concurrent set data structures (e.g. [21, 12, 16]) and ordered set
data structures (e.g. [8, 13, 6]), there are only a few concurrent data
structures with efficient linearizable range queries [5, 2, 17, 19, 7, 3].

This paper proposes a new concurrent ordered set data structure that
internally makes use of an immutable data structure. The difference between an
immutable data structure and its mutable counterpart is that the immutable
data structure’s update operations do not modify the given data structure
instance in-place but instead return a new version, leaving the input instance
intact. For many data structures, e.g. binary search trees, the operations of
the immutable version are asymptotically as efficient as in its mutable
counterpart [14]. As an example, the insert operation of an immutable balanced
binary search tree only needs to make a copy of the nodes on the path to the
inserted node, which only consists of $\mathcal{O}(\log{}n)$ nodes, where $n$
is the number of items that are stored in the search tree.

One can derive a concurrent ordered set data structure with linearizable range
query support from a single mutable reference to an immutable data structure
[9]. A lookup or a range query simply performs the operation in the referenced
immutable data structure. An update operation repeatedly tries to update the
reference using an atomic compare-and-swap operation [9] until the update
succeeds. Unfortunately, this coarse-grained approach does not scale when
concurrent updates are common due to the scalability bottleneck that exists in
the updating of the shared reference. Instead, several data structures [5, 2]
use immutable parts that can store a fixed number of items to shorten the time
range queries need to spend reading shared mutable data. This fine-grained
approach can be efficient when it is possible to fine-tune the size of the
data structure’s immutable parts to fit the sizes of the range queries (the
number of items within the range) and the contention level. However, the fine-
grained approach does not work well when the access pattern is unknown or
differs in different parts of the data structure.

The _main contribution_ of this paper is a new concurrent ordered set data
structure with linearizable range query support that solves the problems with
the coarse-grained and fine-grained approaches described above by dynamically
changing the sizes of its immutable parts to fit the workload at hand. The new
data structure is based on the contention adapting search tree (CA tree) [18,
19] and an immutable data structure. Previous results [19] show that CA trees
using mutable data structures provide good scalability in scenarios with short
range queries. However, previous CA tree variants’ scalability for large range
queries is limited as their range queries lock out other threads from large
portions of the data structure for a time period whose length is proportional
to the number of items with keys in the given range. The new CA tree variant
eliminates this problem by utilizing an immutable data structure. As is shown
in this work, the new CA tree variant’s ability to reduce the lock holding
times does not only make its scalability substantially better compared to the
old CA tree variants but also much better than the other recently proposed
data structures with linearizable range query support.

This paper starts with a high-level description of CA trees (Section 2). The
new CA tree variant and its implementation are described in Sections 3 and 4.
Analytical and experimental comparisons with related data structures are given
in Sections 5 and 6. The paper finishes with a conclusion (Section 7).

##  2\. High-Level Description of Contention Adapting Search Trees

Figure 1. The structure of a CA tree. Numbers denote keys.

CA trees are structured as depicted in Figure 1. The items that are stored in
a CA tree are located in sequential data structures under the base nodes (see
Figure 1). To efficiently find a specific item in a CA tree, the search is
directed by the keys in the routing nodes. All items stored under the left
branch of a routing node have keys that are less than the key of the routing
node and all items stored under the right branch have keys that are greater
than or equal to the key in the routing node. The sequential data structures
are protected from concurrent accesses by locks in the base nodes. A base node
lock has a statistics counter which is incremented when a thread needs to wait
to acquire the lock and decremented when no waiting is required. If the
statistics counter in a base node reaches a certain threshold, the items
stored in the base node are split between two new base nodes to reduce the
contention; see Figure 2a and Figure 2b. In the reverse direction, if the
statistics counter in a base node reaches the threshold for low contention
adaption, the items in the base node and a neighbor base node are joined into
one new base node; see Figure 2a and Figure 2c. Base nodes also have a valid
flag (depicted by ✓ and ✗) which is used to indicate if a base node is in the
CA tree or if it has been removed. Operations that end up in an invalid (✗)
base node need to retry the search until they end up in a valid (✓) base node.
Routing nodes also have a valid flag and a lock that are only used rarely
during the low contention optimizing join. Range queries are performed in CA
trees by first finding and locking the base node containing the first key in
the range and then traversing and locking subsequent base nodes until a base
node containing a key which is equal to or greater than the largest key in the
range is found.

An optimization that has been shown to greatly enhance performance of read
operations (lookup and range query) is to let read operations optimistically
attempt to do their operation without writing to shared memory [18, 19]. This
can be done by using a _sequence lock_ [11] as base node lock. A sequence lock
has an operation to read a sequence number from the lock. If a thread gets the
same even sequence number from two calls of this operation, then the sequence
lock guarantees that the lock has not been acquired between the two calls. An
optimistic attempt of a read operation first scans the sequence numbers and
checks the valid flags of the base nodes that the operation needs to read data
from, and then performs the operation, after which the sequence numbers from
the locks have to be checked again to make sure that the sequence numbers
match the previously read sequence numbers. If the optimistic attempt fails,
the operation is done by acquiring the base node locks in read-mode (several
read-mode lock holders can hold the lock at the same time).

The reader is referred to the earlier papers on CA trees [18, 19] for a
detailed description including pseudo-code and arguments that their operations
provide linearizability, deadlock freedom, and livelock freedom.

(a) Initial CA tree

(b) CA tree after a split

(c) CA tree after a join

Figure 2. Effect of the split and join operations on the CA tree of Figure 2a.

##  3\. CA Tree Optimization Enabled by Immutable Data Structures

By using a mutable reference to an immutable data structure as a CA tree’s
sequential data structure, it is straightforward to reduce the amount of time
that read operations spend on reading shared mutable data. Assuming that the
CA tree’s sequential data structure component is implemented with a mutable
reference to an immutable data structure, a lookup or range query operation
only needs to copy the values of the references that are needed by the
operation while traversing shared mutable data. The immutable data structures
referenced by the copied references are then traversed after the base node
locks have been unlocked (or after the second sequence number scan).
Especially for range queries, this optimization can give a large reduction of
the amount of time which is spent on reading shared mutable data as the time
that range queries need to spend on traversing the sequential data structures
is at least linear in the number of items in the range. With the optimization,
range queries may only need to traverse a few base nodes (one in the best
case) while reading shared mutable data even when the number of items in the
range is large.

It is straightforward to see that this optimization does not jeopardize
correctness as the result of a read operation would be the same if the
traversal of the sequential data structures happened instantly at the
linearization point (due to the immutability of the data structures referenced
by the copied references).

##  4\. The Implementation of the Optimized CA Tree

To experimentally evaluate the optimization described in the previous section,
a CA tree using a mutable reference to an immutable treap [20] as its
sequential data structure has been implemented in Java. A treap is a self-
balancing binary search tree with expected time complexity of
$\mathcal{O}(\log{}n)$ for insert, remove and lookup and an expected time
complexity of $\mathcal{O}(\log{}n+r)$ for range queries, where $n$ is the
number of items stored in the data structure and $r$ is the number of items in
the range. The treap also has efficient split and join operations [20] which
is important for the CA tree’s low and high contention adaptions [18]. To
facilitate cache friendly range queries, the treap implementation stores all
items in fat leaf nodes containing arrays that can store up to 64 items.

One heuristic, that CA trees use to reduce the time that future similar range
queries need to spend on traversing base nodes, is to decrement the contention
statistics counters in the locks of base nodes needed by a range query, if
more than one base node is needed; cf. [19]. With the optimization described
in the previous section in place, the portion of a range query that is spent
on traversing shared mutable data is even more affected by the number of base
nodes that the range query needs to access than without the optimization. The
reason for this is that the optimization moves the traversal of the sequential
data structures from within the period that is spent on reading shared mutable
data to after this period. It therefore makes sense to decrement the
contention statistics counters with a larger value, when the optimization is
used, as the potential benefit for similar range queries is larger than
without the optimization. Indeed, experiments show that changing the heuristic
to decrement by the value 100 instead of the value one (which is used by the
old CA tree implementations) gives significantly better performance in
scenarios with large range queries. Except for the change of the value used to
decrement the statistics counters in the described heuristic, the immutable
treap version of the CA tree has the same constants and thresholds for low and
high contention adaptions as described in the previous work [19].

##  5\. Related Work

The CA tree is the only one of the previously proposed approaches for
linearizable range queries [4, 5, 2, 17, 7, 3] that dynamically changes the
synchronization granularity to optimize for the conflicting requirements of
range queries of different sizes and single-key operations [19].

The _SnapTree_ by Bronson et al. [4] has an efficient linearizable clone
operation that returns a copy of the data structure from which a range query
operation can easily be derived. _SnapTree_ ’s clone operation waits for
active update operations and forces subsequent update operations to copy nodes
lazily before node modifications so that the copy is not modified. The
behavior of _SnapTree_ resembles the behavior of the data structure
implemented from a single mutable reference to an immutable data structure
(that is discussed in Section 1) when range queries are common. The _SnapTree_
can thus serve as an example of the coarse-grained approach for doing range
queries.

The lock-free $k$-ary search tree is an unbalanced external search tree with
up to $k$ keys stored in every node [6]. Range queries in $k$-ary search trees
are performed by doing a read scan and a validation scan of the immutable leaf
nodes containing items in the range [5]. The range query operation needs to
retry if the validation scan fails. The $k$-ary is an example of the fine-
grained approach discussed in Section 1. Another example of this fine-grained
approach based on software transactional memory is the Leaplist [2].

Chatterjee has proposed a general method for doing range queries in lock-free
ordered set data structures [7] based on the work by Erez and Shahar [15].
Unfortunately, the scalability of Chatterjee’s method suffers from the global
sequential hot spot in the list of range-collector objects that all range
queries have to write to in the worst case.

The _KiWi_ data structure by Basin et al. [3] supports wait-free range queries
and lookup operations as well as lock-free update operations. Update
operations help range queries by storing multiple versions of inserted items
when it is needed for the range queries. Similarly to Robertson’s data
structure [17], _KiWi_ ’s range queries atomically increment a global version
counter which is used by update operations to decide if storing an additional
version is necessary. _KiWi_ ’s global version number counter is bound to
become a scalability bottleneck with a high enough level of parallelism.
Similarly to the treap based CA tree, _KiWi_ tries to improve cache locality
by storing items in arrays that can store up to $k$ items.

A fundamental difference between the other efficient methods for range queries
in ordered set data structures and the optimized CA tree is the time spent by
range queries reading shared mutable data and thus the time in which conflicts
with update operations can happen. In the other methods [5, 2, 17, 19, 7, 3],
this time is at least linear in the number of items inside the range while the
optimized CA tree can do much better as is described in Section 3.

##  6\. Evaluation

We now experimentally evaluate the optimized CA tree implementation using the
immutable treap described in Section 4 (_Im-Tr-CA_). _Im-Tr-CA_ will be
compared to the recently proposed methods for doing linearizable range queries
in ordered sets: _SnapTree_ [4], $k$-ary [5], Chatterjee’s method applied to a
lock-free skiplist [7] (_ChatterjeeSL_), _KiWi_ [3] and the two CA tree
variants that use a mutable skiplist with fat nodes (_SL-CA_) and a mutable
AVL tree (_AVL-CA_) as sequential data structures [19]. The lock-free
skiplist, called ConcurrentSkipListMap, from the Java library that only
supports range queries that are not linearizable (_NonAtomicSL_) is also
included in the comparison. All data structures were provided by their
respective authors and are implemented in Java. The maximum number of items in
the nodes ($k$) is set to 64 for $k$-ary, _Im-Tr-CA_ and _SL-CA_ as this value
has previously been shown to give good results [5]. _KiWi_ ’s constants are
set as described in the _KiWi_ paper [3].

The benchmarks were run on a machine with four Intel(R) Xeon(R) E5-4650 CPUs
(2.70GHz each with eight cores and hyperthreading, giving a total of 32 actual
and 64 logical cores), turbo boost turned off, 128GB of RAM, running Linux
3.16.0-4-amd64 and Oracle JVM 1.8.0_131 (with the JVM flags -Xmx8g -Xms8g
-XX:+UseCondCardMark -server -d64). Each data point comes from the average of
three measurements runs of 10 seconds each that were preceded by 3 warm up
runs, also of 10 seconds each. The purpose of the warm up runs is to give the
just-in-time compiler enough time to compile the code. Error bars showing the
minimum and maximum measurements are displayed when they are large enough to
be seen.

The keys for the operations lookup, insert and remove as well as the starting
keys for range queries are randomly generated from a range of size $S$. The
data structure is pre-filled before the start of each benchmark run by
performing $S/2$ random insert operations. In all experiments presented in the
main part of this paper $S=10^{6}$. The interested reader can find results for
$S=10^{5}$ and $S=10^{7}$ in the appendix of this paper. Range queries
calculate the sum of the items in the range and the number of items in the
range. As a sanity check, the average number of items that are traversed per
range query is calculated and checked against the expected value.

(a) w:20% r:55% q:25%-10

(b) w:20% r:55% q:25%-1000

(c) w:20% r:55% q:25%-100000

Figure 3. Throughput (operations/$\mu$s) on the y-axis and thread count on the
x-axis.

### The Random Operations Benchmark

This benchmark measures throughput of a mix of operations performed by $N$
threads. In all captions, benchmark scenarios are described by strings of the
form w:$A$% r:$B$% q:$C$%-$R$, meaning that the benchmark performs $(A/2)$%
insert, $(A/2)$% remove, $B$% lookup operations and $C$% range queries of
maximum range size $R$. The range sizes are randomly set to values between 1
and $R$.

Figure 3 shows the results from three scenarios with increasing range sizes.
In the scenario with small range queries of maximum size 10 (Figure 3a), the
best performing data structures (the CA trees and $k$-ary) are almost
indistinguishable. _ChatterjeeSL_ and _KiWi_ that have a global scalability
bottleneck, as explained in the previous section, both scale worse in this
scenario. _Im-Tr-CA_ scales well in this scenario due to its ability to adapt
the sizes of its immutable parts but does not get much benefit from its quick
traversal of shared mutable data as conflicts between threads are rare for all
data structures in this scenario.

Conflicts are still relatively rare in the scenario with range queries of
maximum size 1000 (Figure 3b). The top performing data structures in this
scenario (_Im-Tr-CA_ , _SL-CA_ , _KiWi_ and $k$-ary) are those with cache
locality friendly nodes that store several items in arrays. However, _Im-Tr-
CA_ and _SL-CA_ , that adapt their synchronization granularity to the scenario
at hand, outperform _KiWi_ and $k$-ary with a wide margin in this scenario.

The scenario that has large range queries of maximum size 100000 (Figure 3c)
shows the distinguishing feature of _Im-Tr-CA_ that outperforms all the other
data structures with a large margin. Conflicts between range queries and
update operations are very likely with these large range queries but the
conflicts are significantly less costly in _Im-Tr-CA_ due to its short
critical sections, as is explained in Section 3.

### Separate Threads for Range Queries and Updates

Most of the time is spent doing range queries when large range queries are
used in the random operations benchmark. Thus, another benchmark is needed to
measure the data structures’ ability to handle large range queries
concurrently with frequent update operations. To this end, we use a similar
benchmark to the one developed by the _KiWi_ authors. This benchmark is
motivated by large scale applications that require quick updates of a data set
while other threads do large linearizable range queries concurrently (for
analytics) [3]. In this benchmark, half the threads do update operations
(insert and remove with equal probability) while the other half do range
queries with a range of fixed size. The throughput for updates is presented
separately from the range query throughput so that one can study the
performance of these operations separately. Note that in the graphs that show
the range query throughput, the number of operations per $\mu$s multiplied by
the range query size is shown on the y-axis to make the graphs more readable.

(a) Range queries, range size 32K (parallel updates)

(b) Range queries 16 threads (parallel updates)

(c) Updates (parallel range queries, range size 32K)

(d) Updates 16 threads (parallel range queries)

Figure 4. Results for benchmark with separate threads doing updates and range
queries.

Figure 4a and Figure 4c show the results of this benchmark with a range query
size of 32K and with varying thread counts. In Figure 4b and Figure 4d, the
thread count is fixed to 32 (16 updaters and 16 threads doing range queries)
and the x-axis shows varying range query sizes. First of all, _Im-Tr-CA_ with
its short range query critical section is overall the fastest data structure
in the scenarios. _KiWi_ is the second most performant data structure in the
scenarios with range query sizes larger than 2000. The bumpy performance of
_CA-SL_ in Figure 4b can be explained by the fact that the range queries
acquire the base node locks in read-mode which enables concurrent range
queries to bypass waiting update operations and take over the lock. _CA-SL_
thus provides good throughput for range queries with a range size of 512
because conflicts are rare and with a range size of 128K as “conflicts” with
other range queries that have already acquired the relevant base nodes are
common. _ChatterjeeSL_ ’s and _KiWi_ ’s update operations need to read the
RangeCollector list (_ChatterjeeSL_) or the global version number (_KiWi_)
which are updated by range queries. The more frequent updates of these global
objects with smaller range queries can explain the slight partial upward trend
that exists for _ChatterjeeSL_ and _KiWi_ in Figure 4d. $k$-ary’s range
queries are starved by update operations in the scenarios with large range
queries. The _SnapTree_ ’s operations are slow in most scenarios due to its
coarse-grained approach for doing range queries, but the _SnapTree_ ’s
performance is better in scenarios with larger and less frequent range
queries.

Table 1 shows the average number of base nodes and the number of base nodes
traversed per range query in _Im-Tr-CA_ after the benchmark runs of the
scenarios displayed in Figure 4b and Figure 4d. It is evident from the table
data that _Im-Tr-CA_ ’s range queries spend a very short time traversing
shared mutable data even for large range queries (e.g. approximately the time
it takes to traverse 13 base nodes in the case with range queries of size
32K). After the base nodes have been traversed, the collected immutable data
can be traversed without any need to care about other threads and without
disturbing other threads.

Table 1. Statistics for _Im-Tr-CA_ in the scenarios displayed in Figure 4b and Figure 4d. Range Size | 2 | 4 | 8 | 32 | 128 | 512 | 2K | 8K | 32K | 128K
---|---|---|---|---|---|---|---|---|---|---
# base nodes | 2.5K | 2.1K | 1.7K | 1.0K | 590 | 390 | 310 | 310 | 390 | 430
$\frac{\text{\\# traversed base nodes}}{\text{\\# range queries}}$ | 1.0 | 1.0 | 1.0 | 1.0 | 1.1 | 1.2 | 1.6 | 3.5 | 13 | 56

##  7\. Conclusion

A new CA tree variant that makes use of an immutable data structure has been
presented. The advantage of the new CA tree variant over the CA tree variants
that use mutable data structures as the sequential data structure component is
that the new variant drastically reduces the time period in which conflicts
between large range queries and other operations can happen. Compared to all
other data structures with linearizable range query support, the CA trees have
the advantage that they dynamically adapt the synchronization granularity to
fit the workload at hand. The experimental comparison shows that the presented
implementation’s quick traversal of shared mutable data and cache friendly
design makes the implementation outperform the best of the other data
structures with a wide margin in scenarios with large range queries.
Furthermore, the new CA tree variant also performs better or close to the best
of the other data structures in scenarios with small range queries due to its
ability to dynamically change its synchronization granularity. As future work,
we plan to design and evaluate a lock-free CA tree variant. A lock-free CA
tree variant could potentially give even better performance as it could avoid
priority inversions and other lock related problems.

### Acknowledgments

Vincent Gramoli gave me the idea of looking into immutable data structures in
combination with the CA tree. Amelie Lind, Martin Viklund, Stephan Brandauer,
Andreas Löscher, Elias Castegren and Konstantinos Sagonas helped me improve
the language. This work was supported by the Linnaeus centre of excellence
UPMARC (Uppsala Programming for Multicore Architectures Research Center).

##  Appendix A Source Code

The source code for the CA tree implementations and the benchmarks can be
found online
(https://www.it.uu.se/research/group/languages/software/im_tr_ca).

##  Appendix B Results with Other Set Sizes

Results corresponding to the results in figures 3 and 4 but with smaller set
sizes (the key range size $S=10^{5}$) can be found in figures 5 and 6. The
corresponding results for larger set sizes ($S=10^{7}$) can be found in
figures 7 and 8. The statistics corresponding to the statistics in Table 1 but
with the smaller and larger set sizes can be found in tables 2 and 3.

In the cases with the smallest set size ($S=10^{5}$), the ranges of size 32K
and 128K span 32% and 100% of the set represented by the data structures; see
Figure 6. _Im-Tr-CA_ ’s range queries lock out update operations from the
portion of the set that is covered by the range query. Even though this only
happens for a short period of time as Table 2 shows, it still has a negative
effect on update operations as Figure 6d shows. This is compensated by _Im-Tr-
CA_ ’s excellent performance for range queries in these scenarios as Figure 6b
shows.

In the cases with the largest set size ($S=10^{7}$), the ranges span a smaller
part of the sets represented by the data structures which explains why many of
the other data structures are closer to _Im-Tr-CA_ in these scenarios; see
figures 7 and 8.

## References

  * [1] Flurry analytics.  https://developer.yahoo.com/flurry/docs/analytics/.  Accessed: 2017-07-26.
  * [2] Hillel Avni, Nir Shavit, and Adi Suissa.  Leaplist: Lessons learned in designing TM-supported range queries.  In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC ’13, pages 299–308, New York, NY, USA, 2013. ACM.
  * [3] Dmitry Basin, Edward Bortnikov, Anastasia Braginsky, Guy Golan-Gueta, Eshcar Hillel, Idit Keidar, and Moshe Sulamy.  KiWi: A key-value map for scalable real-time analytics.  In Proceedings of the 22Nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’17, pages 357–369, New York, NY, USA, 2017. ACM.
  * [4] Nathan G. Bronson, Jared Casper, Hassan Chafi, and Kunle Olukotun.  A practical concurrent binary search tree.  In Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’10, pages 257–268, New York, NY, USA, 2010. ACM.
  * [5] Trevor Brown and Hillel Avni.  Range queries in non-blocking k-ary search trees.  In Roberto Baldoni, Paola Flocchini, and Ravindran Binoy, editors, Principles of Distributed Systems: 16th International Conference, OPODIS 2012\. Proceedings, pages 31–45. Springer, 2012.
  * [6] Trevor Brown and Joanna Helga.  Non-blocking k-ary search trees.  In Antonio Fernàndez Anta, Giuseppe Lipari, and Matthieu Roy, editors, Principles of Distributed Systems: 15th International Conference, OPODIS 2011. Proceedings, pages 207–221. Springer, 2011.
  * [7] Bapi Chatterjee.  Lock-free linearizable 1-dimensional range queries.  In Proceedings of the 18th International Conference on Distributed Computing and Networking, ICDCN ’17, pages 9:1–9:10, New York, NY, USA, 2017. ACM.
  * [8] Keir Fraser.  Practical lock-freedom.  PhD thesis, University of Cambridge Computer Laboratory, 2004.
  * [9] M. Herlihy.  A methodology for implementing highly concurrent data structures.  In Proceedings of the Second ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming, PPoPP ’90, pages 197–206, New York, NY, USA, 1990. ACM.
  * [10] Maurice P. Herlihy and Jeannette M. Wing.  Linearizability: A correctness condition for concurrent objects.  ACM Trans. Program. Lang. Syst., 12(3):463–492, July 1990.
  * [11] Christoph Lameter.  Effective synchronization on Linux/NUMA systems.  In Proc. of the Gelato Federation Meeting, 2005.
  * [12] Maged M. Michael.  High performance dynamic lock-free hash tables and list-based sets.  In Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures, pages 73–82, New York, NY, USA, 2002\. ACM.
  * [13] Aravind Natarajan and Neeraj Mittal.  Fast concurrent lock-free binary search trees.  In Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’14, pages 317–328, New York, NY, USA, 2014. ACM.
  * [14] Chris Okasaki.  Purely functional data structures.  Cambridge University Press, 1999.
  * [15] Erez Petrank and Shahar Timnat.  Lock-free data-structure iterators.  In Proceedings of the 27th International Symposium on Distributed Computing - Volume 8205, DISC 2013, pages 224–238, New York, NY, USA, 2013. Springer-Verlag New York, Inc.
  * [16] Aleksandar Prokopec, Nathan Grasso Bronson, Phil Bagwell, and Martin Odersky.  Concurrent tries with efficient non-blocking snapshots.  In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’12, pages 151–160, New York, NY, USA, 2012. ACM.
  * [17] Callum Robertson.  Implementing contention-friendly range queries in non-blocking key-value stores.  Bachelor thesis, The University of Sydney, November 2014.
  * [18] Konstantinos Sagonas and Kjell Winblad.  Contention adapting search trees.  In 14th International Symposium on Parallel and Distributed Computing, ISPDC, pages 215–224. IEEE, 2015.
  * [19] Konstantinos Sagonas and Kjell Winblad.  Efficient support for range queries and range updates using contention adapting search trees.  In Xipeng Shen, Frank Mueller, and James Tuck, editors, Languages and Compilers for Parallel Computing - 28th International Workshop, LCPC, volume 9519 of LNCS, pages 37–53. Springer, 2016.
  * [20] R. Seidel and C. R. Aragon.  Randomized search trees.  Algorithmica, 16(4):464–497, Oct 1996.
  * [21] Ori Shalev and Nir Shavit.  Split-ordered lists: Lock-free extensible hash tables.  Journal of the ACM (JACM), 53(3):379–405, May 2006.
  * [22] Jeff Shute, Radek Vingralek, Bart Samwel, Ben Handy, Chad Whipkey, Eric Rollins, Mircea Oancea, Kyle Littlefield, David Menestrina, Stephan Ellner, John Cieslewicz, Ian Rae, Traian Stancescu, and Himani Apte.  F1: A distributed SQL database that scales.  Proceedings of the VLDB Endowment, 6(11):1068–1079, August 2013\.

(a) w:20% r:55% q:25%-10

(b) w:20% r:55% q:25%-1000

(c) w:20% r:55% q:25%-100000

Figure 5. Results with key range of size $10^{5}$ which corresponds to a set
size of approximately $5\times 10^{4}$. Throughput (operations/$\mu$s) on the
y-axis and thread count on the x-axis.

(a) Range queries, range size 32K (parallel updates)

(b) Range queries 16 threads (parallel updates)

(c) Updates (parallel range queries, range size 32K)

(d) Updates 16 threads (parallel range queries)

Figure 6. Results for benchmark with separate threads doing updates and range queries with key range of size $10^{5}$ which corresponds to a set size of approximately $5\times 10^{4}$. Table 2. Statistics for _Im-Tr-CA_ in the scenarios displayed in Figure 6b and Figure 6d. Range Size | 2 | 4 | 8 | 32 | 128 | 512 | 2K | 8K | 32K | 128K
---|---|---|---|---|---|---|---|---|---|---
# base nodes | 890 | 720 | 570 | 330 | 190 | 120 | 97 | 130 | 90 | 96
$\frac{\text{\\# traversed base nodes}}{\text{\\# range queries}}$ | 1.0 | 1.0 | 1.1 | 1.1 | 1.2 | 1.6 | 3.0 | 11 | 27 | 98

(a) w:20% r:55% q:25%-10

(b) w:20% r:55% q:25%-1000

(c) w:20% r:55% q:25%-100000

Figure 7. Results with key range of size $10^{7}$ which corresponds to a set
size of approximately $5\times 10^{6}$. Throughput (operations/$\mu$s) on the
y-axis and thread count on the x-axis.

(a) Range queries, range size 32K (parallel updates)

(b) Range queries 16 threads (parallel updates)

(c) Updates (parallel range queries, range size 32K)

(d) Updates 16 threads (parallel range queries)

Figure 8. Results for benchmark with separate threads doing updates and range queries with key range of size $10^{7}$ which corresponds to a set size of approximately $5\times 10^{6}$. Table 3. Statistics for _Im-Tr-CA_ in the scenarios displayed in Figure 8b and Figure 8d. Range Size | 2 | 4 | 8 | 32 | 128 | 512 | 2K | 8K | 32K | 128K
---|---|---|---|---|---|---|---|---|---|---
# base nodes | 6.0K | 5.3K | 4.5K | 2.9K | 1.8K | 1.2K | 900 | 860 | 1.0K | 1.1K
$\frac{\text{\\# traversed base nodes}}{\text{\\# range queries}}$ | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.1 | 1.2 | 1.7 | 4.2 | 15


# Repeated-Root Cyclic Codes with Optimal Parameters or Best Parameters
Known††thanks:  The research of Hao Chen was supported by NSFC Grant 62032009.
The research of Cunsheng Ding was supported by The Hong Kong Research Grants
Council under Grant No. 16301123 and partially by the UAEU-AUA joint research
grant G00004614.

Hao Chen Hao Chen is with the College of Information Science and
Technology/Cyber Security, Jinan University, Guangzhou, Guangdong Province,
510632, China (e-mail: haochen@jnu.edu.cn).  Cunsheng Ding  C. Ding is with
the Department of Computer Science and Engineering, The Hong Kong University
of Science and Technology, Hong Kong, China (cding@ust.hk).

###### Abstract

Cyclic codes are the most studied subclass of linear codes and widely used in
data storage and communication systems. Many cyclic codes have optimal
parameters or the best parameters known. They are divided into simple-root
cyclic codes and repeated-root cyclic codes. Although there are a huge number
of references on cyclic codes, few of them are on repeated-root cyclic codes.
Hence, repeated-root cyclic codes are rarely studied. There are a few families
of distance-optimal repeated-root binary and $p$-ary cyclic codes for odd
prime $p$ in the literature. However, it is open whether there exists an
infinite family of distance-optimal repeated-root cyclic codes over
${\mathbf{{F}}}_{q}$ for each even $q\geq 4$.

In this paper, three infinite families of distance-optimal repeated-root
cyclic codes with minimum distance 3 or 4 are constructed; two other infinite
families of repeated-root cyclic codes with minimum distance 3 or 4 are
developed; four infinite families of repeated-root cyclic codes with minimum
distance 6 or 8 are presented; and two infinite families of repeated-root
binary cyclic codes with parameters $[2n,k,d\geq(n-1)/\log_{2}n]$, where
$n=2^{m}-1$ and $k\geq n$, are constructed. In addition, 27 repeated-root
cyclic codes of length up to $254$ over ${\mathbf{{F}}}_{q}$ for
$q\in\\{2,4,8\\}$ with optimal parameters or best parameters known are
obtained in this paper. The results of this paper show that repeated-root
cyclic codes could be very attractive and are worth of further investigation.

Index terms: Cyclic code, distance-optimal code, linear code, repeated-root
cyclic code.

##  1 Introduction

###  1.1 Cyclic codes and repeated-root cyclic codes

The Hamming weight $wt_{H}({\bf a})$ of a vector ${\bf
a}=(a_{1},\ldots,a_{n})\in{\bf F}_{q}^{n}$ is the cardinality of its support

$supp({\bf a})=\\{i:a_{i}\neq 0\\}.$

The Hamming distance $d_{H}({\bf a},{\bf b})$ between two vectors ${\bf a}$
and ${\bf b}$ is defined to be the Hamming weight of ${\bf a}-{\bf b}$. For a
code ${\bf C}\subseteq{\bf F}_{q}^{n}$, its minimum Hamming distance is

$d_{H}=\min_{{\bf a}\neq{\bf b}}\\{d_{H}({\bf a},{\bf b}):{\bf a},{\bf
b}\in{\bf C}\\}.$

An $[n,k,d_{H}]_{q}$ linear code is a $k$-dimensional linear subspace of
${\mathbf{{F}}}_{q}^{n}$ with minimum Hamming distance $d_{H}$. It is well-
known that the Hamming distance of a linear code ${\bf C}$ is the minimum
Hamming weight of its non-zero codewords. For the theory of error-correcting
codes in the Hamming metric, the reader is referred to [18, 29, 16]. A code
${\bf C}$ in ${\bf F}_{q}^{n}$ of minimum distance $d_{H}$ and cardinality $M$
is called an $(n,M,d_{H})_{q}$ code. For an $[n,k,d_{H}]_{q}$ linear code, the
Singleton bound asserts that $d_{H}\leq n-k+1$. When the equality holds, this
code is called a maximal distance separable (MDS) code. Reed-Solomon codes are
well-known MDS codes [16].

We recall the sphere packing bound for $(n,M,d)_{q}$ codes,

$M\cdot V_{(q,n)}(\lfloor\frac{d-1}{2}\rfloor)\leq q^{n},$

where $V_{(q,n)}(r)=1+n(q-1)+\displaystyle{n\choose
2}(q-1)^{2}+\cdots+\displaystyle{n\choose r}(q-1)^{r}$ is the volume of the
ball with radius $r$ in the Hamming metric space ${\mathbf{{F}}}_{q}^{n}$
([16, 29, 18]). If there is an $(n,M,d)_{q}$ code and there is no
$(n,M,d^{\prime})_{q}$ code with $d^{\prime}>d$, this $(n,M,d)_{q}$ code is
said to be distance-optimal. An $(n,M,d)_{q}$ code is distance-optimal with
respect to the sphere packing bound, provided that $M\cdot
V_{(q,n)}(\lfloor\frac{d}{2}\rfloor)>q^{n}$.

A linear code ${\mathbf{{C}}}\subseteq{\mathbf{{F}}}_{q}^{n}$ is called cyclic
if $(c_{0},c_{1},\ldots,c_{n-1})\in\mathcal{C}$ implies
$(c_{n-1},c_{0},\ldots,c_{n-2})\in\mathcal{C}$. The dual code of a cyclic code
${\mathbf{{C}}}$ is also a cyclic code. A codeword
${\mathbf{c}}=(c_{0},c_{1},\ldots,c_{n-1})$ in a cyclic code is identified
with the polynomial
$\mathbf{c}(x)=c_{0}+c_{1}x+\cdots+c_{n-1}x^{n-1}\in{\mathbf{{F}}}_{q}[x]/(x^{n}-1)$.
Then every cyclic code ${\mathbf{{C}}}$ is identified with a principal ideal
in the ring ${\mathbf{{F}}}_{q}[x]/(x^{n}-1)$, which is generated by a factor
$g(x)$ of $x^{n}-1$ with the smallest degree. This polynomial $g(x)$ is called
the _generator polynomial_ of ${\mathbf{{C}}}$ and $h(x)=(x^{n}-1)/g(x)$ is
called the _check polynomial_ of ${\mathbf{{C}}}$. It is well known that the
generator polynomial of the dual code ${\mathbf{{C}}}^{\perp}$ is the
reciprocal polynomial of $h(x)$.

Let $n$ be a positive integer satisfying $\gcd(n,q)=1$. Throughout this paper,
$i\bmod{n}$ denotes the unique integer $u$ such that $0\leq u\leq n-1$ and
$i\equiv u\pmod{n}$. Set
${\mathbf{{Z}}}_{n}={\mathbf{{Z}}}/n{\mathbf{{Z}}}=\\{0,1,\ldots,n-1\\}$. For
any $a\in{\mathbf{{Z}}}_{n}$, the $q$-cyclotomic coset modulo $n$ of $a$ is
defined by

$C_{a}^{(q,n)}=\\{aq^{i}\bmod{n}:0\leq i\leq\ell_{a}-1\\},$

where $\ell_{a}$ is the smallest positive integer such that
$aq^{\ell_{a}}\equiv a\pmod{n}$. The smallest nonnegative integer in
$C_{a}^{(q,n)}$ is called the coset leader. It is clear that the
$q$-cyclotomic cosets correspond to irreducible factors of $x^{n}-1$ in
${\mathbf{{F}}}_{q}[x]$. Therefore, the generator polynomial of a cyclic code
of length $n$ over ${\mathbf{{F}}}_{q}$ is the product of several irreducible
factors of $x^{n}-1$. The defining set of a cyclic code with generator
polynomial ${g(x)}$ with respect to an $n$-th primitive root $\beta$ in an
extension field of ${\mathbf{{F}}}_{q}$ is the the following set

${\bf T}=\\{i:{g}(\beta^{i})=0\\}.$

Then the defining set of a cyclic code is the disjoint union of several
cyclotomic cosets. If there are $\delta-1$ consecutive elements in the
defining set of a cyclic code, then the minimum distance of this cyclic code
is at least $\delta$. This is the famous BCH bound for cyclic codes ([2, 3,
14, 16, 29, 18]). The reader is referred to [12, 24] for the Hartmann-Tzeng
bound and Roos bound for cyclic codes. Repeated-root cyclic codes over
${\mathbf{{F}}}_{q}$ are these cyclic codes with generator polynomial ${g(x)}$
having repeated roots over an extension field of ${\mathbf{{F}}}_{q}$. A
cyclic code over ${\mathbf{{F}}}_{q}$ with generator polynomial having no
repeated root over any extension field of ${\mathbf{{F}}}_{q}$ is called a
simple-root cyclic code.

###  1.2 BCH cyclic codes

Let $\gcd(q,n)=1.$ Let $m=\mathrm{ord}_{n}(q)$, which is the smallest positive
integer $\ell$ such that $q^{\ell}\equiv 1\pmod{n}$. Let $\alpha$ be a
primitive element of ${\mathbf{{F}}}_{q^{m}}$. Define
$\beta=\alpha^{(q^{m}-1)/n}$. Then $\beta$ is an $n$-th primitive root of
unity. Define

$\mathrm{m}_{\beta^{i}}(x)=\prod_{j\in C_{i}^{(q,n)}}(x-\beta^{j}).$

It is easily seen that $\mathrm{m}_{\beta^{i}}(x)$ is an irreducible
polynomial in ${\mathbf{{F}}}_{q}[x]$ and a factor of $x^{n}-1$. Let
$\delta\geq 2$ be an integer and $b$ be an integer. Define

$\displaystyle
g_{(q,n,\delta,b)}(x)={\mathrm{lcm}}\\{\mathrm{m}_{\beta^{b}}(x),\ldots,\mathrm{m}_{\beta^{b+\delta-2}}(x)\\},$
(1)

where ${\mathrm{lcm}}$ denotes the least common multiple of the set of
polynomials over ${\mathbf{{F}}}_{q}$. Let ${\mathbf{{C}}}_{(q,n,\delta,b)}$
denote the cyclic code over ${\mathbf{{F}}}_{q}$ with length $n$ and generator
polynomial $g_{(q,n,\delta,b)}(x)$. This code
${\mathbf{{C}}}_{(q,n,\delta,b)}$ is called a _BCH code_ with designed
distance $\delta$. It is well known that the minimum distance of
${\mathbf{{C}}}_{(q,n,\delta,b)}$ is lower bounded by $\delta$. This follows
from the famous BCH bound for cyclic codes [16, 18]. The BCH codes introduced
in 1959-1960 ([2, 3, 14, 6, 9]), are one kind of the most important codes in
coding theory and practice. Many best known binary codes can be constructed
from binary BCH codes. Some BCH codes and Goppa codes can be considered as
subfield subcodes of generalized Reed-Solomon codes, and contain examples of
optimal binary codes for many parameters ([18, 16, 11]). In this paper, we
will use BCH codes to construct repeated-root cyclic codes.

###  1.3 Motivations and objectives of this paper

Cyclic codes were introduced by E. Prange [23] and there are a lot of
references on cyclic codes. But most of those references are about cyclic
codes with simple roots and there are a very small number of references on
cyclic codes with repeated roots [1, 4, 15, 17, 28, 21, 25, 31], although
there are more repeated-root cyclic codes than simple-root cyclic codes. This
shows that repeated-root cyclic codes are rarely studied and much less
understood. This is the first motivation of this paper.

Although cyclic codes are a small subclass of linear codes, many cyclic codes
are distance-optimal linear codes ([7],[11]). For example, the optimal
$[63,56,4]_{2}$ binary code and the optimal $[63,50,6]_{2}$ binary code are
BCH codes. However, these distance-optimal cyclic codes are not repeated-root
cyclic codes. In [28] and [15], two infinite families of distance-optimal
repeated-root binary codes with parameters $[2(2^{m}-1),2(2^{m}-1)-m-2,4]_{2}$
were constructed. In [15], an infinite family of distance-optimal repeated-
root binary codes with parameters

$\left[2\frac{4^{m}-1}{3},2\frac{4^{m}-1}{3}-2m-2,4\right]_{2}$

and 39 distance-optimal binary codes with length up to 256 were constructed.
The second motivation is the following questions:

  * •

What are the distance-optimal repeated-root cyclic codes of length up to $254$
over ${\mathbf{{F}}}_{q}$ for $q\in\\{4,8\\}$?

  * •

Is there any infinite family of distance-optimal repeated-root cyclic codes
over ${\mathbf{{F}}}_{q}$ for each even $q\geq 4$? If the answer to this
question is positive, how can one construct such an infinite family of cyclic
codes?

It is interesting to construct distance-optimal codes. Distance-optimal binary
codes with minimum distance four and six were constructed in [8, 13, 30]. Only
a small number of distance-optimal codes with minimum distance six were
reported in the literature ([13], [30, Theorem 9]). It is always a challenging
problem to construct distance-optimal codes with larger minimum distances. The
first objective of this paper is to construct infinite families of distance-
optimal repeated-root cyclic codes of small minimum distances with optimal
parameters or best parameters known.

It is a long-standing open problem whether there exists an infinite family of
asymptotically good cyclic codes [20]. Then it is interesting to construct
infinite families of rate $\frac{1}{2}$ explicit cyclic codes such that their
minimum distances are as large as possible. Recently, an infinite family of
$[2^{m}-1,2^{m-1}]_{2}$ binary cyclic codes with square-root-like lower bounds
on their minimum distances and dual minimum distances was constructed in [27].
An infinite family of $[n,\frac{n+1}{2},d\geq\frac{n}{\log_{2}n}]_{2}$ binary
cyclic codes with $n=2^{p}-1$ and $p$ being an odd prime number, was
constructed in [26]. Motivated by these works, the second objective of this
paper is to construct infinite families of repeated-root binary cyclic codes
with parameters $[2n,k,d\geq(n-1)/\log_{2}n]$, where $n=2^{m}-1$ and $k\geq
n$.

###  1.4 The organisation of this paper

The rest of this paper is organised as follows. Section 2 recalls the
generalised van Lint theorem, which is the basic tool of this paper. Section 3
constructs several infinite families of repeated-root cyclic codes with
minimum distance four or three. Section 4 presents two infinite families of
repeated-root cyclic codes with minimum distance six or eight. Section 5
proposes two infinite families of repeated-root cyclic codes over
${\mathbf{{F}}}_{q}$ with minimum distance 6 for $q\geq 4$. Section 6
constructs two infinite families of repeated-root binary cyclic codes with
large dimensions and large minimum distances. Section 7 summarises the
contributions of this paper and makes some concluding remarks.

##  2 The generalized van Lint theorem

In this section, we recall the following result in [5], which is the basic
tool for constructing repeated-root cyclic codes in this paper.

Let ${\mathbf{{C}}}_{1}$ and ${\mathbf{{C}}}_{2}$ be two linear codes with
parameters $[n,k_{1},d_{1}]_{q}$ and $[n,k_{2},d_{2}]_{q}$, respectively. The
Plotkin sum of ${\mathbf{{C}}}_{1}$ and ${\mathbf{{C}}}_{2}$ is denoted by
${\mathrm{Plotkin}}({\mathbf{{C}}}_{1},{\mathbf{{C}}}_{2})$ and defined by

$\displaystyle{\mathrm{Plotkin}}({\mathbf{{C}}}_{1},{\mathbf{{C}}}_{2}):=\\{({\mathbf{u}}|{\mathbf{u}}+{\mathbf{v}}):{\mathbf{u}}\in{\mathbf{{C}}}_{1},\,{\mathbf{v}}\in{\mathbf{{C}}}_{2}\\},$

where ${\mathbf{u}}|{\mathbf{v}}$ denotes the concatenation of the two vectors
${\mathbf{u}}$ and ${\mathbf{v}}$. It is well known that ${\mathbf{{C}}}$ has
parameters $[2n,k_{1}+k_{2},\min\\{2d_{1},d_{2}\\}]_{q}$ [18]. The Plotkin sum
is also called the $[{\bf u}|{\bf u}+{\bf v}]$ construction and was introduced
in 1960 by Plotkin [22].

The $[{\bf u}|{\bf u}+{\bf v}]$ construction of binary repeated-root cyclic
codes was given by van Lint in his paper [28]. The following theorem is a
generalization of the original van Lint theorem.

######  Theorem 2.1 (The generalized van Lint theorem [5]).

Let $q$ be a power of $2$ and $n$ be an odd positive integer. Let ${\bf
C}_{1}\subseteq{\bf F}_{q}^{n}$ be a cyclic code with generator polynomial
$g_{1}(x)\in{\bf F}_{q}[x]$ and ${\bf C}_{2}\subseteq{\bf F}_{q}^{n}$ be a
cyclic code generated by the polynomial $g_{1}(x)g_{2}(x)\in{\bf F}_{q}[x]$,
where $g_{2}(x)$ is a divisor of $x^{n}+1$. Then the code
${\mathrm{Plotkin}}({\mathbf{{C}}}1,{\mathbf{{C}}}_{2})$ is permutation-
equivalent to the repeated-root cyclic code ${\mathbf{{C}}}(g_{1},g_{2})$ of
length $2n$ generated by the polynomial $g_{1}(x)^{2}g_{2}(x)$. In addition,
the cyclic code ${\mathbf{{C}}}({\mathbf{{C}}}_{1},{\mathbf{{C}}}_{2})$ has
generator polynomial

$\frac{g_{1}(x)^{2}g_{2}(x)}{\gcd(g_{1}(x),g_{2}(x))},$

dimension

$2n-2\deg(g_{1}(x))-\deg(g_{2}(x))+\deg(\gcd(g_{1}(x),g_{2}(x)))$

and minimum distance

$d({\mathbf{{C}}}({\mathbf{{C}}}_{1},{\mathbf{{C}}}_{2}))=\min\\{2d({\mathbf{{C}}}_{1}),d({\mathbf{{C}}}_{2})\\},$

here and hereafter $d({\mathbf{{C}}})$ denotes the minimum distance of
${\mathbf{{C}}}$.

Notice that some of the conclusions in Theorem 2.1 may be wrong if $q$ is odd.
By definition, the code ${\mathbf{{C}}}_{2}$ in Theorem 2.1 has generator
polynomial

$\frac{g_{1}(x)g_{2}(x)}{\gcd(g_{1}(x),g_{2}(x))}$

and dimension

$n-\deg(g_{1}(x))-\deg(g_{2}(x))+\deg(\gcd(g_{1}(x),g_{2}(x))).$

Therefore, ${\mathbf{{C}}}_{2}$ is a subcode of ${\mathbf{{C}}}_{1}$.

In this paper, two cyclic codes ${\mathbf{{C}}}_{1}$ and ${\mathbf{{C}}}_{2}$
of odd length $n$ over ${\mathbf{{F}}}_{q}$ satisfying
${\mathbf{{C}}}_{2}\subseteq{\mathbf{{C}}}_{1}$ are properly selected or
designed, where $q$ is even. Let $g_{1}(x)$ and $g_{1}(x)g_{2}(x)$ be the
generator polynomials of ${\mathbf{{C}}}_{1}$ and ${\mathbf{{C}}}_{2}$,
respectively. We will study the corresponding repeated-root cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{1},{\mathbf{{C}}}_{2})$. To make the repeated-
root cyclic code ${\mathbf{{C}}}({\mathbf{{C}}}_{1},{\mathbf{{C}}}_{2})$ have
very good or optimal parameters, the two building blocks ${\mathbf{{C}}}_{1}$
and ${\mathbf{{C}}}_{2}$ must be chosen carefully.

##  3 Infinite families of repeated-root cyclic codes with minimum distance
four or three

In this section, we construct several infinite families of repeated-root
cyclic codes with minimum distance four or three. To prove the distance
optimality of some of them, we need the following lemma.

######  Lemma 3.1.

[10]. Let ${\mathbf{{C}}}$ be an $[n,k,d]$ linear code with even $d$. Then

$\sum_{i=0}^{(d-2)/2}\binom{n-1}{i}(q-1)^{i}\leq q^{n-1-k}.$

The following theorem gives an infinite family of distance-optimal repeated-
root binary cyclic codes with minimum distance four and is due to van Lint
[28]. We document it here for completeness.

######  Theorem 3.1.

[28] Let $m\geq 4$ be an integer and $n=2^{m}-1$. Then the repeated-root
binary cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,2,0)},{\mathbf{{C}}}_{(2,n,3,0)})$ has
parameters $[2(2^{m}-1),2(2^{m}-1)-m-2,4]_{2}$ and generator polynomial
$(x-1)^{2}\mathrm{m}_{\beta}(x)$, where $\beta$ is a primitive element of
${\mathbf{{F}}}_{2^{m}}$. In addition,
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,2,0)},{\mathbf{{C}}}_{(2,n,3,0)})$ is
distance-optimal with respect to the sphere-packing bound.

######  Example 3.1.

The first four codes in the family of codes
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,2,0)},{\mathbf{{C}}}_{(2,n,3,0)})$ have
the following parameters:

$[30,24,4]_{2},\ [62,55,4]_{2},\ [126,118,4]_{2},\ [254,245,4]_{2}.$

All of them are distance-optimal.

The following theorem gives an infinite family of distance-optimal repeated-
root cyclic codes over ${\mathbf{{F}}}_{q}$ with minimum distance three for
even $q\geq 4$.

######  Theorem 3.2.

Let $m\geq 2$ be an integer and $n=q^{m}-1$, where $q\geq 4$ is even. Then the
repeated-root cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,3,0)})$ has
parameters $[2(q^{m}-1),2(q^{m}-1)-m-2,3]_{q}$ and generator polynomial
$(x-1)^{2}\mathrm{m}_{\beta}(x)$, where $\beta$ is a primitive element of
${\mathbf{{F}}}_{q^{m}}$. Furthermore, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,3,0)})$ is
distance-optimal with respect to the bound in Lemma 3.1 and the sphere packing
bound.

######  Proof..

By definition, the BCH code ${\mathbf{{C}}}_{(q,n,2,0)}$ has generator
polynomial $x-1$. It follows from the BCH bound that
$d({\mathbf{{C}}}_{(q,n,2,0)})\geq 2$. On the other hand, the codeword $x-1$
in ${\mathbf{{C}}}_{(q,n,2,0)}$ has Hamming weight $2$. Consequently,
$d({\mathbf{{C}}}_{(q,n,2,0)})=2$ and ${\mathbf{{C}}}_{(q,n,2,0)}$ has
parameters $[n,n-1,2]_{q}$.

By definition, the BCH code ${\mathbf{{C}}}_{(q,n,3,0)}$ has generator
polynomial $(x-1)\mathrm{m}_{\beta}(x)$. It follows from the BCH bound that
$d({\mathbf{{C}}}_{(q,n,3,0)})\geq 3$. We now prove that
${\mathbf{{C}}}_{(q,n,3,0)}$ has a codeword of Hamming weight $3$. To this
end, we consider the following set

$\displaystyle\left\\{\frac{\beta^{i}+1}{\beta^{q^{m}-2}+1}:1\leq i\leq
q^{m}-2\right\\}=J\cup\\{1\\},$

where

$J=\left\\{\frac{\beta^{i}+1}{\beta^{q^{m}-2}+1}:1\leq i\leq
q^{m}-3\right\\}.$

Notice that $J\cap\\{0,1\\}=\emptyset$ and $|J|=q^{m}-3$. There exists an
integer $i$ with $1\leq i\leq q^{m}-3$ such that

$b:=\frac{\beta^{i}+1}{\beta^{q^{m}-2}+1}\in{\mathbf{{F}}}_{q}\setminus\\{0,1\\}.$

Put

$b_{1}=\frac{1}{1+b}\in{\mathbf{{F}}}_{q}\setminus\\{0,1\\}$

and

$b_{2}=\frac{b}{1+b}\in{\mathbf{{F}}}_{q}\setminus\\{0,1\\}.$

Then $b_{1}\neq b_{2}$. Let

$c(x)=1+b_{1}x^{i}+b_{2}x^{q^{m}-2}.$

It is easily verified that $c(1)=c(\beta)=0$. Therefore, $c(x)$ is a codeword
in ${\mathbf{{C}}}_{(q,n,3,0)}$. Consequently,
$d({\mathbf{{C}}}_{(q,n,3,0)})=3$. It is easily seen that the cyclotomic coset

$C_{1}^{(q,n)}=\\{1,q,\ldots,q^{m-1}\\}.$

Hence $\deg(\mathrm{m}_{\beta}(x))=m$. As a result,
$\dim({\mathbf{{C}}}_{(q,n,3,0)})=n-m-1$. Consequently,
${\mathbf{{C}}}_{(q,n,3,0)}$ has parameters $[n,n-m-1,3]_{q}$.

Since $\mathrm{m}_{\beta}(x)$ is irreducible and has degree $m\geq 2$, we have
that $\gcd(x-1,\mathrm{m}_{\beta}(x))=1$. By Theorem 2.1 the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,3,0)})$ has
generator polynomial $(x-1)^{2}\mathrm{m}_{\beta}(x)$ and parameters
$[2(q^{m}-1),2(q^{m}-1)-m-2,3]_{q}$.

It follows from the sphere packing bound that any linear code ${\mathbf{{C}}}$
with parameters $[2(q^{m}-1),2(q^{m}-1)-m-2,d]_{q}$ must satisfy $d\leq 4$. It
then follows from Lemma 3.1 that there is no linear code with parameters
$[2(q^{m}-1),2(q^{m}-1)-m-2,4]_{q}$ for $q\geq 4$ and $m\geq 2$. Hence, the
code ${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,3,0)})$
is distance-optimal. This completes the proof.

######  Example 3.2.

Let $(q,m)=(4,2)$. Then the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,3,0)})$ has
parameters $[30,26,3]_{4}$ and is distance-optimal. Notice the code with the
same parameters in [11] is not known to be cyclic.

######  Example 3.3.

Let $(q,m)=(4,3)$. Then the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,3,0)})$ has
parameters $[126,121,3]_{4}$ and is distance-optimal. Notice the code with the
same parameters in [11] is not known to be cyclic.

######  Example 3.4.

Let $(q,m)=(8,2)$. Then the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,3,0)})$ has
parameters $[126,122,3]_{8}$ and is distance-optimal. Notice the code with the
same parameters in [11] is not known to be cyclic.

The next theorem documents another infinite family of distance-optimal
repeated-root cyclic codes of minimum four.

######  Theorem 3.3.

Let $m\geq 2$ be an integer and $n=q^{m}-1$, where $q\geq 4$ is even. Then the
repeated-root cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,4,0)})$ has
parameters $[2(q^{m}-1),2(q^{m}-1)-2m-2,4]_{q}$ and generator polynomial
$(x-1)^{2}\mathrm{m}_{\beta}(x)\mathrm{m}_{\beta^{2}}(x)$, where $\beta$ is a
primitive element of ${\mathbf{{F}}}_{q^{m}}$. In addition, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,4,0)})$ is
distance-optimal with respect to the sphere packing bound if $qm>8$.

######  Proof..

It was shown in the proof of Theorem 3.2 that ${\mathbf{{C}}}_{(q,n,2,0)}$ has
parameters $[n,n-1,2]_{q}$ and generator polynomial $x-1$.

By definition, the BCH code ${\mathbf{{C}}}_{(q,n,4,0)}$ has generator
polynomial $(x-1)\mathrm{m}_{\beta}(x)\mathrm{m}_{\beta^{2}}(x)$. It follows
from the BCH bound that $d({\mathbf{{C}}}_{(q,n,4,0)})\geq 4$. It can be
easily verified that $|C_{1}^{(q,n)}|=|C_{2}^{(q,n)}|=m.$ Consequently,
${\mathbf{{C}}}_{(q,n,4,0)}$ has parameters $[n,n-2m-1,d\geq 4]_{q}$.

Since $\mathrm{m}_{\beta^{i}}(x)$ is irreducible and has degree $m\geq 2$ for
$i\in\\{1,2\\}$, we have that
$\gcd(x-1,\mathrm{m}_{\beta}(x)\mathrm{m}_{\beta^{2}}(x))=1$. By Theorem 2.1
the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,4,0)})$ has
generator polynomial $(x-1)^{2}\mathrm{m}_{\beta}(x)\mathrm{m}_{\beta^{2}}(x)$
and parameters $[2(q^{m}-1),2(q^{m}-1)-2m-2,4]_{q}$. It can be verified that
$V_{(q,2n)}(2)>q^{2m+2}$ if $qm>8$. Hence, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,4,0)})$ is
distance-optimal with respect to the sphere packing bound. This completes the
proof.

######  Example 3.5.

Let $(q,m)=(4,2)$. Then the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,4,0)})$ has
parameters $[30,24,4]_{4}$ and is distance-optimal according to [11]. Notice
that the linear code with the same parameters in [11] is not known to be
cyclic.

######  Example 3.6.

Let $(q,m)=(4,3)$. Then the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,4,0)})$ has
parameters $[126,118,4]_{4}$ and is distance-optimal. Notice that the linear
code with the same parameters in [11] is not known to be cyclic.

######  Example 3.7.

Let $(q,m)=(8,2)$. Then the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,4,0)})$ has
parameters $[126,120,4]_{8}$ and is distance-optimal. Notice that the linear
code with the same parameters in [11] is not known to be cyclic.

The next theorem presents an infinite family of repeated-root cyclic codes
with minimum distance three or four.

######  Theorem 3.4.

Let $m\geq 2$ be an integer and $n=(q^{m}-1)/(q-1)$, where $q\geq 4$ is even.
Then the repeated-root binary cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,3,0)})$ has
parameters $[2n,2n-m-2,3\leq d\leq 4]_{q}$ and generator polynomial
$(x-1)^{2}\mathrm{m}_{\beta}(x)$, where $\beta$ is a primitive $n$-th root of
unity in ${\mathbf{{F}}}_{q^{m}}$.

######  Proof..

By definition, the BCH code ${\mathbf{{C}}}_{(q,n,2,0)}$ has generator
polynomial $x-1$. It follows from the BCH bound that
$d({\mathbf{{C}}}_{(q,n,2,0)})\geq 2$. On the other hand, the codeword $x-1$
in ${\mathbf{{C}}}_{(q,n,2,0)}$ has Hamming weight $2$. Consequently,
$d({\mathbf{{C}}}_{(q,n,2,0)})=2$ and ${\mathbf{{C}}}_{(q,n,2,0)}$ has
parameters $[n,n-1,2]_{q}$.

By definition, the BCH code ${\mathbf{{C}}}_{(q,n,3,0)}$ has generator
polynomial $(x-1)\mathrm{m}_{\beta}(x)$. It follows from the BCH bound that
$d({\mathbf{{C}}}_{(q,n,3,0)})\geq 3$. It can be verified that

$\deg(\mathrm{m}_{\beta}(x))=m.$

As a result, $\dim({\mathbf{{C}}}_{(q,n,3,0)})=n-m-1$. Consequently,
${\mathbf{{C}}}_{(q,n,3,0)}$ has parameters $[n,n-m-1,3\leq d\leq 4]_{q}$.

Since $\gcd(x-1,\mathrm{m}_{\beta}(x))=1$, by Theorem 2.1 the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,3,0)})$ has
generator polynomial $(x-1)^{2}\mathrm{m}_{\beta}(x)$ and parameters
$[2n,2n-m-2,d\geq 3]_{q}$. It follows from the sphere packing bound that
$d({\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,3,0)}))\leq
4$. This completes the proof.

######  Example 3.8.

The following is a list of codes in the family of the codes
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,3,0)})$ in
Theorem 3.4.

  * •

When $(q,m)=(4,2)$, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,3,0)})$ has
parameters $[10,6,4]_{4}$. This code is distance-optimal with respect to the
Griesmer bound. Notice that the linear code with the same parameters in [11]
is not known to be cyclic.

  * •

When $(q,m)=(4,3)$, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,3,0)})$ has
parameters $[42,37,3]_{4}$. This code is distance-optimal according to Theorem
3.4. Notice that the linear code with the same parameters in [11] is not known
to be cyclic.

  * •

When $(q,m)=(4,4)$, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,3,0)})$ has
parameters $[170,164,3]_{4}$. This code is distance-optimal according to
Theorem 3.4. Notice that the linear code with the same parameters in [11] is
not known to be cyclic.

  * •

When $(q,m)=(8,2)$, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,3,0)})$ has
parameters $[18,14,4]_{8}$. This code is distance-optimal according to Theorem
3.4. Notice that the linear code with the same parameters in [11] is not known
to be cyclic.

  * •

When $(q,m)=(8,3)$, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,3,0)})$ has
parameters $[146,141,3]_{8}$ and is distance-optimal according to Theorem 3.4.
No best linear code over ${\mathbf{{F}}}_{8}$ with length $146$ and dimension
$141$ is reported in [11].

To the best knowledge of the authors, no infinite family of linear codes with
the same length and dimension better than
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,3,0)})$ is
reported in the literature. The next theorem presents an infinite family of
repeated-root cyclic codes with minimum distance four.

######  Theorem 3.5.

Let $m\geq 2$ be an integer and $n=(q^{m}-1)/(q-1)$, where $q\geq 4$ is even.
Then the repeated-root binary cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,4,0)})$ has
parameters $[2n,2n-2m-2,4]_{q}$ and generator polynomial
$(x-1)^{2}\mathrm{m}_{\beta}(x)\mathrm{m}_{\beta^{2}}(x)$, where $\beta$ is a
primitive $n$-th root of unity in ${\mathbf{{F}}}_{q^{m}}$.

######  Proof..

By definition, the BCH code ${\mathbf{{C}}}_{(q,n,2,0)}$ has generator
polynomial $x-1$. It follows from the BCH bound that
$d({\mathbf{{C}}}_{(q,n,2,0)})\geq 2$. On the other hand, the codeword $x-1$
in ${\mathbf{{C}}}_{(q,n,2,0)}$ has Hamming weight $2$. Consequently,
$d({\mathbf{{C}}}_{(q,n,2,0)})=2$ and ${\mathbf{{C}}}_{(q,n,2,0)}$ has
parameters $[n,n-1,2]_{q}$.

By definition, the BCH code ${\mathbf{{C}}}_{(q,n,4,0)}$ has generator
polynomial $(x-1)\mathrm{m}_{\beta}(x)\mathrm{m}_{\beta^{2}}(x)$. It follows
from the BCH bound that $d({\mathbf{{C}}}_{(q,n,4,0)})\geq 4$. It can be
verified that

$\deg(\mathrm{m}_{\beta}(x))=\deg(\mathrm{m}_{\beta^{2}}(x))=m.$

As a result, $\dim({\mathbf{{C}}}_{(q,n,4,0)})=n-2m-1$. Consequently,
${\mathbf{{C}}}_{(q,n,4,0)}$ has parameters $[n,n-2m-1,d\geq 4]_{q}$.

Since $\gcd(x-1,\mathrm{m}_{\beta}(x)\mathrm{m}_{\beta^{2}}(x))=1$, by Theorem
2.1 the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,4,0)})$ has
generator polynomial $(x-1)^{2}\mathrm{m}_{\beta}(x)\mathrm{m}_{\beta^{2}}(x)$
and parameters $[2n,2n-2m-2,4]_{q}$. This completes the proof.

######  Example 3.9.

The following is a list of codes in the family of the codes
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,4,0)})$ in
Theorem 3.5.

  * •

When $(q,m)=(4,2)$, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,4,0)})$ has
parameters $[10,4,4]_{4}$. The distance-optimal linear code with parameters
$[10,4,6]_{4}$ in [11] is not known to be cyclic.

  * •

When $(q,m)=(4,3)$, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,4,0)})$ has
parameters $[42,34,4]_{4}$. The best linear code with parameters
$[42,34,5]_{4}$ in [11] is not known to be cyclic.

  * •

When $(q,m)=(4,4)$, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,4,0)})$ has
parameters $[170,160,4]_{4}$. The best linear code with parameters
$[170,160,5]_{4}$ in [11] is not known to be cyclic.

  * •

When $(q,m)=(8,2)$, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,4,0)})$ has
parameters $[18,12,4]_{8}$. The distance-optimal linear code with parameters
$[18,12,6]_{8}$ in [11] is not known to be cyclic.

  * •

When $(q,m)=(8,3)$, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,4,0)})$ has
parameters $[146,138,4]_{8}$. No best linear code over ${\mathbf{{F}}}_{8}$
with length $146$ and dimension $138$ is reported in [11].

To the best knowledge of the authors, no infinite family of linear codes with
the same length and dimension better than
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,2,0)},{\mathbf{{C}}}_{(q,n,4,0)})$ is
reported in the literature.

Combining Theorems 3.1, 3.2 and 3.3, we deduce the following existence result.

######  Theorem 3.6.

For each even $q\geq 2$, there is an infinite family of distance-optimal
repeated-root cyclic codes of minimum distance four.

For each even $q\geq 4$, there is an infinite family of distance-optimal
repeated-root cyclic codes of minimum distance three.

The following theorem describes an infinite family of distance-optimal
repeated-root cyclic codes over ${\mathbf{{F}}}_{4}$.

######  Theorem 3.7.

Let $m\geq 2$ be an integer and $n=2^{2m-1}-1$. Then the repeated-root cyclic
code ${\mathbf{{C}}}({\mathbf{{C}}}_{(4,n,2,0)},{\mathbf{{C}}}_{(4,n,4,0)})$
has parameters $[2n,2n-2m-1,4]_{4}$. Furthermore, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(4,n,2,0)},{\mathbf{{C}}}_{(4,n,4,0)})$ is
distance-optimal with respect to the sphere packing bound for $m\geq 3$.

######  Proof..

By definition, the BCH code ${\mathbf{{C}}}_{(4,n,2,0)}$ has generator
polynomial $x-1$ and thus dimension $n-1$. It follows from the BCH bound that
$d({\mathbf{{C}}}_{(4,n,2,0)})\geq 2$. It then follows from the Singleton
bound that $d({\mathbf{{C}}}_{(4,n,2,0)})=2$. Hence,
${\mathbf{{C}}}_{(4,n,2,0)}$ has parameters $[n,n-1,2]_{4}$.

Since $4^{2m}-2=2(2^{2m-1}-1)$, $2$ is in the $4$-cyclotomic coset
$C_{1}^{(4,n)}$. By definition, the BCH code ${\mathbf{{C}}}_{(4,n,4,0)}$ has
generator polynomial $(x-1)\mathrm{m}_{\beta}(x)$. It can be verified that
$|C_{1}^{(4,n)}|=2m-1.$ Consequently,

$\dim({\mathbf{{C}}}_{(4,n,4,0)})=n-2m.$

It follows from the BCH bound that $d({\mathbf{{C}}}_{(4,n,4,0)})\geq 4.$ Note
that $\gcd(x-1,m_{\beta}(x))=1$. The desired conclusions on the parameters of
the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(4,n,2,0)},{\mathbf{{C}}}_{(4,n,4,0)})$ then
follow from Theorem 2.1. It is straightforward to verify that the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(4,n,2,0)},{\mathbf{{C}}}_{(4,n,4,0)})$ is
distance-optimal with respect to the sphere packing bound for $m\geq 3$. This
completes the proof.

######  Example 3.10.

The first three codes in the family of codes
${\mathbf{{C}}}({\mathbf{{C}}}_{(4,n,2,0)},{\mathbf{{C}}}_{(4,n,4,0)})$ are
listed below.

  * •

When $m=2$, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(4,n,2,0)},{\mathbf{{C}}}_{(4,n,4,0)})$ has
parameters $[14,9,4]_{4}$ and is optimal according to [11]. Notice that the
best linear code known with parameters $[14,9,4]_{4}$ in [11] is not known to
be cyclic.

  * •

When $m=3$, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(4,n,2,0)},{\mathbf{{C}}}_{(4,n,4,0)})$ has
parameters $[62,55,4]_{4}$ and is optimal. Notice that the best linear code
known with parameters $[62,55,4]_{4}$ in [11] is not known to be cyclic.

  * •

When $m=4$, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(4,n,2,0)},{\mathbf{{C}}}_{(4,n,4,0)})$ has
parameters $[254,245,4]_{4}$ and is optimal. Notice that the best linear code
known with parameters $[254,245,4]_{4}$ in [11] is not known to be cyclic.

##  4 Infinite families of repeated-root cyclic codes over
${\mathbf{{F}}}_{2}$ with best parameters known

The following theorem documents an infinite family of repeated-root binary
cyclic codes with minimum distance $6$.

######  Theorem 4.1.

Let $m\geq 3$ be an integer and $n=2^{m}-1$. Then the repeated-root binary
cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,1)},{\mathbf{{C}}}_{(2,n,6,0)})$ has
parameters $[2(2^{m}-1),2(2^{m}-1)-3m-1,6]_{2}$ and generator polynomial
$(x-1)\mathrm{m}_{\beta}(x)^{2}\mathrm{m}_{\beta^{3}}(x)$, where $\beta$ is a
primitive element of ${\mathbf{{F}}}_{2^{m}}$.

######  Proof..

By definition, the BCH code ${\mathbf{{C}}}_{(2,n,3,1)}$ has generator
polynomial $\mathrm{m}_{\beta}(x)$ and parameters $[n,n-m,3]_{2}$, as it is
the binary Hamming cyclic code.

By definition, the BCH code ${\mathbf{{C}}}_{(2,n,6,0)}$ has generator
polynomial $(x-1)\mathrm{m}_{\beta}(x)\mathrm{m}_{\beta^{3}}(x)$. It follows
from the BCH bound that $d({\mathbf{{C}}}_{(2,n,6,0)})\geq 6$. It can be
easily verified that $|C_{1}^{(2,n)}|=|C_{3}^{(2,n)}|=m.$ Consequently,
${\mathbf{{C}}}_{(2,n,6,0)}$ has parameters $[n,n-2m-1,d\geq 6]_{2}$.

Since $\mathrm{m}_{\beta^{i}}(x)$ is irreducible and has degree $m\geq 3$ for
$i\in\\{1,3\\}$, we deduce that
$\gcd(\mathrm{m}_{\beta}(x),(x-1)\mathrm{m}_{\beta^{3}}(x))=1$. By Theorem 2.1
the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,1)},{\mathbf{{C}}}_{(2,n,6,0)})$ has
generator polynomial $(x-1)\mathrm{m}_{\beta}(x)^{2}\mathrm{m}_{\beta^{3}}(x)$
and parameters $[2(2^{m}-1),2(2^{m}-1)-3m-1,6]_{2}$. This completes the proof.

######  Example 4.1.

The following is a list of the first five codes in the family of binary cyclic
codes ${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,1)},{\mathbf{{C}}}_{(2,n,6,0)})$.

  * •

When $m=3$, the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,1)},{\mathbf{{C}}}_{(2,n,6,0)})$ has
parameters $[14,4,6]_{2}$. Notice that the best linear code known with
parameters $[14,4,7]_{2}$ in [11] is not known to be cyclic.

  * •

When $m=4$, the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,1)},{\mathbf{{C}}}_{(2,n,6,0)})$ has
parameters $[30,17,6]_{2}$. Notice that the best linear code known with
parameters $[30,17,6]_{2}$ in [11] is not known to be cyclic.

  * •

When $m=5$, the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,1)},{\mathbf{{C}}}_{(2,n,6,0)})$ has
parameters $[62,46,6]_{2}$. Notice that the best linear code known with
parameters $[62,46,6]_{2}$ in [11] is not known to be cyclic.

  * •

When $m=6$, the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,1)},{\mathbf{{C}}}_{(2,n,6,0)})$ has
parameters $[126,107,6]_{2}$. Notice that the best linear code known with
parameters $[126,107,6]_{2}$ in [11] is not known to be cyclic.

  * •

When $m=7$, the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,1)},{\mathbf{{C}}}_{(2,n,6,0)})$ has
parameters $[254,232,6]_{2}$. Notice that the best linear code known with
parameters $[254,232,6]_{2}$ in [11] is not known to be cyclic.

In all the five cases, the upper bound on the minimum distance of the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,1)},{\mathbf{{C}}}_{(2,n,6,0)})$ is $7$
according to [11]. Hence, in these five cases the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,1)},{\mathbf{{C}}}_{(2,n,6,0)})$ is
distance-almost-optimal.

To the best knowledge of the authors, no infinite family of binary linear
codes with the same length and dimension better than
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,1)},{\mathbf{{C}}}_{(2,n,6,0)})$ is
reported in the literature. The following theorem documents an infinite family
of repeated-root binary cyclic codes with minimum distance $8$.

######  Theorem 4.2.

Let $m\geq 5$ be an integer and $n=2^{m}-1$. Then the repeated-root binary
cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,0)},{\mathbf{{C}}}_{(2,n,8,0)})$ has
parameters $[2(2^{m}-1),2(2^{m}-1)-4m-2,8]_{2}$ and generator polynomial
$(x-1)^{2}\mathrm{m}_{\beta}(x)^{2}\mathrm{m}_{\beta^{3}}(x)\mathrm{m}_{\beta^{5}}(x)$,
where $\beta$ is a primitive element of ${\mathbf{{F}}}_{2^{m}}$.

######  Proof..

By definition, the BCH code ${\mathbf{{C}}}_{(2,n,3,0)}$ has generator
polynomial $(x-1)\mathrm{m}_{\beta}(x)$ and parameters $[n,n-m-1,4]_{2}$, as
it is the even-weight subcode of the binary Hamming cyclic code.

By definition, the BCH code ${\mathbf{{C}}}_{(2,n,8,0)}$ has generator
polynomial
$(x-1)\mathrm{m}_{\beta}(x)\mathrm{m}_{\beta^{3}}(x)\mathrm{m}_{\beta^{5}}(x)$.
It follows from the BCH bound that $d({\mathbf{{C}}}_{(2,n,8,0)})\geq 8$. It
can be easily verified that
$|C_{1}^{(2,n)}|=|C_{3}^{(2,n)}|=|C_{5}^{(2,n)}|=m$ for $m\geq 5$.
Consequently, ${\mathbf{{C}}}_{(2,n,8,0)}$ has parameters $[n,n-3m-1,d\geq
8]_{2}$ for $m\geq 5$.

Since $\mathrm{m}_{\beta^{i}}(x)$ is irreducible and has degree $m\geq 5$ for
$i\in\\{1,3,5\\}$, we deduce that
$\gcd(\mathrm{m}_{\beta}(x)(x-1),\mathrm{m}_{\beta^{3}}(x)\mathrm{m}_{\beta^{5}}(x))=1$.
By Theorem 2.1 the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,0)},{\mathbf{{C}}}_{(2,n,8,0)})$ has
generator polynomial
$(x-1)^{2}\mathrm{m}_{\beta}(x)^{2}\mathrm{m}_{\beta^{3}}(x)\mathrm{m}_{\beta^{5}}(x)$
and parameters $[2(2^{m}-1),2(2^{m}-1)-4m-2,8]_{2}$. This completes the proof.

######  Example 4.2.

The following is a list of the first four codes in the family of binary cyclic
codes ${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,0)},{\mathbf{{C}}}_{(2,n,8,0)})$.

  * •

When $m=4$, the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,0)},{\mathbf{{C}}}_{(2,n,8,0)})$ has
parameters $[30,14,8]_{2}$ and is distance-optimal according to [11]. Notice
that the best linear code known with parameters $[30,14,8]_{2}$ in [11] is not
known to be cyclic. Note that the the parameters of the code in the case $m=4$
are not given by Theorem 4.2.

  * •

When $m=5$, the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,0)},{\mathbf{{C}}}_{(2,n,8,0)})$ has
parameters $[62,40,8]_{2}$. Notice that the best linear code known with
parameters $[62,40,8]_{2}$ in [11] is not known to be cyclic.

  * •

When $m=6$, the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,0)},{\mathbf{{C}}}_{(2,n,8,0)})$ has
parameters $[126,100,8]_{2}$. Notice that the best linear code known with
parameters $[126,100,8]_{2}$ in [11] is not known to be cyclic.

  * •

When $m=7$, the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,0)},{\mathbf{{C}}}_{(2,n,8,0)})$ has
parameters $[254,224,8]_{2}$. Notice that the best linear code known with
parameters $[254,224,8]_{2}$ in [11] is not known to be cyclic.

In all the four cases, the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,0)},{\mathbf{{C}}}_{(2,n,8,0)})$ has
the same parameters as the best linear code in [11].

To the best knowledge of the authors, no infinite family of binary linear
codes with the same length and dimension better than
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,3,0)},{\mathbf{{C}}}_{(2,n,8,0)})$ is
reported in the literature.

##  5 Two infinite families of repeated-root cyclic codes over
${\mathbf{{F}}}_{q}$ with minimum distance 6 for $q\geq 4$

In this section, we construct two infinite families of repeated-root cyclic
codes over ${\mathbf{{F}}}_{q}$ with minimum distance 6 for $q\geq 4$.

######  Theorem 5.1.

Let $m\geq 2$ be an integer and $n=q^{m}-1$, where $q\geq 4$ is even. Then the
repeated-root cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,3,0)},{\mathbf{{C}}}_{(q,n,6,0)})$ has
parameters $[2(q^{m}-1),k,6]_{q}$, where

  * •

$k=2(q^{m}-1)-4m-2$ if $q=4$, and

  * •

$k=2(q^{m}-1)-5m-2$ if $q>4$,.

######  Proof..

By definition, the BCH code ${\mathbf{{C}}}_{(q,n,3,0)}$ has generator
polynomial $(x-1)\mathrm{m}_{\beta}(x)$. It was shown in the proof of Theorem
3.2 that ${\mathbf{{C}}}_{(q,n,3,0)}$ has parameters $[n,n-m-1,3]_{q}$.

It follows from the BCH bound that $d({\mathbf{{C}}}_{(q,n,6,0)})\geq 6.$ We
now determine the generator polynomial and the dimension of the code
${\mathbf{{C}}}_{(q,n,6,0)}$. When $q=4$, the generator polynomial of the code
${\mathbf{{C}}}_{(4,n,6,0)}$ is
$(x-1)\mathrm{m}_{\beta}(x)\mathrm{m}_{\beta^{2}}(x)\mathrm{m}_{\beta^{3}}(x)$.
It can be verified that

$|C_{1}^{(4,n)}|=|C_{2}^{(4,n)}|=|C_{3}^{(4,n)}|=m.$

Therefore, $\dim({\mathbf{{C}}}_{(4,n,6,0)})=n-3m-1$. When $q>4$, the
generator polynomial of the code ${\mathbf{{C}}}_{(q,n,6,0)}$ is
$(x-1)\mathrm{m}_{\beta}(x)\mathrm{m}_{\beta^{2}}(x)\mathrm{m}_{\beta^{3}}(x)\mathrm{m}_{\beta^{4}}(x)$.
It can be verified that

$|C_{1}^{(q,n)}|=|C_{2}^{(q,n)}|=|C_{3}^{(q,n)}|=|C_{4}^{(q,n)}|=m.$

Therefore, $\dim({\mathbf{{C}}}_{(q,n,6,0)})=n-4m-1$.

Since $\gcd(n,q)=1$, $x^{n}-1$ has no repeated roots in
${\mathbf{{F}}}_{q^{m}}$. We have then

$\gcd((x-1)\mathrm{m}_{\beta}(x),\mathrm{m}_{\beta^{2}}(x)\mathrm{m}_{\beta^{3}}(x))=1$

if $q=4$ and

$\gcd((x-1)\mathrm{m}_{\beta}(x),\mathrm{m}_{\beta^{2}}(x)\mathrm{m}_{\beta^{3}}(x)\mathrm{m}_{\beta^{4}}(x))=1$

if $q>4$ . The desired conclusions then follow from Theorem 2.1. This
completes the proof.

######  Example 5.1.

The following is a list of codes in the family of cyclic codes
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,3,0)},{\mathbf{{C}}}_{(q,n,6,0)})$ for
$q\geq 4$.

  * •

When $(q,m)=(4,2)$, the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,3,0)},{\mathbf{{C}}}_{(q,n,6,0)})$ had
parameters $[30,20,6]_{4}$. Notice that the best linear code known with
parameters $[30,20,6]_{4}$ in [11] is not known to be cyclic.

  * •

When $(q,m)=(4,3)$, the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,3,0)},{\mathbf{{C}}}_{(q,n,6,0)})$ had
parameters $[126,112,6]_{4}$. Notice that the best linear code known with
parameters $[126,112,6]_{4}$ in [11] is not known to be cyclic.

  * •

When $(q,m)=(8,2)$, the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,3,0)},{\mathbf{{C}}}_{(q,n,6,0)})$ had
parameters $[126,114,6]_{8}$. Notice that the best linear code known with
parameters $[126,114,7]_{8}$ in [11] is not known to be cyclic.

To the best knowledge of the authors, no infinite family of linear codes with
the same length and dimension better than
${\mathbf{{C}}}({\mathbf{{C}}}_{(q,n,3,0)},{\mathbf{{C}}}_{(q,n,6,0)})$ for
$q\geq 4$ is reported in the literature. The following theorem describes an
infinite family of repeated-root cyclic codes over ${\mathbf{{F}}}_{4}$.

######  Theorem 5.2.

Let $m\geq 2$ be an integer and $n=2^{2m-1}-1$. Then the repeated-root cyclic
code ${\mathbf{{C}}}({\mathbf{{C}}}_{(4,n,3,1)},{\mathbf{{C}}}_{(4,n,6,0)})$
has parameters $[2n,2n-6m+2,6]_{4}$.

######  Proof..

By definition, the BCH code ${\mathbf{{C}}}_{(4,n,3,1)}$ has generator
polynomial $\mathrm{m}_{\beta}(x)$. It can be verified that

$|C_{1}^{(4,n)}|=2m-1.$

Consequently,

$\dim({\mathbf{{C}}}_{(4,n,3,1)})=n-2m+1.$

It follows from the BCH bound that $d({\mathbf{{C}}}_{(4,n,3,1)})\geq 3$. It
then follows from the sphere packing bound that
$d({\mathbf{{C}}}_{(4,n,3,1)})\leq 4$. It follows from the bound of Lemma 3.1
that $d({\mathbf{{C}}}_{(4,n,3,1)})\neq 4$. Consequently,
$d({\mathbf{{C}}}_{(4,n,3,1)})=3$ and the code ${\mathbf{{C}}}_{(4,n,3,1)}$
has parameters $[n,n-2m+1,3]_{4}$.

Since $4^{2m}-2=2(2^{2m-1}-1)$, $2$ is in the $4$-cyclotomic coset
$C_{1}^{(4,n)}$. By definition, the BCH code ${\mathbf{{C}}}_{(4,n,6,0)}$ has
generator polynomial $(x-1)\mathrm{m}_{\beta}(x)\mathrm{m}_{\beta^{3}}(x)$. It
can be verified that

$|C_{3}^{(4,n)}|=2m-1.$

Consequently,

$\dim({\mathbf{{C}}}_{(4,n,6,0)})=n-4m+1$

It follows from the BCH bound that $d({\mathbf{{C}}}_{(4,n,6,0)})\geq 6.$ Note
that $\gcd(\mathrm{m}_{\beta}(x),(x-1)m_{\beta^{3}}(x))=1$. The desired
conclusions then follow from Theorem 2.1.

######  Example 5.2.

The first three codes in the family of codes
${\mathbf{{C}}}({\mathbf{{C}}}_{(4,n,3,1)},{\mathbf{{C}}}_{(4,n,6,0)})$ are
listed below.

  * •

When $m=2$, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(4,n,3,1)},{\mathbf{{C}}}_{(4,n,6,0)})$ has
parameters $[14,4,6]_{4}$. Notice that the best linear code known with
parameters $[14,4,9]_{4}$ in [11] is not known to be cyclic.

  * •

When $m=3$, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(4,n,3,1)},{\mathbf{{C}}}_{(4,n,6,0)})$ has
parameters $[62,46,6]_{4}$. Notice that the best linear code known with
parameters $[62,46,8]_{4}$ in [11] is not known to be cyclic.

  * •

When $m=4$, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(4,n,3,1)},{\mathbf{{C}}}_{(4,n,6,0)})$ has
parameters $[254,232,6]_{4}$. Notice that the best linear code known with
parameters $[254,232,8]_{4}$ in [11] is not known to be cyclic.

To the best knowledge of the authors, no infinite family of linear codes with
the same length and dimension better than
${\mathbf{{C}}}({\mathbf{{C}}}_{(4,n,3,1)},{\mathbf{{C}}}_{(4,n,6,0)})$ is
reported in the literature.

##  6 Infinite families of repeated-root binary cyclic codes with large
dimensions and large minimum distances

The following theorem describes an infinite family of repeated-root binary
cyclic codes with parameters $[2n,n,d\geq\frac{n}{\log_{2}n}]_{2}$.

######  Theorem 6.1.

Let $m\geq 3$ be a prime and $n=2^{m}-1$. Put $h=\frac{2^{m-1}-1}{m}$. Let
$\delta_{h}$ denote the $h$-th largest nonzero $2$-cyclotomic coset leader
modulo $n$. Then the repeated-root cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,\delta_{h}+2,1)},{\mathbf{{C}}}_{(2,n,\delta_{h}+2,0)})$
has parameters $[2n,n,d]_{2}$, where

$d\geq\delta_{h}+3\geq\frac{n-1+2m}{m}.$ (2)

######  Proof..

By definition, each nonzero $2$-cyclotomic coset leader modulo $n$ must be a
positive odd integer. Consequently,

$\delta_{h}\geq 2h-1=\frac{n-1}{m}-1.$

It follows from the BCH bound that

$d({\mathbf{{C}}}_{(2,n,\delta_{h}+2,1)})\geq\delta_{h}+2.$

Since $m$ is a prime, each nonzero $2$-cyclotomic coset must have cardinality
$m$. Consequently,

$\dim({\mathbf{{C}}}_{(2,n,\delta_{h}+2,1)})=2^{m-1}.$

Let $g(x)$ denote the generator polynomial of
${\mathbf{{C}}}_{(2,n,\delta_{h}+2,1)}$. By definition,
${\mathbf{{C}}}_{(2,n,\delta_{h}+2,0)}$ has generator polynomial $(x-1)g(x)$,
and is thus the even-weight subcode of
${\mathbf{{C}}}_{(2,n,\delta_{h}+2,1)}$. As a result,

$\dim({\mathbf{{C}}}_{(2,n,\delta_{h}+2,0)})=2^{m-1}-1.$

It is known that the extended code of ${\mathbf{{C}}}_{(2,n,\delta_{h}+2,1)}$
is affine-invariant. Hence, the minimum distance of
${\mathbf{{C}}}_{(2,n,\delta_{h}+2,1)}$ must be odd. Consequently,

$d({\mathbf{{C}}}_{(2,n,\delta_{h}+2,0)})\geq
d({\mathbf{{C}}}_{(2,n,\delta_{h}+2,1)})+1\geq\delta_{h}+3.$

It then follows from Theorem 2.1 that

$\displaystyle
d({\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,\delta_{h}+2,1)},{\mathbf{{C}}}_{(2,n,\delta_{h}+2,0)}))$
$\displaystyle\ \
=\min\\{2d({\mathbf{{C}}}_{(2,n,\delta_{h}+2,1)}),d({\mathbf{{C}}}_{(2,n,\delta_{h}+2,0)})\\}$
$\displaystyle\ \ \geq\delta_{h}+3$ $\displaystyle\ \ \geq\frac{n-1+2m}{m}$

and

$\dim({\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,\delta_{h}+2,1)},{\mathbf{{C}}}_{(2,n,\delta_{h}+2,0)}))=2^{m-1}+2^{m-1}-1=n.$

Furthermore, the code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,\delta_{h}+2,1)},{\mathbf{{C}}}_{(2,n,\delta_{h}+2,0)})$
has generator polynomial $(x-1)g(x)^{2}$. This completes the proof.

The code ${\mathbf{{C}}}_{(2,n,\delta_{h}+2,1)}$ was proposed and studied in
[26], where a much better lower bound on
$d(({\mathbf{{C}}}_{(2,n,\delta_{h}+2,1)})$ was developed. Specifically, the
following result on $\delta_{h}$ was proved in [26]:

  * •

When $m\in\\{,3,5\\}$, $\delta_{h}=\frac{2^{m}-2}{m}-1$.

  * •

When $m=7$, $\delta_{h}=\frac{2^{m}-2}{m}+1$.

  * •

When $m\geq 11$ is a prime, $\delta_{h}\geq\frac{2^{m}-2}{m}-1+2\Lambda$,
where

$\displaystyle\Lambda=\sum_{i=2}^{\lfloor\frac{m}{\upsilon(m)+2}\rfloor}\frac{(-1)^{i}}{i}\binom{m-i(\upsilon(m)+1)-1}{i-1}2^{m-i(\upsilon(m)+2)}+\left\lfloor\frac{2^{m-\upsilon(m)-2}-2^{\upsilon(m)}}{2^{\upsilon(m)+1}-1}\right\rfloor+1,$

and $\upsilon(m)=\lfloor\log_{2}m\rfloor$.

Using the better lower bound on $\delta_{h}$ above, the lower bound in (2) on

$d({\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,\delta_{h}+2,1)},{\mathbf{{C}}}_{(2,n,\delta_{h}+2,0)}))$

can be improved to a large extent for $m\geq 11$.

######  Example 6.1.

When $m=3$, then the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,\delta_{h}+2,1)},{\mathbf{{C}}}_{(2,n,\delta_{h}+2,0)})$
has parameters $[14,7,4]_{2}$. This code is distance-optimal according to
[11], where the linear code with the same parameters is not known to be
cyclic.

######  Example 6.2.

When $m=5$, then the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,\delta_{h}+2,1)},{\mathbf{{C}}}_{(2,n,\delta_{h}+2,0)})$
has parameters $[62,31,8]_{2}$. The best linear code with parameters
$[62,31,12]$ in [11] is not known to be cyclic.

The following theorem presents another infinite family of repeated-root binary
cyclic codes.

######  Theorem 6.2.

Let $m\geq 3$ be a prime and $n=2^{m}-1$. Put

$h_{2}=\frac{2^{m-1}-1}{m}\mbox{ and
}h_{1}=\frac{h_{2}+1}{2}=\frac{2^{m-1}-1+m}{2m}.$

Let $\delta_{h_{i}}$ denote the $h_{i}$-th largest nonzero $2$-cyclotomic
coset leader modulo $n$. Then the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,\delta_{h_{1}},1)},{\mathbf{{C}}}_{(2,n,\delta_{h_{2}}+2,1)})$
has parameters $[2n,n+2^{m-2}+(m+1)/2,d]_{2}$, where

$d\geq\frac{n-1}{m}.$ (3)

######  Proof..

By definition, each nonzero $2$-cyclotomic coset leader modulo $n$ must be a
positive odd integer. Consequently,

$\delta_{h_{2}}\geq 2h_{2}-1=\frac{n-1}{m}-1$

and

$\delta_{h_{1}}\geq 2h_{1}-1=\frac{n-1}{2m}.$

It follows from the BCH bound that

$d({\mathbf{{C}}}_{(2,n,\delta_{h_{2}}+2,1)})\geq\delta_{h_{2}}+2\geq\frac{n-1+m}{m}$

and

$d({\mathbf{{C}}}_{(2,n,\delta_{h_{1}},1)})\geq\delta_{h_{1}}\geq\frac{n-1}{2m}$

Since $m$ is a prime, each nonzero $2$-cyclotomic coset must have cardinality
$m$. Consequently,

$\dim({\mathbf{{C}}}_{(2,n,\delta_{h_{2}}+2,1)})=2^{m-1}.$

and

$\dim({\mathbf{{C}}}_{(2,n,\delta_{h_{1}},1)})=n-(h_{1}-1)m=n-\frac{2^{m-1}-1-m}{2}.$

Since $h_{1}=(h_{2}+1)/2$, ${\mathbf{{C}}}_{(2,n,\delta_{h_{2}}+2,1)}$is a
subcode of ${\mathbf{{C}}}_{(2,n,\delta_{h_{1}},1)}$. Since $\gcd(2,n)=1$,
$x^{n}-1$ has no repeated roots. It then follows from Theorem 2.1 that

$\displaystyle\dim({\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,\delta_{h_{1}},1)},{\mathbf{{C}}}_{(2,n,\delta_{h_{2}}+2,1)}))$
$\displaystyle\ \
=\dim({\mathbf{{C}}}_{(2,n,\delta_{h_{1}},1)})+\dim({\mathbf{{C}}}_{(2,n,\delta_{h_{2}}+2,1)})$
$\displaystyle\ \ =n+2^{m-2}+(m+1)/2$

and

$\displaystyle
d({\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,\delta_{h_{1}},1)},{\mathbf{{C}}}_{(2,n,\delta_{h_{2}}+2,1)}))$
$\displaystyle\ \
=\min\\{2d({\mathbf{{C}}}_{(2,n,\delta_{h_{1}},1)}),d({\mathbf{{C}}}_{(2,n,\delta_{h}+2,1)})\\}$
$\displaystyle\ \ \geq\frac{n-1}{m}.$

######  Example 6.3.

When $m=3$, then the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,\delta_{h_{1}},1)},{\mathbf{{C}}}_{(2,n,\delta_{h_{2}}+2,1)})$
has parameters $[14,11,2]_{2}$. This code is distance-optimal according to
[11], where the linear code with the same parameters is not known to be
cyclic.

######  Example 6.4.

When $m=5$, then the cyclic code
${\mathbf{{C}}}({\mathbf{{C}}}_{(2,n,\delta_{h_{1}},1)},{\mathbf{{C}}}_{(2,n,\delta_{h_{2}}+2,1)})$
has parameters $[62,42,6]_{2}$. The best linear code with parameters
$[62,42,8]$ in [11] is not known to be cyclic.

To the best knowledge of the authors, no infinite family of binary linear
codes with the same lengths and dimensions better than any of the two infinite
families of cyclic cods is reported in the literature.

##  7 Summary of contributions and concluding remarks

The contributions of this paper are summarized as follows.

  * •

An infinite family of distance-optimal repeated-root cyclic codes with
parameters $[2(q^{m}-1),2(q^{m}-1)-m-2,3]_{q}$ was constructed (see Theorem
3.2), where $m\geq 2$ and $q\geq 4$ is even.

  * •

An infinite family of distance-optimal repeated-root cyclic codes with
parameters $[2(q^{m}-1),2(q^{m}-1)-2m-2,4]_{q}$ was constructed (see Theorem
3,3), when $m\geq 2$ and $q\geq 4$ is even.

  * •

An infinite family of repeated-root cyclic codes with parameters
$[2n,2n-m-2,3\leq d\leq 4]_{q}$ was constructed (see Theorem 3.4), where
$n=(q^{m}-1)/(q-1)$, $m\geq 2$ and $q\geq 4$ is even. No infinite family of
linear codes over ${\mathbf{{F}}}_{q}$ with the same length and dimension but
better minimum distance is reported in the literature.

  * •

An infinite family of repeated-root cyclic codes with parameters
$[2n,2n-2m-2,4]_{q}$ was constructed (see Theorem 3.5), where
$n=(q^{m}-1)/(q-1)$, $m\geq 2$ and $q\geq 4$ is even. No infinite family of
linear codes over ${\mathbf{{F}}}_{q}$ with the same length and dimension but
better minimum distance is reported in the literature.

  * •

An infinite family of distance-optimal repeated-root cyclic codesover
${\mathbf{{F}}}_{4}$ with parameters
$[2(2^{2m-1}-1),2(2^{2m-1}-1)-2m-1,4]_{4}$ was constructed (see Theorem 3.7),
where $m\geq 2$.

  * •

An infinite family of repeated-root cyclic codes with parameters
$[2(2^{m}-1),2(2^{m}-1)-3m-1,6]_{2}$ was constructed (see Theorem 4.1), wher
$m\geq 3$. No infinite family of linear codes over ${\mathbf{{F}}}_{2}$ with
the same length and dimension but better minimum distance is reported in the
literature.

  * •

An infinite family of repeated-root cyclic codes with parameters
$[2(2^{m}-1),2(2^{m}-1)-4m-2,8]_{2}$ was constructed (see Theorem 4.2), wher
$m\geq 5$. No infinite family of linear codes over ${\mathbf{{F}}}_{2}$ with
the same length and dimension but better minimum distance is reported in the
literature.

  * •

An infinite family of repeated-root cyclic codes with parameters
$[2(q^{m}-1),k,6]_{q}$ was constructed (see Theorem 5.1), where $m\geq 2$ and

    * –

$k=2(q^{m}-1)-4m-2$ if $q=4$, and

    * –

$k=2(q^{m}-1)-5m-2$ if $q>4$ is even.

No infinite family of linear codes over ${\mathbf{{F}}}_{q}$ with the same
length and dimension but better minimum distance is reported in the
literature.

  * •

An infinite family of repeated-root cyclic codes over ${\mathbf{{F}}}_{4}$
with parameters $[2(2^{2m-1}-1),2(2^{2m-1}-1)-6m+2,6]_{4}$ was constructed
(see Theorem 5.2), where $m\geq 2$. No infinite family of linear codes over
${\mathbf{{F}}}_{4}$ with the same length and dimension but better minimum
distance is reported in the literature.

  * •

An infinite family of repeated-root cyclic codes with parameters
$[2(2^{m}-1),2^{m}-1,d]_{2}$ was constructed (see Theorem 6.1), where

$d\geq\frac{n-1+2m}{m}$

and $m\geq 3$ is a prime. The lower bound on the minimum distance is much
better than the square-root bound. No infinite family of linear codes over
${\mathbf{{F}}}_{2}$ with the same length and dimension but better minimum
distance is reported in the literature.

  * •

An infinite family of repeated-root cyclic codes with parameters

$[2(2^{m}-1),2^{m}-1+2^{m-2}+(m+1)/2,d\geq(2^{m}-2)/m]_{2}$

was constructed (see Theorem 6.2), where $m\geq 3$ is a prime. The lower bound
on the minimum distance is much better than the square-root bound. No infinite
family of linear codes over ${\mathbf{{F}}}_{2}$ with the same length and
dimension but better minimum distance is reported in the literature.

In summary, three infinite families of distance-optimal repeated-root cyclic
codes over ${\mathbf{{F}}}_{q}$ for even $q$ were constructed in this paper.
In addition, 27 repeated-root cyclic codes of length up to $254$ over
${\mathbf{{F}}}_{q}$ for $q\in\\{2,4,8\\}$ with optimal parameters or best
parameters known were obtained in this paper (see Table LABEL:tab:A-q-5-3).
Notice that some of the binary codes in Table LABEL:tab:A-q-5-3 may be the
same as those in [15, 28, 4].

The results of this paper demonstrate that there are infinite families of
repeated-root cyclic codes over ${\mathbf{{F}}}_{q}$ with minimum distance 3
or 4 for each even $q$. Several families of distance-optimal repeated-root
binary cyclic codes with minimum distance 4 and several families of distance-
optimal repeated-root $p$-ary cyclic codes with minimum distance 3 for odd
prime $p$ were constructed in [15]. However, it seems difficult to construct
an infinite family of distance-optimal repeated-root cyclic codes over small
finite fields with minimum distance 6 or more. This is also true for the
construction of distance-optimal linear codes over small finite fields.
Although the theory and practice of cyclic codes have been extensively
developed, repeated-root cyclic codes are less studied and understood. Further
research into repeated-root cyclic codes would be necessary and interesting.

Finally, we would point out that all the repeated-root cyclic codes
constructed in this paper are built on BCH cyclic codes. This may explain why
they are either distance-optimal or have the best parameters known compared
with other infinite families of linear codes. Further information on BCH codes
could be found in [6, 9].

Table 1:  Repeated-root cyclic codes in this paper. $q$ | Cyclic code | Optimality
---|---|---
$2$ | $[14,7,4]_{2}$ | Optimal
$2$ | $[14,11,2]_{2}$ | Optimal
$2$ | $[30,14,8]_{2}$ | Optimal
$2$ | $[30,17,6]_{2}$ | Best known
$2$ | $[30,24,4]_{2}$ | Optimal
$2$ | $[62,40,8]_{2}$ | Optimal
$2$ | $[62,46,6]_{2}$ | Best known
$2$ | $[62,55,4]_{2}$ | Optimal
$2$ | $[126,100,8]_{2}$ | Best known
$2$ | $[126,107,7]_{2}$ | Best known
$2$ | $[126,118,4]_{2}$ | Optimal
$2$ | $[254,224,8]_{2}$ | Best known
$2$ | $[254,232,6]_{2}$ | Best known
$2$ | $[254,245,4]_{2}$ | Optimal
$4$ | $[10,6,4]_{4}$ | Optimal
$4$ | $[14,9,4]_{4}$ | Optimal
$4$ | $[30,20,6]_{4}$ | Best known
$4$ | $[30,24,4]_{4}$ | Optimal
$4$ | $[42,37,3]_{4}$ | Optimal
$4$ | $[62,55,4]_{4}$ | Optimal
$4$ | $[126,112,6]_{4}$ | Best known
$4$ | $[126,118,4]_{4}$ | Optimal
$4$ | $[126,121,3]_{4}$ | Optimal
$4$ | $[170,164,3]_{4}$ | Optimal
$4$ | $[254,245,4]_{4}$ | Optimal
$8$ | $[18,14,4]_{8}$ | Optimal
$8$ | $[126,120,4]_{8}$ | Optimal
$8$ | $[126,122,3]_{8}$ | Optimal

## References

  * [1] A. Batoul, K. Guenda and Hulliver, Repeated-root isodual cyclic codes over finite fields, in: S. El Hajji et al. (Eds.): C2SI 2015, LNCS 9084, pp. 119–132, 2015.
  * [2] R. C. Bose and D. K. Ray-Chaudhuri, On a class of error-correcting binary group codes, Inf. and Contr., vol. 3, pp. 68-79, 1960.
  * [3] R. C. Bose and D. K. Ray-Chaudhuri, Further results on error-correcting binary group codes, Inf. and Contr., vol. 3, pp. 279-290, 1960.
  * [4] G. Castagnoli, J. L. Massey, P. A. Scholler and N. von Seemann, On repeated-root cyclic codes, IEEE Trans. Inf. Theory, vol. 37, no. 2, pp. 337-342, 1991.
  * [5] H. Chen and C. Ding, Self-dual cyclic codes with square-root-like lower bounds on their Minimum distances, preprint, submitted, 2023.
  * [6] C. Ding, Parameters of Several Classes of BCH Codes, IEEE Transactions on Information Theory, vol. 61, no. 10, pp. 5322-5330, 2015.
  * [7] C. Ding, Codes from Difference Sets, Singapore: World Scientific, 2015
  * [8] C. Ding and T. Helleseth, Optimal ternary cyclic codes from monomials, IEEE Trans. Inf. Theory, vol. 59, no. 9, pp. 5898-5904, 2013.
  * [9] C. Ding and C. Li, BCH cyclic codes, Discrete Mathematics, to appear.
  * [10] W. Fang, J. Wen and F. Fu, A $q$-polynomial approach to constacyclic codes, Finite Fields Appl., vol. 47, pp. 161–182, 2017.
  * [11] M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, Online available at http://www.codetables.de.
  * [12] C. R. P. Hartmann and K. K. Tzeng, Generalizations of the BCH bound, Infomation and Control, vol. 20, pp.489-498, 1972.
  * [13] Z. Heng, C. Ding and W. Wang, Optimal binary linear codes from maximal arcs, IEEE Trans. Inf. Theory, vol. 66, no. 9, pp. 5387-5394, 2020.
  * [14] A. Hocquenghem, Codes correcteurs d’erreurs, Chiffres (Paris), vol. 2, pp. 147-156, 1959.
  * [15] S. Huang, Z. Sun and S. Zhu, On the construction of several classes of optimal repeated-root cyclic codes, ACTA ELECTRONICA SINICA, vol. 50, no. 1, pp. 142–148, 2022.
  * [16] W. C. Huffman and V. Pless, Fundamentals of error-correcting codes, Cambridge University Press, Cambridge, U. K., 2003.
  * [17] X. Li and Q. Yue, The Hamming distances of repeated-root cyclic codes of length $5p^{s}$, Discrete Applied Mathematics, vol. 284, pp. 29–41, 2020.
  * [18] F. J. MacWilliams and N. J. A. Sloane, The Theory of error-correcting codes, 3rd Edition, North-Holland Mathematical Library, vol. 16. North-Holland, Amsterdam, 1977.
  * [19] C. Li, C. Ding and S. Li, LCD cyclic codes over finite fields, IEEE Trans. Inf. Theory, vol. 63, no. 7, pp. 4344-4356, 2017.
  * [20] C. Martinez-Perez and W. Willems, Self-dual doubly even $2$-quasi-cyclic transitive codes are asymptotically good, IEEE Trans. Inf. Theory, vol. 53, no. 11, pp. 4302-4307, 2007.
  * [21] B. Pang, S. Zhu and J. Li, On LCD repeated-root cyclic codes over finite fields, J. Appl. Math. Comput., vol. 56, pp. 625–635, 2018.
  * [22] M. Plotkin, Binary codes with specified minimum distance, IRE Trans., vol. IT-6, pp. 445–450, 1960.
  * [23] E. Prange, Cyclic error-correcting codes in two symbols, TN-57-013, Technical notes issued by Air Force Cambridge Research Labs, 1957.
  * [24] C. Roos, A new lower bound for the minimum distance of a cyclic codes, IEEE Trans. Inf. Theory, vol. 29, no. 2, pp. 330-332, 1983.
  * [25] R. Sobhani, Matrix-product structure of repeated-root cyclic codes over finite fields, Finite Fields and Their Applications, vol. 39, pp. 216–232, 2016.
  * [26] Z. Sun, C. Li and C. Ding, An infinite family of binary cyclic codes with best parameters, IEEE Trans. Inf. Theory, DOI: 10.1109/TIT.2023.3307732.
  * [27] C. Tang and C. Ding, Binary $[n,\frac{n+1}{2}]$ cyclic codes with good minimum distances, IEEE Trans. Inf. Theory, vol. 68, no. 12, pp. 7842-7849, 2022.
  * [28] J. H. van Lint, Repeated-root cyclic codes, IEEE Trans. Inf. Theory, vol. 37, no. 2, pp. 343-345, 1991.
  * [29] J. H. van Lint, Introduction to coding theory, Springer, 3rd Edition, Berlin, Hong Kong and Tokyo, 1999.
  * [30] X. Wang, D. Zheng and C. Ding, Some punctured codes of several families of binary linear codes, IEEE Trans. Inf. Theory, vol. 67, no. 8, pp. 5133-5148, 2021.
  * [31] A. Zeh and M. Ulmschneider , Decoding of repeated-root cyclic codes up to new bounds on their minimum distance, Probl. Inf. Transm. vol. 51, no. 3, pp. 217–230, 2015 (arXiv:1506.02820 [cs.IT]).