On Network-Error Correcting Convolutional Codes under the BSC Edge Error Model

Convolutional network-error correcting codes (CNECCs) are known to provide error correcting capability in acyclic instantaneous networks within the network coding paradigm under small field size conditions. In this work, we investigate the performance of CNECCs under the error model of the network where the edges are assumed to be statistically independent binary symmetric channels, each with the same probability of error pe(0 <= p(e) < 0.5). We obtain bounds on the performance of such CNECCs based on a modified generating function (the transfer function) of the CNECCs. For a given network, we derive a mathematical condition on how small p(e) should be so that only single edge network-errors need to be accounted for, thus reducing the complexity of evaluating the probability of error of any CNECC. Simulations indicate that convolutional codes are required to possess different properties to achieve good performance in low p(e) and high p(e) regimes. For the low p(e) regime, convolutional codes with good distance properties show good performance. For the high p(e) regime, convolutional codes that have a good slope ( the minimum normalized cycle weight) are seen to be good. We derive a lower bound on the slope of any rate b/c convolutional code with a certain degree.

Network Error Correction for Unit-Delay, Memory-Free Networks Using Convolutional Codes

A single source network is said to be memory-free if all of the internal nodes (those except the source and the sinks) do not employ memory but merely send linear combinations of the symbols received at their incoming edges on their outgoing edges. In this work, we introduce network-error correction for single source, acyclic, unit-delay, memory-free networks with coherent network coding for multicast. A convolutional code is designed at the source based on the network code in order to correct network- errors that correspond to any of a given set of error patterns, as long as consecutive errors are separated by a certain interval which depends on the convolutional code selected. Bounds on this interval and the field size required for constructing the convolutional code with the required free distance are also obtained. We illustrate the performance of convolutional network error correcting codes (CNECCs) designed for the unit-delay networks using simulations of CNECCs on an example network under a probabilistic error model.

Distributed Space Time Coding for Wireless Two-Way Relaying

We consider the wireless two-way relay channel, in which two-way data transfer takes place between the end nodes with the help of a relay. For the Denoise-And-Forward (DNF) protocol, it was shown by Koike-Akino et al. that adaptively changing the network coding map used at the relay greatly reduces the impact of Multiple Access Interference at the relay. The harmful effect of the deep channel fade conditions can be effectively mitigated by proper choice of these network coding maps at the relay. Alternatively, in this paper we propose a Distributed Space Time Coding (DSTC) scheme, which effectively removes most of the deep fade channel conditions at the transmitting nodes itself without any CSIT and without any need to adaptively change the network coding map used at the relay. It is shown that the deep fades occur when the channel fade coefficient vector falls in a finite number of vector subspaces of, which are referred to as the singular fade subspaces. DSTC design criterion referred to as the singularity minimization criterion under which the number of such vector subspaces are minimized is obtained. Also, a criterion to maximize the coding gain of the DSTC is obtained. Explicit low decoding complexity DSTC designs which satisfy the singularity minimization criterion and maximize the coding gain for QAM and PSK signal sets are provided. Simulation results show that at high Signal to Noise Ratio, the DSTC scheme provides large gains when compared to the conventional Exclusive OR network code and performs better than the adaptive network coding scheme.

Network-error correcting codes using small fields

Recently, Ebrahimi and Fragouli proposed an algorithm to construct scalar network codes using small fields (and vector network codes of small lengths) satisfying multicast constraints in a given single-source, acyclic network. The contribution of this paper is two fold. Primarily, we extend the scalar network coding algorithm of Ebrahimi and Fragouli (henceforth referred to as the EF algorithm) to block network-error correction. Existing construction algorithms of block network-error correcting codes require a rather large field size, which grows with the size of the network and the number of sinks, and thereby can be prohibitive in large networks. We give an algorithm which, starting from a given network-error correcting code, can obtain another network code using a small field, with the same error correcting capability as the original code. Our secondary contribution is to improve the EF Algorithm itself. The major step in the EF algorithm is to find a least degree irreducible polynomial which is coprime to another large degree polynomial. We suggest an alternate method to compute this coprime polynomial, which is faster than the brute force method in the work of Ebrahimi and Fragouli.

Wireless Network-Coded Bidirectional Relaying Using Latin Squares for M-PSK Modulation

