In the paradigm of network coding, when the network topology information cannot be utilized completely, random linear network coding (RLNC) is proposed as a feasible coding scheme. But since RLNC neither considers the global network topology nor coordinates codings between different nodes, it may not achieve the best possible performance of network coding. Hence, the performance analysis of RLNC is very important for both theoretical research and practical applications. Motivated by a fact that different network topology information can be available for different network communication problems, we study and obtain several upper and lower bounds on the failure probability at sink nodes depending on different network topology information in this paper, which is also the kernel to discuss some other types of network failure probabilities. In addition, we show that the obtained upper bounds are tight, the obtained lower bound is asymptotically tight, and we give the worst cases for different scenarios.

To reduce the cost of fault management in all-optical networks, it is a promising approach to detect the degradation of optical signal quality solely at the terminal points of all-optical monitoring paths. The all-optical monitoring paths must be routed so that all single-link failures can be localized using route information of monitoring paths where signal quality degradation is detected. However, route computation for the all-optical monitoring paths that satisfy the above condition is time consuming. This paper proposes a procedure for deriving the lower bounds of the required number of monitoring paths to localize all single-link failures, and proposes an efficient monitoring path computation method based on the derived lower bounds. The proposed method repeats the route computation for the monitoring paths until feasible routes can be found, while the assumed number of monitoring paths increases, starting from the lower bounds. With the proposed method, the minimum number of monitoring paths with the overall shortest routes can be obtained quickly by solving several small-scale integer linear programming problems when the possible terminal nodes of monitoring paths are arbitrarily given. Thus, the proposed method can minimize the required number of monitors for detecting the degradation of signal quality and the total overhead traffic volume transferred through the monitoring paths.

In this paper, we study lower bounds on the query complexity of testing algorithms for various problems. Given an oracle that returns information of an input object, a testing algorithm distinguishes the case that the object has a given property P from the case that it has a large distance to having P with probability at least . The query complexity of an algorithm is measured by the number of accesses to the oracle. We introduce two reductions that preserve the query complexity. One is derived from the gap-preserving local reduction and the other is from the L-reduction. By using the former reduction, we show linear lower bounds on the query complexity for testing basic NP-complete properties, i.e., 3-edge-colorability, directed Hamiltonian path/cycle, undirected Hamiltonian path/cycle, 3-dimensional matching and NP-complete generalized satisfiability problems. Also, using the second reduction, we show a linear lower bound on the query complexity of approximating the size of the maximum 3-dimensional matching.

In this paper, we investigate the smallest value of p for which a (J,L,p)-QC LDPC code with girth 6 exists for J=3 and J=4. For J=3, we determine the smallest value of p for any L. For J=4, we determine the smallest value of p for L ≤ 301. Furthermore we provide examples of specific constructions meeting these smallest values of p.

Let A(n, d, w) denote the maximum possible number of code words in binary (n,d,w) constant weight codes. For smaller instances of (n, d, w)s, many improvements have occurred over the decades. However, unknown instances still remain for larger (n, d, w)s (for example, those of n > 30 and d > 10). In this paper, we propose a new class of binary constant weight codes that fill in the remaining blank instances of (n, d, w)s. Specifically, we establish several new non-trivial lower bounds such as 336 for A(64, 12, 8), etc. (listed in Table 2). To obtain these results, we have developed a new systematic technique for construction by means of groups acting on some sets. The new technique is performed by considering a triad (G, Ω, f) := ("Group G," "Set Ω," "Action f on Ω") simultaneously. Our results described in Sect. 3 are obtained by using permutations of the elements of a set that include ∞ homogeneously like the other elements, which play a role to improve their randomness. Specifically, in our examples, we adopt the following model such as (PGL2(Fq), P1(Fq), "linear fractional action of subgroups of PGL2(Fq) on P1(Fq)") as a typical construction model. Moreover, as an application, the essential examples in [7] constructed by using an alternating group are again reconstructed with our new technique of a triad model, after which they are all systematically understood in the context of finite subgroups that act fractionally on a projective space over a finite field.

Sequence estimation (SE) of narrow-band digital FM signals, such as CPFSK and GMSK, with non-coherent limiter/discriminator (L/D) and integrate and dump (I&D) detection is investigated in detail using both analysis and simulation. The BER is studied from approximate upper and lower bounds obtained through Chernoff bounding techniques and minimum error event path probability along with a Gaussian noise assumption for high SNR. Various IF filters and the dependence of the error probability upon modulation index are considered. The results show an optimum modulation index around h 0.55, and clearly demonstrate the effectiveness and limitations of sequence estimation.

Consider a random digraph G=(V,A), where |V|=n and an arc (u,v) is present in A with probability p(n) independent of the existence of the other arcs. We discuss the expected number of vertices reachable from a vertex, the expected size of the transitive closure of G and their related topics based on the properties of reachability, where the reachability from a vertex s to t is defined as the probability that s is reachable to t. Let γn,p(n) denote the reachability s to t (s) in the above random digraph G. (In case of s=t, it requires another definition. ) We first present a method of computing the exact value of γn,p(n) for given n and p(n). Since the computation of γn,p(n) by this method requires O(n3) time, we then derive simple upper and lower bounds γn,p(n)U and γn,p(n)L on γn,p(n), respectively, and in addition, we give an upper bound n,p(n) on γn,p(n)U, which is easier to analyze but is still rather accurate. Then, we discuss the asymptotic behavior of n,p(n) and show that, if p(n)=α/(n-1), limnn,p(n) converges to one of the solutions of the equation 1-x-e-α x=0. Furthermore, as for (n) and (n), which are upper bounds on the expected number of reachable vertices and the expected size of the transitive closure of G, resp. , it turns out that limn(n) =α/(1-α) if p(n)=α/(n-1) for 0<α<1; otherwise either 0 or , and limn(n)=α if p(n)=α/(n-1)2 for α0; otherwise either 0 or .

Relations between well-known bounds for the minimum distance of binary cyclic codes such as BCH bound (dBCH), HT bound (dHT) and new bounds dA, dB proposed recently by Shen et al. are investigated. We prove firstly dBCH dA and secondly dHT dB. We also give binary cyclic codes which satisfy dA dHT.

We define two restricted classes of Boolean circuits by assuming the following conditions on underlying graphs of circuits, and prove, for each class, nonlinear lower bounds on size of circuits computing cyclic shifts: for any two paths from the same input to the same output node, the sequences of depths of nodes along these paths are the same. A circuit is partitioned into subcircuits such that each subcircuit has at most o(log n) output gates and the multivalued circuit obtained from the partition is directed tree. These two conditions are driven from different points of view, and lower bounds are established for each one of them.

For a discrete Lyapunov matrix equation, we present another such equation that shares the solution to the original one. This renders some existing lower bounds for measures of the size of the solution meaningful, when they yield only trivial bounds. A generalization of this result is suggested.