waashk/dblp huggingface dataset:
separating distributed source coding from network coding. this correspondence considers the problem of distributed source coding of multiple sources over a network with multiple receivers. each receiver seeks to reconstruct all of the original sources. the work by ho et al. 2004 demonstrates that random network coding can solve this problem at the potentially high cost of jointly decoding the source and the network code. motivated by complexity considerations we consider the performance of separate source and network codes. previous work by effros et al. 2003 demonstrates the failure of separation between source and network codes for nonmulticast networks.we demonstrate that failure for multicast networks. we study networks with capacity constraints on edges. it is shown that the problem with two sources and two receivers is always separable. counterexamples are presented for other cases.
distributed network protocols. the primary topic of this dissertation is disjoint np-pairs. a disjoint np-pair is a pair of disjoint, nonempty sets in np. the study of disjoint np-pairs is motivated by its connections to secure public-key cryptosystems and to propositional proof complexity. one fundamental question in the study of disjoint np-pairs is whether there exist p-inseparable or np-hard disjoint np-pairs. this question is closely related to the existence of secure public-key cryptosystems. another important question on disjoint np-pairs is whether the class of all disjoint np-pairs has a complete pair. a negative answer to this question would imply non-existence of optimal propositional proof systems, which is a well-studied but still open question in proof theory. we study these questions and obtain results that give better understandings of these questions, as well as the relations between disjoint np-pairs and propositional proof systems. in particular, we show that the above questions cannot be settled with relativizable techniques. it has been recently known that the degree structure of disjoint np-pairs is identical to the degree structure of canonical np-pairs of propositional proof systems. this makes it interesting and important to study the degree structure of disjoint np-pairs. we study this and prove that the degree structure of disjoint np-pairs is "universal'' in the sense that every countable distributive lattice can be embedded into every interval of degrees of disjoint np-pairs by maps that preserve the least or greatest elements. we also study the question how much information canonical np-pairs contain of their corresponding propositional proof systems. we obtain various results demonstrating that canonical np-pairs reflect the properties of their corresponding propositional proof systems, but only to certain extent. the secondary topic of this dissertation is structural properties of complete sets. what structural properties complete sets of different complexity classes have is a basic problem in computational complexity. it is important to study such computational structure of complete sets, because they, by reductions of all the sets in the class to the complete sets, represent all of the structure that a class might have. for this reason, the study of structural properties of complete sets gave us a better understanding of the computational power of various complexity classes, and also might lead to proofs of separation results in complexity theory. we mainly study robustness, autoreducibility, and mitoticity of complete sets. in particular we solve the open question whether polynomial 2-tt autoreducibilty implies polynomial-time 2-tt mitoticity.
raptor codes. lt-codes are a new class of codes introduced by luby for the purpose of scalable and fault-tolerant distribution of data over computer networks. in this paper, we introduce raptor codes, an extension of lt-codes with linear time encoding and decoding. we will exhibit a class of universal raptor codes: for a given integer k and any real ε > 0, raptor codes in this class produce a potentially infinite stream of symbols such that any subset of symbols of size k(1 + ε) is sufficient to recover the original k symbols with high probability. each output symbol is generated using o(log(1/ ε)) operations, and the original symbols are recovered from the collected ones with o(k log(1/ε)) operations.we will also introduce novel techniques for the analysis of the error probability of the decoder for finite length raptor codes. moreover, we will introduce and analyze systematic versions of raptor codes, i.e., versions in which the first output elements of the coding system coincide with the original k elements.
bandwidth- and power-efficient routing in linear wireless networks. the goal of this paper is to establish which practical routing schemes for wireless networks are most suitable for power-limited and bandwidth-limited communication regimes. we regard channel state information (csi) at the receiver and point-to-point capacity-achieving codes for the additive white gaussian noise (awgn) channel as practical features, interference cancellation (ic) as possible, but less practical, and synchronous cooperation (csi at the transmitters) as impractical. we consider a communication network with a single source node, a single destination node, and n-1 intermediate nodes placed equidistantly on a line between them. we analyze the minimum total transmit power needed to achieve a desired end-to-end rate for several schemes and demonstrate that multihop communication with spatial reuse performs very well in the power-limited regime, even without ic. however, within a class of schemes not performing ic, single-hop transmission (directly from source to destination) is more suitable for the bandwidth-limited regime, especially when higher spectral efficiencies are required. at such higher spectral efficiencies, the gap between single-hop and multihop can be closed by employing ic, and we present a scheme based upon backward decoding that can remove all interference from the multihop system with an arbitrarily small rate loss. this new scheme is also used to demonstrate that rates of o(log n) are achievable over linear wireless networks even without synchronous cooperation.
asymptotic analysis of multistage cooperative broadcast in wireless networks. cooperative broadcast aims to deliver a source message to a locally connected network by means of collaborating nodes. in traditional architectures, node cooperation has been at the network layer. recently, physical layer cooperative schemes have been shown to offer several advantages over the network layer approaches. this form of cooperation employs distributed transmission resources at the physical layer as a single radio with spatial diversity. in decentralized cooperation schemes, collaborating nodes make transmission decisions based on the quality of the received signal, which is the only parameter available locally. in this case, critical parameters that influence the broadcast performance include the source/relay transmission powers and the decoding threshold (the minimum signal-to-noise ratio (snr) required to decode a transmission). we study the effect of these parameters on the number of nodes reached by cooperative broadcast. in particular, we show that there exists a phase transition in the network behavior: if the decoding threshold is below a critical value, the message is delivered to the whole network. otherwise, only a fraction of the nodes is reached, which is proportional to the source transmit power. our approach is based on the idea of continuum approximation, which yields closed-form expressions that are accurate when the network density is high.
capacity of queues via point-process channels. a conceptually simple proof for the capacity formula of an exponential server timing channel is provided. the proof links the timing channel to the point-process channel with instantaneous noiseless feedback. this point-process approach enables a study of timing channels that arise in multiserver queues, queues in tandem, and other simple configurations. although the capacities of such channels remain to be found, the paper provides some analytical bounds and highlights a method to find achievable rates via simulations.
design of some new efficient balanced codes. a balanced code with r check bits and k information bits is a binary code of length k+r and cardinality 2k such that each codeword is balanced; that is, it has [k+ r/1] 1''s and [k+r /2] 0''s. this paper contains new methods to construct efficient balance codes based on the concept of tail-map. a tail-map is and injective function from the set of the very unbalanced words to the set of the balanced ones. to design balanced codes, those information words with a low number of 1''s or 0''s are encoded using tail-maps, while those that have almost the same number of 1''s and 0''s are encoded using the single maps defined by knuth''s complementation method. three different tail-map constructions are presented. balanced codes with r check bits and k > 2r +1-2, k > 3.2r -8 and k > 5.2r -10r + c(r )(c(r )e{ -15,-10,-5, 0,+5}) information bits are given, improving the constructions found in the literature. the tail-maps used in the first two constructions can be computed using a parallel scheme. key words: balanced codes, data integrity, data synchronization, dc-free codes, unidirectional errors. cstr 93-60-19 jiang zhu, lihua zhao, ted lewis, weldon jackson, and russel wilson, "harts: hard real-time software development environment we introduce a hard real-time software development environment, called harts, which consists of a design tool and a scheduling tool. the design tool supports a hierarchical design diagram which combines the control and data flow of a hard real-time application. the design hierarchy separates a design into self-contained subdesigns. yet, the design can be flattened to give you a global view. in a distributed environment, the hierarchy provides a natural way for assigning subdesigns to different processors. the design diagram is quite intuitive, and yet it can be automatically analyzed for scheduleability. the scheduling tool schedules task graphs (directed acyclic graphs whose nodes are periodic tasks) with its heuristic algorithms which try to use as few processors as possible to meet both the timing and precedence constraints. based on a generated schedule, the scheduling tool can further simulate the task execution with highly animated user interfaces, which goes beyond the traditional way of examining a schedule as a static gannett chart. although the design tool and the scheduling tool has not been fully integrated, we show that the current scheduling tool can be easily extended to schedule the precedence-constrained periodic task set derived from a design diagram. keywords: real-time, hard real-time, hard real-time system design, real-time control, scheduling, real-time scheduling, hard real-time scheduling.
a unification of network coding and tree-packing (routing) theorems. given a network of lossless links with rate constraints, a source node, and a set of destination nodes, the multicast capacity is the maximum rate at which the source can transfer common information to the destinations. the multicast capacity cannot exceed the capacity of any cut separating the source from a destination; the minimum of the cut capacities is called the cut bound. a fundamental theorem in graph theory by edmonds established that if all nodes other than the source are destinations, the cut bound can be achieved by routing. in general, however, the cut bound cannot be achieved by routing. ahlswede et al. established that the cut bound can be achieved by performing network coding, which generalizes routing by allowing information to be mixed. this paper presents a unifying theorem that includes edmonds' theorem and ahlswede et al.'s theorem as special cases. specifically, it shows that the multicast capacity can still be achieved even if information mixing is only allowed on edges entering relay nodes. this unifying theorem is established via a graph theoretic hardwiring theorem, together with the network coding theorems for multicasting. the proof of the hardwiring theorem implies a new proof of edmonds' theorem.
on the path-loss attenuation regime for positive cost and linear scaling of transport capacity in wireless networks. wireless networks with a minimum inter-node separation distance are studied where the signal attenuation grows in magnitude as 1/ρδ with distance ρ. two performance measures of wireless networks are analyzed. the transport capacity is the supremum of the total distance-rate products that can be supported by the network. the energy cost of information transport is the infimum of the ratio of the transmission energies used by all the nodes to the number of bit-meters of information thereby transported.if the phases of the attenuations between node pairs are uniformly and independently distributed, it is shown that the expected transport capacity is upper-bounded by a multiple of the total of the transmission powers of all the nodes, whenever δ > 2 for two-dimensional networks or δ > 5/4 for one-dimensional networks, even if all the nodes have full knowledge of all the phases, i.e., full channel state information. if all nodes have an individual power constraint, the expected transport capacity grows at most linearly in the number of nodes due to the linear growth of the total power. this establishes the best case order of expected transport capacity for these ranges of path-loss exponents since linear scaling is also feasible.if the phases of the attenuations are arbitrary, it is shown that the transport capacity is upper-bounded by a multiple of the total transmission power whenever δ > 5/2 for two-dimensional networks or δ > 3/2 for one-dimensional networks, even if all the nodes have full channel state information. this shows that there is indeed a positive energy cost which is no less than the reciprocal of the above multiplicative constant. it narrows the transition regime where the behavior is still open, since it is known that when δ < 3/2 for two-dimensional networks, or δ < 1 for one-dimensional networks, the transport capacity cannot generally be bounded by any multiple of the total transmit power.
an outer bound for multisource multisink network coding with minimum cost consideration. the max-flow min-cut bound is a fundamental result in the theory of communication networks, which characterizes the optimal throughput for a point-to-point communication network. the recentwork of ahlswede et al. extended it to single-source multisink multicast networks and li et al. proved that this bound can be achieved by linear codes. following this line, erez and feder as well as ngai and yeung proved that the max-flow min-cut bound remains tight in single-source two-sink nonmulticast networks. but the max-flow min-cut bound is in general quite loose (see yeung, 2002). on the other hand, the admissible rate region of communication networks has been studied by yeung and zhang as well as song and yeung, but the bounds obtained by these authors are not explicit. in this work, we prove a new explicit outer bound for arbitrary multisource multisink networks and demonstrate its relation with the minimum cost network coding problem. we also determine the capacity region for a special class of three-layer networks.
properties and applications of preimage distributions of perfect nonlinear functions. the preimage distributions of perfect nonlinear functions from an abelian group of order n to an abelian group of order 3 or 4, respectively, are studied. based on the properties of the preimage distributions of perfect nonlinear functions from an abelian group of order 3r to an abelian group of order 3, the weight distributions of the ternary linear codes cπ from the perfect nonlinear functions π(x) from f3r to itself are determined. these results suggest that two open problems, proposed by carlet, ding, and yuan in 2005 and 2006, respectively, are answered.
optimal constellations for the low-snr noncoherent mimo block rayleigh-fading channel. reliable communication over the discrete-input/continuous-output noncoherent multiple-input multiple-output (mimo) rayleigh block-fading channel is considered when the signal-to-noise ratio (snr) per degree of freedom is low. two key problems are posed and solved to obtain the optimum discrete input. in both problems, the average and peak power per space-time slot of the input constellation are constrained. in the first one, the peak power to average power ratio (ppapr) of the input constellation is held fixed, while in the second problem, the peak power is fixed independently of the average power. in the first ppapr-constrained problem, the mutual information, which grows as o(snr2), is maximized up to second order in snr. in the second peak-constrained problem, where the mutual information behaves as o(snr), the structure of constellations that are optimal up to first order, or equivalently, that minimize energy per bit, are explicitly characterized. furthermore, among constellations that are first-order optimal, those that maximize the mutual information up to second order, or equivalently, the wideband slope, are characterized. in both ppapr-constrained and peak-constrained problems, the optimal constellations are obtained in closed form as solutions to nonconvex optimizations, and interestingly, they are found to be identical. due to its special structure, the common solution is referred to as space-time orthogonal rank one modulation, or storm. in both problems, it is seen that storm provides a sharp characterization of the behavior of noncoherent mimo capacity.
recursive space-time trellis codes using differential encoding. differential space-time modulation (dstm) has been recently proposed by hughes, and hochwald and sweldens when the channel information is not known at the receiver, where the demodulation is in fact the same as the coherent demodulation of space-time block coding by replacing the channel matrix with the previously received signal matrix. on the other hand, the dstm also needs a recursive memory of a matrix block at the encoder and therefore provides a trellis structure when the channel information is known at the receiver, which is the interest of this paper. this recursive structure of the dstm has been adopted lately by schlegel and grant in joint with a conventional binary code and joint iterative decoding/demodulation with a superior performance. the number of states of the trellis from the recursive structure depends on both the memory size, which is fixed in this case, and the unitary space-time code (ustc). when a ustc for the dstm forms a group, the number of states is the same as the size of the ustc, otherwise the number of the states is the size of the semi-group generated by the ustc from all the multiplications of the matrices in the ustc. it is well known in the conventional convolutional coding (cc) or the trellis coded modulation (tcm), the free (hamming or euclidean) distance (or the performance) increases when the number of states increases by adding more memory with a properly designed cc or tcm. in this paper, we systematically study and design the ustc/dstm for the recursive space-time trellis modulation and show that the diversity product increases when the number of states increases, which is not because of the memory size but because of the different ustc designs that generate different sizes of semi-groups. we propose a new ustc design criterion to ensure that the trellis structure improves the diversity product over the ustc as a block code. based on the new criterion, we propose a new class of ustc design for an arbitrary number of transmit antennas that has an analytical diversity product formula for two transmit antennas. we then follow schlegel and grant's approach for joint encoding and iterative decoding of a binary coded dstm (turbo space-time coding) and numerically show that our new ustc designs for the recursive space-time trellis modulation outperforms the group ustc used by schlegel and grant.
joint source-channel coding excess distortion exponent for some memoryless continuous-alphabet systems. we investigate the joint source-channel coding (jscc) excess distortion exponent ej (the exponent of the probability of exceeding a prescribed distortion level) for some memoryless communication systems with continuous alphabets. we first establish upper and lower bounds for ej for systems consisting of a memoryless gaussian source under the squared-error distortion fidelity criterion and a memoryless additive gaussian noise channel with a quadratic power constraint at the channel input. a necessary and sufficient condition for which the two bounds coincide is provided, thus exactly determining the exponent. this condition is observed to hold for a wide range of source-channel parameters. as an application, we study the advantage in terms of the excess distortion exponent of jscc over traditional tandem (separate) coding for gaussian systems. a formula for the tandem exponent is derived in terms of the gaussian source and gaussian channel exponents, and numerical results show that jscc often substantially outperforms tandem coding. the problem of transmitting memoryless laplacian sources over the gaussian channel under the magnitude-error distortion is also carried out. finally, we establish a lower bound for ej for a certain class of continuous source-channel pairs when the distortion measure is a metric.
random sensory networks: a delay analysis. a fundamental function performed by a sensory network is the retrieval of data gathered collectively by sensor nodes. the metrics that measure the efficiency of this data collection process are time and energy. in this paper, we study via simple discrete mathematical models, the statistics of the data collection time in sensory networks. specifically, we analyze the average minimum delay in collecting randomly located/distributed sensors data for networks of various topologies when the number of nodes becomes large. furthermore, we analyze the impact of various parameters such as size of packet, transmission range, and channel erasure probability on the optimal time performance. our analysis applies to directional antenna systems as well as omnidirectional ones. this paper focuses on directional antenna systems and briefly presents results on omnidirectional antenna systems. finally, a simple comparative analysis shows the respective advantages of the two systems.
a finite-length algorithm for ldpc codes without repeated edges on the binary erasure channel. this paper considers the performance, on the binary erasure channel, of low-density parity-check (ldpc) codes without repeated edges in their tanner graphs. a modification to existing finite-length analysis algorithms is presented for these codes.