Mathematical Problems of Computer Science 51, 7--20, 2019. 

 
 

UDC 519.712.6 
 

Complexity of Error-Correcting Code Based on Nearest 
Neighbor Search Algorithm1  

 
 

Levon H. Aslanyan and Hayk E. Danoyan 
 

Institute for Informatics and Automation Problems of NAS RA 
e-mail: lasl@sci.am, hed@ipia.sci.am 

 
 

Abstract 
 

 
The Nearest Neighbor search algorithm considered in this paper is well 

known (Elias algorithm). It uses error-correcting codes and constructs 
appropriate hash-coding schemas. These schemas preprocess the data in the 
form of lists. Each list is contained in some sphere, centered at a code-word. 
The algorithm is considered for the cases of perfect codes, so the spheres and, 
consequently, the lists do not intersect. As such codes exist for the limited set 
of parameters, the algorithm is considered for some other generalizations of 
perfect codes, and then the same data point may be contained in different lists. 
A formula of time complexity of the algorithm is obtained for these cases, 
using coset weight structures of the mentioned codes.     

Keywords: NN search, Best match, Hash-coding schema, Perfect Codes, 
Uniformly Packed codes, Quasi-perfect codes. 

 
 
 
 

1.  Introduction 
 
Let 𝐸𝐸 = {0,1}. Consider Cartesian degree 𝐸𝐸𝑛𝑛, which is known as the set of vertexes of n-
dimensional unit cube. For any 𝑥𝑥, 𝑦𝑦 ∈ 𝐸𝐸𝑛𝑛 denote by 𝑑𝑑(𝑥𝑥, 𝑦𝑦) the Hamming distance between 
vectors x and y. For an arbitrary 𝑥𝑥 ∈ 𝐸𝐸𝑛𝑛 denote by 𝑆𝑆𝑟𝑟𝑛𝑛(𝑥𝑥) the sphere of radius r, centred at x, i.e., 
𝑆𝑆𝑟𝑟𝑛𝑛(𝑥𝑥) = {𝑦𝑦 𝑦𝑦 ∈ 𝐸𝐸𝑛𝑛, 𝑑𝑑(𝑥𝑥, 𝑦𝑦) ≤ 𝑟𝑟⁄ } and by 𝑂𝑂𝑟𝑟𝑛𝑛(𝑥𝑥) denote the shell of radius r, centred at x, i.e., 
𝑂𝑂𝑟𝑟𝑛𝑛(𝑥𝑥) = {𝑦𝑦 𝑦𝑦 ∈ 𝐸𝐸𝑛𝑛, 𝑑𝑑(𝑥𝑥, 𝑦𝑦) = 𝑟𝑟⁄ }. We will denote by 𝑐𝑐𝑐𝑐𝑟𝑟(𝑥𝑥) the carrier of vector 𝑥𝑥 =

1 Partially supported by grants № 18RF-144, and № 18T-1B407 of the Science Committee of the Ministry of Education and 
Science of Armenia 

 
7 
 

                                                 



Complexity of Error-Correcting Code Based on Nearest Neighbor Search Algorithm 8 

(𝑥𝑥1, … , 𝑥𝑥𝑛𝑛) then 𝑐𝑐𝑐𝑐𝑟𝑟(𝑥𝑥) = {𝑖𝑖 𝑥𝑥𝑖𝑖 = 1, 𝑖𝑖 = 1, … , 𝑛𝑛⁄ }. Denote by 𝑤𝑤(𝑥𝑥) the weight of vector 𝑥𝑥, i.e., 
𝑤𝑤(𝑥𝑥) = ∑ 𝑥𝑥𝑖𝑖

𝑛𝑛
𝑖𝑖=1 .    

Let us have a subset 𝐹𝐹 ⊆ 𝐸𝐸𝑛𝑛 and a  vector 𝑥𝑥 ∈ 𝐸𝐸𝑛𝑛. Let us consider the problem of finding 
the set of nearest neighbors of 𝑥𝑥 from 𝐹𝐹. More precisely it is required to find the set 𝐹𝐹𝑥𝑥 =
{𝑦𝑦 ∈ 𝐹𝐹 𝑑𝑑(𝑥𝑥, 𝑦𝑦) = 𝑑𝑑(𝑥𝑥, 𝐹𝐹)}⁄ . Hash coding schemaes are considered [1,2] for preprocessing the 
data. A brief description of such schemes is brought below.    

Hash function is defined as a function ℎ: 𝐸𝐸𝑛𝑛 → 𝑉𝑉, where 𝑉𝑉 = {𝑣𝑣1, … , 𝑣𝑣𝑁𝑁} is a finite set of 
𝑁𝑁 elements [1]. Cases are usually considered, when 𝑉𝑉 = 𝐸𝐸𝑘𝑘, 𝑘𝑘 ≤ 𝑛𝑛. The subset F is represented 
as a union of 𝑁𝑁 disjoint sets (lists). Denote by 𝐵𝐵𝑖𝑖 the set {𝑥𝑥 ∈ 𝐸𝐸𝑛𝑛 ℎ(𝑥𝑥) = 𝑣𝑣𝑖𝑖⁄ }. The 𝑖𝑖-th list 𝐿𝐿𝑖𝑖 
stores those vectors belonging to 𝐹𝐹, which have the same hash value, i.e., 𝐿𝐿𝑖𝑖 =
{𝑥𝑥 ∈ 𝐹𝐹 ℎ(𝑥𝑥) = 𝑣𝑣𝑖𝑖⁄ } or 𝐿𝐿𝑖𝑖 = 𝐵𝐵𝑖𝑖⋂𝐹𝐹, 𝑖𝑖 = 1, … , 𝑁𝑁. Hash coding schemae is called balanced if 
|𝐵𝐵𝑖𝑖| = 2𝑛𝑛 𝑁𝑁⁄ . 

The Elias algorithm [2] considers blocks 𝐵𝐵𝑖𝑖 ordering them by their distances at vector 𝑥𝑥. 
Mention that we must have an efficient method to find all blocks 𝐵𝐵𝑗𝑗1, 𝐵𝐵𝑗𝑗2, … , 𝐵𝐵𝑗𝑗𝑠𝑠(𝑗𝑗)  located at 
distance 𝑗𝑗 from 𝑥𝑥 if such blocks exist. After the step of ordering, the algorithm examines the lists 
𝐿𝐿𝑗𝑗1, 𝐿𝐿𝑗𝑗2, … , 𝐿𝐿𝑗𝑗𝑠𝑠(𝑗𝑗)  one after another by increasing 𝑗𝑗𝑡𝑡. Let the best match distance be denoted by 𝛿𝛿 
(also the current value of the best match distance in the algorithm). Due to 𝐹𝐹 ≠ ∅ initialization of 
𝛿𝛿 will happen in some step. Now, if the current values obey 𝛿𝛿 < 𝑗𝑗 algorithm stopes the work. All 
blocks with higher distances than 𝛿𝛿 at 𝑥𝑥 do not need to be examined. In the reminder case 𝛿𝛿 ≥ 𝑗𝑗, 
examining the nonempty list 𝐿𝐿𝑗𝑗𝑡𝑡 the algorithm can change the best match distance 𝛿𝛿, also 
refreshing the current best match set,  or the 𝛿𝛿 will remain unchanged and the current best match 
set will be updated. The pseudocode of the algorithm is brought below: 