The design of modulation schemes for the physical layer network-coded two-way relaying scenario is considered with a protocol which employs two phases: multiple access (MA) phase and broadcast (BC) phase. It was observed by Koike-Akino et al. that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of MA interference which occurs at the relay during the MA phase and all these network coding maps should satisfy a requirement called the exclusive law. We show that every network coding map that satisfies the exclusive law is representable by a Latin Square and conversely, that this relationship can be used to get the network coding maps satisfying the exclusive law. The channel fade states for which the minimum distance of the effective constellation at the relay become zero are referred to as the singular fade states. For M - PSK modulation (M any power of 2), it is shown that there are (M-2/4 - M/2 + 1) M singular fade states. Also, it is shown that the constraints which the network coding maps should satisfy so that the harmful effects of the singular fade states are removed, can be viewed equivalently as partially filled Latin Squares (PFLS). The problem of finding all the required maps is reduced to finding a small set of maps for M - PSK constellations (any power of 2), obtained by the completion of PFLS. Even though the completability of M x M PFLS using M symbols is an open problem, specific cases where such a completion is always possible are identified and explicit construction procedures are provided. Having obtained the network coding maps, the set of all possible channel realizations (the complex plane) is quantized into a finite number of regions, with a specific network coding map chosen in a particular region. It is shown that the complex plane can be partitioned into two regions: a region in which any network coding map which satisfies the exclusive law gives the same best performance and a region in which the choice of the network coding map affects the performance. The quantization thus obtained analytically, leads to the same as the one obtained using computer search for M = 4-PSK signal set by Koike-Akino et al., when specialized for Simulation results show that the proposed scheme performs better than the conventional exclusive-OR (XOR) network coding and in some cases outperforms the scheme proposed by Koike-Akino et al.

On the feasibility of network alignment for three-source three-destination Multiple Unicast networks with delays

A transform approach to network coding was in-troduced by Bavirisetti et al. (arXiv:1103.3882v3 [cs.IT]) as a tool to view wireline networks with delays as k-instantaneous networks (for some large k). When the local encoding kernels (LEKs) of the network are varied with every time block of length k >1, the network is said to use block time varying LEKs. In this work, we propose a Precoding Based Network Alignment (PBNA) scheme based on transform approach and block time varying LEKs for three-source three-destination multiple unicast network with delays (3-S3-D MUN-D). In a recent work, Menget al. (arXiv:1202.3405v1 [cs.IT]) reduced the infinite set of sufficient conditions for feasibility of PBNA in a three-source three-destination instantaneous multiple unicast network as given by Das et al. (arXiv:1008.0235v1 [cs.IT]) to a finite set and also showed that the conditions are necessary. We show that the conditions of Meng et al. are also necessary and sufficient conditions for feasibility of PBNA based on transform approach and block time varying LEKs for 3-S3-D MUN-D.

Wireless network-coded accumulate-compute and forward two-way relaying

The design of modulation schemes for the physical layer network-coded two way wireless relaying scenario is considered. It was observed by Koike-Akino et al. for the two way relaying scenario, that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of multiple access interference which occurs at the relay during the MA Phase and all these network coding maps should satisfy a requirement called exclusive law. We extend this approach to an Accumulate-Compute and Forward protocol which employs two phases: Multiple Access (MA) phase consisting of two channel uses with independent messages in each channel use, and Broadcast (BC) phase having one channel use. Assuming that the two users transmit points from the same 4-PSK constellation, every such network coding map that satisfies the exclusive law can be represented by a Latin Square with side 16, and conversely, this relationship can be used to get the network coding maps satisfying the exclusive law. Two methods of obtaining this network coding map to be used at the relay are discussed. Using the structural properties of the Latin Squares for a given set of parameters, the problem of finding all the required maps is reduced to finding a small set of maps. Having obtained all the Latin Squares, the set of all possible channel realizations is quantized, depending on which one of the Latin Squares obtained optimizes the performance. The quantization thus obtained, is shown to be the same as the one obtained in [7] for the 2-stage bidirectional relaying.

Wireless network-coded three-way relaying using Latin Cubes

