Browse Prior Art Database

A graph theoretical solution for sequencing the interconnect of electronic components

IP.com Disclosure Number: IPCOM000010452D
Original Publication Date: 2002-Dec-03
Included in the Prior Art Database: 2002-Dec-03
Document File: 5 page(s) / 130K

Publishing Venue

Motorola

Related People

by Joseph Hoshen: AUTHOR [+5]

Abstract

This paper describes a graph theoretical solution to the problem of sequencing the interconnection of n electronic devices. The solution forms a partitioning a complete graph of order n into a disjoint set of subgraphs, where each subgraph represents a sequencing number. The subgraphs are used to construct two types of arrays that can be used to sequence the interconnection of the devices. Based on the graph solution, this paper provides simple and efficient algorithms for generating the sequencing arrays

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 30% of the total text.

A graph theoretical solution for sequencing the interconnect of electronic components

        � � � � � � � � � � �

by Joseph Hoshen, Tony Belkin , Ed Benyukhis Anton Mazur and Dmitry Ornatskyy

Abstract

This paper describes a graph theoretical solution to the problem of sequencing the interconnection of n electronic devices. The solution forms a partitioning a complete graph of order n into a disjoint set of subgraphs, where each subgraph represents a sequencing number. The subgraphs are used to construct two types of arrays that can be used to sequence the interconnection of the devices. Based on the graph solution, this paper provides simple and efficient algorithms for generating the sequencing arrays

� I.      Introduction�

The Harmony Wireless Communication System™ (HWCS) is a digital integrated wireless communications system offering the core communication capabilities of dispatch (push to talk), telephone interconnect (cellular phone), and messaging services. HWCS is comprised of three principal components, the compact mobile switching office (MSO), the Motorola Enhanced Base Transceiver System (EBTS cell sites) and the Subscriber Units, which are the mobile wireless devices used by an end-user for communication.

The MSO processes dispatch, telephone interconnect and messaging calls, manages the mobility of Subscriber Units, and provides the interface between the RF network and the wireline PSTN network. The MSO consists of a Mobile Switching Center (MSC), a Base Station Controller (BSC) and a set of H110 linked I/O cards

The H110 bus routes voice, messaging and control traffic between the I/O cards. The system employs hyperchannels, which are contiguous blocks of time slots on the H110 bus, used for inter I/O card routing. At system initialization time, each pair of n I/O cards is assigned a hyperchannel such that n(n-1)/2 hyperchannels are created. The hyperchannel connectivity arrangement can be viewed as a complete graph consisting of n nodes.

At initialization, the system software sets up the hyperchannel links sequentially. However, to create a functioning links, the system requires that the hyperchannel links be set in a defined order. The requirement is that when I/O card i is initialized, the link from i to j is set in the same order as j to i is set when I/O card j is initialized.

The next section, Section II, describes the representation of the sequencing problems in terms of arrays. It also offers graph solutions that enable the computation of these arrays. Section III provides algorithmic solutions to the graph representations.

     II.      A graph theoretical solution to the sequencing problem

The sequencing order of the hyperchannel links can be represented by a B array. The array columns represent the device initialization order. The rows denote node numbers. If the number of nodes, n, is even then, for each sequence number, n/2 pairs of n nodes exist for (n-1)/2 sequence numbers that form a n´(n-1) dimensioned B array. If n is odd, for e...