Elias Algorithm   // 𝑛𝑛 is the word length, 𝑁𝑁 is the number of blocks 
input 𝑥𝑥, 𝐹𝐹,   // 𝐹𝐹 ≠ ∅ 
integer 𝛿𝛿 = ∞,   // the current best match distance 
set 𝑆𝑆 = ∅,   // 𝑆𝑆-is the current set of vectors of 𝐹𝐹 located at distance 𝛿𝛿 from 𝑥𝑥 
integer 𝑗𝑗 = −1, // current distance of blocks under consideration from 𝑥𝑥 
while(𝑗𝑗 < 𝛿𝛿) 
         { 
            j++,   
            if(𝑠𝑠(𝑗𝑗) ≠ 0)  // 𝑠𝑠(𝑗𝑗) is the number of blocks located at distance 𝑗𝑗 from 𝑥𝑥  
               for(integer i=0, i<s(j), i++) 
                   { 
                      if(𝐿𝐿𝑗𝑗𝑖𝑖 ≠ ∅)   // start examine the list L𝑗𝑗𝑖𝑖, i-th list with j distanse block  
                      if(𝛿𝛿 ≤ 𝑑𝑑(𝑥𝑥, 𝐿𝐿𝑗𝑗𝑖𝑖)   // δ is  unchanged    
                      𝑆𝑆 = 𝑆𝑆 ∪ �𝑂𝑂𝛿𝛿

𝑛𝑛(𝑥𝑥) ∩ 𝐿𝐿𝑗𝑗𝑖𝑖�  // 𝑂𝑂𝛿𝛿
𝑛𝑛(𝑥𝑥) is the 𝛿𝛿 neighborhood of 𝑥𝑥 

                      else  
                            { 
                               𝑆𝑆 = 𝑂𝑂𝛿𝛿

𝑛𝑛(𝑥𝑥) ∩ 𝐿𝐿𝑗𝑗𝑖𝑖,   // δ is changed  
                               𝛿𝛿 = 𝑑𝑑(𝑥𝑥, 𝐿𝐿𝑗𝑗𝑖𝑖) 
                            }   
                    } 
         } 
return 𝑆𝑆,   // 𝑆𝑆 =  𝐹𝐹𝑥𝑥,  𝛿𝛿 = 𝑑𝑑(𝑥𝑥, 𝐹𝐹) 

 
Fig.  1:  Pseudocode of Elias Algorithm. 



L. Aslanyan and H. Danoyan  
 

9 

By the complexity of the algorithm we mean the average number of examined lists over all 
files and queries, supposing that  
a) each vector 𝑥𝑥 ∈ 𝐸𝐸𝑛𝑛  equally likely can be requested. 
b) each vector 𝑧𝑧 ∈ 𝐸𝐸𝑛𝑛 independently appears in 𝐹𝐹 with the same probability 𝑝𝑝. This gives 
probabilistic distribution over the set of subsets of 𝐸𝐸𝑛𝑛.  

It is known [2, 3] that the algorithm is optimal, when the blocks are isoperimetric sets, a 
particular case of which is a sphere. 
 
 
2. Coset Weight Distribution of Uniformly Packed  Codes 
 
A nonempty subset C of 𝐸𝐸𝑛𝑛 we call a code [4]. The code 𝐶𝐶 will be called linear if 𝐶𝐶 is a linear 
subspase of 𝐸𝐸𝑛𝑛. Denote by 𝑑𝑑𝐶𝐶 the minimum distance of code 𝐶𝐶 i.e. 𝑑𝑑𝐶𝐶 = 𝑚𝑚𝑖𝑖𝑛𝑛𝑐𝑐1,𝑐𝑐2∈𝐶𝐶

𝑐𝑐1≠𝑐𝑐2

𝑑𝑑(𝑐𝑐1, 𝑐𝑐2). The 

packing radius [4] of 𝐶𝐶 is called the following nonnegative integer: 𝑟𝑟𝐶𝐶 = [(𝑑𝑑𝐶𝐶 − 1) 2⁄ ]. Denote 
by 𝑅𝑅𝐶𝐶 the covering radius of the code 𝐶𝐶, i.e., 𝑅𝑅𝐶𝐶 = 𝑚𝑚𝑐𝑐𝑥𝑥𝑥𝑥∈𝐸𝐸𝑛𝑛

𝑚𝑚𝑖𝑖𝑛𝑛
𝑐𝑐∈𝐶𝐶

𝑑𝑑(𝑥𝑥, 𝑐𝑐). In the sequel, when it 
doesn’t cause a confusion, we use notations 𝑑𝑑, 𝑟𝑟 and 𝑅𝑅 instead of 𝑑𝑑𝐶𝐶, 𝑟𝑟𝐶𝐶 and 𝑅𝑅𝐶𝐶, respectively. We 
say that we have a code 𝐶𝐶[𝑛𝑛, 𝑘𝑘, 𝑑𝑑]𝑅𝑅 if the code 𝐶𝐶 is linear, have dimension 𝑘𝑘, codes length n, 
minimum distance d and covering radius 𝑅𝑅. When the code is nonlinear (or it is not known 
whether the code is linear or not), we use the notation 𝐶𝐶(𝑛𝑛, 𝑀𝑀, 𝑑𝑑)𝑅𝑅 instead, where 𝑀𝑀 = |𝐶𝐶|. We 
also use this for linear codes as the second alternative notation. Recall that the code 𝐶𝐶 is called 
perfect [4], if 𝑟𝑟 = 𝑅𝑅. It is known [4, 5] that in binary space nontrivial perfect codes can have 
only the following two parameter sets:  
(I) (2𝑚𝑚 − 1, 22

𝑚𝑚−𝑚𝑚−1, 3)1,  
(II) [23,11,7]3. 
Here (I) corresponds to the parameters of Hemming codes and (II) refers to the case of Golay 
code. 

