This paper describes the implementation and demonstration of local networks for the hyper-media photonic information network (HM-PIN), a candidate for the information service platform offering broadcast and telecommunication services. In addition, the feasibility of the HM-PIN is also demonstrated using prototype local network systems. This local network adopts architecture based on wavelength-division-multiplexing (WDM) and broadcast-and-select (B&S) switching, and supports all HM-PIN services except inter-local-network communication. The major issues of this proposed network are the technologies that support many broadcast channels and reduce channel selection cost. This paper also considers the combination of WDM technology and three alternatives: electrical TDM, subcarrier multiplexing (SCM or electrical FDM), and optical TDM (O-TDM). Three 128 ch (8 wavelengths 16 channels) WDM B&S prototype systems are built to demonstrate the feasibility of the proposed HM-PIN. In WDM/SCM, 30 and 20 Mb/s channels are realized as 16-QAM and 64-QAM, and 155 Mb/s channels are realized by WDM/TDM. Moreover, these three prototypes were connected to form a small HM-PIN and applications such as video distribution and IP datagram cut-through are demonstrated. Furthermore, the delay and throughput of the HM-PIN are evaluated by connecting a local network to a 200-km WDM-ring backbone network. Our discussions and demonstrations confirm the impact and feasibility of the proposed hyper-media photonic information network.

This paper presents large capacity switching systems for a local network using the broadcast-and-select (B&S) architecture. The B&S switching system, based on optical time-division multiplexing (OTDM), can provide several hundreds of Gbit/s by using a nonlinear optical switch as the time-channel selector. Moreover, the combination of OTDM and wavelength-division multiplexing (WDM) can realize throughputs over Tbit/s. In experiments, first, all-optical selection from a 51.2-Gbit/s data-stream to yield a 160-Mbit/s data-channel is demonstrated for a B&S OTDM switching system. Second, all-optical selection from a 25.6-Gbit/s 2 (51.2-Gbit/s) WDM data-stream to yield a 160-Mbit/s data-channel is demonstrated for a B&S OTDM and WDM switching system. Finally, the number of optical amplifiers that one user has to share in the B&S OTDM switching system is discussed.

This paper describes the implementation and demonstration of local networks for the hyper-media photonic information network (HM-PIN), a candidate for the information service platform offering broadcast and telecommunication services. In addition, the feasibility of the HM-PIN is also demonstrated using prototype local network systems. This local network adopts architecture based on wavelength-division-multiplexing (WDM) and broadcast-and-select (B&S) switching, and supports all HM-PIN services except inter-local-network communication. The major issues of this proposed network are the technologies that support many broadcast channels and reduce channel selection cost. This paper also considers the combination of WDM technology and three alternatives: electrical TDM, subcarrier multiplexing (SCM or electrical FDM), and optical TDM (O-TDM). Three 128 ch (8 wavelengths 16 channels) WDM B&S prototype systems are built to demonstrate the feasibility of the proposed HM-PIN. In WDM/SCM, 30 and 20 Mb/s channels are realized as 16-QAM and 64-QAM, and 155 Mb/s channels are realized by WDM/TDM. Moreover, these three prototypes were connected to form a small HM-PIN and applications such as video distribution and IP datagram cut-through are demonstrated. Furthermore, the delay and throughput of the HM-PIN are evaluated by connecting a local network to a 200-km WDM-ring backbone network. Our discussions and demonstrations confirm the impact and feasibility of the proposed hyper-media photonic information network.

This paper proposes local lightwave networks with grouping property which are based on a wavelength division multiplexing (WDM). The proposed network is partitioned into several groups according to traffic volume between stations so that traffic is more likely to be within groups. The stations within a group are connected to a broadcast-and-select WDM network with star topology. For inter-group communication, a WDM network of each group is connected to another star-topology WDM network through a special station called a router. In the proposed network, intra-group communication is achieved by one hop and inter-group communication goes through multiple hops. We analyze the average hop number, the maximum throughput, and the mean packet delay of the proposed network and investigate its performance characteristics. Since the proposed network has the better performance as its grouping property strengthens, it is fit for local lightwave networks with the locality of traffic.