The design of modulation schemes for the physical layer network-coded three-way wireless relaying scenario is considered. The protocol employs two phases: Multiple Access (MA) phase and Broadcast (BC) phase with each phase utilizing one channel use. For the two-way relaying scenario, it was observed by Koike-Akino et al. [4], that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of multiple access interference which occurs at the relay during the MA phase and all these network coding maps should satisfy a requirement called exclusive law. This paper does the equivalent for the three-way relaying scenario. We show that when the three users transmit points from the same 4-PSK constellation, every such network coding map that satisfies the exclusive law can be represented by a Latin Cube of Second Order. The network code map used by the relay for the BC phase is explicitly obtained and is aimed at reducing the effect of interference at the MA stage.

A matroidal framework for network-error correcting codes

Matroidal networks were introduced by Dougherty et al. and have been well studied in the recent past. It was shown that a network has a scalar linear network coding solution if and only if it is matroidal associated with a representable matroid. The current work attempts to establish a connection between matroid theory and network-error correcting codes. In a similar vein to the theory connecting matroids and network coding, we abstract the essential aspects of network-error correcting codes to arrive at the definition of a matroidal error correcting network. An acyclic network (with arbitrary sink demands) is then shown to possess a scalar linear error correcting network code if and only if it is a matroidal error correcting network associated with a representable matroid. Therefore, constructing such network-error correcting codes implies the construction of certain representable matroids that satisfy some special conditions, and vice versa.

An asymptotically optimal push-pull method for multicasting over a random network

We consider multicast flow problems where either all of the nodes or only a subset of the nodes may be in session. Traffic from each node in the session has to be sent to every other node in the session. If the session does not consist of all the nodes, the remaining nodes act as relays. The nodes are connected by undirected edges whose capacities are independent and identically distributed random variables. We study the asymptotics of the capacity region (with network coding) in the limit of a large number of nodes, and show that the normalized sum rate converges to a constant almost surely. We then provide a decentralized push-pull algorithm that asymptotically achieves this normalized sum rate.

Channel quantization for physical layer network-coded two-way relaying

The design of modulation schemes for the physical layer network-coded two way relaying scenario is considered with the protocol which employs two phases: Multiple access (MA) Phase and Broadcast (BC) phase. It was observed by Koike-Akino et al. that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of multiple access interference which occurs at the relay during the MA phase. In other words, the set of all possible channel realizations (the complex plane) is quantized into a finite number of regions, with a specific network coding map giving the best performance in a particular region. We obtain such a quantization analytically for the case when M-PSK (for M any power of 2) is the signal set used during the MA phase. We show that the complex plane can be classified into two regions: a region in which any network coding map which satisfies the so called exclusive law gives the same best performance and a region in which the choice of the network coding map affects the performance, which is further quantized based on the choice of the network coding map which optimizes the performance. The quantization thus obtained analytically, leads to the same as the one obtained using computer search for 4-PSK signal set by Koike-Akino et al., for the specific value of M = 4.

Precoding-Based Network Alignment Using Transform Approach for Acyclic Networks With Delay

The algebraic formulation for linear network coding in acyclic networks with the links having integer delay is well known. Based on this formulation, for a given set of connections over an arbitrary acyclic network with integer delay assumed for the links, the output symbols at the sink nodes, at any given time instant, is a F(p)m-linear combination of the input symbols across different generations, where F(p)m denotes the field over which the network operates (p is prime and m is a positive integer). We use finite-field discrete Fourier transform to convert the output symbols at the sink nodes, at any given time instant, into a F(p)m-linear combination of the input symbols generated during the same generation without making use of memory at the intermediate nodes. We call this as transforming the acyclic network with delay into n-instantaneous networks (n is sufficiently large). We show that under certain conditions, there exists a network code satisfying sink demands in the usual (nontransform) approach if and only if there exists a network code satisfying sink demands in the transform approach. When the zero-interference conditions are not satisfied, we propose three precoding-based network alignment (PBNA) schemes for three-source three-destination multiple unicast network with delays (3-S 3-D MUN-D) termed as PBNA using transform approach and time-invariant local encoding coefficients (LECs), PBNA using time-varying LECs, and PBNA using transform approach and block time-varying LECs. We derive sets of necessary and sufficient conditions under which throughputs close to n' + 1/2n' + 1, n'/2n' + 1, and n'/2n' + 1 are achieved for the three source-destination pairs in a 3-S 3-D MUN-D employing PBNA using transform approach and time-invariant LECs, and PBNA using transform approach and block time-varying LECs, where n' is a positive integer. For PBNA using time-varying LECs, we obtain a sufficient condition under which a throughput demand of n(1)/n, n(2)/n, and n(3)/n can be met for the three source-destination pairs in a 3-S 3-D MUN-D, where n(1), n(2), and n(3) are positive integers less than or equal to the positive integer n. This condition is also necessary when n(1) + n(3) = n(1) + n(2) = n where n(1) >= n(2) >= n(3).