For 𝑥𝑥 ∈ 𝐸𝐸𝑛𝑛 the coset of linear code 𝐶𝐶 is called  the set 𝑥𝑥 + 𝐶𝐶 = {𝑥𝑥 + 𝑐𝑐 𝑐𝑐 ∈ 𝐶𝐶⁄ }. As it is 
known [4], two different cosets do not intersect, and their union covers the  space 𝐸𝐸𝑛𝑛. We denote 
by 𝐺𝐺𝐶𝐶 the generator matrix of the linear code 𝐶𝐶[𝑛𝑛, 𝑘𝑘], which rows forming a basis of code 𝐶𝐶. Let 
us denote by  𝐻𝐻𝐶𝐶 the parity check matrix of linear code 𝐶𝐶. Recall that 𝐻𝐻𝐶𝐶 is (𝑛𝑛 − 𝑘𝑘) × 𝑘𝑘 matrix 
and for 𝐻𝐻𝐶𝐶 holds the relation 𝑐𝑐 ∈ 𝐶𝐶 ⟺ 𝐻𝐻𝐶𝐶𝑐𝑐𝑇𝑇 = 0. Later, when it is clear which code we mean, 
we will use notations 𝐻𝐻 and 𝐺𝐺 instead of 𝐻𝐻𝐶𝐶 and 𝐺𝐺𝐶𝐶, respectively. For 𝑥𝑥 ∈ 𝐸𝐸𝑛𝑛 denote by 𝐴𝐴𝑖𝑖(𝑥𝑥) 
the number of codewords of C located at distance 𝑖𝑖 from 𝑥𝑥. The nonnegative integers 
𝐴𝐴0
𝐶𝐶, 𝐴𝐴1

𝐶𝐶, … , 𝐴𝐴𝑛𝑛𝐶𝐶, where 𝐴𝐴𝑖𝑖
𝐶𝐶 = |{𝑐𝑐 ∈ 𝐶𝐶 𝑤𝑤(𝑐𝑐) = 𝑖𝑖⁄ }| are called weight spectra of code 𝐶𝐶. Let us 

denote by 𝑊𝑊𝐶𝐶(𝑥𝑥, 𝑦𝑦) the weight enumerator of code 𝐶𝐶:  𝑊𝑊𝐶𝐶(𝑥𝑥, 𝑦𝑦) = ∑ 𝐴𝐴𝑖𝑖
𝐶𝐶𝑥𝑥𝑛𝑛−𝑖𝑖𝑦𝑦𝑖𝑖𝑛𝑛𝑖𝑖=0 . We can 

consider weight enumerators depending only on one variable, i.e., 𝑊𝑊𝐶𝐶(𝑥𝑥) = ∑ 𝐴𝐴𝑖𝑖
𝐶𝐶𝑥𝑥𝑖𝑖𝑛𝑛𝑖𝑖=0 . Denote 

by 𝐾𝐾𝑗𝑗
𝑛𝑛(𝑖𝑖) the Kravchouk polynomial of degree 𝑗𝑗 [4] i. e. 𝐾𝐾𝑗𝑗

𝑛𝑛(𝑖𝑖) = ∑ (−1)𝑗𝑗𝑗𝑗𝑙𝑙=0 �
𝑛𝑛 − 𝑖𝑖
𝑗𝑗 − 𝑙𝑙��

𝑖𝑖
𝑙𝑙
�.  

A code C will be called quasi-perfect if 𝑅𝑅 = 𝑟𝑟 + 1 [4], [6]. Many families of quasi perfect 
codes are known for the covering radius ≤ 4 [6], [9-13] but the general problem of existence of 
quasi-perfect codes by the given parameters isn’t completely solved yet [6]. A particular class of 
quasi-perfect codes is the class of uniformly packed codes. A code 𝐶𝐶 will be called uniformly 
packed [8] if there are numbers 𝑐𝑐1, … , 𝑐𝑐𝑅𝑅(𝐶𝐶) such that for 𝑥𝑥 ∈ 𝐸𝐸𝑛𝑛 takes place ∑ 𝛼𝛼𝑖𝑖𝐴𝐴𝑖𝑖(𝑥𝑥) = 1

𝑅𝑅(𝐶𝐶)
𝑖𝑖=0 . 

Theorem 1: Let 𝐶𝐶 be a uniformly packed code with parameters 𝑐𝑐0𝑐𝑐1, … , 𝑐𝑐𝑅𝑅. Then the 
polynomial   𝐿𝐿𝐶𝐶(𝑥𝑥) = ∑ 𝛼𝛼𝑖𝑖𝐾𝐾𝑖𝑖

𝑛𝑛(𝑥𝑥)𝑅𝑅𝑖𝑖=0  has 𝑅𝑅 distinct integer roots between 0 and 𝑛𝑛.   



Complexity of Error-Correcting Code Based on Nearest Neighbor Search Algorithm 10 

Let us denote those roots by 𝜉𝜉1, … , 𝜉𝜉𝑅𝑅. Mention that if 𝐶𝐶 is a uniformly packed code 
containing zero vector then there exists a uniformly packed code with the same parameters and 
minimum weight 𝛽𝛽, where 0 ≤ 𝛽𝛽 ≤ 𝑅𝑅, which we will denote by 𝐶𝐶𝛽𝛽.    
From Theorem 1 and its proof [8] follows: 

Theorem 2: [8]. For the weight function of the uniformly packed code 𝐶𝐶𝛽𝛽 the following equality 
takes place:  

𝑊𝑊𝐶𝐶𝛽𝛽(𝑥𝑥) =
(1+𝑥𝑥)𝑛𝑛

𝐿𝐿(0)
+ ∑ 𝐵𝐵𝜉𝜉𝑖𝑖

𝛽𝛽(1 + 𝑥𝑥)𝑛𝑛−𝜉𝜉𝑖𝑖(1 − 𝑥𝑥)𝜉𝜉𝑖𝑖𝑅𝑅𝑖𝑖=1 . 
(1) 

 

In (1) 𝐵𝐵𝜉𝜉𝑖𝑖
𝛽𝛽-s are coefficients of the representation of polynomial  𝑊𝑊𝐶𝐶𝛽𝛽(𝑥𝑥) in basis (1 + 𝑥𝑥)

𝑛𝑛−𝑖𝑖(1 −
𝑥𝑥)𝑖𝑖, 𝑖𝑖 = 0, . . . , 𝑛𝑛 (recall that the set of polynomials of degree ≤ 𝑛𝑛 forms a linear space of 
dimension 𝑛𝑛 + 1). 𝐵𝐵𝜉𝜉𝑖𝑖

𝛽𝛽-s can be calculated from (1) by equalizing the corresponding coefficients 
in left and right sides and assuming that we know the first 𝑅𝑅 coefficients of 𝑊𝑊𝐶𝐶𝛽𝛽(𝑥𝑥). So, to find 
the coefficients 𝐵𝐵𝜉𝜉𝑖𝑖

