Modular architecture PET decoder for ATM networks

Field of application

The invention relates in general to digital transmission networks functioning in an Asynchronous Transfer Mode (ATM) and more in particular to an error correcting technique of Priority Encoding Transmission (PET).

Background of the invention

In recent years a widespread use of digital techniques for storing and transmitting information has been witnessed. The success of these techniques is due to the availability of cost effective hardware components. Among network technologies dedicated to the above cited services, the ATM technique (Asynchronous Transfer Mode) permits the transmission of multi-media information in a flexible and efficient manner. The ATM technique was developed to solve all aspects of multi-media applications, video, audio, and data transmissions on a same network, with the same protocol, regardless of the type (LAN, MAN or WAN).

The ATM technology provides for a bandwidth with a variable bit-rate that may reach the order of Gigabit/sec and a scalability of the number of network nodes as required by the general architecture of switched networks.

Differently from switched circuit networks, the ATM packet-switched network has the advantage of engaging the channel only during the actual transfer of information.

The procedure of traffic control of ATM networks has not yet reached a consolidated standard, many problems still remain to be solved. One of the main problems of this technology is the possible loss of packets, which in case of video transmissions may result in a degradation of the images that exceeds acceptable levels. Indeed, in some instances the average loss of packets may reach peaks of about 5%. A loss of packets may occur for different causes: <ul id="ul0001" list-style="dash" compact="compact"><li>when the packets arrive after the maximum permitted time delay;</li><li>when the buffer overflows, that is, when its filling threshold is exceeded;</li><li>when a traffic congestion occurs due to an abrupt variation of the information flow or network hardware problems.</li></ul>

If a traffic congestion occurs and some packets are lost, the network is unable to ensure a satisfactory service. To provide for adequate bandwidth characteristics, an ATM-base should have the ability to implement a traffic control procedure like for example a Call Admission Control (CAC) or of a local control at node level (control of the average and peak number of packets reading the interconnection buffers). Although such procedures are implemented at their best, packet losses would be in any case inevitable because of the intervention of policing structures through intelligent agents, and in case of machine malfunctionings.

The method developed by Berkeley and referred to as PET (Priority Encoded Transmission)^[1] is based on coding the information with different levels of redundance depending on its importance. ^[1] A. Albanese, J. Blömer, J. Edmonds, M. Luby: <i>Priority Encoding Transmission</i>. Technical report, International Computer Science Institute, Berkeley, CA, August 1994.

The PET technique is based upon a redundant coding of original information distributed over a plurality of distinct packets. The redundance added during the coding phase is such that, even in case of loss of coded packets, the original information can be fully retrieved from the information existing in the remaining packets.

The PET coding algorithm

The PET coding technique^[1] is an algorithm of information dispersion^[2] that consists in adding, to the message to be transmitted, a proper redundance^[3], before dividing, this encoded message into a plurality of portions which represents the packets that are sent through the transmission medium, so that even by receiving only a fraction of the total number of the packets it is possible to reconstruct the original message. ^[1] A. Albanese, J. Blömer, J. Edmonds, M. Luby: <i>Priority Encoding Transmission</i>. Technical report, International Computer Science Institute, Berkeley, CA, August 1994. ^[2] M.O. Rabin: <i>Efficient Dispersal of Information for Security</i>, <i>Load Balancing and Fault Tolerance</i>. Journal of the Association for Computing Machinery, Vol. 36, No 2. April 1989. ^[3] R. Storn: <i>Modeling and Optimization of PET-Redundancy Assignment for MPEG Sequences.</i> Technical report, International Computer Science Institute, Berkeley, CA, August, May 1995.

The original information stream is divided in a set of messages, coded independently one from the other, as depicted in Figure 1.

Hence, each message is divided in segments, each having a certain priority grade.

The priority is generally specified in terms of the minimum percentage of packets of the whole message required to correctly decode the segment^[4]^[5]. ^[4] A. Albanese, M. Kalfane, B. Lamparter, M. Luby: <i>Application Programmer Interface to PET.</i> Technical report, International Computer Science Institute, Berkeley, CA, August 25, 1995. ^[5] C. Leichner: <i>Hierarchical Encoding of MPEG Sequences using Priority Encoding Transmission (PET)</i>. Dissertation, International Computer Science Institute, Berkeley, CA, November 1994.

The number of blocks for each segment depends on its length and corresponding priority.

The priority of a segment is expressed in terms of its blocks length: the higher the priority the shorter are the blocks, as shown in Figure 2.

For each segment, the length of the block is the same, because they have the same priority.