A Matroidal Framework for Network-Error Correcting Codes

Matroidal networks were introduced by Dougherty et al. and have been well studied in the recent past. It was shown that a network has a scalar linear network coding solution if and only if it is matroidal associated with a representable matroid. A particularly interesting feature of this development is the ability to construct (scalar and vector) linearly solvable networks using certain classes of matroids. Furthermore, it was shown through the connection between network coding and matroid theory that linear network coding is not always sufficient for general network coding scenarios. The current work attempts to establish a connection between matroid theory and network-error correcting and detecting codes. In a similar vein to the theory connecting matroids and network coding, we abstract the essential aspects of linear network-error detecting codes to arrive at the definition of a matroidal error detecting network (and similarly, a matroidal error correcting network abstracting from network-error correcting codes). An acyclic network (with arbitrary sink demands) is then shown to possess a scalar linear error detecting (correcting) network code if and only if it is a matroidal error detecting (correcting) network associated with a representable matroid. Therefore, constructing such network-error correcting and detecting codes implies the construction of certain representable matroids that satisfy some special conditions, and vice versa. We then present algorithms that enable the construction of matroidal error detecting and correcting networks with a specified capability of network-error correction. Using these construction algorithms, a large class of hitherto unknown scalar linearly solvable networks with multisource, multicast, and multiple-unicast network-error correcting codes is made available for theoretical use and practical implementation, with parameters, such as number of information symbols, number of sinks, number of coding nodes, error correcting capability, and so on, being arbitrary but for computing power (for the execution of the algorithms). The complexity of the construction of these networks is shown to be comparable with the complexity of existing algorithms that design multicast scalar linear network-error correcting codes. Finally, we also show that linear network coding is not sufficient for the general network-error correction (detection) problem with arbitrary demands. In particular, for the same number of network errors, we show a network for which there is a nonlinear network-error detecting code satisfying the demands at the sinks, whereas there are no linear network-error detecting codes that do the same.

Wireless Network-Coded Accumulate-Compute-and-Forward Two-Way Relaying

For the physical-layer network-coded wireless two-way relaying, it was observed by Koike-Akino et al. that adaptively changing the network coding map used at the relay according to channel conditions greatly reduces the impact of multiple-access interference, which occurs at the relay, and all these network coding maps should satisfy a requirement called exclusive law. We extend this approach to an accumulate-compute-and-forward protocol, which employs two phases: a multiple access (MA) phase consisting of two channel uses with independent messages in each channel use and a broadcast (BC) phase having one channel use. Assuming that the two users transmit points from the same 4-phase-shift keying (PSK) constellation, every such network coding map that satisfies the exclusive law can be represented by a Latin square of side 16, and conversely, this relationship can be used to get the network coding maps satisfying the exclusive law. Two methods of obtaining this network coding map to be used at the relay are discussed. Using the structural properties of the Latin squares for a given set of parameters, the problem of finding all the required maps is reduced to finding a small set of maps for the case. Having obtained all the Latin squares, a criterion is provided to select a Latin square for a given realization of fade state. This criterion turns out to be the same as the one used byMuralidharan et al. for two-stage bidirectional relaying.

SDC: Scalable description coding for adaptive streaming media

Video compression techniques enable adaptive media streaming over heterogeneous links to end-devices. Scalable Video Coding (SVC) and Multiple Description Coding (MDC) represent well-known techniques for video compression with distinct characteristics in terms of bandwidth efficiency and resiliency to packet loss. In this paper, we present Scalable Description Coding (SDC), a technique to compromise the tradeoff between bandwidth efficiency and error resiliency without sacrificing user-perceived quality. Additionally, we propose a scheme that combines network coding and SDC to further improve the error resiliency. SDC yields upwards of 25% bandwidth savings over MDC. Additionally, our scheme features higher quality for longer durations even at high packet loss rates.