𝛽𝛽, we must solve the corresponding linear system of 𝑅𝑅 equations with 𝑅𝑅 
variables.  

From Theorem 2 follows:    
  

𝐴𝐴𝑗𝑗
𝐶𝐶𝛽𝛽 =

�
𝑛𝑛
𝑗𝑗�

∑ 𝑎𝑎𝑖𝑖
𝑅𝑅
𝑖𝑖=0 �

𝑛𝑛
𝑖𝑖�

+ ∑ �𝐵𝐵𝜉𝜉𝑖𝑖
𝛽𝛽𝐾𝐾𝑗𝑗

𝑛𝑛(𝜉𝜉𝑖𝑖)�𝑅𝑅𝑖𝑖=1 . 
 
 

(2) 

 
 
 

3. Hamming Code, Extended Hamming Code, Golay Code and Two Error-
Correcting Primitive BCH Codes  
 
Denote by ℋ𝑚𝑚 the Hamming code of length 2𝑚𝑚 − 1. As we know [4], ℋ is [2𝑚𝑚 − 1, 2𝑚𝑚 − 𝑚𝑚 −
1,3]1 perfect code. The parity check matrix of ℋ is as follows: 
    

𝐻𝐻ℋ = �
0 0 ⋯ 1
⋮ ⋮ ⋯ ⋮

0 1 ⋱ 1
1 0 ⋯ 1

�, 
 
 

 
i.e.,  columns of 𝐻𝐻ℋ are all nonzero vectors of length 𝑚𝑚. As it is known [4], perfect codes have 
𝑅𝑅 + 1 different types of coset, i.e., all cosets with the same minimum weight have the same 
weight distribution.  

Now let 𝐻𝐻11 be the binary Hadamard matrix  of Paley type [4], i.e.,    
 



L. Aslanyan and H. Danoyan  
 

11 

𝐻𝐻11 =

⎝

⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎛

1 1 0 1 1 1 0 0 0 1 0
0 1 1 0 1 1 1 0 0 0 1
1 0 1 1 0 1 1 1 0 0 0
0 1 0 1 1 0 1 1 1 0 0
0 0 1 0 1 1 0 1 1 1 0
0 0 0 1 0 1 1 0 1 1 1
1 0 0 0 1 0 1 1 0 1 1
1 1 0 0 0 1 0 1 1 0 1
1 1 1 0 0 0 1 0 1 1 0
0 1 1 1 0 0 0 1 0 1 1
1 0 1 1 1 0 0 0 1 0 1⎠

⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎞

. 

 
Let 𝐼𝐼11 be the identity matrix of size 11 × 11. The generator matrix of extended Golay code 

[4] is as follows:  
 

𝐺𝐺��̂�𝒢� = �111
𝑇𝑇

0
𝐼𝐼11
011

011𝑇𝑇
1

𝐻𝐻11
111

�, 
 
where by 0𝑚𝑚 and 1𝑚𝑚 are defined the vectors of length 𝑚𝑚 consisting of all 0’s and 1’s, 
respectively.   

The Golay code 𝒢𝒢 is obtained by deleting the last coordinate from every codeword of 𝒢𝒢. As 
it is known, [4]  𝒢𝒢 is a perfect three error correcting [23,12,7]3 code, therefore we can consider 
it as a uniformly packed code with parameters  𝑐𝑐0 = 𝑐𝑐1 = 𝑐𝑐2 = 𝑐𝑐3 = 1. Roots of 𝐿𝐿𝒢𝒢(𝑥𝑥) are 𝜉𝜉1 =
8, 𝜉𝜉2 = 12 and  𝜉𝜉3 = 16.       

The extended Hamming code ℋ�𝑚𝑚 is a [2𝑚𝑚, 2𝑚𝑚 − 𝑚𝑚 − 1,4]2 code [4], which is obtained 
from Hamming code by adding the parity check bit, i.e., the parity check matrix of extended 
Hamming code is as follows:  

Hℋ�𝑚𝑚 = �

1    ⋯      1
                1
      Hℋ    ⋮
                1

�. 

 
As it is known, the extended Hamming code is a uniformly packed code [6] and has four 

types of coset weight distribution. 
Let us denote a finite field of 𝑞𝑞 elements (where 𝑞𝑞 is a power of a prime number) by 𝐹𝐹𝑞𝑞. We 

will consider finite fields with characteristic 2. Denote by 𝛼𝛼 the primitive element of the field 
𝐹𝐹𝑞𝑞.Consider the set of formal polynomials 𝐹𝐹𝑞𝑞[𝑥𝑥] with coefficients from the field 𝐹𝐹𝑞𝑞. As it is 
known [4], the factor ring 𝑅𝑅[𝑥𝑥] = 𝐹𝐹𝑞𝑞[𝑥𝑥]/(𝑥𝑥𝑛𝑛 − 1) is a ring of principal ideals, i.e., each ideal in 
𝑅𝑅[𝑥𝑥] is principal. An [𝑛𝑛, 𝑘𝑘] code 𝐶𝐶 will be called a cyclic code if  𝐶𝐶 is linear, and if from 𝑐𝑐 =
(𝑐𝑐1, 𝑐𝑐2, … , 𝑐𝑐𝑛𝑛) ∈ 𝐶𝐶, it follows that (𝑐𝑐𝑛𝑛, 𝑐𝑐1, … , 𝑐𝑐𝑛𝑛−1) ∈ 𝐶𝐶. We can correspond the polynomial 𝑐𝑐1 +
𝑐𝑐2𝑥𝑥 + ⋯ + 𝑐𝑐𝑛𝑛𝑥𝑥𝑛𝑛−1 to each vector (𝑐𝑐1, 𝑐𝑐2, … , 𝑐𝑐𝑛𝑛), so we can consider a code as the subset of  
𝑅𝑅[𝑥𝑥]. It is known [4], that each cyclic code is an ideal of 𝑅𝑅[𝑥𝑥], i.e., there is a unique polynomial 
𝑔𝑔(𝑥𝑥) such that ∀𝑐𝑐(𝑥𝑥) ∈ 𝐶𝐶 ∃𝑓𝑓(𝑥𝑥) 𝑐𝑐(𝑥𝑥) = 𝑓𝑓(𝑥𝑥)𝑔𝑔(𝑥𝑥), where multiplication is taken in 𝑅𝑅[𝑥𝑥]. 

Two error correcting BCH codes (denoted by 𝔅𝔅𝑚𝑚) are defined as cyclic codes for lengths 
𝑛𝑛 = 2𝑚𝑚 − 1 [4,5] with a generator polynomial: 
  

𝑔𝑔(𝑥𝑥) = 𝐿𝐿𝐶𝐶𝑀𝑀{𝑀𝑀𝛼𝛼(𝑥𝑥), 𝑀𝑀𝛼𝛼3(𝑥𝑥)}, 
 



