Search

Orbit codes, as special constant dimension codes, have attracted much attention due to their applications for error correction in random network coding. This paper is devoted to constructing large orbit codes by making full use of unitary space. Firstly, we construct a cyclic unitary group of order $q^{2n}-1$ by means of the companion matrix of a primitive polynomial over finite fields $\mathbb {F}_{q^{2}}$ , and so the corresponding code is unitary cyclic orbit code. As a special application, a new quaternary orbit code $(6,63,4,3)$ is given. Secondly, we obtain orbit codes with large size using the external direct product of unitary groups acting on the direct sum of subspaces. Finally, a table is given for illustrating our codes improve upon those constructed by Trautmann et al. and Poroch et al.

In this work, we study two classes of quasi-cyclic (QC) codes and examine how several properties can be combined into the codes of these classes. We start with the class of QC codes generated by diagonal generator polynomial matrices; a QC code in this class is a direct sum of cyclic codes. Then we move on to the class of QC codes of index 2; various binary codes with good parameters are found in this class. In each class, we describe the generator polynomial matrices of reversible codes, self-orthogonal codes, and self-dual codes. Hence, we demonstrate how such properties can be merged in codes of these classes. Particularly for QC codes of index 2, we prove a necessary and sufficient condition for the self-orthogonality of reversible codes. Then we show that reversible QC codes of index 2 are self-dual under the same conditions in which self-dual codes are reversible. We clarify that self-orthogonal reversible QC codes of index 2 over $\mathbb {F}_{q}$ exist for even and odd $q$ , however self-dual reversible codes exist only for even $q$ . Theoretical results are reinforced by several numerical examples. Computer search is used to present some self-dual reversible QC codes of index 2 that have the best known parameters as linear codes. Finally, we highlight the class of 1-generator binary QC codes of index 2 by exploring many self-dual reversible codes that achieve the upper bound on the minimum distance for their parameters.

In diffusion-based molecular communication (MC), some of the message molecules may not reach the receiver in their expected time slot due to the diffusion process. These straying molecules from previous time slots interfere with the message molecules of the current time slot which leads to inter-symbol-interference (ISI) in MC. In this paper, we propose and analyze the weighted higher order detector for MC systems to mitigate/reduce the ISI and noise. The proposed weighted higher order sum of molecules concentration enhances the signal-to-noise ratio due to the reduced channel tail and noise effect in a frame. Further, the proposed detector does not estimate instantaneous channel impulse response at the receiver, hence, is simple and has low complexity. Numerical results show that the proposed detector performs better than the conventional direct sum detection method. The impact of diffusion coefficient, number of molecules and noise distribution on the proposed detector is also analyzed.

A locally repairable code with availability has the property that every code symbol can be recovered from multiple, disjoint subsets of other symbols of small size. In particular, a code symbol is said to have $(r,t)$-availability if it can be recovered from $t$ disjoint subsets, each of size at most $r$. A code with availability is said to be 'rate-optimal', if its rate is maximum among the class of codes with given locality, availability, and alphabet size. This paper focuses on rate-optimal binary, linear codes with small availability, and makes four contributions. First, it establishes tight upper bounds on the rate of binary linear codes with $(r,2)$ and $(2,3)$ availability. Second, it establishes a uniqueness result for binary rate-optimal codes, showing that for certain classes of binary linear codes with $(r,2)$ and $(2,3)$-availability, any rate optimal code must be a direct sum of shorter rate optimal codes. Third, it presents novel upper bounds on the rates of binary linear codes with $(2,t)$ and $(r,3)$-availability. In particular, the main contribution here is a new method for bounding the number of cosets of the dual of a code with availability, using its covering properties. Finally, it presents a class of locally repairable linear codes associated with convex polyhedra, focusing on the codes associated with the Platonic solids. It demonstrates that these codes are locally repairable with $t = 2$, and that the codes associated with (geometric) dual polyhedra are (coding theoretic) duals of each other., Shorter version of the paper was presented at ISIT 2017. The updated second version contains a new section on rate upper bounds for binary linear codes with (2,t) and (r,3)-availability

We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity ≤ O(k), and distributional communication complexity ≥ 2k. This shows that a communication protocol cannot always be compressed to its internal information. By a result of Braverman [1], our gap is the largest possible. By a result of Braverman and Rao [2], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity cannot hold.

