Massachusetts Institute of Technology

California Institute of Technology

University of Illinois

Ntt Docomo, Inc.

Rohde and Schwarz Gmbh & Co. Kg

National Science Foundation

Codevector Technology

Ralf Koetter

Muriel Medard

Tracey Ho

Supratim Deb

Michelle Effros

Desmond S Lun

Shirin Jalali

Nuala Koetter, Legal Representative

David R Karger

Andrew Carl Singer

Xiaomeng Shi

Gerhard Bauch

Joerg Widmer

Alexander Vardy

Georg Zeitler

Joschi Tobias Brauchle

Niranjan Ratnakar

Systems and methods for characterizing networks are disclosed. In several embodiments, a network analyzer applies a network analysis to a network that replaces components of the network in a model of the network with equivalent or bounding models. The network analyzer can then characterize the simplified model of the network and an assessment can be made concerning the accuracy of the characterization of the network.

Systems and methods of network analysis and characterization

A method and computer program product for providing a random linear coding approach to distributed data storage is presented. A file is broken into a plurality of pieces. For every peer (peer means storage-location with limited storage space), the number of coded-pieces the peer can store is determined. Each of the coded-piece is determined by taking random linear combination of all the pieces of the entire file. The associate code-vector is stored for every coded-piece. The file is retrieved by collecting code-vectors and the coded-pieces from the peers and viewing the collected code-vectors as a matrix. When a dimension of the matrix is equal to the number of pieces of the file, the file is recovered using the collection of code vectors in the matrix.

Random linear coding approach to distributed data storage

A relay station for being operative in a mobile communication system, comprising a receiver for receiving a radio signal from a source, the radio signal comprising symbols representing an encoded information, the encoded information being based on an encoding rule and comprising payload information and redundancy information. The relay station comprising a soft detector for detecting a symbol from the radio signal to obtain soft information, the soft information comprising information on the symbol and reliability information on the information on the symbol. The relay station further comprising a quantizer for quantizing the soft information to obtain quantized soft information and a transmitter for transmitting an information on the quantized soft information to a destination.

Relay station for a mobile communication system

An encoder structure for an error correcting code with arbitrary parity positions is presented. The invention is effective for all error correcting codes whose parity check matrix is of the Vandermonde type. In contrast to conventional encoder circuits, the parity symbols produced by this encoder are not restricted to form a block of consecutive parity symbols at the beginning or at the end of a codeword, but may be spread arbitrarily within the codeword. A general structure of the parity check matrix for such a code is found by exploiting the special Vandermonde structure of matrices. From this general parity check matrix, an expression for the evaluation of the parity symbols in terms of a polynomial with limited degree is derived. An efficient hardware implementation of the proposed encoder is suggested.

Systematic encoder with arbitrary parity positions

In some aspects, a method of automated base-calling using at least one image obtained from a chemical sequencing process performed simultaneously on a plurality of DNA strands, the at least one image including intensity information corresponding to locations of at least one base in the plurality of DNA strands is provided. The method comprises processing the at least image to obtain a function corresponding to the intensity information in the at least one image for the at least one base, the function incorporating intensity information corresponding to each of the plurality of DNA strands, identifying a plurality of peaks in the function, the plurality of peaks indicating possible locations for the at least one base in the plurality of DNA strands, assigning membership to each of the plurality of peaks by determining whether each of the plurality of peaks is believed to have resulted from none, one or multiple of the plurality of DNA strands, and computing a sequence for the at least one base for each of the plurality of DNA strands based, at least in part, on the membership assignment.

Methods and apparatus for automated base-calling on multiple DNA strands

A network and a method for transmitting processes in a network are disclosed, where a randomized coding approach is provided. Network nodes transmit on each outgoing link a linear combination of incoming signals, specified by independently and randomly chosen code coefficients from a finite field. The approach allows robust, distributed transmission and compression of information in networks and is advantageous over routing-based approaches.

Randomized distributed network coding

A method and computer program product for performing minimum cost routing with network coding is presented. The method and system model a network as a directed graph. A cost per unit flow is associated with each link of the directed graph. A link capacity is associated with each link of the directed graph. A network code is then computed that sets up a routing connection that achieves an optimal cost using the cost per unit flow for each link of the directed graph and using the link capacity for each link of the directed graph.

Minimum-cost routing with network coding

A method and device employing an iterative MMSE equalization-decoder soft information exchange decoding. The method uses a MMSE equalizer which receives and outputs soft information. The equalizer exchanges soft information with a soft input soft output decoder, preferably an error correction decoder. The nature of the equalizer permits solutions beyond one-dimensional data streams and permits solutions for long channel lengths and multi-dimensional data since the solution is not a function of the channel impulse response.

Iterative MMSE equalization-decoder soft information exchange decoding method and device

An algorithmic soft-decision decoding method for Reed-Solomon codes proceeds as follows. Given the reliability matrix &Pi; showing the probability that a code symbol of a particular value was transmitted at each position, computing a multiplicity matrix M which determines the interpolation points and their multiplicities. Given this multiplicity matrix M, soft interpolation is performed to find the non-trivial polynomial Q (X,Y) of the lowest (weighted) degree whose zeros and their multiplicities are as specified by the matrix M. Given this non-trivial polynomial Q (X,Y), all factors of Q (X,Y) of type Y&minus;&fnof;(X) are found, where &fnof;(X) is a polynomial in X whose degree is less than the dimension k of the Reed-Solomon code. Given these polynomials &fnof;(X), a codeword is reconstructed from each of them, and the most likely of these codewords selected as the output of the algorithm. The algorithmic method is algebraic, operates in polynomial time, and significantly outperforms conventional hard-decision decoding, generalized minimum distance decoding, and Guruswami-Sudan decoding of Reed-Solomon codes. By varying the total number of interpolation points recorded in the multiplicity matrix M, the complexity of decoding can be adjusted in real time to any feasible level of performance. The algorithmic method extends to algebraic soft-decision decoding of Bose-Chaudhuri-Hocquenghem codes and algebraic-geometry codes.

Growing community of inventors

Champaign, IL, United States of America

Ralf Koetter