Metrics that agree on the support of vectors and nearest neighbor decoding

• Grant number: 15/11286-8
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: September 01, 2015
• End date: September 07, 2019
• Field of knowledge: Physical Sciences and Mathematics - Mathematics
• Agreement: Coordination of Improvement of Higher Education Personnel (CAPES)
• Principal Investigator: Marcelo Firer
• Grantee: Roberto Assis Machado
• Host Institution: Instituto de Matemática, Estatística e Computação Científica (IMECC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated research grant: 13/25977-7 - Security and reliability of Information: theory and practice, AP.TEM
• Associated scholarship(s): 17/14616-4 - Generalizations of threshold graphs, BE.EP.DR

Abstract

A message transmitted through a communication channel is subjected to transmission errors, that is, the receiver cannot identify the original message that was sent him. There is a decoding method called nearest neighbour that uses a metric to determine the closest codeword to the received message. In the classical coding theory, we often consider the Hamming or Lee metrics. Considering these metrics, some metric aspects of codes were studied, such as: (I) packing radius, (II) covering radius, (III) MacWilliams identity, (IV) perfect codes, etc. The use of the Hamming or Lee metrics is justified by the fact that the nearest neighbour decoding matches to the maximum likelihood decoding for the simplest channel model, the memoryless symmetric channel. For complex channels it is necessary to define and study other families of metrics and the metric aspects of the codes admitting these metrics. In 1995, Brualdi, Graves and Lawrence introduced a generalization for Hamming metric called poset metrics. Several relations obtained for the Hamming metric were extended to the family of hierarchical poset metrics over the years. These results appear dispersed through the literature with long proofs. Considering the systematic-canonical form for linear codes, introduced in 2012 by Felix and Firer, we prove these and other properties, that characterize the hierarchical poset metrics in a simple and short way. The first generalization of poset metrics, called poset-blocks metric, (that allows a large "flexibility" to construct metrics balls) was introduced by Alves, Panek and Firer, in 2008. To this family, the detailed description of the symmetry group and the characterization of a MacWilliams-type identity are already known. In this year, some generalizations of the poset metrics were proposed (still unpublished works): (a) directed graph metric; (b) coverage metric; (c) poset-Lee metric; (d) semi-lattice metric.In this project we propose to study metric aspects of linear codes for those generalizations. (AU)

Scientific publications

(7)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

KOSLOCHKA, ALEXANDR V.; LIU, XUJUN; MACHADO, ROBERTO; MILENKOVIC, OLGICA; IEEE. Directed Intersection Representations and the Information Content of Digraphs. 2019 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), v. N/A, p. 5-pg., 2019-01-01. (15/11286-8)

MACHADO, ROBERTO; FIRER, MARCELO; IEEE. Weights which respect support and NN-decoding. 2019 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), v. N/A, p. 5-pg., 2019-01-01. (15/11286-8, 13/25977-7)

ETZION, TUVI; FIRER, MARCELO; MACHADO, ROBERTO ASSIS. Metrics Based on Finite Directed Graphs and Coding Invariants. IEEE TRANSACTIONS ON INFORMATION THEORY, v. 64, n. 4, 1, p. 2398-2409, APR 2018. (15/11286-8, 14/10745-6, 13/25977-7)

LIU, XUJUN; MACHADO, ROBERTO ASSIS; MILENKOVIC, OLGICA. Directed Intersection Representations and the Information Content of Digraphs. IEEE TRANSACTIONS ON INFORMATION THEORY, v. 67, n. 1, p. 347-357, JAN 2021. (15/11286-8)

MACHADO, ROBERTO ASSIS; FIRER, MARCELO. Weights Which Respect Support and NN-Decoding. IEEE TRANSACTIONS ON INFORMATION THEORY, v. 66, n. 6, p. 3664-3674, JUN 2020. (13/25977-7, 15/11286-8)

MACHADO, ROBERTO ASSIS; PINHEIRO, JERRY ANDERSON; FIRER, MARCELO. Characterization of Metrics Induced by Hierarchical Posets. IEEE TRANSACTIONS ON INFORMATION THEORY, v. 63, n. 6, p. 3630-3640, JUN 2017. (15/11286-8, 16/01551-9, 13/25977-7)

ETZION, TUVI; FIRER, MARCELO; MACHADO, ROBERTO ASSIS. Metrics Based on Finite Directed Graphs and Coding Invariants. IEEE TRANSACTIONS ON INFORMATION THEORY, v. 64, n. 4, p. 12-pg., 2018-04-01. (15/11286-8, 14/10745-6, 13/25977-7)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

MACHADO, Roberto Assis. Teoria de códigos: uma abordagem usando métricas que respeitam suporte e outros problemas. 2019. Doctoral Thesis - Universidade Estadual de Campinas (UNICAMP). Instituto de Matemática, Estatística e Computação Científica Campinas, SP.