Coded data generation or conversion – Digital code to digital code converters – To or from nrz codes
Reexamination Certificate
2001-11-08
2003-08-26
JeanPierre, Peguy (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from nrz codes
C341S106000, C341S069000
Reexamination Certificate
active
06611216
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to data compression. More specifically, the invention relates to encoding/decoding data for use in communications systems.
BACKGROUND OF THE INVENTION
One design factor in communication systems is the scheme of encoding used to transmit data. One such scheme, popular in serial communication lines such as T1 is referred to as Non Return to Zero Inverted (NRZI) encoding. In NRZI, the last transmitted bit is fed back or stored to determine the outcome of the next bit encoded.
FIG. 1
shows a traditional NRZI encoding engine
100
that encodes an input bitstream
105
into an output bitstream
110
. The last transmitted bit is fed back into the encoding engine
100
to determine the next bit in output bitstream
110
. The logic for determining the content of output bitstream
110
is as follows. If the current bit of input bitstream
105
is a zero, then the current output bit is the opposite of the last transmitted bit. If however the current input bit is one, then the output bit is the same as the last transmitted bit. For instance, consider the following input bitstream “0110010111010” (from left to right) and that the start is a low state or a zero. In this case the output bitstream would be “1110110000110”. NRZI encoding is inherently serial in nature, since the last transmitted bit determines how the current input bit should be handled in order to encode that current input bit. Thus, for a unit of data such as an 8-bit byte to be NRZI encoded, it must be processed bit-by-bit in a serial fashion. This impacts the speed and efficiency of the communications system in handling data through its nodes. If bytes or other units of data could be encoded and decoded through NRZI but without resorting to serializing of the data and then re-assembly back into bytes, system efficiency can be increased.
Another technique called Zero Insertion is used to prevent a long string of ones a phenomenon known as flag sequence duplication. In SDLC (Synchronous Data Link Control), a flag sequence known as the “
7
E” flag separates frames of data. The binary equivalent of the
7
E flag would be 01111110, and thus has a string of 6 consecutive ones. If such a string occurs in the data stream itself (between real
7
E flags), the decoding may confuse it for a flag indicating the start of another frame. To avoid this confusion, whenever a series of five 1s is encountered, a zero is inserted into the data stream. As with the NRZI encoding process, this too is inherently serial, in that the number of consecutive ones must be counted as they occur in the data stream. When decoded, these zeroes are removed, also in the same serial manner. As a result, even if NRZI itself were not serial, zero insertion and removal would still remain a strictly serial operation, once again adversely impacting the speed of the communications system.
SUMMARY OF THE INVENTION
What is disclosed is a method comprising forming an address for non-return-to zero inverted (NRZI) encoding of a current input data byte, and accessing in a look-up table an NRZI output value pointed to by the address, the NRZI output value the equivalent of having performed NRZI encoding upon the current input data byte.
REFERENCES:
patent: 4520346 (1985-05-01), Shimada
patent: 5021894 (1991-06-01), Naito et al.
patent: 5136436 (1992-08-01), Kahlman
patent: 5192949 (1993-03-01), Suzuki et al.
patent: 5257365 (1993-10-01), Powers et al.
patent: 5379419 (1995-01-01), Heffernan et al.
patent: 5699061 (1997-12-01), Shimpuku
patent: 5706495 (1998-01-01), Chadha et al.
patent: 5745764 (1998-04-01), Leach et al.
patent: 5765028 (1998-06-01), Gladden
patent: 5781896 (1998-07-01), Dalal
patent: 5794228 (1998-08-01), French et al.
patent: 5794229 (1998-08-01), French et al.
patent: 5794246 (1998-08-01), Sankaran et al.
patent: 5799300 (1998-08-01), Agrawal et al.
patent: 5805885 (1998-09-01), Leach et al.
patent: 5822751 (1998-10-01), Gray et al.
patent: 5832475 (1998-11-01), Agrawal et al.
patent: 5850547 (1998-12-01), Waddington et al.
patent: 5852821 (1998-12-01), Chen et al.
patent: 5864857 (1999-01-01), Ohata et al.
patent: 5890151 (1999-03-01), Agrawal et al.
patent: 5905985 (1999-05-01), Malloy et al.
patent: 5918225 (1999-06-01), White et al.
patent: 5926820 (1999-07-01), Agrawal et al.
patent: 5940822 (1999-08-01), Haderie et al.
patent: 5963936 (1999-10-01), Cochrane et al.
patent: 5978788 (1999-11-01), Castelli et al.
patent: 5978796 (1999-11-01), Malloy et al.
patent: 5987467 (1999-11-01), Ross et al.
patent: 5991754 (1999-11-01), Raitto et al.
patent: 5999192 (1999-12-01), Selfridge et al.
patent: 6003029 (1999-12-01), Agrawal et al.
patent: 6006216 (1999-12-01), Griffin et al.
patent: 6023695 (2000-02-01), Osborn et al.
patent: 6064999 (2000-05-01), Dalal
patent: 6108647 (2000-08-01), Poosala et al.
patent: 6115705 (2000-09-01), Larson
patent: 6122628 (2000-09-01), Castelli et al.
patent: 6134541 (2000-10-01), Castelli et al.
patent: 6141655 (2000-10-01), Johnson et al.
patent: 6151601 (2000-11-01), Papierniak et al.
patent: 6161103 (2000-12-01), Rauer et al.
patent: 6163774 (2000-12-01), Lore et al.
patent: 6173310 (2001-01-01), Yost et al.
patent: 6182061 (2001-01-01), Matsuzawa et al.
patent: 6189004 (2001-02-01), Rassen et al.
patent: 6208975 (2001-03-01), Bull et al.
patent: 6212515 (2001-04-01), Rogers
patent: 6212524 (2001-04-01), Weissman et al.
patent: 6356214 (2002-03-01), McDonald et al.
patent: WO 98/49636 (1998-11-01), None
Research Report entitled “Modeling Multidimensional Databases” by R. Agrawal et al., IBM Almaden Research Center, 1995; Presented at the 13thInternational Conference on Data Engineering Apr. 1997, pp. 1-23.
Scientific article entitled “A Data Model for Supporting On-Line Analytical Processing” by C. Li and X.S. Wang; Presented at the International Conference on Information and Knowledge Management, 1996, pp. 81-88.
Scientific article entitled “On the Computation of Multidimensional Aggregates” by S. Agarwal et al.; Presented at the 22ndVLDB Conference, 1996, pp. 1-16.
Web-based Product Review for Arbor Software Corporation's “Essbase 4.0” by Stewart McKie, DBMS, Jul. 1996, http://www.dbmsmag.com/9607d13.html, pp. 1-4.
Scientific article entitled “Implementing Data Cubes Efficiently” by Venky Harinarayan et al.; Presented at the ACM SIGMOD International Conference on Management of Data, Jun. 4-6, 1996, pp. 205-216.
Scientific article entitled “Optimizing Statistical Queries by Exploiting Orthogonality and Interval Properties of Grouping Relations” by C. Li and X. Wang; Presented at the 8thInternational Conference on Scientific & Statistical Database Management, Jun. 1996, pp. 1-10.
Scientific article entitled “Efficiently Supporting Ad Hoc Queries in Large Datasets of Time Sequences” by Flip Korn et al.; Presented at ACM SIGMOD International Conference on Management of Data, May 11-15, 1997, http://www.acm.org/pubs/citations/proceedings/mod/253260.p289-korn/, pp. 1-22.
Scientific article entitled “Towards the Building of a Dense-Region-Based OLAP System” by Cheung et al., Data and Knowledge Engineering, vol. 36, No. 1, 2001, http://www.elsevier.nl/gej-ng/10/16/74/62/24/24/abstract.html, pp. 1-27.
Web-based product brochure entitled “See Data from All Angles with Multidimensional Database Software” by SAS/MCCB® Server, www.sas.com/products/mddb/index.html, 2001, 1 page.
Scientific article entitled “How to Roll a Join: Asynchronous Incremental View Maintenance” by Salem et al.; Presented at ACM SIGMOD on Management of Data and Symposium on Principles of Database Systems, May 15-18, 2000, http://www.acm.org/pubs/citations/proceedings/mod/342009/p 129-salem/#abstract, pp. 1-13.
Scientific article entitled “Hierarchies and Relative Operators in the OLAP Environment” by Pourabbas et al., SIGMOD Record, vol. 29, No. 1, Mar. 2000, http://dblp.uni-trier.de/db/journals/sigmod/sigmod29.html, pp. 1-8.
Chapter 4 entitled “Extending Practical Pre-Aggregation in On-Line Analytical Processing” of the Ph.D Dissertation entitled “Aspects of Data Modeling and Query Proce
McDonald Rickie
Monsson Cai
Ukhalkar Sanjeev
Blakely , Sokoloff, Taylor & Zafman LLP
Cisco Technology Inc.
Jean-Pierre Peguy
LandOfFree
Fast look-up table based scheme for NRZI encoding/decoding... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast look-up table based scheme for NRZI encoding/decoding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast look-up table based scheme for NRZI encoding/decoding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3130929