Entanglement-assisted quantum error correcting codes have the nice feature that they can be constructed from classical additive codes that do not need to be self-orthogonal — an advantage over stabilizer codes. In the literature, these codes were investigated for finite fields, mostly binary fields. A generalization of the Pauli basis to nice error bases indexed by rings allows one to consider alphabet sizes that are not restricted to powers of a prime. The main goal of this paper is to show how entanglement-assisted quantum error correcting codes over nice rings can be constructed. We develop the rudiments of symplectic geometry over rings and prove that an R-module with antisymmetric bicharacter can be decomposed as an orthogonal direct sum of hyperbolic pairs.

This paper investigates the dimensions of ℒ-semilinear subspaces of Vn. It first obtains some necessary and sufficient conditions that each basis has the same number of elements. Then it presents that over some zerosumfree semirings, each basis also has the same number of elements. In the end, it discusses the relationships between the direct sums and the dimensions of semilinear subspaces of n-dimensional vectors and shows a necessary and sufficient condition that a sum of semilinear subspaces is a direct sum over some zerosumfree semirings.

A strong direct product theorem for a problem in a given model of computation states that, in order to compute k instances of the problem, if we provide resource which is less than k times the resource required for computing one instance of the problem with constant success probability, then the probability of correctly computing all the k instances together, is exponentially small in k. In this paper, we consider the model of two-party bounded-round public-coin randomized communication complexity. We show a direct product theorem for the communication complexity of any relation in this model. In particular, our result implies a strong direct product theorem for the two-party constant-message public-coin randomized communication complexity of all relations. As an immediate application of our result, we get a strong direct product theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols. Our result generalizes the result of Jain [2011] which can be regarded as the special case when t=1. Our result can be considered as an important progress towards settling the strong direct product conjecture for the two-party public-coin communication complexity, a major open question in this area. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used in Jain~\cite{Jain:2011}. %, where a strong direct product theorem for the %two-party one-way public-coin communication complexity of all %relations is shown (that is the special case of our result when $t=1$). One key tool used in our work and also in Jain~\cite{Jain:2011} is a message compression technique due to Braver man and Rao~\cite{Braverman2011}, who used it to show a {\em direct sum} theorem in the same model of communication complexity as considered by us. Another important tool that we use is a correlated sampling protocol, which for example, has been used in Holenstein~\cite{Holenstein2007} for proving a parallel repetition theorem for two-prover games.

Let A l = [a ij (l)] be a strictly upper triangular n×n matrix on Cn with a jj+1(l) ≠ 0 for j=1, 2, …, n −1 and R=⊕k i=1 A i In this paper, we prove that if S is the double commutants of R, then there are polynomials p i (Z)=∑n−1 j=0 C ij Zj of degree less than n−1 such that S is a diagonalmatrix with the form S=diag(p 1 (A 1 ), p 2 (A 2 ), …, p k (A k )).

The blind decomposition of the observations, as a set of additive components of simpler structure, is a problem with many applications in scientific and practical fields. Our study assumes that the component signals are of bounded nature, and relies on the geometric decomposition of the convex set that supports the observations as a Minkowski direct sum of the convex sets that support the components. This last property, which is weaker than the mutual independence of the additive components of the observations, is sufficient for the essential identifiability of the bounded and indecomposable components. In practice, it is usual that the components lie in one-dimensional complex subspaces. Therefore, for this case, we describe a sequential method for their recovery.

Multistage RVQs with optimal direct sum decoder codebooks have been successfully designed and implemented for data compression. The same design concept has yielded good results in the application of image-content classification and has also provided an effective platform to perform image driven data mining (IDDM). To make it computationally feasible, the current design methods entail encoder codebook designed in a sequential but suboptimal manner. Based on the sub-optimal codebook design approach, the sequential search path is greedy based on a stage wise nearest-neighborhood strategy instead of a direct sum nearest-neighborhood requirement. Markov random field (MRF) provides a suitable framework to exploit the structure of multistage residual vector quantizers with optimal direct-sum direct sum decoder codebooks combined with sequential-search encoders to achieve optimized classification in the maximum aposteriori sense (MAP).