Complexity of Error-Correcting Code Based on Nearest Neighbor Search Algorithm 12 

where  by 𝑀𝑀𝛼𝛼𝑖𝑖(𝑥𝑥) is denoted the minimal polynomial of the element 𝛼𝛼
𝑖𝑖. These codes have the 

dimension 2𝑚𝑚 − 2𝑚𝑚 − 1 and minimum distance equal to 5 [4].  It is known that two error 
correcting BCH codes are quasi-perfect codes [4,13,14]. The weight distribution of BCH codes 
was calculated in [4, 13,14]. For odd 𝑚𝑚 two error correcting BCH codes are also uniformly 

packed [8] with parameters 𝑐𝑐0 = 𝑐𝑐1 = 1, 𝑐𝑐2 = 𝑐𝑐3 =
6

𝑛𝑛−1
. Roots of 𝐿𝐿𝔅𝔅(𝑥𝑥) are 𝜉𝜉1 =

𝑛𝑛+1
2
− �𝑛𝑛+1

2
, 

𝜉𝜉2 =
𝑛𝑛+1
2

 and 𝜉𝜉3 =
𝑛𝑛+1
2

+ �𝑛𝑛+1
2

. It is known, that there are four distinct coset weight 

distributions.  
For even 𝑚𝑚 two error correcting BCH codes are not uniformly packed. It is proved that there 

are eight distinct coset weight distributions in this case, which are brought in [14].     
 
 
 

4. Complexity of the Algorithm  

Suppose we have an [𝑛𝑛, 𝑘𝑘] code C with covering radius R and 𝐶𝐶 = �𝑐𝑐1, 𝑐𝑐2, … , 𝑐𝑐2𝑘𝑘�. We define a 
hash function ℎ: 𝐸𝐸𝑛𝑛 ⟶ 𝐶𝐶, associated to the code 𝐶𝐶 in the following way: 
 

ℎ𝐶𝐶(𝑥𝑥) = �𝑐𝑐𝑖𝑖/𝑑𝑑(𝑥𝑥, 𝑐𝑐𝑖𝑖) = 𝑚𝑚𝑖𝑖𝑛𝑛𝑐𝑐∈𝐶𝐶
{𝑑𝑑(𝑥𝑥, 𝑐𝑐)}�. (3) 

 

As it follows from (3),  ℎ𝐶𝐶(𝑥𝑥) could be a multivalued function because the blocks 𝐵𝐵𝑖𝑖 are spheres 
of radius 𝑅𝑅, and they can intersect (recall that 𝐵𝐵𝑖𝑖 = {𝑥𝑥 ∈ 𝐸𝐸𝑛𝑛 ℎ𝐶𝐶(𝑥𝑥) = 𝑐𝑐𝑖𝑖⁄ }, 𝑖𝑖 ∈ {1, … , 2𝑘𝑘}). When 
the code 𝐶𝐶 is perfect, the mentioned blocks do not intersect, and their union covers the unit cube. 
The formula below for complexity of algorithm is brought for the case corresponding to 
Hamming code. We also consider hash functions associated to codes in some sense “near” the 
perfect codes. Such property also has the so called quasi-perfect codes. Indeed, the algorithm is 
proposed for balanced hash coding schemas where different blocks 𝐵𝐵𝑖𝑖 do not intersect; we also 
consider the algorithm for the case of intersecting blocks. In this case, when blocks intersect, we 
create the list in a similar way. Repeated elements bring some redundancy (in terms of memory). 

To obtain a formula of complexity of the algorithm, for 𝑥𝑥 ∈ 𝐸𝐸𝑛𝑛 let us consider Fig. 2.  In 
Fig. 2  𝐹𝐹1, 𝐹𝐹2, … , 𝐹𝐹22𝑛𝑛 are all subsets of vertexes of unit cube and each 𝐹𝐹𝑖𝑖 could be generated with 
the corresponding probability𝑝𝑝𝑖𝑖.  
 

 
x 

p1 p2  p22n  probability 
 F1 F2 ⋯ F22n  subset 
 B1 a11x  a12x  ⋯ a122n

x   
blocks B2 a21x  a22x  ⋯ a222n

x   
 ⋮ ⋮ ⋮ ⋯ ⋮  
 B2k a2k1

x  a2k2
x  ⋯ a

2k22
n

x   

Fig. 2. 

We will use the values 𝑐𝑐𝑖𝑖𝑗𝑗
𝑥𝑥  putting them in the cells corresponding to block 𝐵𝐵𝑖𝑖 and subset 𝐹𝐹𝑗𝑗, 

where 

𝑐𝑐𝑖𝑖𝑗𝑗
𝑥𝑥 = �1, 𝑖𝑖𝑓𝑓 𝐵𝐵𝑖𝑖𝑖𝑖𝑠𝑠 𝑐𝑐𝑐𝑐𝑛𝑛𝑠𝑠𝑖𝑖𝑑𝑑𝑐𝑐𝑟𝑟𝑐𝑐𝑑𝑑 𝑖𝑖𝑛𝑛 𝑐𝑐𝑐𝑐𝑠𝑠𝑐𝑐 𝑐𝑐𝑓𝑓 𝑠𝑠𝑐𝑐𝑠𝑠 𝐹𝐹𝑖𝑖 𝑐𝑐𝑛𝑛𝑑𝑑 𝑣𝑣𝑐𝑐𝑟𝑟𝑠𝑠𝑐𝑐𝑥𝑥 𝑥𝑥,

0 𝑐𝑐𝑠𝑠ℎ𝑐𝑐𝑟𝑟𝑤𝑤𝑖𝑖𝑠𝑠𝑐𝑐.                                                                            
 

 



L. Aslanyan and H. Danoyan  
 

13 

As we mentioned, the complexity of the algorithm will be represented as  
 

𝛼𝛼(ℎ𝐶𝐶) =
1

2𝑛𝑛
� � � 𝑝𝑝𝑗𝑗𝑐𝑐𝑖𝑖𝑗𝑗

𝑥𝑥

1≤𝑗𝑗≤22𝑛𝑛1≤𝑖𝑖≤2𝑘𝑘𝑥𝑥∈𝐸𝐸𝑛𝑛
 

Let us denote  𝛷𝛷𝑥𝑥(𝐵𝐵𝑖𝑖) = ∑ 𝑝𝑝𝑗𝑗𝑐𝑐𝑖𝑖𝑗𝑗
𝑥𝑥

1≤𝑗𝑗≤22𝑛𝑛 . As we can see, 𝛷𝛷𝑥𝑥(𝐵𝐵𝑖𝑖) is the probability that the 
block Bi will be considered by the algorithm when the vector x is requested. Then 

 

