The crosstalk effect is one of the main problems in deep sub-micron designs of high-speed buses. To mitigate the crosstalk effect, there are several types of crosstalk avoidance codes proposed in the literature. In this paper, we are particularly interested in generating forbidden transition codes that do not have opposite transitions on any two adjacent wires. For this, we propose asequential bit-stuffingalgorithm and aparallel bit-stuffingalgorithm. For the sequential bit-stuffing algorithm, we perform a worst-case analysis and a probabilistic analysis. We show by both theoretic analysis and simulations that the coding rate of the sequential bit-stuffing encoding scheme is quite close to the Shannon capacity. In particular, for a bus with$n=10$parallel wires, the difference is only 2.2 percent. Using a Markov chain analysis, we show that the coding rate of the parallel bit-stuffing algorithm is only slightly lower than that of the sequential bit-stuffing algorithm. The implementation complexity of the parallel bit-stuffing algorithm is linear with$n$. In comparison with the existing forbidden transition codes that use the Fibonacci representation in the literature, our bit-stuffing algorithms not only achieve higher coding rates but also have much lower implementation complexity.

In this paper, we propose an algorithm that detects overlapping communities in networks (graphs) based on a simple node behavior model. The key idea in the proposed algorithm is to find communities in an agglomerative manner such that every detected community S has the following property: For each node i ∈ S, we have (i) the fraction of nodes in S \ {i} that are neighbors of node i is greater than a given threshold, or (ii) the fraction of neighbors of node i that are in S \ {i} is greater than another given threshold. Through computer simulations of random graphs with built-in overlapping community structure, including LFR benchmark random graphs and Erdös-Rényi type random graphs, we show that our algorithm has excellent performance. Furthermore, we apply our algorithm to several real-world networks and show that the overlapping communities detected by our algorithm are very close to the known communities in these networks.

Motivated by the design of high speed switching fabrics, in this paper we propose a bit-stuffing algorithm for generating forbidden transition codes to mitigate the crosstalk effect between adjacent wires in long on-chip buses. We first model a bus with forbidden transition constraints as a forbidden transition channel, and derive the Shannon capacity of such a channel. Then we perform a worst case analysis and a probabilistic analysis for the bit-stuffing algorithm. We show by both theoretic analysis and simulations that the coding rate of the bit stuffing encoding scheme for independent and identically distributed (i.i.d.) Bernoulli input traffic is quite close to the Shannon capacity, and hence is much better than those of the existing forbidden transition codes in the literature, including the Fibonacci representation.