Network coding is a promising generalization of routing which allows a node to generate output messages by encoding its received messages. An important scenario where network coding offers unique advantages is a multi...
详细信息
ISBN:
(纸本)9781424410422
Network coding is a promising generalization of routing which allows a node to generate output messages by encoding its received messages. An important scenario where network coding offers unique advantages is a multicast network where a source node generates messages and multiple receivers collect the messages. In a multicast network, linear network codes are preferred due to its sufficiency and simplicity. In this paper, we propose a method to transform the linear coding problem to a graph theory problem. With the help of hypergraphs, we model the linear codes by constructing a pseudo-dual graph of the multicast network. A valid linear code is equal to a cover in the pseudo-dual graph satisfying some constraints. By iterative refinements, an eligible cover can be found in polynomial time. Moreover, this method can be readily applied to many minimum network coding problems as well.
The famous max-flow min-cut theorem states that a source node s can send information through a network (V, E) to a sink node t at a rate determined by the min-cut separating s and t. Recently, it has been shown that t...
详细信息
The famous max-flow min-cut theorem states that a source node s can send information through a network (V, E) to a sink node t at a rate determined by the min-cut separating s and t. Recently, it has been shown that this rate can also be achieved for multicasting to several sinks provided that the intermediate nodes are allowed to re-encode the information they receive. We demonstrate examples of networks where the achievable rates obtained by coding at intermediate nodes are arbitrarily larger than if coding is not allowed. We give deterministic polynomial time algorithms and even faster randomized algorithms for designing linear codes for directed acyclic graphs with edges of unit capacity. We extend these algorithms to integer capacities and to codes that are tolerant to edge failures.
Network coding shows,that data rate can be increased if information is allowed, to be encoded in the network nodes. The recent work of Li, Yeung and Cai [1], and Koetter and Medard [2], shows that linear network codin...
详细信息
ISBN:
(纸本)0780386477
Network coding shows,that data rate can be increased if information is allowed, to be encoded in the network nodes. The recent work of Li, Yeung and Cai [1], and Koetter and Medard [2], shows that linear network coding is sufficient for single source multicast network. The restrictiveness of usage of linear code is still an unknown in the general multisource multicast network. In this paper, we characterize the achievable information rate region for single source node multi-source multicast networks with two sinks. We further show that linear coding is sufficient for achieving the maximum network capacity.
The prediction and modeling of protein structure is a central problem in bioinformatics. Neural networks have been used extensively to predict the secondary structure of proteins. While significant progress has been m...
详细信息
ISBN:
(纸本)0819453560
The prediction and modeling of protein structure is a central problem in bioinformatics. Neural networks have been used extensively to predict the secondary structure of proteins. While significant progress has been made by using multiple sequence data, the ability to predict secondary structure from a single sequence and a single prediction network has stagnated with an accuracy of about 75%. This implies that there is some limit to the accuracy of the prediction. In order to understand this behavior we asked the question of what happens as we change the target function for the prediction. Instead of predicting a derived quantity, such as whether a given chain is a helix, sheet or turn, we tested whether a more directly observed quantity such as the distance between a pair of alpha-carbon atoms could be predicted with reasonable accuracy. The alpha-carbon atom position is central to each residue in the protein and the distances between them in sequence define the backbone of protein. Knowledge of the distances between the alpha-carbon atoms is sufficient to determine the three dimensional structure of the protein. We have trained on distance data derived from the complete protein structure database (pdb) using a multi-layered perceptron (MLP) feedforward neural network with back propagation. It shows that the root of mean square error is 4.4 Angstrom while the mean of actual output is 11.5 Angstrom with orthogonal coding of protein primary sequence. Other coding schemes including BLOSUM62 coding and linear coding were tested with another two target functions of cutoff accuracy and correlation coefficient. The best correlation coefficient was achieved with BLOSUM62 coding scheme and the cutoff accuracy reached about 60%.
In this paper, we construct fault-tolerant linear finite-state machines (LFSMs) in which error. detection and correction can be performed nonconcurrently (e.g., periodically). More specifically, by jointly choosing th...
详细信息
In this paper, we construct fault-tolerant linear finite-state machines (LFSMs) in which error. detection and correction can be performed nonconcurrently (e.g., periodically). More specifically, by jointly choosing the state encoding constraints and the redundant dynamics of the fault-tolerant LFSM we enable an external checker to detect and identify errors due to past faults based on the current, possibly corrupted state of. the LFSM. The paper presents systematic constructions of fault-tolerant LFSMs based on a characterization of nonconcurrent error detection/correction in terms of state encoding constraints and redundant dynamics. In particular, we develop a scheme that uses Bose-Chaudhuri-Hocquenghem (BCH) coding and obtains fault-tolerant LFSMs that require 2D additional state variables and have the ability to correct up to D errors in any state variable at any time step in the time interval consisting of the latest N time steps of operations The construction uses the minimum possible number of additional state variables and requires an error detecting/correcting mechanism with computational complexity that is only linear in N.
作者：
Hadjicostis, CNVerghese, GCUniv Illinois
Coordinated Sci Lab Urbana IL 61801 USA Univ Illinois
Dept Elect & Comp Engn Urbana IL 61801 USA MIT
Electromagnet & Elect Syst Lab Cambridge MA 02139 USA MIT
Dept Elect Engn & Comp Sci Cambridge MA 02139 USA
This note discusses fault tolerance in linear finite-state machines (LFSMs). By replacing a given LFSM with a larger, redundant LFSM that preserves the state of the original one in some linearly encoded form, various ...
详细信息
This note discusses fault tolerance in linear finite-state machines (LFSMs). By replacing a given LFSM with a larger, redundant LFSM that preserves the state of the original one in some linearly encoded form, various alternatives to modular redundancy are considered. We characterize the class of appropriate redundant machines in terms of added dynamics and their coupling with the dynamics of the original machine, and illustrate how these can be chosen to minimize redundant hardware.
Aiming at the local intensity anamorphosis in general linearly coded profilometry, the post treatment methods under different decoding conditions are proposed, in which the distorted intensities are rehabilitated or e...
详细信息
Aiming at the local intensity anamorphosis in general linearly coded profilometry, the post treatment methods under different decoding conditions are proposed, in which the distorted intensities are rehabilitated or eliminated by our routines. The experimental results show that the measuring error and system cost can be effectively reduced while the reliability can be improved by introducing those methods into decoding process.
A new triangulation-based optical profilometry-linearly coded profilometry (LCP)-is presented. In this method, a linear coding technique is introduced. It uses a periodic sawtoothlike structure light to code the surfa...
详细信息
A new triangulation-based optical profilometry-linearly coded profilometry (LCP)-is presented. In this method, a linear coding technique is introduced. It uses a periodic sawtoothlike structure light to code the surface being measured and the phase-shifting technique to decode the profile. A coding light that has isosceles triangle teeth is proposed. To realize the decoding, at least three samples are needed. When more than three samples are used, higher accuracy can be obtained. A decoding method of LCP with an even number of samples is provided. This method has been realized in my laboratory and the experimental results verify the reliability of LCP. Because the coding method used in LCP is simpler than that used in phase-measuring profilometry, LCP has a faster measuring speed. (C) 1997 Optical Society of America.
A new optical profilometry-linearly coded profilometry (LCP)-is presented. It uses a sawtoothlike linear light structure to code the surface to be measured and a phase-shifting technique to decode the profile. Two kin...
详细信息
A new optical profilometry-linearly coded profilometry (LCP)-is presented. It uses a sawtoothlike linear light structure to code the surface to be measured and a phase-shifting technique to decode the profile. Two kinds of coding-light structure, one with right-angle triangle teeth and the other with isosceles triangle teeth, are proposed. For coding with light with right-angle triangle teeth, a general decoding method is given. In addition, an optimum sampling manner and the measurement error are discussed with respect to a special case. For coding with light with isosceles triangle teeth, a decoding method with three samples is given. In our laboratory, an experimental system was established, and experiments that verified the reliability of the proposed methods were performed. Experimental results typical of those obtained are given. We find that LCP is similar to the widely used phase-measuring profilometry but has a faster measuring speed. (C) 1997 Optical Society of America.
It is shown that any lexicographic code S with minimal distance d has a unique basis where each basis vector is a one followed by a string of zeros, followed by d - 1 nonzero digits a(ij). Furthermore, the matrix A = ...
详细信息
It is shown that any lexicographic code S with minimal distance d has a unique basis where each basis vector is a one followed by a string of zeros, followed by d - 1 nonzero digits a(ij). Furthermore, the matrix A = (a(ij)) has no singular minors over the nim-field. The dual code when S has finite length is also computed.
暂无评论