The PET coding technique consists in considering the m words of the different blocks as the coefficients of a polynomial of order m-1 over a Galois field GF[p], as illustrated in Figure 3.

The polynomial of order m-1, evaluated at different n points over a Galois field GF[p], is uniformly distributed on n packets.

The current implementation of the PET technique is based on erasure codes and considers instrumental the use of integer arithmetic within the Galois field GF[p] (that is the field of the rests of p modulus), within which all the operations are with modulus p.

The original information stream is considered as a sequence of unitary elements (for example, bytes of 8 bits or words of 16 bit), which for simplicity in the ensuing text will be referred to as "words".

After having divided the messages in segments, the segments are partitioned in blocks, so that all blocks of the same segment have the same length m (represented by the number of words) according to a scheme as that depicted in Figure 4. Of course, blocks belonging to different segments may have different lengths.

The m words of each block are considered as the coefficients of a polynomial of order m-1 over the GF[p] field:<maths id="math0001" num=""><math display="block"><mrow><msub><mrow><mtext>p(x)= a</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><msub><mrow><mtext>+a</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>x+a</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msup><mrow><mtext>x</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><msub><mrow><mtext>+.....+a</mtext></mrow><mrow><mtext>m-1</mtext></mrow></msub><msup><mrow><mtext>x</mtext></mrow><mrow><mtext>m-1</mtext></mrow></msup></mrow></math><img file="EP0903955A1_D0001.tif" /></maths>

The coding of the block is formed by the sequence of the n words (n&gt;=m) obtained by evaluating the polynomial at n distinct points of GF[p]. These n values are distributed in n packets so that each packet contains only one value of p(x), calculated in a distinct point of GF[p].

The above described algorithm is repeated for each single block of each segment and the sequence of packets that encode the original message is obtained by grouping within the same packet the polynomial values evaluated for the same point of GF[p] relative to all the segments. In this way, the information relative to each segment are uniformly spread over all the packets.

Of course, when words of 16 bits are mapped over the field GF[2¹⁶+1], there will be a high probability of not using an element of the Galois field. To avoid possible overflow problems, it is possible to operate always with units of 16 bits (even after the mapping), by eliminating the unused element and keeping its location (which will be referred to as its <b>offset</b> or by the symbol ε) properly stored in order to be able to recover the original value after having completed the execution of the required operations.

Besides the offset of the point at which the polynomial is evaluated, it is necessary to introduce the information relative to the priority of the various segments and to their length, in order to be able of exactly reconstructing the original message. This information constitutes a further segment, which in the ensuing description will be referred to as the Priority Table or briefly PT. The priority of the PT segment must be at least equal to that of the segment of highest priority of the message, in order to make possible the decoding of such a PT segment without waiting for a correct reception of other packets.

Decoding of a segment

In the first place a decoder must ascertain that the number of packets received be equal to at least the minimum number m required.

By assuming that this basic requisite is fulfilled; a vector <b>D</b> of the GF[p] points over the Galois field to which the relative packets, desuming this from the packet's headers themselves, is initialized<maths id="math0002" num=""><img file="EP0903955A1_D0002.tif" /></maths>

Starting from said <b>D</b> vector an m*m square matrix A may create<maths id="math0003" num=""><img file="EP0903955A1_D0003.tif" /></maths>

It should be noticed that the j-th column of matrix A is constituted by the j-th powers of the elements of the vector <b>D</b>.

Thence, the decoder must consider all the corresponding words of the m packets relative to the same block (into which the segments are subdivided). These words represent, in a coded form, the m polynomial values associated to the block itself. The decoder must then decode taking into account the respective offset (ε), stored in the header, and reconstruct the vector B with the resulting polynomial values:<maths id="math0004" num=""><img file="EP0903955A1_D0004.tif" /></maths>

At this stage the decoder must solve the linear system<maths id="math0005" num="(2)"><math display="block"><mrow><mtext>Ax = B</mtext></mrow></math><img file="EP0903955A1_D0005.tif" /></maths> where x is a column-vector of m elements, thus obtaining the m words of the original block.

Scope and summary of the invention

The object of the present invention is to provide a system for implementing the Priority Encoding Transmission (PET) algorithm having a modular architecture, finalized toward the realization of a device easily integrable in a hardware system suited for multimedia applications.

The system of the invention is defined in claim 1 and other particularly important and advantageous features are defined in additional dependent claims based on claim 1.

The system of the present invention rests on the recognition of the peculiarity that the A matrix depends only on the points GF[p] to which the PET packets pertain; therefore, such a matrix remains constant for all the blocks of all the segments of the original message.

