1-4hit |
In the field of computer science, the network reliability problem for evaluating the network failure probability has been extensively investigated. For a given undirected graph G, the network failure probability is the probability that edge failures (i.e., edge erasures) make G unconnected. Edge failures are assumed to occur independently with the same probability. The main contributions of the present paper are the upper and lower bounds on the expected network failure probability. We herein assume a simple random graph ensemble that is closely related to the Erd
The capacity (i.e., maximum flow) of a unicast network is known to be equal to the minimum s-t cut capacity due to the max-flow min-cut theorem. If the topology of a network (or link capacities) is dynamically changing or unknown, it is not so trivial to predict statistical properties on the maximum flow of the network. In this paper, we present a probabilistic analysis for evaluating the accumulate distribution of the minimum s-t cut capacity on random graphs. The graph ensemble treated in this paper consists of undirected graphs with arbitrary specified degree distribution. The main contribution of our work is a lower bound for the accumulate distribution of the minimum s-t cut capacity. The feature of our approach is to utilize the correspondence between the cut space of an undirected graph and a binary LDGM (low-density generator-matrix) code. From some computer experiments, it is observed that the lower bound derived here reflects the actual statistical behavior of the minimum s-t cut capacity of random graphs with specified degrees.
Yoshitoshi YAMASHITA Eiji OKAMOTO Yasunori IWANAMI Yozo SHOJI Morio TOYOSHIMA Yoshihisa TAKAYAMA
We propose a novel channel model of satellite-to-ground optical transmission to achieve a global-scale high-capacity communication network. In addition, we compose an effective channel coding scheme based on low-density generator matrix (LDGM) code suitable for that channel. Because the first successful optical satellite communication demonstrations are quite recent, no practical channel model has been introduced. We analyze the results of optical transmission experiments between ground station and the Optical Inter-orbit Communications Engineering Test Satellite (OICETS) performed by NICT and JAXA in 2008 and propose a new Markov-based practical channel model. Furthermore, using this model we design an effective long erasure code (LEC) based on LDGM to achieve high-quality wireless optical transmissions.
Yoshihide TONOMURA Daisuke SHIRAI Takayuki NAKACHI Tatsuya FUJII Hitoshi KIYA
In this paper, we introduce layered low-density generator matrix (Layered-LDGM) codes for super high definition (SHD) scalable video systems. The layered-LDGM codes maintain the correspondence relationship of each layer from the encoder side to the decoder side. This resulting structure supports partial decoding. Furthermore, the proposed layered-LDGM codes create highly efficient forward error correcting (FEC) data by considering the relationship between each scalable component. Therefore, the proposed layered-LDGM codes raise the probability of restoring the important components. Simulations show that the proposed layered-LDGM codes offer better error resiliency than the existing method which creates FEC data for each scalable component independently. The proposed layered-LDGM codes support partial decoding and raise the probability of restoring the base component. These characteristics are very suitable for scalable video coding systems.