An architecture is presented for efficient and reliable delivery of multimedia contents from a primary center (PC) to secondary centers (SCs). Requested contents are delivered from the PC to the SCs through a satellite broadcast channel, or from one SC to another SC through a terrestrial channel. Cycling methods are presented that enable sharing of the contents directory of each SC. Several fundamental models and algorithms are introduced for possible consideration during the planning and design of a contents-delivery system. Simulation has shown that using both satellite broadcast and terrestrial channels for contents delivery is superior in terms of cost to the conventional use of only a satellite network.

Unequal error protection (UEP) is a very promising coding technique for satellite broadcasting, as it gradually reduces the transmission rate. From the viewpoint of bandwidth efficiency, UEP should be achieved in the context of multilevel coded modulation. However, the conventional mapping between encoded bits and modulation signals, usually realized for multilevel block modulation codes and multistage decoding, is not very compatible with UEP coding because of the large number of resulting nearest neighbor codewords. In this paper, new coded modulation schemes for UEP based on unconventional partitioning are proposed. A linear operation referred to as interlevel combination is introduced. This operation generalizes previous partitioning proposed for UEP applications and provides additional flexibility with respect to UEP capabilities. The error performance of the proposed codes are evaluated both by computer simulations and a theoretical analysis. The obtained results show that the proposed codes achieve good tradeoff between the proportion and the error performance of each error protection level.

Almost all broadcasting systems and their equipment would be digitalized in the near future. In Japan, investigation of digital broadcasting has been going on for a long time, aiming at a realization of improvement of picture quality, new services, system flexibility, etc. Japanese digital broadcasting systems under development have a lot of technical merits, for example, a high transmission capacity and a hierarchical transmission scheme for satellite, and mobile reception for terrestrial digital broadcasting systems, compared to conventional digital systems.

Let T1, , Tn be n spanning trees rooted at node r of graph G. If for any node v, n paths from r to v, each path in each spanning tree of T1, , Tn, are internally disjoint, then T1, , Tn are said to be independent spanning trees rooted at r. A graph G is called an n-channel graph if G has n independent spanning trees rooted at each node of G. We generalize the definition of n-channel graphs. If for any node v of G, among the n paths from r to v, each path in each spanning tree of T1, , Tn, there are k internally disjoint paths, then T1, , Tn are said to be (k,n)-independent spanning trees rooted at r of G. A graph G is called a (k,n)-channel graph if G has (k,n)-independent spanning trees rooted at each node of G. We study two fault-tolerant communication tasks in (k,n)-channel graphs. The first task is reliable broadcasting. We analyze the relation between the reliability and the efficiency of broadcasting in (k,n)-channel graphs. The second task is secure message distribution such that one node called the distributor attempts to send different messages safely to different nodes. We should keep each message secret from the nodes called adversaries. We give two message distribution schemes in (k,n)-channel graphs. The first scheme uses secret sharing, and it can tolerate up to t+k-n listening adversaries for any t < n if G is a (k,n)-channel graph. The second scheme uses unverifiable secret sharing, and it can tolerate up to t+k-n disrupting adversaries for any t < n/3 if G is a (k,n)-channel graph.

In the multipath mobile channel, the received signal suffers from both the fluctuation in the received field intensity caused by fading and waveform distortion caused by the echo. Diversity reception using multiple spaced antennas is an effective method to compensate for fading, while echo cancellation with an adaptive array is good at compensating for waveform distortion. In this paper, an adaptive switching echo cancellation/diversity reception method to compensate for both waveform distortion and fading is proposed. The proposed switching reception monitors the impacts of channel conditions on received signal and then one of an echo canceller and a diversity receiver is selected accordingly to compensate the channel. The compensation performance of the proposed switching reception in terms of both average DUR (Desired to Undesired signal Ratio) and the probability of DUR below a threshold value is investigated with computer simulation. The results show that the adaptive switching echo cancellation/diversity reception has realized the advantages of both adaptive echo cancellation and diversity reception.

