Classification of Weight Posets and Digraphs Admitting the Extended Hamming Code to Be a 2-perfect Code

Abstract

원소의 개수가 q개인 유한체를 Fq이라 하고, Fq상에서의 n 차원 벡터 공간을 Fnq라고 하자. 부호론은 Fnq의 부분집합에 대해 연구하는 학문이다. q = 2인 경우가 부호론에서가장중요하게다루는경우이며, 이논문에서는q = 2인경우에 한해서 다루고 있다. 부호론은 그간 해밍 메트릭이 부여된 Fn2 에 관해 주로 연구가 진행됐다. 하지만 1980년대 후반 이래로,해밍메트릭외의새로운메트릭이등장했고,부호론의 기존 문제들을 이 새로운 메트릭을 통한 일반화하려는 시도들이 있었다. 2018년에는 n개의 꼭짓점을 갖는 유향 그래프에 기반한 Fn2 위의 메트릭이 소개되었다. 그리고 이후로부터, 유향 그래프 메트릭의 대수적 버전이라고 생각할 수 있는 가중 반순서 집합 메트릭이 소개되었다. 여기에서 가중 반순서 집합이란 각각의 점들이 가중치를 갖는 반순서 집합을 말한다. 가중 반순서 집합 메트릭은 반순서 집합 메트릭의 일반화로 볼 수 있다. 가중 반순서 집합 메트릭과 유향 그래프 메트릭은 밀접한 관계를 가지고 있다. 가중 반순서 집합 메트릭은 유향 그래프 메트릭에 의해 유도될 수 있는 한편, 몇몇 유향 그래프 메트릭은 가중 반순서 집합으로부터 얻어질 수 있다. 길이가 8인 확장된 해밍 부호가 두 개의 오류를 교정하는 완전 부호가 되도록 하는 가중 반순서 집합과 유향 그래프에 대해서는 선행연구에 의해 분류가 되어 있었다. 이 학위 논문에서는 길이가 16인 확장된 해밍 부호가 두 개의 오류를 교정하는 완전 부호가 되도록 하는 가중 반순서 집합과 유향그래프의 분류하는 문제에 관심을 갖는다. 우선 완전 부호의 정의를 가중 반순서 집합 메트릭 공간과 유향 그래프 메트릭 공간에 대해 확장하였다. 이후 각각의 가중 반순서 집합과 유향그래프가 확장된 해밍 부호가 완전 부호가 되도록 할 수 있는지의 여부는 이들의 구조 벡터에 의해 결정됨을 증명하였다. 구조 벡터의 길이를 s라고 하자. III단원과 IV단원을 통해 확장된 해밍 부호가 완전 부호가 되도록 하는 가중 반순서 집합(s = 3, 4, 5의 경우)과 유향그래프(s = 3, 4의 경우)를 각각 분류하였다. 그리고 이 분류의 결과로서, 길이가 16인 해밍 부호의 경우에 대해서는 모든 가중 반순서 집합과 유향 그래프를 모두 분류할 수 있었다.

Let Fq be the finite field with q elements, and Fnq be the n-dimensional vector space over Fq. In coding theory one is mainly concerned on the study of subset of Fnq. In this thesis, we will restrict ourselves when q = 2. The study has mainly focused on when Fn2 is equipped with the Hamming metric. However, since the late 1980’s, non Hamming metrics have been introduced and there are several attempts have been made to generalize classical problems of the coding theory when Fn2 is equipped with the non Hamming metric. In 2018, Etzion et al. introduced metrics on Fn2 based on directed graphs on n vertices. After that, Hyun et al. introduced weighted poset metrics on Fn2 which may be considered as an algebraic version of directed graph metric. A weighted poset is a poset in which every point has a weight. One can introduce weighted poset metric as a generalization of poset metric. It can be shown that weighted poset metric and directed graph metric are closely related. On the one hand, weighted poset metric can be induced from directed graph metric, and on the other hand, some of directed graph metric can be induced from weighted poset metric. These relations are described. Weighted posets and directed graphs which admit the extended Hamming code of length 8 to be a 2-perfect code have been classified by Hyun et al. In this thesis, we are interested in the problem of classifying weighted posets and directed graphs which admit the extended Hamming code of length 16 to be a 2-perfect code. We first extend the definition of perfect codes on weighted poset metric and digraph metric spaces. It will be shown that every weighted poset or directed graph which admits extended Hamming code is completely determined by its structure vector. Let s be the length of the structure vector. In Chapter III (resp. IV), we will classify structure vectors of weighted posets (resp. directed graphs) which admit the extended Hamming code eHm,m ≥ 2 to be a 2-perfect code when s = 3, 4, 5 (resp. s = 3, 4). As a consequence our classification, we will classify weighted posets and directed graphs which admit the extended Hamming code of length 16 to be a 2-perfect code.