Metrics Based on Finite Directed Graphs and Coding Invariants

Autor(es)

Etzion, Tuvi ; Firer, Marcelo ; Machado, Roberto Assis

• Tipo de documento: Artigo Científico
• Fonte: IEEE TRANSACTIONS ON INFORMATION THEORY; v. 64, n. 4, p. 12-pg., 2018-04-01.

Resumo

Given a finite directed graph with n vertices, we define a metric d(G) on F-q(n), where F-q is the finite field with q elements. The weight of a word is defined as the number of vertices that can be reached by a directed path from a vertex within the support of the vector. Two canonical forms, which do not affect the metric, are given to each graph. Based on these forms we characterize each such metric. We further use these forms to prove that two graphs with different canonical forms yield different metrics. Efficient algorithms to check if a set of metric weights define a metric based on a graph are given. We provide tight bounds on the number of metric weights required to reconstruct the metric. Furthermore, we give a complete description of the group of linear isometries of the graph metrics and a characterization of the graphs for which every linear code admits a G-canonical decomposition. Considering those graphs, we are able to derive an expression of the packing radius of linear codes in such metric spaces. Finally, given a directed graph which determines a hierarchical poset, we present sufficient and necessary conditions to ensure the validity of the MacWilliams identity and the MacWilliams extension property. (AU)

• Processo FAPESP: 15/11286-8 - Métricas que respeitam suporte e decodificação de máxima proximidade
• Beneficiário: Roberto Assis Machado
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Processo FAPESP: 14/10745-6 - Polinômio enumerador de pesos para métrica poset
• Beneficiário: Marcelo Firer
• Modalidade de apoio: Auxílio à Pesquisa - Pesquisador Visitante - Internacional
• Processo FAPESP: 13/25977-7 - Segurança e confiabilidade da informação: teoria e prática
• Beneficiário: Marcelo Firer
• Modalidade de apoio: Auxílio à Pesquisa - Temático