We propose two fault-tolerant broadcasting schemes in star graphs. One of the schemes can tolerate up to n2 faults of the crash type in the n-star graph. The other scheme can tolerate up to (n3d1)/2 faults of the Byzantine type in the n-star graph, where d is the smallest positive integer satisfying nd!. Each of the schemes is designed for the single-port mode, and it completes the broadcasting in O(n log n) time. These schemes are time optimal. For the former scheme we analyze the reliability in the case where faults of the crash type are randomly distributed. It can tolerate (n!)α faults randomly distributed in the n-star graph with a high probability, where α is any constant less than 1.

We have investigated the operation of a reflection type magnetostatic wave signal-to-noise enhancer in detail. It has good enhancement characteristics, low insertion loss, and low operating power. It is also composed of a transducer using a ceramic substrate having a high dielectric constant and an LaGa-YIG film with low saturation magnetization to enable direct operation in the 400-MHz band (the IF band of current DBS receivers). Enhancement of 8 dB was achieved over a 40-MHz bandwidth. Although its operating frequency range depends critically on device temperature, we can compensate for the temperature dependence by adjusting the bias magnetic field. Experiments showed that the enhancer improved the received carrier-to-noise ratio by 2 to 3 dB, providing good noise reduction in DBS reception.

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.

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.

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.

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.

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.

This paper proposes a novel phase ambiguity resolver with combining a very low power Viterbi decoder employing a scarce state transition scheme to realize cost effective receivers for the PCM sound broadcasting satellite service. The theoretical analyses on phase decision performance show that the proposed resolver achieves the symbol-by-symbol phase detection and decides correctly phases of the demodulated data even if the bit error probability of 710-2. The resolver also reduces the phase decision time to below 1/1000 of that of the conventional resolver. Furthermore, experimental results of the power consumption estimate that the prototype Viterbi decoder consumes only 60mW at the data rate of 24.576Mbit/s.

A signal-to-noise enhancer with a bandwidth that is six times as wide as that of the conventional type is presented. A new circuit construction, the combination of two MSSW filters which have the same insertion loss in the broadband and two 90 hybrids, is effective to remarkably extend the bandwidth. The enhancement of the enhancer amounts to 20 dB in the operating frequency range of 1.9 GHz150 MHz in 0 to 60 degrees centigrade. This enhancer has accomplished FM threshold extension because the S/N is improved by 1 to 7 dB below the C/N of 9 dB. It was demonstrated that this new enhancer is effective for noise reduction in practical DBS reception.

We discuss ISDB (Integrated Services Digital Broadcasting) which has a transport structure to meet the technical requirements such as the flexibility and the extensibility of broadcasting in the future. The basic configuration of the ISDB transmission signal for distribution into various transmission channels is shown. Hybrid multiplexing, which uses common fixed-length packets and structured transmission units called "slots," is introduced to construct a transmission signal for low-cost signal processing in ISDB receivers. We show that a fixed packet length of 40-240 bytes results in high transmission efficiency in a diverse range of service arrangements. Furthermore, we use transmission control methods, which show the relationship between programs and packet IDs, to select the desired program with certainty and ease.

In the future satellite broadcasting system in 21GHz band, the rainfall attenuation is a most significant problem. To solve this problem, the hierarchical transmission systems have been studied. This paper analyzes the performance of the hierarchical modulation scheme from the view point of power assignment in the presence of the rainfall attenuation. This paper shows an optimum power assignment ratio to maximize the spectral efficiency and the signal-to-noise ratio of received image, and these optimum ratio is varied with the measure of system performance.

OFDM (Orthogonal Frequency Division Multiplexing) is a useful digital modulation method for terrestrial digital broadcasting systems, both for digital TV broadcasting and digital audio broadcasting. OFDM is a kind of multicarrier modulation and shows excellent performance especially in multipath environments and in mobile reception. Other advantages are its resistance to interference signals and its suitability for digital signal processing. When each carrier of the OFDM signal is modulated with DQPSK, we call it DQPSK-OFDM. DQPSK-OFDM is a basic OFDM system, which is especially suitable for mobile reception. This paper describes how a DQPSK-OFDM system works and shows several experimental and simulation results. The experimental results mainly concern the performance of the DQPSK-OFDM system relative to various disturbances such as multipath (ghost) signals, nonlinearity of the channel, and interference from analog signals. The transmission characteristics of DQPSK-OFDM are investigated and the basic criteria for the system design of DQPSK-OFDM are discussed.

