Linear Codes over Finite Fields Based on Greedy Algorithms

and Their Applications

Rama Asad Nadweh1,*

1 Online Islamic University, Department of Science and Information Technology, Doha, Qatar

Received: June 11, 2023 Revised: September 24, 2023 Accepted: December 17, 2023 ⋆ Corresponding author

ABSTRACT

In this paper, we prove that for any ordered basis B1 of a vector space, there is a basis B2 for which the greedy code

generated using the B-ordering is linear with respect to B2, where B2 is derived from B1 by a lower triangular matrix

P, namely B2 = PB1. In addition, we prove a similar result for self-orthogonal greedy codes.

Keywords: Greedy algorithm Finite field Linear codes Coding theory

1. INTRODUCTION

A word is a sequence of digits, and its length is the number

of digits in the sequence. Let A = {a1, . . . ,aq} be a finite

set called the alphabet, and let A n be the set of all strings of

length n over A . Any nonempty subset C ⊆ A n is called a

q-ary block code, and each string in C is called a codeword.

If C contains M codewords, then C has length n and size M,

or is an (n,M)-code. A code over the alphabet A = {0,1} is

called a binary code.

Let F be a field, let n be a positive integer, and let u =

(x1,x2, . . . ,xn). The Hamming weight is

wh(u) = |{i ∈ {1,2, . . . ,n} : xi ̸= 0}| , (1)

that is, the number of nonzero coordinates of u. For two

words x and y of the same length, the Hamming distance

dh(x,y) is the number of coordinates in which they differ. A

code C has minimum distance

d(C) = min{dh(x,y) : x,y ∈ C, x ̸= y}. (2)

1.1.1 Lexicographic Ordering

If a list is arranged in its natural order, the codes obtained

from it are called lexicodes. For binary words, the natural

order uses 0 < 1. Thus,

(c1,c2, . . . , cn) < (b1,b2, . . . ,bn)

if there is a nonnegative integer k such that ci = bi for 1 ≤

i ≤ k and ck+1 = 0, while bk+1 = 1. For example, (1,0,1) <

(1,1,0). Lexicodes are linear codes [2].

1.1.2 B-Orderings

Let V be a finite-dimensional vector space over a finite

field F = {λ0,λ1, . . . ,λq−1}, where λ0 = 0, and let B =

{b1,b2, . . . ,bn} be an ordered basis. A B-ordering is generated

recursively. The first q vectors are

0, λ1b1, λ2b1, . . . ,λq−1b1.

If qk vectors have been generated using b1,b2, . . . ,bk, the

next (q−1)qk vectors are generated by adding λibk+1 to

the vectors already produced, in their existing order, for i =

1,2, . . . ,q−1.

Let d ≥ 1. The greedy code is the set C selected by the