Coding theory finds its significant impacts when data should be transmitted under noisy channel. While error-correcting codes detect and correct a certain number of errors, constrained codes encode original messages so that encoded data do not contain any data sequences that can be easily affected by channel noise. Constrained codes have been mainly applied to data storage media.
The study of constrained codes is strongly related to the study of sofic shifts, which are set of bi-infinite sequences characterised by labelled directed graphs, called presentations. Presentations give us important properties such as capacities or encoding/decoding schemes. We therefore have been analyzing constrained codes from the perspective of graph theory, with an aim of proposing more robust and reliable data storage media.
Wireless Body Area Networks (WBANs) are one of short-range communications in which biological information (e.g., ECG or EEG) is transmitted. In WBANs, reliable data communication is paramount, so coding can be a powerful tool to support it. At the same time, devices used in WBANs must be small enough so as to be easily attached to or implanted under patients’ skin, which implies that power consumption is also strongly desired.
We therefore consider robustness of lightweight coding schemes using the connectivity of graphs. We also focus on Low-Density Parity Check (LDPC) codes, which are well known to possess high error correcting performance, as a candidate of coding schemes for WBANs. Since LDPC codes can be characterised by bipartite graphs (called Tanner graphs) and their performance relies on the topology of Tanner graphs, we attempt to further improve their performance by analyzing Tanner graphs.
Distributed Line (DL) graphs have been introduced by Zhang et. al. in 2012 as a suitable candidate for Peer-to-Peer (P2P) Network topology. Indeed, DL graphs have reasonably small diameter (the length of the longest paths between distinct vertices) and are preferable in the sense of having constant out-degree (which corresponds to the amount of routing information each peer possesses) regardless of the number of vertices. Furthermore, DL graphs locally change the topology when some vertices are added or removed, so costs due to user joins/leaves can be reduced.
We have been further discussing useful properties on DL graphs, for the purpose of practical implementation of DL graphs in P2P networks. We also aim to not only propose theoretical results but also to execute simulations to support the efficiency of DL graphs.