Consider the following {\em Simultaneous Message Passing} ($\smp$) model for computing a relation $f \subseteq \cX \times \cY \times \cZ$. In this model $\alice$, on input $x \in \cX$ and $\bob$, on input $y\in\cY$, send one message each to a third party $\referee$ who then outputs a $z \in \cZ$ such that $(x,y,z)\in f$. We first show optimal {\em Direct sum} results for all relations $f$ in this model, both in the quantum and classical settings, in the situation where we allow shared resources (shared entanglement in quantum protocols and public coins in classical protocols) between $\alice$ and $\referee$ and $\bob$ and $\referee$ and no shared resource between $\alice$ and $\bob$. This implies that, in this model, the communication required to compute $k$ simultaneous instances of $f$, with constant success overall, is at least $k$-times the communication required to compute one instance with constant success. This in particular implies an earlier Direct sum result, shown by Chakrabarti, Shi, Wirth and Yao~\cite{ChakrabartiSWY01} for the Equality function (and a class of other so-called robust functions), in the classical $\smp$ model with no shared resources between any parties. Furthermore we investigate the gap between the $\smp$ model and the one-way model in communication complexity and exhibit a partial function that is exponentially more expensive in the former if quantum communication with entanglement is allowed, compared to the latter even in the deterministic case.

Aimed at that available application of smooth homomorphism is around the comparison of two smooth modulus with each other and any of its application to construct new smooth modulus has not been seen, this paper applies smooth homomorphism and modulus to construct smooth projective modulus and proves three theprems:1. the theorem that lifts some examples of smooth projective modulus. 2. the sufficient and necessary condition that the direct sum of two smooth modulus is smooth projective modulus; 3. the uniqueness of smooth projective module. The smooth projective is different from classical module. The former is based on fuzzy equality and smooth binary operation, the latter is based on crisp equality and classical binary operation. This paper is different from the fundamental theorem of smooth homomorphism of modulus in application of homomorphism . The former applies homomorphism to construct new module--projective module, the latter applied homomorphism to comparison of two smooth modulus with each other.

Discrepancy is a versatile bound in communication complexity which can be used to show lower bounds in randomized, quantum, and even weakly-unbounded error models of communication. We show an optimal product theorem for discrepancy, namely that for any two Boolean functions f, g, disc(f odot g)=thetas(disc(f) disc(g)). As a consequence we obtain a strong direct product theorem for distributional complexity, and direct sum theorems for worst-case complexity, for bounds shown by the discrepancy method. Our results resolve an open problem of Shaltiel (2003) who showed a weaker product theorem for discrepancy with respect to the uniform distribution, discUodot(fodotk)=O(discU(f))k/3. The main tool for our results is semidefinite programming, in particular a recent characterization of discrepancy in terms of a semidefinite programming quantity by Linial and Shraibman (2006).

Behavioral system theory has become a successful framework in providing a viewpoint that does not depend on a priori notions of inputs/outputs. In particular, this theory provides notions as controllability, without an explicit reference to the state space formalism. One also obtains several interesting consequences of controllability, for example, direct sum decomposition of the signal space with a controllable behavior B as a direct summand. While there are some attempts to extend this theory to infinite-dimensional systems, for example, delay systems, the overall picture remains incomplete. This article extends this theory, particularly the notion of controllability, to a well-behaved class of infinite-dimensional systems, called pseudorational. A crucial notion in this context is the Bezout identity, and we relate a recent result to the context of behavioral controllability. We establish its relationships with notions as image representation and direct sum decompositions.

The MRA super-wavelet theory was investigated in the direct sum Hilbert space L2(R)(m)=Sigmaj=1 moplusL2(R). It is shown that a super-wavelet arises from our MRA construction if and only if the dimension of each particular linear space is either zero or one. In particular, when Ei is a bounded normalized tight frame wavelet set, it is shown that a super-wavelet arise from our MRA construction if and only if Ei s =cupkges12-k Ei is 2pi - translation congruent to a subset of [-pi, pi]. In addition, an example is given.

We show that any deterministic data-stream algorithm that, makes a constant number of passes over the input and gives a constant, factor approximation of the length of the longest increasing subsequence in a sequence of length n must use space Omega(radicn). This proves a conjecture made by Gopalan, Jayram, Krauthgamer and Kumar |10| who proved a matching upper bound. Our results yield asymptotically tight tower bounds for all approximation factors, thus resolving the main open problem, from their paper. Our proof is based on analyzing a related communication problem and proving a direct sum type property for it.