𝛼𝛼(ℎ𝐶𝐶) =
1

2𝑛𝑛
� � 𝛷𝛷𝑥𝑥(𝐵𝐵𝑖𝑖)

1≤𝑖𝑖≤2𝑘𝑘𝑥𝑥∈𝐸𝐸𝑛𝑛
. 

 

It is easy to understand that for a fixed query x the block Bi will be examined if the sphere 
𝑆𝑆𝑑𝑑(𝑥𝑥,𝐵𝐵𝑖𝑖)−1
𝑛𝑛  does not contain any vector belonging to F. In that case, all blocks Bl such that 
𝑑𝑑(𝑥𝑥, 𝐵𝐵𝑙𝑙) ≤ 𝑑𝑑(𝑥𝑥, 𝐵𝐵𝑖𝑖) − 1, will be examined. Let j vary over all possible distances between vector 
𝑥𝑥 and blocks 𝐵𝐵𝑖𝑖. Denote by 𝑇𝑇𝑥𝑥(𝑗𝑗) the number of blocks located at distance  ≤ 𝑗𝑗 from vector 𝑥𝑥, 
then 

𝛼𝛼(ℎ𝐶𝐶) =
1

2𝑛𝑛
� � 𝑇𝑇𝑥𝑥(𝑗𝑗)𝑉𝑉(𝑗𝑗)

0≤𝑗𝑗≤𝑛𝑛𝑥𝑥∈𝐸𝐸𝑛𝑛
, 

(4) 

 
where V(j) denotes the probability that the nearest vector in F is located at distance j from x. 
Recall that [2]  

𝑉𝑉(𝑗𝑗) = �1 − (1 − 𝑝𝑝)�
𝑛𝑛
𝑗𝑗�� (1 − 𝑝𝑝)∑ �

𝑛𝑛
𝑙𝑙�

𝑗𝑗−1
𝑙𝑙=0 . 

As  𝑑𝑑(𝑥𝑥, 𝐶𝐶𝑖𝑖) = 𝑤𝑤(𝑥𝑥 + 𝑐𝑐𝑖𝑖), then the number of vectors  located at distance i is equal to 𝐴𝐴𝑖𝑖
𝑥𝑥+𝐶𝐶. The 

sphere with centre 𝑐𝑐𝑖𝑖 and radius 𝑅𝑅 will be located at a distance ≤ 𝑗𝑗 from vector 𝑥𝑥 if and only if 
𝑑𝑑(𝑥𝑥, 𝑐𝑐𝑖𝑖) ≤ 𝑗𝑗 + 𝑅𝑅. Therefore 

𝑇𝑇𝑥𝑥(𝑗𝑗) = � 𝐴𝐴𝑖𝑖
𝑥𝑥+𝐶𝐶

𝑗𝑗+𝑅𝑅

𝑖𝑖=0

. 
 
(5) 

  
We consider that 𝐴𝐴𝑖𝑖

𝑥𝑥+𝐶𝐶 = 0 when 𝑖𝑖 > 𝑛𝑛.  
Taking into account formulas (4) and  (5) and the coset weight structures for considered codes, 
we may formulate the following: 

Proposition 1: The complexity of the algorithm for the hash function defined by  [2𝑚𝑚 − 1, 2𝑚𝑚 −
𝑚𝑚 − 1,3]1 Hamming code ℋ𝑚𝑚 is: 

α�hℋm� =
1

2m
� V(j) ���Ai

ℋm + (2m − 1)Ai
e1+ℋm�

j+1

i=0

�
0≤j≤2m−1

, 
 

(6) 

where by  𝑐𝑐𝑖𝑖 is denoted any fixed vector of weight 𝑖𝑖.  

Proposition 2: For the Golay code 𝒢𝒢 the complexity of the algorithm is:    

𝛼𝛼�ℎ𝒢𝒢� = � 𝑉𝑉(𝑗𝑗)
0≤𝑗𝑗≤23

��
1

211
𝐴𝐴𝑖𝑖
𝒢𝒢 +

23
211

𝐴𝐴𝑖𝑖
e1+𝒢𝒢 +

253
211

𝐴𝐴𝑖𝑖
e2+𝒢𝒢 +

5819
211

𝐴𝐴𝑖𝑖
e3+𝒢𝒢�

𝑗𝑗+3

𝑖𝑖=0

. 
 
(7) 



Complexity of Error-Correcting Code Based on Nearest Neighbor Search Algorithm 14 

Proposition 3: For the code ℋ�𝑚𝑚 the complexity of the algorithm is:       
 

𝛼𝛼�ℎℋ�𝑚𝑚� = � 𝑉𝑉(𝑗𝑗) ���
1

2𝑚𝑚+1
𝐴𝐴𝑖𝑖
ℋ�𝑚𝑚 +

1
2
𝐴𝐴𝑖𝑖
e1+ℋ�𝑚𝑚 +

2𝑚𝑚 − 1
2𝑚𝑚+1

𝐴𝐴𝑖𝑖
𝑢𝑢+ℋ�𝑚𝑚�

𝑗𝑗+2

𝑖𝑖=0

�
0≤𝑗𝑗≤2𝑚𝑚

, 
 

(8) 

where by 𝑢𝑢𝑖𝑖 is denoted any fixed vector of weight 2, the first coordinate of which is equal to 1. 
 

Proposition 4: For two error correcting BCH code 𝔅𝔅𝑚𝑚 of length 2𝑚𝑚 − 1 for odd 𝑚𝑚 the 
complexity of the algorithm is: 
 

𝛼𝛼�ℎ𝔅𝔅𝑚𝑚� =  � 𝑉𝑉(𝑗𝑗)
0≤𝑗𝑗≤2𝑚𝑚−1

��
1

22𝑚𝑚
𝐴𝐴𝑖𝑖
𝔅𝔅𝑚𝑚 +

2𝑚𝑚 − 1
22𝑚𝑚

𝐴𝐴𝑖𝑖
e1+𝔅𝔅𝑚𝑚 +

𝑗𝑗+3

𝑖𝑖=0

 

+
(2𝑚𝑚 − 1)(2𝑚𝑚−1 − 1)

22𝑚𝑚
𝐴𝐴𝑖𝑖
e2+𝔅𝔅𝑚𝑚 +

22𝑚𝑚−1 + 2𝑚𝑚−1 − 1
22𝑚𝑚

𝐴𝐴𝑖𝑖
e3+𝔅𝔅𝑚𝑚�. 

 
 
(9) 
 

 
 
5. Numeric Results              
 