In this paper, we propose a high performance highly modular ATM switch architecture known as Bodhi which is suitable for small, large, and very large size ATM switch implementations. Its basic configuration consists of two stages: an input stage and an output stage. The input stage consists of input group modules (IGMs) and output stage output group modules (OGMs). Each IGM-OGM pair is connected by multiple paths which carry cells from IGMs to OGMs. Excess cells at the IGMs are recycled to minimize the cell loss probability. Another module called recirculation module is used to couple several IGMs together to create additional routes for recirculating cells which gives this architecture robustness against nonuniform and directed traffic. Multicasting has been implemented by integrating copying and broadcasting techniques, and using some novel techniques to minimize the switch complexity. A shared buffer architecture is employed for OGMs such that it implements multiple priorities dynamically in a weighted manner, requires no speedup, and, can function in standalone mode as small switches. The performance of Bodhi has been evaluated by computer simulation to select design parameters for a 1k 1k (k=1024) switch fabric. It allows growability from 2. 4 gigabit to 150 gigabit switch, and, expandability to 100+ Terabit switch with the complexity increasing approximately linearly with size. Based on the study presented in this paper, it is seen that the Bodhi architecture offers a high degree of modularity, weighted dynamic priority control, robustness against nonuniform traffic conditions, low complexity, low latency, and, supports multicasting efficiently and without any limitation. Bodhi, therefore, has high potential for application in high speed broadband networks.

The construction of fault-tolerant processor arrays with interconnections of cube-connected cycles (CCCs) by using an advanced spare-connection scheme for k-out-of-n redundancies called "generalized additional bypass linking" is described. The connection scheme uses bypass links with wired OR connections to spare processing elements (PEs) without external switches, and can reconfigure complete arrays by tolerating faulty portions in these PEs and links. The spare connections are designed as a node-coloring problem of a CCC graph with a minimum distance of 3: the chromatic numbers corresponding to the number of spare PE connections were evaluated theoretically. The proposed scheme can be used for constructing various k-out-of-n configurations capable of quick broadcasting by using spare circuits, and is superior to conventional schemes in terms of extra PE connections and reconfiguration control. In particular, it allows construction of optimal r-fault-tolerant configurations that provide r spare PEs and r extra connections per PE for CCCs with 4x PEs (x: integer) in each cycle.

This work is targeted to understand the operating principle of the feedback type echo canceller for use in an FM broadcasting receiver and to study its compensating features and the effects of the practical operating environment on its performance. The effects of the tap interval and the compensation performance in the presence of an echo with excess delay 0 - 15 µs are examined. The results show that the tap interval should be selected according to the observable bandwidth of the channel transfer function and the performance of a feedback type echo canceller has a wavelike curve with respect to the excess delay of the echo. To improve the performance of the feedback type echo canceller, an adaptive echo canceller operating with CM algorithm is proposed and examined with computer simulation. The results show that the compensation performance is improved.

A graph G is called an n-channel graph at vertex r if there are n independent spanning trees rooted at r. A graph G is called an n-channel graph if G is an n-channel graph at every vertex. Independent spanning trees of a graph play an important role in fault-tolerant broadcasting in the graph. In this paper we show that if G1 is an n1-channel graph and G2 is an n2-channel graph, then G1G2 is an (n1 + n2)-channel graph. We prove this fact by a construction of n1+n2 independent spanning trees of G1G2 from n1 independent spanning trees of G1 and n2 independent spanning trees of G2. As an application we describe a fault-tolerant broadcasting scheme along independent spanning trees.

In this paper, coded modulation techniques suitable for satellite broadcasting of digital high-definition TV are studied. An overview of current approaches to satellite broadcasting is presented. New constructions of coded modulation schemes for unequal error protection (UEP), based on both block and trellis codes, are introduced in this paper. The proposed schemes can achieve both better overall performance and enhanced graceful degradation of the received signal, in comparison with existing digital satellite broadcasting approaches.

The mesh-connected computers with hyperbus broadcasting are an extension of the mesh-connected computers with multiple broadcasting. Instead of using local buses, we use global buses to connect processors. Such a strategy efficiently reduces the time complexity of the semigroup problem from O(N) to O(log N). Also, the matrix multiplication and the transitive closure problems are solved in O(log N) and O(log2 N) time, respectively. Then, based on these operations, several interesting problems such as the connected recognition problem, the articulation problem, the dominator problem, the bridge problem, the sorting problem, the minimum spanning tree problem and the bipartite graph recognition problem can be solved in the order of polylogarithmic time.