In this paper, the novel hardware sharing architectures are proposed for realizations of fast 4times4 and 8times8 forward/inverse integer transforms in the H.264/AVC. Based on matrix factorizations, the cost-effective architectures for fast one-dimensional (1D) 4times4 and 8times8 forward/inverse integer transforms can be derived through the Kronecker and direct sum operations. By applying the concept of hardware sharing, the proposed hardware schemes for fast integer transforms need less number of shifters and adders than the direct realization architecture, where the direct architecture just implements the individual 4times4 and individual 8times8 integer transforms independently. With low hardware cost and regular modularity, the proposed hardware sharing architectures are suitable for VLSI implementations to accomplish the H.264/AVC signal processing

In the last century together with Levon Khachatrian we established a diametric theorem in Hamming space Hn=(Xn,d H ). Now we contribute a diametric theorem for such spaces, if they are endowed with the group structure Gn=nΣ 1 G, the direct sum of a group G on X={0,1,...,q-1}, and as candidates are considered subgroups of Gn. For all finite groups G, every permitted distance d, and all n≥d subgroups of Gnwith diameter d have maximal cardinality qd. Other extremal problems can also be studied in this setting.

We prove that corruption, one of the most powerful measures used to analyze 2-party randomized communication complexity, satisfies a strong direct sum property under rectangular distributions. This direct sum bound holds even when the error is allowed to be exponentially close to 1. We use this to analyze the complexity of the widely-studied set disjointness problem in the usual "number-on-the-forehead" (NOF) model of multiparty communication complexity.

In this paper, we first prove that every Hermitian code is a direct sum of concatenated Reed-Solomon codes over GF(q/sup 2/), which provides a new method to calculate the dimension of the Hermitian code. Based on this, we present a new decoding algorithm for Hermitian code. Our algorithm is especially efficient in decoding burst errors. Finally, a method to optimize Hermitian code is obtained. The optimized code maintains the same dimension and error correctability, but the complexity for burst error correction can be reduced from O(n/sup 5/3/) to O(n).

Let V=(n, k:) be an irreducible cyclic code over F/sub q//sup m/, the finite field of q/sup m/ elements. Let /spl alpha/_ be a basis of F/sub q//sup m/ over F/sub q/. Under the simplifying assumption (n,q)=1, it is shown that d/spl alpha/_(V), the q-ary image of V with respect to /spl alpha/, is decomposable into the direct sum of a fixed number of irreducible quasicyclic codes. This characterization allow us to obtain a lower bound on the minimum distance of d/spl alpha/_(V) by determining a lower bound on the number of not-null blocks in a typical codeword of d/spl alpha/_(V), for four specific subclasses of codes.

This paper provided a unified geometric framework for kinematic analysis and synthesis of parallel manipulators. We gave a strict definition on motion types of a mechanism based on distributions on a Lie group. We derived conditions for parallel manipulators with Lie subgroup motions using the intersection of the permissible velocity spaces, or the direct sum of the constraint force spaces of each subchain, and the integration theory on a Lie group. Several practical examples were studied in detail to verify our approach.

Full diversity signal constellations for any numbers of transmitter antennas and for any orders which are constructed from 2/spl times/2 Hamiltonian matrices are investigated in this paper. The diversity product of a 2/spl times/2 Hamiltonian constellation equals one half of the Euclidean distance between two points in C/sup 2/. By considering the transformation from R/sup 4/ to C/sup 2/, the idea of group codes is used to construct a high diversity product constellation for any order L. The (L,4) cyclic group codes are considered to obtain L 4-dimensional codewords for group codes. We show that our 2/spl times/2 Hamiltonian constellations have higher diversity product than orthogonal and diagonal constellation designs. We extend our construction to the general case for any numbers of transmitter antennas M>2 by using a direct sum of 2/spl times/2 Hamiltonian matrices for M even, and a direct sum of 2/spl times/2 Hamiltonian matrices with the L/sup th/ roots of unity for M odd. It is shown that these constellations outperform cyclic groups and some of those obtained using fixed-point free groups.