Even having formulas, it is hard to imagine the practical complexities of things. To compare the 
results with those in [2], we provide numeric results for propositions 1 to 4 to demonstrate the 
complexity of the algorithm for each case of hash-coding schema. Table 1 demonstrates the 
formula (6) in cases of Hamming code of length 2𝑚𝑚 − 1 for 𝑚𝑚 = 4. Table 2 demonstrates the 
formula (7) in case of Golay code. Tables 3 and 4 demonstrate the formula (8) in cases of 
extended Hamming code of length 2𝑚𝑚 − 1 for 𝑚𝑚 = 4 and 𝑚𝑚 = 5. Table 5 demonstrates the 
formula (9) in case of BCH codes of length 2𝑚𝑚 − 1 for 𝑚𝑚 = 5. 

 
Table 1: Complexity of the algorithm in case of Hamming code of length 15. 

 
Subset generation  
probability  𝑝𝑝  

Average number of 
considered blocks  

The percentage relation of 
considered elements and 
cardinality of subset 

1 1 0.05 
2-1 4.28 0.21 
2-2 6.2 0.3 
2-3 10.1 0.49 
2-4 17.31 0.85 
2-5 26.3 1.28 
2-6 42.27 2.06 
2-7 67.67 3.3 
2-8 107.23 5.24 
2-9 170.38 8.32 
2-10 268.45 13.11 
2-11 418.26 20.42 
2-12 638.09 31.16 
2-13 901.17 44.0 
2-14 1001.82 48.92 
2-15 823.24 40.2 



L. Aslanyan and H. Danoyan  
 

15 

Table 2: Complexity of the algorithm in case of Golay code of length 23                              
 

Subset generation 
 probability  𝑝𝑝 

Average number of  
considered blocks 

The percentage relation of 
considered elements and 
cardinality of subset  

1 1 0.02 
2-1 3.16 0.08 
2-2 4.26 0.10 
2-3 5.45 0.13 
2-4 8.54 0.21 
2-5 12.86 0.31 
2-6 17.14 0.42 
2-7 24.51 0.6 
2-8 36.97 0.90 
2-9 51.85 1.27 
2-10 75.16 1.83 
2-11 109.80 2.68 
2-12 157.04 3.83 
2-13 227.57 5.55 
2-14 325.28 7.94 
2-15 463.76 11.32 
2-16 654.12 15.97 
2-17 911.53 22.25 
2-18 1249.29 30.50 
2-19 1674.63 40.88 
2-20 2176.78 53.14 

 

Table 3: The case of extended Hamming code of length 𝑛𝑛 = 16. 
 

Subset generation  
probability  p 

Average number of 
considered blocks 

The percentage relation of 
considered elements and 
cardinality of subset  

1 4.28 0.89 

2-1 13.03 2.72 

2-2 17.83 3.72 

2-3 25.47 5.32 

2-4 39.69 8.29 

2-5 56.14 11.73 

2-6 80.80 16.89 

2-7 119.08 24.89 

2-8 171.14 35.77 

2-9 247.85 51.81 

2-10 354.80 74.17 

2-11 502.63 105.07 



Complexity of Error-Correcting Code Based on Nearest Neighbor Search Algorithm 16 

2-12 699.58 146.24 

2-13 947.74 198.12 

2-14 1196.9 250.20 

2-15 1235.31 258.23 

2-16 977.51 204.34 

 

Table 4: The case of extended Hamming code of length n=32. 
 

Subset generation  
probability  p 

Average number of  
considered blocks 

The percentage relation of 
considered elements and 
cardinality of subset 

1 8.26 0.0001 
2-1 47.01 0.0005 
2-2 66.43 0.0008 
2-3 82.93 0.001 
2-4 147.70 0.001 
2-5 280.41 0.003 
2-6 419.46 0.005 
2-7 568.55 0.007 
2-8 976.12 0.012 
2-9 1731.29 0.02 
2-10 2572.65 0.03 
2-11 4038.7 0.04 
2-12 7117.07 0.08 
2-13 11173.6 0.13 
2-14 18011.1 0.22 
2-15 30662.2 0.37 
2-16 48773 0.6 
2-17 81535.8 1.00 
2-18 133110 1.63 
2-19 218976 2.69 
2-20 358907 4.42 
2-21 587880 7.24 
2-22 957978 11.79 
2-23 1.55722∙106 19.17 
2-24 2.511422∙106 30.16 
2-25 4.0295∙106 49.63 
2-26 6.3936∙106 78.74 

2-27 1.0009∙107 123.27   

2-28 1.53811∙107 189.44 

2-29 2.29847∙107 283.09 

2-30 3.16976∙107 390.41 

2-31 3.4639∙107 462.64   

2-32 2.82105∙107 347.46   



L. Aslanyan and H. Danoyan  
 

17 

Table 5: The case of two error correcting BCH code of length n=31. 
 

Subset generation 
probability  𝑝𝑝 

Average number of  

considered blocks 

The percentage relation of  

considered elements and 
cardinality of subset  

1 4.87 0.001 

2-1 20.23 0.004 

2-2 27.93 0.006 

2-3 34.07 0.007 

2-4 54.72 0.01 

2-5 94.71 0.02 

2-6 135.65 0.03 

2-7 179.04 0.04 

2-8 284.66 0.06 

2-9 463.67 0.10 

2-10 658.39 0.15 

2-11 987.25 0.22 

2-12 1597.11 0.37 

2-13 2363.61 0.54 

2-14 3624.62 0.84 

2-15 5683.15 1.32 

2-16 8556.05 1.98 

2-17 13333.3 3.09 

2-18 20290.5 4.71 

2-19 31196.3 7.25 

2-20 47458 11.03 

2-21 72165.5 16.77 

2-22 108815 25.29 

2-23 162915 37.87 

2-24 241404 56.11 

2-25 353024 82.06 

2-26 507518 117.977 

2-27 713305 165.813 



Complexity of Error-Correcting Code Based on Nearest Neighbor Search Algorithm 18 

2-28 971293 225.785 

2-29 1.22855∙106 

 

285.587 

2-30 1.26797∙106 

 

294.749 

2-31 1.00312∙106   233.184 

  
 

6.  Conclusion  
The Nearest Neighbor search algorithm considered in this paper is well known (Elias algorithm). 
It uses hash-coding schemas for data preprocessing. These schemas partition the space into non- 
intersecting blocks of the same cardinality. It is known that the algorithm is optimal when these 
blocks are spheres. Such partitions may be obtained by error-correcting codes. The algorithm is 
considered for the cases of perfect codes, so the spheres and, consequently, the lists do not 
intersect. As such codes exist for a limited set of parameters, the algorithm is considered for 
some other generalizations of perfect codes, and then the same data point may be contained in 
different lists. A formula of time complexity of the algorithm is obtained for these cases. These 
formulas show the area of practical use of the algorithm: the algorithm encounters “the course of 
dimensionality”, i.e., as the word length grows, the algorithm turns into an exhaustive search in a 
file.  
 
 
References 
 

