Codes, Metrics, and Applications

2016 ISIT Plenary Talk
Codes, Metrics, and Applications
Alexander Barg
University of Maryland



Applications of coding in communication and computer science give rise to various metrics on strings over a finite alphabet. We consider a class of metrics induced by partial orders on the code coordinates, paying special attention to one such metric (the Niederreiter-Rosenbloom-Tsfasman metric) and its applications in wireless, list decoding, approximation theory, and polar coding. We discuss combinatorics of the ordered metric space, and extend some of the results to general partial orders. We continue with several results related to distance distributions of linear codes and their extentions to the ordered case, as well as links with matroids on partial orders. In conclusion, we mention a further extension to infinite orders and an unexpected appearance of wavelet-like functions.

This line of work has developed over a number of years and draws on joint papers with many colleagues, including, in particular, (former) students Andrew McGregor, Punarbasu Purkayastna, and Woomyoung Park.