This paper describes an adaptively weighted code division multiplexing (AW-CDM) system, in other words, power controlled spread-spectrum multiplexing system and describes its application to hierarchical digital broadcasting of television signals. The AW-CDM, being combined with multi-resolutional video encoder, can provide such a hierarchical transmission that allows both high quality services for fixed receivers and reduced quality services for mobile/portable receivers. The carrier and the clock are robustly regenerated by using a spread-spectrum multiplexed pseudorandom noise (PN) sounder as a reference in the receiver. The PN reference is also used for Rake combining with signals via different paths, and for adaptive equalization (EQ). In a prototype AW-CDM modem, three layers of hierarchical video signals (highs: 5.91Mbps, middles: 1.50Mbps, and lows: 0.46 Mbps) are divided into a pair of 64 orthogonal spread-spectrum subchannels, each of which can be given a different priority and therefore a different threshold. In this case, three different thresholds are given. The modem's transmission rate is 9.7Mbps in the 6MHz band. Indoor transmission tests confirm that lows (weighted power layer I), middles (averaged power layer II), and highs (lightened power layer III) are retrievable under conditions in which the desired to undesired signal ratios (DURs) are respectively 0dB, 8.5dB, and 13.5dB. If the undesired signals are multipaths, these performances are dramatically improved by Rake combining and EQ. The AW-CDM system can be used for 20-30 Mbps advanced television (ATV) transmission in the 6-MHz bandwidth simply by changing the binary inputs into quaternary or octonary inputs.

When a new digital broadcasting system is introduced for the viewers, it is important to be able to include new services and system aspects. That is to give the viewers new experiences and meet the demands they might have in the future. To fulfil the viewers expectations, is a key for success for the introduction of new service and product. It is equally important to look at the long term perspective and have the possibility to gradually develop the digital broadcasting systems we establish today. A fully integrated multimedia system is a hybrid of different media services, distribution paths and display object. The pros and cons of each of them must be examined and each of them used where best suited. This will probably give a more complex media world with fuzzy borders between what is broadcasting, packaged media and what is the on-line information society. In order to balance this, any new digital multimedia system needs to be developed with an open architecture, based on generally agreed standards and possibly follow a non-proprietary approach. IDUN, a prototype system for multimedia broadcasting, is on its way to fulfil these requirements. IDUN combines the powerful point to multi-point emission, domestic data storage and computer processing with the telecommunication network. It is feasible to introduce it in the analogue world of today but could better be utilised in a fully digital future. Some possible services are further proposed. Some of them with a tight relation to what a broadcaster already produces, which could give an evolutionary transfer to the new digital world.

It is well known that weather conditions affect the performance of satellite broadcasting receiving systems. For example, snow accretion on antennas degrades the receiving performance seriously because it reduces received signal power and also can increase antenna noise. Since effects of the weather are considered to differ for various types of receiving antenna, an investigation on this phenomenon is very important. A study on weather effects to three types of satellite broadcasting receiving antenna, a planar antenna, a center-fed parabolic reflector antenna, and an offset parabolic reflector antenna, is presented in this paper. Since the performance of receiving antennas can be determined by a parameter G/T, a long-term and continuous measurement of G/T must be performed. Furthermore, the measurement of more than one receiving system should be performed simultaneously. Also, the measurement should be performed in a snowy area (in winter) and a rainy area (in the other seasons) to evaluate the effect of the weather. To fulfil the criterion, a continuous measurement system of G/T has been built in Hokkaido University, Sapporo. Sapporo, which is located at latitude 42 degrees north, has a long and snowy winter, and also has rainy days in the other seasons so that we can evaluate the effect of weather. Using this measurement system, cumulative distributions of measurement results are obtained so that the performance of different types of receiving system can be evaluated. In this paper, some considerations on the noise level are also discussed briefly to evaluate the performance degradation of the receiving systems.

This paper briefly considers future broadcasting technologies, including digital television as a system for the near future and three-dimensional television as a part of a system to be developed rather later. However, due to limitations of space, this paper discusses only video technologies in detail. First, the status of bit reduction technologies for digital television is described and then satellite digital broadcasting and terrestrial digital broadcasting are also discussed. The authors stress the necessity of the further development of digital video compression technologies. Later, we discuss three-dimensional television, we describe requirements for the service and the present status of the technologies. And last, the paper considers the future prospects for a three-dimensional television service.