Efficient parallel algorithms for several problems on proper circular arc graphs are presented in this paper. These problems include finding a maximum matching, partitioning into a minimum number of induced subgraphs each of which has a Hamiltonian cycle (path), partitioning into induced subgraphs each of which has a Hamiltonian cycle (path) with at least k vertices for a given k, and adding a minimum number of edges to make the graph contain a Hamiltonian cycle (path). It is shown here that the above problems can all be solved in logarithmic time with a linear number of EREW PRAM processors, or in constant time with a linear number of BSR processors. A more important part of this work is perhaps the extension of basic BSR to allow simultaneous multiple BROADCAST instructions.

Multimedia Database Systems as the tool to extract and generate additional values from multimedia 'Contents' are discussed in this paper with putting emphasis on the mediator functions between users and contents. Firstly, we discuss about 'what to do' from the view point of four promising contents sources: 'on the network,' 'in the digital broadcasting' 'in the library' and 'in the real world.' From this view pont, four types of multimedia database systems are defined. 'What to do' for each database system is also discussed. Two concrete multimedia database systems with unique mediator functions, stream-type multimedia database platform GOLS and the intelligent access and authoring system using multiple media synchronization are proposed with experimental evaluation results and concrete multimedia database applications.

Recursive Diagonal Torus (RDT) is a class of interconnection network for massively parallel computers with 216 nodes. In this paper, message transfer algorithms on the RDT are proposed and discussed. First, a simple one-to-one message routing algorithm called the vector routing is introduced and its practical extension called the floating vector routing is proposed. In the floating vector routing both the diameter and average distance are improved compared with the fixed vector routing. Next, broadcasting and hypercube emulation algorithm scheme on the RDT are shown. Finally, deadlock-free message routing algorithms on the RDT are discussed. By a simple modification of the e-cube routing and a small numbers of additional virtual channels, both one-to-one message transfer and broadcast can be achieved without deadlock.

In this paper we analyze the reliability of a simple broadcasting scheme for hypercubes (HCCAST) with random faults. We prove that HCCAST (n) (HCCAST for the n-dimensional hypercube) can tolerate Θ(2n/n) random faulty nodes with a very high probability although it can tolerate only n - 1 faulty nodes in the worst case. By showing that most of the f-fault configurations of the n dimensional hypercube cannot make HCCAST (n) fail unless f is too large, we illustrate that hypercubes are inherently strong enough for tolerating random faults. For a realistic n, the reliability of HCCAST (n) is much better than that of the broadcasting algorithm described in [6] although the latter can asymptotically tolerate faulty links of a constant fraction of all the links. Finally, we compare the fault-tolerant performance of the two broadcasting schemes for n = 15, 16, 17, 18, 19, 20, and we find that for those practical valuse, HCCAST (n) is very reliable.

We study all-to-all broadcasting in hypercubes with randomly distributed Byzantine faults. We construct an efficient broadcasting scheme BC1-n-cube running on the n-dimensional hypercube (n-cube for short) in 2n rounds, where for communication by each node of the n-cube, only one of its links is used in each round. The scheme BC1-n-cube can tolerate (n-1)/2 Byzantine faults of nodes and/or links in the worst case. If there are exactly f Byzantine faulty nodes randomly distributed in the n-cabe, BC1-n-cube succeeds with a probability higher than 1(64nf/2n) n/2. In other words, if 1/(64nk) of all the nodes(i.e., 2n/(64nk) nodes) fail in Byzantine manner randomly in the n-cube, then the scheme succeeds with a probability higher than 1kn/2. We also consider the case where all nodes are faultless but links may fail randomly in the n-cube. Broadcasting by BC1-n-cube is successful with a probability hig her than 1kn/2 provided that not more than 1/(64(n1)k) of all the links in the n-cube fail in Byzantine manner randomly. For the case where only links may fail, we give another broadcasting scheme BC2-n-cube which runs in 2n2 rounds. Broadcasting by BC2-n-cube is successful with a high probability if the number of Byzantine faulty links randomly distributed in the n-cube is not more than a constant fraction of the total number of links. That is, it succeeds with a probability higher than 1nkn/2 if 1/(48k) of all the links in the n-cube fail randomly in Byzantine manner.