Abstract:
A method and system for parallel encoding of data for bit-stuffed HDLC compatible transmission is presented. The method analyses a byte in parallel with four recirculated previously encoded bits during each clock cycle. The recirculated bits allow for correct analysis of the presence of a fifth consecutive one within the byte including the first four bits thereof. The encoded byte is provided to a FIFO and, when 8 bits are stored therein, the eight most significant bits are extracted from the FIFO for transmission via a digital or analogue network. The FIFO provides two bytes without receiving an intervening encoded data byte when a risk of an overflow exists.

Description:
FIELD OF THE INVENTION 
     This invention relates generally to digital communications and more particularly to a method of encoding and decoding data for a digital communication system. 
     BACKGROUND OF THE INVENTION 
     In transmitting HDLC encoded information a variable number of data bits are transmitted between two delimiting flags--one at the beginning and one at the end. The flags and the data therebetween form a data frame. Unfortunately, a flag byte is transmitted as a series of bits which are possibly contained within the data. As such, data encoding--bit stuffing--is used to eliminate any occurrences of a flag bit sequence from within the data. 
     For example, a flag of 6 consecutive `1` bits preceded by a `0` bit and followed by a `0` bit indicates a frame beginning and a frame ending. During data transmission, when five consecutive `1` bits occur, a `0` bit is inserted after the fifth consecutive `1` bit to ensure that six consecutive `1` bits--a start frame flag or end frame flag--do not occur and that a reverse process of bit unstuffing is straightforward. For decoding of the encoded data, every time five `1` bits are detected, the following `0` bit is removed from the data. When the following bit is a `1` bit, it is a flag and appropriate processing of the frame occurs. 
     In serial communication, this results in a transmission of a greater number of bits for a number of input data bits. At the receiving end, the stuffed bits are removed and the number of input data bits is decoded. When transmitting a number of bytes, the method is not problematic because the bytes sent are the bytes received and only during bit stuffing, transmission, and bit unstuffing is the number of data bits effected. For example, a bit stream of sixteen consecutive one bits is encoded as a start frame flag, five consecutive `1` bits, a `0` bit, five consecutive `1` bits, a `0` bit, five consecutive `1` bits, a `0` bit, a `1` bit and an end frame flag. The total frame length is 8+5+1+5+1+5+1+1+8 or 35 bits. The number of bits is not an integral number of bytes--eight bits. 
     A second common approach to bit stuffing is used in byte level communication such as that used with modems. The method involves bit stuffing in a fixed bit length fashion to provide, for example, error detection. One common scheme is parity. In parity, a bit is added to every predetermined number of bytes. Usually the predetermined number is one. For each byte, a parity is determined and a bit indicating the parity is stuffed. When a bit is stuffed for each byte, this results in an increase in transmitted data of 12.5% --an undesirable amount. 
     The process of HDLC bit stuffing is designed to operate at substantially low communications speeds in the order of megabits. In order to perform encoding, a simple counter is used. Every one bit increments the counter; every zero bit resets the counter. When the counter reaches 5, a zero bit is stuffed and the counter is reset. Decoding is performed using a similar counter based system. The counter operates at a same speed as the data communications channel. Unfortunately, current communication paradigms are exceeding 25 Mbits per second, some carrying data at data rates over a Giga bit (1000 Mbits) per second. At these speeds, it is difficult to implement at low cost the HDLC bit stuffing circuits currently in use. Essentially, the effects of noise and other effects of high speed circuitry, renders such an HDLC more expensive and more difficult to design. 
     An encoder decoder for variable length codes is taught by Machado in U.S. Pat. No. 4,675,652 issued Jun. 23, 1987. The encoder encodes data in a fixed ratio of decoded to encoded bits. As such, the encoder decoder is not applicable to HDLC encoding wherein for each 8 bits of data, eight, nine or ten bits result. 
     In U.S. Pat. No. 5,583,500 in the name of Allen et al. and issued on Dec. 10, 1996, a method of encoding and decoding variable bit length data is presented. The patent discloses a system wherein code words are encoded and decoded in a variable length manner. During encoding, each code word is encoded separately and therefore, parallel encoding of code words is performed. During decoding, code word lengths are known and encoded data is divided into code words and allocated sufficient buffer memory for the decoded code word. The method is for use in video signal transmission. 
     Unfortunately, in HDLC encoding, a number of encoded bits is determined by bit contents and is not known in advance. Also, encoding of any bit requires knowledge of the previous 4 encoded bits. Because of these limitations, serial encoding of HDLC data is used as described above. 
     It would be advantageous to provide a means for transmitting HDLC encoded data signals via a packet oriented data network such as a Sonet network. 
     It would be advantageous to provide a low cost high speed HDLC encoding circuit. 
     OBJECT OF THE INVENTION 
     In an attempt to overcome these and other limitations of the prior art, it is an object of the present invention to provide a high speed parallel HDLC encoder and a method of performing HDLC encoding and decoding for high speed digital networks. 
     SUMMARY OF THE INVENTION 
     In accordance with the invention there is provided a 1. A method of encoding and decoding data in a digital communication system comprising the steps of: 
     a) providing a memory buffer for storing one of encoded data and decoded data; 
     b) receiving a plurality of bits; 
     c) analysing n consecutive bits from the received bits and k previous output bits for a predetermined sequence of m bits where n is an integer greater than 1, where m is an integer, and where k is an integer greater than or equal to (m-1); 
     d) transforming the n bits, in dependence upon the analysis, to provide a number of output bits, where the n bits and the k consecutive bits are indicative of the number and content of the output bits; 
     e) when at least j bits are stored in the memory buffer, providing j bits to a transmitting means; 
     f) storing some of the output bits in the memory buffer; and, 
     g) repeating steps (b) through (g). 
     In accordance with the invention there is provided a method of encoding and decoding data in a digital communication system comprising the steps of: providing a plurality of n bit values to a transforming means, where n is an integer greater than 1; in dependence upon the occurrence of predetermined patterns of bits within each f bit value, where f is an integer greater than n and wherein an f bit value is formed by an n bit value and a preceding (f-n) bits, performing in parallel at least one of stuffing bits into and unstuffing bits from said n bit value to provide output bits; storing the output bits; and, when at least a predetermined number of bits is stored, providing bits for one of data transmission and data reception. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     An exemplary embodiment of the invention will now be discussed in conjunction with the attached drawings in which: 
     FIG. 1 is a diagram of potential bit sequences for HDLC encoding and associated encoded bit sequences wherein eight bits are encoded simultaneously in dependence upon the eight bits and four previous bits; 
     FIG. 2 is a simplified flow diagram of a method of performing HDLC encoding in parallel; 
     FIG. 3 is a simplified block diagram of an implementation of a device according to the invention using a first-in-first-out memory buffer; 
     FIG. 4a is a simplified flow diagram of a method of encoding parallel data according to the invention and using a look up table; and, 
     FIG. 4b is a simplified block diagram of an implementation of a device according to the invention using a first-in-first-out memory buffer and a ROM look-up table for encoding/decoding operations. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Sonet networks are high speed optical communications networks carrying packetised data. Often the data packets are 8 bits in length. These fixed length data packets are commonly provided to and received from a Sonet transceiver in parallel. Encoding of this data in parallel has numerous advantages which are evident from the following disclosure. 
     Throughout the disclosure the terms encoding is used to mean transforming bits for transmission and decoding is used to mean transforming bits that are received. Bit-stuffing is a form of encoding which is a form of transforming data. Bit unstuffing is a form of decoding which is also a form of transforming data. 
     In transmitting HDLC information using byte oriented transmissions, a variable number of data bits are transmitted with each packet. The number of bits is variable because of bits included within packets using bit-stuffing. The most common approach to bit-stuffing is used in digital data communications having a continuous serial data stream for which HDLC was designed and where addition of data bits has little effect other than upon throughput. As described above, when certain bit patterns occur, additional bits are inserted within or following the pattern. 
     An embodiment is disclosed herein with reference to a packet size of eight bits--eight bits are received in parallel and eight bits are provided for transmission during each clock cycle. It is evident to those of skill in the art that the method is applicable to packets of other sizes, both larger and smaller. 
     Referring to FIG. 1 a diagram of possible bit stuffing patterns is shown. The bits in the table that are being processed--bit--stuffed--are labeled a through h and the bits in a data store awaiting transmission are labeled 16 through 0. In all 17 bits await transmission while 8 bits are processed and up to two extra bits are stuffed. Those data values that are not shown are pseudo don&#39;t cares; they are selected such that the data values do not match another data value in the table and thereby result in another five consecutive `1` bit code. For example, referring to DEC --  13, the intervening bit, `b,` must be a `0` bit. Referring to DEC --  06, when c, d, e, f, and g are all `1` bits, the resulting data is the same as DEC --  07. Therefore, DEC --  06 precludes c through e being all `1` bits. 
     As is evident from the table of FIG. 1, there is a small finite number of bit-stuffing options. This number, 15, is determined in dependence upon the value of the 12 bits 3 . . . 1, and a . . . h. The analysis of the 12 bits is a straightforward operation. Of course, one of the bit-stuffing options results in no bit-stuffing--input data is provided as output data. Once a stuffing pattern is determined, the data in the data store is shifted down (left in the figure) and the stuffed data is stored within the data store. In the data store shown in FIG. 1, the rightmost data bits provide four of the twelve bits necessary for processing the following eight bits. Preferably, the four bits are provided to the data store and recycled to the processing circuit allowing transmission of the four bits during processing of a subsequent byte. Eight bits are transmitted each cycle to remain synchronous with the communication network. When bit stuffing has resulted in an extra eight bits, an extra byte is available for transmission. Data input is suspended for one clock cycle while an additional byte is transmitted. The method then proceeds. 
     Referring to FIG. 2, a simplified flow diagram of a method of performing HDLC encoding in parallel is shown. A predetermined number of bits in the form of an eight bit byte is provided to an encoder. The encoder processes the bits to determine output bits. eight, nine, or ten bits result from the processing. The output bits comprises the input bits and up to two `0` bits inserted as described above. The processing is performed in parallel using, for example, logic gates. Preferably, output bits are determined in parallel to maximise circuit speed. 
     Each bit is determined in dependence upon all previous input bits to ensure that, for example, six contiguous `1` bits are not stuffed with two `0` bits. As is evident from FIG. 1, the input bits are determinative of the output bit pattern; each output bit is determined from the input bits only. Alternatively, each output bit is used in determining a next output bit. Once the encoded data is determined, a byte of data is provided from the data store to a transceiver and the output bits--from eight to ten bits--are provided to the data store. Alternatively, when the data store contains two bytes, two bytes are provided to the transceiver and the output bits--from eight to ten bits--are provided to the data store. 
     
                                           TABLE 1__________________________________________________________________________Sample logic to implement bit stuffing__________________________________________________________________________bito[a] = biti[a]zerob = bits[3] bits[2] bits[1] bits[0] biti[a]bito[b] = biti[b] NOT (zerob)shiftc = zerobzeroc = NOT(bits[3]) bits[2] bits[1] bits[0] biti[a] biti[b]bito[c] = NOT(zeroc) ((biti[b] shiftc) (biti[c] NOT(shiftc)))shiftd=zerob zeroczerod = NOT(bits[2])  bits[1]bits[0] biti[a] biti[b] biti[c]bito[d] = NOT(zerod) ((biti[c] shiftd) (biti[d] NOT(shiftd)))shifte= zerob zeroc zerodzeroe = NOT(bits[1])  bits[0]biti[a] biti[b] biti[c] biti[d]bito[e] = NOT(zeroe) ((biti[d] shifte) (biti[e] NOT(shifte)))shiftf= zerob zeroc zerod zeroezerof = NOT(bits[0]biti[a] biti[b] biti[c] biti[d] biti[e]bito[f] = NOT(zerof) ((biti[e] shiftf) (biti[f] NOT(shiftf)))shiftg= zerob zeroc zerod zeroe zerofzerog = NOT(biti[a] biti[b] biti[c] biti[d] biti[e] biti[f]bito[g] = NOT(zerog) ((biti[f] shiftg) (biti[g] NOT(shiftg)))shifth= zerob zeroc zerod zeroe zerof zerogzeroh = (NOT(biti[b] biti[c] biti[d] biti[e] biti[f] biti[g]) (zerobbiti[b]biti[c] biti[d] biti[e] biti[f])bito[h] = NOT(zeroh) ((biti[g] shifth) (biti[h] NOT(shifth)))shifti.sub.-- 1 = zerob zeroc zerod zeroe zerof zerog zerohshifti.sub.-- 2 = zerob zerohi.sub.-- exists = zeroi shifti.sub.-- 1 shifti.sub.-- 2zeroi = (NOT(biti[c]) biti[d] biti[e] biti[f] biti[g] biti[h]) (zerocbiti[c]biti[d] biti[e] biti[f] biti[g]) (zerob NOT(biti[b]) biti[c] biti[d]biti[e] biti[f] biti[g])bito[i] = NOT(zeroi) ((biti[g] (shifti.sub.-- 2) (biti[h] (NOT(shifti.sub.-- 2) shifti.sub.-- 1))))shiftj.sub.-- 2 = (zerob (zeroh zeroi)) (zeroc zeroi)zeroj = (zeroc NOT(biti[c]) biti[d] biti[e] biti[f] biti[g] biti[h])(zerobNOT(biti[c]) biti[d] biti[e] biti[f] biti[g] biti[h]) (zerod biti[d]biti[e] biti[f] biti[g] biti[h])j.sub.-- exists = zeroj shiftj.sub.-- 2bito[j] = NOT(zeroj) (biti[h] shiftj.sub.-- 2)__________________________________________________________________________ 
    
     Referring to Table 1 above, the bits are labeled as follows: biti[a..h] are the input bits from a byte for transmission, bits[3..0] are four consecutive bits of previously encoded data, one of which is consecutive with a bit from the byte for transmission, and bito[a..j] are the output bits--the results of the encoding process. Zero# is indicative of a stuffed zero at a particular bit location and shift# is indicative of an input bit being shifted by a stuffed `0` bit or two. The `#` in the zero# and shift# are replaced with a bit location (a..j) in Table 1. 
     The bits, bits[3..0] are already stuffed so bito[a] is equal to biti[a] every time. When biti[a] is a fifth consecutive `1` bit, bito[b] is a `0`--it is a stuffed bit--as reflected by the value of zerob. All proceeding bits are shifted at least one space--to the right in FIG. 1--so shiftc is based on zerob. 
     zeroc is based on the five previous bit values--bits[2..0] and biti[a.b] as well as on zerob. When zerob is set, a `0` bit has been stuffed into bito[b] leaving no previous consecutive `1` bits in the encoded bits, therefore, zeroc requires more complicated logic for a determination. As only a limited number of bits are analysed during a cycle, and a finite number of bit patterns exist, the logic shown in Table 1 can be significantly reduced. It has not been reduced or optimised herein to maintain readability. Optimisation of the logic, is a straightforward operation for one of skill in the art. 
     When either zerob or zeroc is set, bito[d] is shifted--to the right in FIG. 1. This is reflected in shiftd which is based on zerob and zeroc. For each output bit bito[c..h], one of three values results--a `0` bit when bit-stuffing of that bit is performed as indicated by zeroc, zerod, . . . a corresponding biti when no bit stuffing has occurred in a previous bit, and a biti of a preceding bit when a single `0` bit has been stuffed. As is evident from a review of FIG. 1, the first possible output bit after two stuffed `0` bits, is bito[i]. Therefore for bito[i..j], there exists a fourth result--a biti preceding the bito by two when two `0` bits have been stuffed. Of course, bito[i] is only filled when at least a `0` bit has been stuffed and bito[j] is only filled when two `0` bits are stuffed. 
     As is evident from Table 1, the logic is more complicated as the number of potential results increases, but is easily extrapolated from the table. For example, using 16 bits of data input and 4 bits from the data store, results in up to 20 data output bits comprising up to four stuffed `0` bits. Therefore, the a output bit has a single result, the b output bit has one of two results, the c through h output bits have one of three results, the i through n output bits have one of four outcomes, the o through p output bits have one of five outcomes, the q through t output bits are only used when bit-stuffing has been performed on the data and, therefore, each has fewer possible results than the preceding bit as well as the possibility of not being used. 
     The method as employed in the flow diagram of FIG. 2 or as implemented using an optimised version of the equations of Table 1, analyses and performs encoding with eight input bits simultaneously and therefore is capable of operating at speeds of approximately eight times those supported by conventional HDLC encoders. Of course, encoding more bits in parallel increases potential data throughput and is limited only by integrated circuit size, and other known design factors. 
     Referring to FIG. 3, a simplified block diagram of a circuit for performing data encoding according to the invention is shown. The circuit comprises an integrated circuit in the form of an ASIC 10. Alternatively, a programmable logic device is used. The ASIC 10 receives a clock signal 12 and eight data input bits 14. Of course, when more data input bits are provided in parallel, the ASIC 10 is designed to receive them. Within the ASIC 10 are two main blocks 22 and 20. A encoding logic block 22 encodes the input data bits and recirculates the last four bits for a subsequent encoding operation. The output bits 24 are loaded into the FIFO block 20. The FIFO block 20 comprises a first-in-first-out (FIFO) memory with an eight bit parallel output 30 and a variable bit input 24a. The FIFO block 20 is loaded with eight, nine or ten bits. In the diagram of FIG. 3, this is controlled by the logical values shifti --  1 26 indicating at least nine bits and shiftj --  2 28 indicating ten bits. The bits cascade to a FIFO block output 30 where, during each clock cycle, a byte is provided out of the ASIC 10 for transmission over a Sonet network. A feedback signal 32 from the FIFO block 20 provided to the encoding logic block 22 and to circuitry (not shown) outside the ASIC 10 pauses data input when the FIFO block 20 may overflow. This provides an extra clock cycle for reducing data within the FIFO block 20 without clocking more encoded data into the FIFO block 20. 
     When clocked the ASIC 10 provides an output byte from the FIFO block output 30 and clocks in an input byte 14. This provides eight free bit spaces within the FIFO block 20 during each clock cycle. Of course, because bit-stuffing is occurring, the eight freed bit spaces are often replaced with nine or ten bits. When overflow is likely, the feedback signal 32 ensures that when clocked, the ASIC 10 provides an output byte and does not clock in an input byte. During decoding, underflow is a potential problem so the feedback signal 32 indicates that no data is being output from the ASIC 10 during a particular clock cycle. 
     When the encoding block 22 provides bits 24 to the FIFO block 20, the encoding block 22 also latches four bits--farthest to the right in FIG. 1--for use in the subsequent cycle. Alternatively, the four bits are provided to the FIFO block 20 and the FIFO block 20 provides the bit values back to the encoding block 22. When the latter is done, the FIFO block 20 is designed to prevent the output of the last four bits until encoding of a next data byte is complete. 
     Referring to FIG. 4a, a method of encoding parallel data according to the invention and using a look up table is shown. In 4b, a block diagram for carrying out the method of FIG. 4a is shown. Twelve bits are provided to lookup table 122. The table comprises twelve address line inputs 114 and twelve data line outputs 124. Look up tables of this magnitude are often formed of several ROMs (shown in FIG. 4b as a single ROM). The twelve bit input 114 is provided to the lookup table and an encoded bit pattern is output. Two of the twelve output bits 126 and 128 are flag bits indicating a presence of extra bits in the stuffed bits. When no bits are stuffed, the extra bits are `0` bits. Of course, different polarity may also be used. When bits are stuffed, one or both of the extra bits are set to `1.` 
     The least significant four bits are recirculated to the ROM input and latched in latch 115 for a subsequent cycle. The eight, nine, or ten bits of an encoded output value are also provided to a FIFO block 120 in the form of a shift register where they are shifted down. When eight bits are in the shift register and the shift register is clocked, the bits are transmitted. When less than eight bits occupy the shift register, the shift register awaits further bits. A quick analysis determines that the shift register will have at most seven bits (less than eight bits) and ten additional bits resulting in a seventeen bit shift register as shown in FIG. 1. Control circuitry 121 is only necessary for determining a number of bits in the shift register and whether eight, nine, or ten bits are being shifted into the shift register. Since both of those are straightforward control tasks, the resulting circuit is simple, efficient, and using an eight bit encoder/decoder (as disclosed) requires substantially 1/8 the clock speed of prior art serial encoders. 
     It is obvious to those of skill in the art that increasing the size of the lookup table to support 16 bit encoding is possible but is likely to increase costs significantly. Therefore, when larger numbers of bits are encoded in parallel, the method described with respect to Table 1 and FIG. 3 is preferred. 
     Numerous other embodiments of the invention are envisaged without departing from the spirit or scope of the invention.