Therefore, it may be assumed to invert the matrix A only once for each message rather that once per each single block of each segment.

However, even such a procedure would be very laborious and would require either a relatively complex hardware system or long processing times.

Instead of inverting the matrix A, it has been considered to carry out a decomposition, by way of the so-called LU (lower-upper) decomposition, in the product of two square matrices having the same dimensions of the matrix A:<maths id="math0006" num="(3)"><math display="block"><mrow><mtext>A = L U</mtext></mrow></math><img file="EP0903955A1_D0006.tif" /></maths> where L (lower) is a triangular lower matrix (that is, having not null elements only along its diagonal and below it) and the matrix U (upper) is a triangular upper matrix (that is, having not null elements only along its diagonal and above it).

Therefore, the solution of the linear system of the original equation (2) becomes the following,<maths id="math0007" num="(4)"><math display="block"><mrow><mtext>L U x = B</mtext></mrow></math><img file="EP0903955A1_D0007.tif" /></maths> which is in turn decomposable in the following two "sub-problems":<maths id="math0008" num=""><math display="block"><mrow><mtable><mtr><mtd><mrow><mtable><mtr><mtd><mrow><mtable><mlabeledtr><mtext>(5)</mtext><mtd><mrow><mtext>L y = B</mtext></mrow></mtd></mlabeledtr></mtable></mrow></mtd></mtr><mtr><mtd><mrow><mtable><mlabeledtr><mtext>(6)</mtext><mtd><mrow><mtext>U x = y</mtext></mrow></mtd></mlabeledtr></mtable></mrow></mtd></mtr></mtable></mrow></mtd></mtr></mtable></mrow></math><img file="EP0903955A1_D0008.tif" /></maths>

These two sub-problems are much simpler than the original problem thanks to the triangular structure of the two matrices L and U, and their solution may be easily reached by simple substitutions.

On this basis, it is possible to realize a dedicated hardware system perfectly capable to implement a PET encoding while remaining relatively simple to integrate in a modular form in a VLSI (Very Large Scale of Integration) device which may be easily integrated in a hardware system, like for example in a "set-top-box" system for multimedia applications.

The PET decoder of the invention is composed of two main modules: <ul id="ul0002" list-style="bullet" compact="compact"><li>the <b>PU</b> (processing unit) module, which carries out the decoding itself by solving the relative systems of equations;</li><li>the <b>CU</b> (Control Unit) module, which interfaces the PU module with the external world, adapts and synchronizes the PET decoder with other external devices, taking into account of the different clocks, recognizes whether or not the format is of the PET type, and supplies to the <b>PU</b> module the information contained in the incoming data packets, in a correct order and format.</li></ul>

Characteristics and advantages of the invention

<ul id="ul0003" list-style="none" compact="compact"><li>1. The PET device of the invention, if compared to other error correcting decoders based on the Reed-Solomon and Viterbi algorithms performs an error correction on the whole message rather than on the single bits.</li><li>2. The added redundancy is not fixed beforehand as in the case of the Reed-Solomon and Viterbi algorithms, instead, it depends on the nature of the message to be coded; this allows an occupancy of the channel of lower transmission band or in the worst of cases equal to such known techniques of error correcting.</li><li>3. The decoder based on the PET algorithm provides for an optimal band occupation while ensuring a good quality of reception even in the case of packet losses.</li><li>4. The modular architecture based on the two instinct units or modules, <b>PU</b> and <b>CU</b>, allows the PET decoder to be independent from the type of format of the data being processed.</li><li>5. The decoding is transparent to fact that the messages be compressed or not, be pictures or sounds or any other type of information. Of course, it is necessary that the decoder part of an application supported by the ATM network and that the message be in PET format.</li><li>6. The PET decoder is designed to have an independent interface with packet switching networks and whichever scalable application. It may, for example, accept different Quality of Service requests.</li><li>7. For applications of this latter type, a certain priority scheme according to which the redundancy is calculated must be prearranged.</li><li>8. The usefulness of the decoder of the invention is not limited to applications wherein compressed data are handled, on the contrary the decoder is able to manage any kind of scalable information.</li></ul>

Brief description of the drawings

