Начиная с начала 2000 года осуществляется внедрение GHIS в здравоохранении, в рамках принятого проекта о реформирование информ Mathematical Problems of Computer Science 39, 119--124, 2013. 119 On Some Properties of Intersection and Union of Spheres in Hamming Metric Haykaz E. Danoyan Yerevan State University e-mail: hdanoyan@yandex.ru Abstract The problems of intersection and union of spheres of the same radius in Hamming metric are considered. The formula for number of points in intersection is derived in case of two spheres. It is proved that three or more spheres of radius (covering radius of a code ) centered at points belonging to some quasi-perfect code intersect at most at one point. It is also proved that the increase of cardinality of union of spheres of the same radius, depending on radius, is a concave function and can have at most one or two maximum values depending on length. Keywords: Nearest neighbors, best-match, Hamming spheres, concave function, quasi- perfect code. 1. Introduction Let . Denote by the set of vertices of the unit cube, that is each vector can be represented as , where , . For each pair of vectors denote by the Hamming distance between the vectors and . For denote by the sphere with centre and radius , that is ⁄ . The carrier of the vector we define as ⁄ . Denote by the weight of vector , that is . Denote by the set of the first natural numbers, i.e. . A code will be called a subset of [1]. Usually the codes are considered for which some other additional properties take place such as linearity, cyclicity, etc. In some cases a problem to find the intersection of spheres of the fixed radius can arise [2-4]. We will consider this problem for a simple case, namely when the centers of the spheres belong to a quasi-perfect code with the covering radius . Recall that a code is called quasi perfect [1] if the following condition holds: , where and ⌊ ⁄ ⌋. The number is called a minimum distance of the code , i.e. . We also consider the problem of increase of union of spheres of some radius depending on the radius. More precisely let us have a set and let ⋃ ⋃ . It is important to check [2],[5] if the function is concave, with one or two maximal values depending on and . mailto:hdanoyan@yandex.ru On Some Properties of Intersection and Union of Spheres in Hamming Metric 120 2. Intersection of Two Spheres In the next section we will consider the problem of intersection of spheresin some cases, so it is useful at first to consider the case of two spheres.Suppose we have two spheres with centers and and radii and respectively. We denote the intersection of the mentioned spheres by i.e. .It is easy to show that each case can be reduced to the case when , therefore furthermore we assume that the mentioned case takes place. Without losing generality we assume, that . It is easy to see that when (where ) the considered intersection is empty, so we suppose that .We denote the cardinality of intersection by . Let us take any vector and find out conditions, under which the vector belongs to the set . Let and (Figure1). β 0 … 0 0 … 1 … 1 1 … 1 d γ 1 … 1 0 … 0 … … 1 … 1 x y α 0 … 0 0 … 0 … … 0 … 0 Fig. 1. In order for belongs to the intersection, and should satisfy the following system of inequalities: { Let us denote [ ]. Consider the following three cases. Case a. . It is easy to see, that when then and when then (Fig. 2). Fig. 2. H. Danoyan 121 Therefore ∑ ∑ ( ) ( ) ∑ ∑ ( ) ( ) . In case when we can write (3) in a simpler form: ( ). Case b. , . This case, in its turn, is divided into two separate cases: Subcase b.1. . By straightforward verification we get that when then and when then (Fig. 3). Fig. 3. Therefore ∑ ∑ ( ) ( ) ∑ ∑ ( ) ( ) . Subcase b.2. . In this case we get that when . Therefore ∑ ∑ ( ) ( ) . Case c. . This case is also divided into two separate cases. Subcase c.1. . We get that when then and when then (Fig. 4). Figure 4. Fig. 4. On Some Properties of Intersection and Union of Spheres in Hamming Metric 122 Therefore ∑ ∑ ( ) ( ) ∑ ∑ ( ) ( ) . Subcase c.2. . In this case we get that when . Therefore ∑ ∑ ( ) ( ) . 3. Intersection of Spheres Centered at Codewords of Quasi-perfect Code Suppose we have spheres with radii centered at points respectively. Now we consider the intersection of spheres with the radius incase when the centers of spheres are codewords of any quasi-perfect code. As we mentioned, we can assume that . Proposition 1. Let vectors becodewords of the quasi-perfect code with an even minimum distance , then ⋂ if and only if I. ( ) , II.⋂ . Otherwise, the considered intersection is empty. Proof. Necessity is obvious let us prove thesufficiency. Note that in this case we have , . From thecondition itfollows that the intersection of the spheres of radius centered at the points is nonempty only if ( ) , . So we get and ( ) , , . Let . From the reasoning of the previous section it follows that , and ( ) therefore there is only belonging to the intersection. Now let us have vectors which are codewords of any quasi-perfect code with an odd minimum distance, i.e . This means that the covering radius of the code is . Suppose we want to know the intersection of spheres with the radius centered at .As we mentioned, consider that . Partition the set into two nonintersecting subsets and in the following way { . From the condition follows that the considered intersection is not empty only when . Without loosing generality assume that . Let Now we can formulate the following: Proposition 2. Let vectors be codewords of the quasi-perfect code with an odd minimum distance , then ⋂ if and only if I. ( ) ( ) II.⋂ . Otherwise the considered intersection is empty. Proof. The schema of proof is analogous to proposition 1. 4. Variation Function of Area Size of Sphere System is Concave Consider an arbitrary .Then it is easy to check that for a fixed the function is concave. For odd there are two maximums of at and H. Danoyan 123 . When is even, then there is one maximal value at the point .In a generalized model a number of packed spheres can be considered. Given a subset and let ⋃ ⋃ . It is important to check if the function is also concave, with one or two maximal values depending on and . A harder generalization will be the case of different radii but our interest will be restricted to the basic case of one fixed . There can also be considered not the spheres but the spherical structures [6]. Consider the case of two vertices, and . If one of these vectors is the negation of the other, then: if is odd, there is one maximum at and for ; when is even, then is increasing in interval and when It reminds to compare the following 2 values: ( ⁄ ) and ( ⁄ ). It is easy to check that the only maximum accepts at , just it needs to take into account that is even. Now consider the case of and , not opposite in . Choose an index and the variable so that . Partition in the direction , then and belong to one of the parts of , let it be the sub- cube . Denote by and the projections of and to . The areas of our consideration n, and , can be partitioned in the direction . In these two dimensional sub-cubes we receive the same pair of vertices: and , and the radius in , and and and the radius in . In theseterms . In fact, we have the same function and the same points for .If suppose that is concave, having 1 or 2 maximal values, then this shifted sum will have the same properties. Now we consider the general case of arbitrary . Denote by and the partition compounds of in direction . Let and be projections of and in direction . In the first step, when we receive: in a union of ⋃ and , and similarly in a union of ⋃ and . In reality, in dimension we have to consider two sets of vertices – those are basic in that cube and these vertices draw spheres around, and the projection vertices that draw spheres around. The second set may add some new neighbours to the basic set produced by the first set. The difficulty to watch these sets concerns the radii difference. To use the induction hypotheses we have to transform the constructions so that a situation appears, that is standard in dimension . For this purpose by an evident note it is sufficient to consider not the basic sets of vertices but the ones appeared after the first step – ⋃ in and ⋃ in . In this case the basic will appear as the sum of 2 functions in dimension by the radius . At this stage we have 2 concave functions in , which have 1 or 2 maximums by the supposition of induction. It is evident that the sum of functions will increase when functions increase separately, and that it decreases in part in case of decrease in both of them. Consider the point of the first decrease in . At least one of the sub-functions has its decrease at . Let this be the function at . The sensitive part that initiates this decrease will be the set . The complementary part can’t be sensitive because its radius is higher in and its decrease must happen earlier and this will cause the summary decrease in . Then, the projection of that appears with the radius in will have the same size in the next step when the radius is equalto . This will sufficiently initiate the decrease in the sub-function at . On Some Properties of Intersection and Union of Spheres in Hamming Metric 124 References [1] F. J. Mac Williams, N. J. A. Sloane, The Theory of Error-Correcting Codes, 1977. [2] I. Honkala, “On the intersection and unions of Hamming Spheres”, The Very Knowledge of Coding, pp. 70-81, 1987. [3] G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, Covering Codes, 1997. [4] R.L. Rivest, “On the optimality of Elias's algorithm for performing best-match searches”, Information Processing, pp. 678-681, 1974. [5] Yu.Zhuravlev, Selected Scientific Works, (in russian), 1998. [6] L. Aslanyan, “Metric decompositions and the discrete isoperimetry”, IFAC Symposium on Manufacturing, Modelling, Management and Control, pp. 433-438, 2000. Submitted 24.12.2012, accepted 18.02.2013. Հեմմինգի մետրիկայում սֆերաների հատման և միավորման որոշ հատկությունների մասին Հ. Դանոյան Ամփոփում Դիտարկվում է Հեմմինգի մետրիկայում սֆերաների հատման և միավորման կետերի գտնելու խնդիրը: Բերված է բանաձև` երկու տարբեր շառավիղներով սֆերաների հատման համար: Ապացուցված է, որ երեք և ավելի r շառավղով սֆերաները, որոնց գագաթները պատկանում են որևէ քվազիկատարյալ կոդի, կարող են հատվել ամենաշատը մեկ կետով (R-ը նշված կոդի ծածկման շառավիղն է): Ապացուցված է նաև, որ սֆերաների միավորման` շառավղից կախված ֆունկցիայի աճը ունի մեկ կամ երկու մաքսիմում` կախված տարածության չափողականությունից: О некоторых свойствах пересечения и объединения сфер в метрике Хемминга А. Даноян Аннотация Рассматривается проблема нахождения пересечения и объединения сфер в метрике Хемминга. Приведена формула для числа точек пересечения для двух сфер. Доказано, что три и более сферы радиуса R,центры которых принадлежат некоторому квазисовершенному коду C, могут пересекаться лишь в одном точке (R радиус покрытия кода C). Также доказано, что возрастание функции числа точек в объединении некоторых сфер от радиуса может иметь один или два максимума в зависимости от меры пространства.