[1] D. E. Knuth, The Art of Computer Programming, vol. 3, Sorting and Searching, 
second edition, Eddison-Wesley, 1998.   

[2] R. Rivest, “On the optimality of Elias’s algorithm for performing best-match 
searches”, Information Processing, pp. 678–681, 1974. 

[3] L. H. Aslanyan and H. E. Danoyan, “On the optimality of the hash-coding type nearest 
neighbour search algorithm”, Selected works of 9th CSIT conference, pp. 1-6, 2013. 

[4] F. J. Mac-Williams and N. J. A. Sloane, The Theory of Error-Correcting Codes, 
Amsterdam, The Netherlands: North-Holland, 1986. 

[5] V. A. Zinoviev and V. K. Leont’ev, “The nonexistence of perfect codes over Galois 
fields”, Problems of Control and Information Theory, vol. 2, no. 2, pp. 123-132, 1973. 

[6] L. A. Bassalygo, G. V. Zaitsevand V. A. Zinoviev, “Uniformly packed codes”, 
Problemy Peredachi Informatsii, vol. 10, no. 1, pp. 9-14, 1974. 

[7] T. Baicheva, I. Bouyukliev and S. Dodunekov, “Binary and ternary linear quasi-
perfect codes with small dimensions”, IEEE Transactions of Information Theory, vol. 
54, no. 9, pp. 4335-4339, 2008. 

[8] E. M. Gabidulin, A. A. Davydov and L. M. Tombak, “Linear codes with covering 
radius 2 and other new covering codes,” IEEE Transactionsof Information Theory, 
vol. 37, no. 1, pp. 219–224, 1991. 



L. Aslanyan and H. Danoyan  
 

19 

[9] A. A. Davydov and A. Yu. Drozhzhina-Labinskaya, “Constructions, families, and 
tables of binary linear covering codes,” IEEE Transactions of Information Theory, vol. 
40, no. 4, pp. 1270–1279, Jul. 1994. 

[10] T. Etzion and B. Mounits, “Quasi-perfect codes with small distance”, IEEE Trans.  
Inform. Theory, vol. 51, no. 11, pp. 3938-3946, 2005. 

[11] T. Etzion and G. Greenberg, “Constructions for perfect mixed codes and other 
covering codes,” IEEE Transactions of Information.Theory, vol. 39, no. 1, pp. 209–
214, 1993. 

[12] D. Gorenstein, W. Peterson and N. Zierler, “Two error-correcting bose-chaudhuri 
codes are quasi perfect”, Information and Control, no. 3, pp. 291-294, 1960. 

[13] T. Kasami, S. Lin and W. Peterson, “Some results on the weight distributions of BCH 
codes”,  IEEE Trans. Information Theory, vol. 12, no. 2, pp. 274-277, 1966. 

[14] P. Charpin “Weight distributions of cosets of two-error-correcting BCH codes, 
extended or not”, IEEE Transactions of Information.Theory, vol. 40, no. 5, pp. 1425–
1442, 1991. 

 
 
 
Submitted 18.02.2019, accepted 15.04.2019. 
 
 

Սխալ ուղղող կոդերի վրա հիմնված մոտակա հարևանների 
փնտրման ալգորիթմի բարդությունը 

 
Լևոն Հ. Ասլանյան և Հայկ Է. Դանոյան 

 
ՀՀ ԳԱԱ Ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ 

e-mail: lasl@sci.am, hed@ipia.sci.am 
 

Ամփոփում 
 
       Հայտնի է մոտակա հարևանների փնտրման հաշ-կոդավորման տիպի Էլիասի 
ալգորիթմը: Ալգորիթմում կարող են կիրառվել սխալ ուղղող կոդերը՝ հաշ-
կոդավորման սխեմա կառուցելու համար: Այդ սխեմաները տվյալները ներկայացնում 
են ցուցակների տեսքով: Կամայական ցուցակ իրենից ներկայացնում է որևէ գնդի 
ենթաբազմություն (Հեմինգի տարածությունում), որի կենտրոնը նշված սխալ ուղղող 
կոդի կոդային բառ է: Ալգորիթմը դիտարկվում է կատարյալ կոդերի համար, 
հետևաբար կոդային բառերի շուրջ համապատասխան շառավղով գնդերը չեն 
հատվում, հետևաբար նշված ցուցակները նույնպես չեն հատվի: Քանի որ կատարյալ 
կոդեր գոյություն ունեն պարամետրերի սպեցիֆիկ արժեքների համար, ալգորիթմը 
դիտարկվել է կատարյալ կոդերի այլ ընդհանրացումներով ստացվող հաշ-
կոդավորման սխեմաների համար, որտեղ, սակայն, միևնույն էլեմենտը կարող է 
պատկանել մի քանի ցուցակների: Նշված դեպքերի համար ստացվել են ալգորիթմի 



Complexity of Error-Correcting Code Based on Nearest Neighbor Search Algorithm 20 

բարդության բանաձևերը՝ կախված կոդի հարակից դասերի կշռային 
կառուցվածքներից: 

Բանալի բառեր` մոտակա հարևանների փնտրում, լավագույն 
համընկնումների փնտրում, հաշ-կոդավորման սխեմա, կատարյալ կոդեր, 
հավասարաչափ փաթեթավորված կոդեր, քվազիկատարյալ կոդեր 

 
 
 

Сложность алгоритма поиска ближайших соседей с кодами 
исправляющими ошибки 

 
Левон А. Асланян и Айк Э. Даноян 

 
Институт проблем информатики и автоматизации НАН РА 

e-mail: lasl@sci.am, hed@ipia.sci.am 
 

Аннотация 
 

Известен алгоритм поиска ближайших соседей (алгоритм Элиаса). Алгоритм 
использует коды,  исправляющие ошибки для построения схем хеш-кодирования. Эти 
схемы представляют данные в форме списков. Каждый список содержится в некоторой 
сфере, центром которого является некоторое кодовое слово. Алгоритм рассматривается 
для случаев совершенных кодов, поэтому указанные сферы и, следовательно, списки не 
пересекаются. Поскольку совершенные коды существуют для очень специфичного набора 
параметров, алгоритм рассматривается для некоторых обобщений совершенных кодов, 
когда одна и та же точка данных может содержаться в разных списках. Для указанных 
случаев получены формулы временной сложности алгоритма с использованием весовой 
структуры смежных классов кодов.  

Ключевые слова:  поиск ближайших соседей, поиск наилучших совпaдений, схемы 
хеш-кодирования, совершенные коды, равномерно упакованные коды, квазисовершенные 
коды