The various aspects and advantages of the invention will become even clearer through the following description and by referring to the attached drawings wherein: <ul id="ul0004" list-style="none" compact="compact"><li><b>Figure 1</b> shows the division of the information stream in independent messages and in segments;</li><li><b>Figure 2</b> shows the block structure of each segment;</li><li><b>Figure 3</b> shows the PET data coding system of the various blocks into which are divided the segments as the coefficients of a polynomial on a Galois field;</li><li><b>Figure 4</b> shows the way the segments are structured in blocks;</li><li><b>Figure 5</b> is a high level functional block diagram of a multimedia hardware application commonly known as "set-top-box";</li><li><b>Figure 6</b> is a block diagram showing the modular architecture of the decoder of the invention;</li><li><b>Figure 7</b> is a block diagram of a PET decoder realized according to the present invention;</li><li><b>Figure 8</b> is a block diagram of the <b>CU</b> unit of the PET decoder of the invention;</li><li><b>Figure 9</b> shows the scheme of the headers reading device:</li><li><b>Figure 10</b> shows the scheme of the memory interface device:</li><li><b>Figure 11</b> shows the scheme of the offset removal device;</li><li><b>Figure 12</b> shows a flowsheet of the functions performed by the central unit block of the <b>CU</b> module;</li><li><b>Figure 13</b> is a block diagram of the processing Unit of the decoder;</li><li><b>Figure 14</b> highlights the functioning scheme of the processing module <b>PU</b>.</li></ul>

DESCRIPTION OF THE CONTROL UNIT CU

The tasks of the Control Unit (<b>CU</b>) consist in reconstructing the blocks to be decoded starting from the packets received, by considering that the original message may be any sequence of information.

The control unit <b>CU</b> is practically an interface between the PET decoder and the external world (ATM interface, multiprogrammable parallel processor. multimedia peripherals), moreover it feeds the data to the Processing Unit (<b>PU</b>) according to the required order and format.

The ensuing description describes the essential blocks constituting the Control Unit CU.

The <b><i>Lo-Hi_In</i></b> and <b><i>Lo-Hi</i></b><i>_<b>Out</b></i> blocks respectively connect the decoder to the ATM network and to a parallel programmable processor allowing, depending on the application, the transfer of 8, 16, 32, 64 bit for each clock pulse.

The <b><i>Control Logic</i></b> module represents the core of the <b>CU</b> module; its task is that of synchronizing the entire system. In first place it recognizes the PET format, and in the affirmative case the decoding is started.

The decoding for each block follows the steps shown in the flowsheet. The first blocks to be decoded are of course those relative to the segments that codify the Priority Table, in order to obtain the basic information for decoding the successive blocks. The first word acquired at the initial instant, or after a reset operation, is interpreted as the PET packet length.

The <b><i>Memory Interface</i></b> block is an arbitration system that prevents possible conflicts between read cycles (when the datum supplied by the ATM interface is ready) and the write cycles (by the <b>CU</b>). The main function of this block consists in generating interface signals with the memory as needed to manage the read and write cycles. Furthermore, there is a need to solve the problem relative to the bus arbitration for preventing the <b><i>Lo-Hi</i></b><i>_<b>In</b></i> module to write in the memory while the <b>CU</b> is reading and viceversa. This problem is overcome by holding a read request if a write request is being served and viceversa.

The block <b><i>Offset Removal</i></b> eliminates the offset from the data by adding 1 if the offset value is less than that of the datum. This module has the task of removing the offset introduced during the coding phase, by generating a 17-bit word starting from two words of 16 bits.

The exchange of information between the <b>CU</b> and the <b>PU</b> modules takes place by way of three buffers contained in the <b>CU</b> module: <b><i>Buff</i></b><i>_<b>In</b></i>, <b><i>Buff</i></b><i>_<b>Out</b></i> and <b><i>Buff</i></b><i>_<b>TP</b></i>. The <b>CU</b> stores in <b><i>Buff</i></b><i>_<b>Out</b></i> the necessary information for the decoding, delivering to the <b>PU</b> module a start signal and indicating whether the information relate to a TP. The <b>PU</b>, after having performed the decoding, stores the data in <b><i>Buff</i></b><i>_<b>TP</b></i> if the data related to priority table or in <b><i>Buff</i></b><i>_<b>In</b></i> if they related to messages.

It should be noticed the presence of a common bus among the blocks: <b><i>Control Logic</i></b>, <b><i>Memory interface</i></b>, <b><i>Lo-Hi In</i></b>, <b><i>Lo-Hi Out</i></b> and <b><i>Offset Removal</i></b>, this is deliberately realized to make the system faster as the datum may be acquired <u>simultaneously</u> by more blocks.

DESCRIPTION OF THE PROCESSING UNIT