The authors discuss the theory and construction of high-speed VLSI DFT (discrete Fourier transform) computational array. The array uses ring arithmetic isomorphic to the direct sum of a set of small quadratic residue ring computations. The array utilizes a generic systolic cell that is used for all elements in the computational process. This includes coding into the quadratic residue number system, array computation, scaling, and reconstruction. In addition to these advantages, the cell also has a built-in fault-detection system that allows fault tolerant computation of each butterfly. Typical VLSI fabrications demonstrate the unique structure and simplicity of the arrays. Example layouts in a 3- mu m double-metal CMOS process are presented. >

An interpretation method of orthographic three-views of a mechanical drawing based on dividing operations into primitive volumes is presented. The method outputs a constructive solid geometry (CSG) solid model composed of a binary tree of direct sum and difference operations for object shapes limited to combinations of six primitives. The main parts of the method are to extract all loops, to obtain the combinations of the loops of 2-D primitives for each view, to generate all possible combinations of 3-D primitives, and to generate a CSG tree of the direct sum and difference operations on them. The algorithm is described, and some examples are shown. >

Many methods of image generation being mainly intended for the realism of images, this pattern generation is a very different graphic generation from them. It is a trial for a sort of graphic art by using a machine. The equipments with machines are mainly composed of a mathematical model which may be constructed by computer programs or switching and other electric circuits. The model, called commutative linear representation systems (CLRS), is suitable for computer programs and electric circuits for linear operations. It has been already shown that there are relations between the index of CLRS and pattern with periodicity. In this paper, basic systems are introduced with the fact that any finite-sized pattern can be represented by them. And any pattern with periodicity can be represented as direct sum of minimum CLRS, which are called quasi-reachable basic system.

Constacyclic codes may naturally be viewed as objects arising from the cohomological concept of a cocycle. Cohomology theory suggests a transformation which is used to show, under certain circumstances, a cyclic code of length mn over a ring R is isomorphic to the direct sum of m constacyclic codes of length n. In particular this isomorphism holds in many local rings (for example Galois rings) and also in the modular ring Z/sub r/.

The design of uniquely decodable DC-free multi-user coding schemes with good rate sums for the multiple access adder channel is described in this paper. It is shown that by using the direct sum construction on short multi-user codes, it is possible to devise longer DC-free multi-user coding schemes with rate sums which increase quite rapidly at each iteration of the construction. Asymptotically, there is no penalty in requiring the coding schemes to be DC-free. In addition, the schemes can be efficiently soft decision decoded using a relatively low complexity sectionalised trellis.

The possibility of obtaining certain decompositions with finite dimensional intersection, for a given two-dimensional behavior, are investigated and related to the factor skew-primeness property of suitable matrix pairs involved in the behavior description. The analysis carried out represents a fist step toward a complete generalization of the preliminary results about direct sum decompositions presented by the authors.

We consider the control of a plant described by a linear system with x /spl epsiv/ R/sup n/ as a state, u /spl epsiv/ R/sup m/-control input, /spl xi/ /spl epsiv/ Rl-unmeasurable input. The considered problem is to give a method of (n-k)-dimensional output controller design so that for the closed-loop system the expression /sup /spl infin///spl int//sub 0/ F(x(t),u(t),/spl xi/(t))dt/spl les/C(x(0)), /spl forall/T>0 is valid, where F is a given quadratic form R/sup n//spl times/R/sup m//spl times/R/sup l//spl rarr/R/sup 1/. In particular variants of this inequality lead to the solution of the H/sup /spl infin//-control problem and the absolute stabilization problem. The solution is based on frequency conditions of n-dimensional robust controllers, due to V. Brusin (1999), and decomposition of the n-dimensional space into a direct sum of subspaces. The application of this method to the spring-connected two-mass system with perturbed stiffness and external disturbances is given.

Given m copies of the same problem, does it take m times the amount of resources to solve these m problems? This is the direct sum problem, a fundamental question that has been studied in many computational models. We study this question in the simultaneous message (SM) model of communication introduced by A.C. Yao (1979). The equality problem for n-bit strings is well known to have SM complexity /spl Theta/(/spl radic/n). We prove that solving m copies of the problem has complexity /spl Omega/(m/spl radic/n); the best lower bound provable using previously known techniques is /spl Omega/(/spl radic/(mn)). We also prove similar lower bounds on certain Boolean combinations of multiple copies of the equality function. These results can be generalized to a broader class of functions. We introduce a new notion of informational complexity which is related to SM complexity and has nice direct sum properties. This notion is used as a tool to prove the above results; it appears to be quite powerful and may be of independent interest.