Figure 14 shows a block diagram of the Processing Unit (<b>PU</b>), which carries out the actual decoding operations, that is reconstructs the original block of data from the coded one.

This <b>PU</b> module must be necessarily implemented in a hardware form because the operations must be executed very quickly (it should be kept in mind that the PET technique was created to protect video/audio sequences for which may require transmission in real time). The different blocks shown in the scheme act in a sequential manner, meaning that when one of them terminates its processing operations, it enables the following block, an so forth.

Fundamentally, the task of the Processing Unit <b>PU</b> is that of solving a system of linear equations:<maths id="math0009" num=""><img file="EP0903955A1_D0009.tif" /></maths> therefore, the PU functioning may be summarized in the following four steps: <ul id="ul0005" list-style="bullet"><li>Construction of the matrix <b>A</b></li><li>Triangular factorization of the matrix<maths id="math0010" num=""><img file="EP0903955A1_D0010.tif" /></maths></li><li>Solution of the system<maths id="math0011" num=""><img file="EP0903955A1_D0011.tif" /></maths></li><li>Solution of the system</li></ul><maths id="math0012" num=""><img file="EP0903955A1_D0012.tif" /></maths>

The figure depicts the whole diagram of the PET Processing Unit; in this scheme, besides the <b>SRAM</b> and <b>ROM</b> memories, are shown the blocks: <b><i>build_A</i></b>, <b><i>Lu_dec</i></b>, <b><i>find_Y</i></b> and <b><i>find_X</i></b>, which implement the above described functions of the four processing steps previously illustrated.

In order to accelerate the decoding operations of the various data segments, the four modules of the Processing Unit function in parallel (pipelining), in order to process data in the four block simultaneously; this is possible because the operations undertaken by the single modules are independent of each other.

The only circuital complexity caused by the pipelining is the need for a circuit that implements an appropriate bus arbitration algorithm, to prevent bus contention situations.

The scheme also include memory devices, necessary for the <b>PU</b> to execute the decoding operations; in particular a static <b>RAM</b> memory or a <b>SRAM</b> where to store the intermediate results of the processing operations, and a <b>ROM</b>, from which extract the necessary information to carry out some decoding operations, typically the divisions.

Once the <b>CU</b> has reconstructed the coded blocks, the <b>CU</b> itself places them in the <b><i>Buffer_Out</i></b>, from where the <b>PU</b> reads them and sends the decoded information to a second buffer <b><i>Buffer_In</i></b>, from where they are sent to the <b><i>Lo-Hi_Out</i></b> block and therefrom retrieved for sending them to the end user.

A further buffer, <b><i>Buffer_TP</i></b>, is required to store the priority table containing the necessary information for decoding, which is itself decoded by the <b>PU</b>, and must be placed at the disposal of the <b>CU</b> in order to correctly reconstruct the distinct blocks.

The integration on a card as described in Figure 3 of the various components: the PET decoder, the low consumption parallel programmable processor, and an MPEG decoder, realizes a module that is capable of satisfying numerous requirements of multimedia systems. The high processing capacity and the possibility to handle physical signals, consents the implementation of many applications in the telematic realm. We may cite as examples of possible areas of application of such a module: <ul id="ul0006" list-style="bullet" compact="compact"><li>Digital network nodes for an integrated management of data and voice (in particular for networks with voice compression)</li><li>interface systems of ATM, WAN and LAM channels</li><li>management of broad band channels wherein the requirement of a high processing speed often comes with the requirements of performing parallel operations on more channels</li><li>compression systems for data, voice and images</li><li>multimedia systems</li><li>Video On Demand</li><li>Pay Per View</li><li>Teleconference</li></ul>

In the field of the management of communication within industrial processes, either continuous or batch, the decoder of the invention is useful for: <ul id="ul0007" list-style="bullet" compact="compact"><li>managing systems of numerical control units and of cells (control of more devices)</li><li>Telecontrol and monitoring systems</li><li>Data acquisition systems</li></ul>

Moreover, in case of specific applications, an autonomous control and regulation system capable of handling physical systems requiring rapid responses and complex processing, may be required, as for example transport systems, building control systems, medical control and diagnostic systems, etc.

Cards incorporating the PET decoder of the invention may be used also as special units for accelerating data processing at work stations and Pc_s, like for example the compression of voice and images, the management of large/size databases for multimedia applications (videoconference, Video on Demand, retrieval of information from CD-ROMs,...), scientific calculations in the chemistry and biology field, simulation of physical phenomena, etc. In all these cases it will be important to ensure a bus compatibility and, in some cases, also the ability of managing external signals.