WPCL 2BJ|x HH Hp P X`h!(#   6p&6p&  c4 P   H8NFOREWORD  H Ё The CCITT (the International Telegraph and Telephone Consultative Committee) is the permanent organ of the International Telecommunication Union (ITU). CCITT is responsible for studying technical, operating and tariff questions and issuing recommendations on them with a view to standardizing telecommunications on a worldwide basis.  H  The Plenary Assembly of CCITT which meets every four years, establishes the topics for study and approves Recommendations prepared by its Study Groups. The approval of Recommendations by the members of CCITT between Plenary Assemblies is covered by the procedure laid down in CCITT Resolution No. 2 (Melbourne, 1988).  H  Recommendation V.42 bis was prepared by Study Group XVII and was approved under the Resolution No. 2 procedure on the 31st of January 1990. UMITU1990  H ЁAll rights reserved. No part of this publication may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying and microfilm, without permission in writing from the ITU. HP X`h!(#Ђ Recommendation V.42 bis Hp P X`h!(#: c4 P DATA COMPRESSION PROCEDURES FOR DATA CIRCUIT TERMINATING >EQUIPMENT (DCE) USING ERROR CORRECTING PROCEDURES  c4 P  The CCITT, considering  H  (a)pthat the use of VSeries DCEs for transmission of asynchronous data onI  HH Ђ Recommendation V.42 bis PAGE7 c4 P  I  HH ЂPAGE6 c4 P  Recommendation V.42 bis  X the general switched telephone network (GSTN) is widespread;  (b)pthat Recommendation V.42 [1] defines error correction procedures providing improved error performance;  (c)pthat improved throughput is possible through the use of data compression procedures;  (d)pthat there is a need to interwork with DCEs not providing data compression; declares the view  that the data compression procedures to be followed by DCEs using the error correcting procedures defined in RecommendationV.42 be as specified in this Recommendation. 1X Scope 1.1h  General  H  This Recommendation describes a data compression procedure for use with VSeries DCEs.  The principal characteristics of the data compression procedure are:  H   a)pa compression procedure based on an algorithm which encodes strings of characters received from data terminal equipment (DTE)  H   b)pa decoding procedure which recovers the strings of characters from received codewords;  H   c)pan automatic transparent mode of operation when uncompressible data is detected.  H  An exploration of the parameters used in this Recommendation is given in S10. 1.2h  Requirements for error correcting procedures  H  For correct operation of the data compression function it is necessary that an error correcting procedure be implemented between the two entities using this Recommendation. In the case of Vseries Recommendations, this requires that the LAPM (link access procedure for modems) error correcting procedures defined in RecommendationV.42 or the error correcting procedures in RecommendationV.120 [2] be implemented.  Note - Undetected bit errors will cause misoperation of the data compression function. Use of a 32bit frame check sequence (FCS) as defined in ISO 3309 [3] substantially reduces the possibility of such errors. It may therefore be desirable to use this 32bit FCS (which is an option in V.42 LAPM) in environments with severe impairments. 1.3h  A DCE employing data compression  H  The data compression function may be used with an errorcorrecting DCE, as shown in Figure1/V.42 bis. The elements of an error correcting Vseries DCE are specified in RecommendationV.42. Q c4 P FIGURE 1/V.42 bis A DCE employing data compression and error control  c4 P 2X Definitions 2.1h  character  H  Single data element, encoded using a predefined number of bits (N c4 P 3 c4 P  = 8). 2.2h  startstop or asynchronous format  H  Startstop or asynchronous format is defined in Recommendations V.7 [4] and V.14 [5]. 2.3h  ordinal value  H  The ordinal value of a character is the numerical equivalent of the binary encoding of the character. For example, the character "A" when encoded as 01000001 would have an ordinal value of 65 c4 P 10 c4 P . 2.4h  alphabet  H  Set of all possible characters which may be sent or received across the DTE/DCE interface. It is assumed in this Recommendation that the ordinal values of the alphabet are contiguous from 0 to N c4 P 4 c4 P  1, where N c4 P 4 c4 P  is the number of characters. 2.5  codeword  H  A codeword, within the context of this Recommendation, is a binary number in the range 0 to N c4 P 2 c4 P  1 which represents a string of characters in compressed form. A codeword is encoded using a number of bits C c4 P 2 c4 P , where C c4 P 2 c4 P  is initially 9 (i.e. N c4 P 3 c4 P Ġ+1) and increases to a maximum of N c4 P 1 c4 P  bits (see S7). 2.6h  control codeword  H  A control codeword is reserved for use in DCEtoDCE signalling of control information related to the compression function whilst in the compressed mode of operation (see S9). 2.7h  command code  Octet which is used for DCEtoDCE signalling of control information related to the compression function whilst in the transparent mode of operation. Command codes are distinguished from normal characters by a preceding escape character (see S2.13).  2.8p tree structure  H  Abstract data structure which is used in this Recommendation to represent a set of strings with the same initial character (see Figure 2/V.42 bis and S6.1). 2.9  leaf node  Point on a tree which represents, within the context of this Recommendation, the last character in a string (see S6.1). 2.10  root node  H  A root node is a point on a tree which represents, within the context of this Recommendation, the first character in a string (see Figure 2/V.42 bis and S6.1). 2.11  compressed operation  H  Compressed operation has two modes. Transitions between the modes may be automatic based on the content of the data received from the DTE (see S7.1).  H2.11.1  compressed mode  A mode of operation in which data from the DTE is transmitted in codewords.  H2.11.2  transparent mode  H  A mode of operation in which compression has been selected but data is being transmitted in uncompressed form. Transparent mode command code sequences may be inserted into the data stream. 2.12  uncompressed operation  H  A mode of operation in which compression has not been selected. The data compression function is inactive. 2.13  escape character  Within the context of this Recommendation, the escape character is a character which, in transparent mode, indicates the beginning of a command code sequence. This has an initial value of zero, and is adjusted on each appearance of the escape character in the data stream from the DTE, whether in transparent mode or compressed mode (see S9.2). 3X Abbreviations  The abbreviations introduced in this Recommendation are:   EIDp Escape in Data, a command code defined in S9.  HX   ETMpEnter Transparent Mode, a control codeword defined in S9.   ECMpEnter Compressed Mode, a command code defined in S9.  H Ђ 4X Overview of the operation of a DCE incorporating a data compression function 4.1h  General  A DCE employing data compression, as depicted in Figure 1/V.42 bis, contains the following components:   a)pDTE/DCE interchange circuits;   b)pa signal converter;   c)pa control function;  d)pan error control function; and   e)pa data compression function.  H  The control function shall have additional capabilities beyond those needed for an error correcting DCE as described in RecommendationV.42. The additional capabilities of the control function are described in S5, and the operation of the data compression function is described in SS6 to 9. The remainder of this section provides an overview of the control function and data compression function. 4.2h  Overview of the control function  H  The control function shall perform, in addition to the functions defined in S6.2 of RecommendationV.42, the following aspects of operation;  H   a)pnegotiation of the presence of the data compression function in the remote DCE, and of parameters associated with the operation of the data compression function;  H   b)pinitialization or reinitialization of the data compression function;  H   c)pcoordination of the establishment of an error controlled connection for use by the peer data compression functions;  H   d)pcoordination of the delivery of data between the DTE/DCE interface and the data compression function, in accordance with the procedures defined in RecommendationV.42, SS6.2 and 8.4, including the provision of the flow control procedures defined therein;  H   e)pcoordination of the delivery of data between the data compression function and the error control function;   f)paction on detection of an exception condition.  HH 4.3h  Overview of the data compression function  H  The data compression function shall implement the procedures defined in this Recommendation, which result in the efficient encoding of data prior  H to transmission over the error controlled connection, and shall have the following capabilities:   a)pinitialization of the data compression function;   b)pdata compression encoding and decoding;  H   c)pa mechanism for switching between compressed and transparent modes of operation.  H 4.4h  Communication between the control function and the data compression function  Communication between the control function and the data compression function is modelled as a set of abstract primitives of the form XNAMETYPE which represent the logical exchange of information and control to accomplish a task or service. In the context of this Recommendation the control function is viewed as the "service user" while the data compression function is viewed as the "service provider". The types of primitive are request, indication, response and confirm.  H  The services expected by the control function are shown in Table 1/V.42 bis. 5X Operation of the control function 5.1h  Negotiation of the data compression function  H  The use of the data compression function and the associated parameters shall be negotiated at link establishment via a protocol (for example, using the XID procedure defined in RecommendationV.42), following which they remain unchanged for the duration of the error corrected connection. c4 P  QTABLE 1/V.42 bis E Services expected by the control function H(P҇Hp P X(VService UPrimitive YS  P p P X(P c4 P ш P  c4 P H(P҇ P  c4 P Initialize the data compression function CINIT Px65.2, 5.6  P  c4 P ш P  c4 P H(P҇ P p P X(P c4 P Indicate an error to the control function CERROR Px65.8  P  c4 P ш P  c4 P H(P҇ P p P X(P c4 P Transfer uncompressed data to/from the data compression function CDATA Px65.4  P  c4 P ш P  c4 P H(P҇ P p P X(P c4 P Transfer compressed data to/from the data compression function CTRANSFER Px65.5  P  c4 P ш P  c4 P H(P҇ P p P X(P c4 P Flush remaining untransmitted data from the encoder CFLUSH Px65.7  P  c4 P ш HH Hp P X`h!(# c4 P   H Ё c4 P  Parameter P c4 P 0 c4 P  specifies whether or not compression is to be used. This parameter also specifies the directions (transmit only, receive only, or both directions). The default value of P c4 P 0 c4 P  is 0, indicating no compression in either direction. If compression is proposed for only one direction, then the only valid response is for the proposed direction or no compression. If compression is proposed for both directions, then valid responses are for both directions, for either single direction, or for no compression.  Parameter P c4 P 1 c4 P  represents a proposed value of N c4 P 2 c4 P  the total number of codewords. P c4 P 1 c4 P  shall have a default value of 512, which is its minimum value; a maximum value is not specified within this Recommendation. Any attempt to specify less than the minimum value shall be considered a procedural error and result in disconnection. When values of P1 a exchanged during the negotiation procedure in one or both directions of transmission, the lower value shall be selected and assigned to N c4 P 2 c4 P  in both DCEs.  H  Note-See Appendix II for guidance on the choice of value of N c4 P 2 c4 P , and its effect on performance.  H  Parameter P c4 P 2 c4 P  is the proposed value for N c4 P 7 c4 P , the maximum string length. The default value of P c4 P 2 c4 P  is 6, and the permitted range is from 6 to 250. The values outside this range are invalid; and attempt to specify such values shall be regarded as a procedural error and result in disconnection. When values of P c4 P 2 c4 P  are exchanged during the negotiation procedure, the lower value shall be selected and assigned to N c4 P 7 c4 P  in both DCEs. 5.2h  Initialization of the data compression function  Following successful negotiation of data compression parameters, the control function shall issue the CINIT request primitive to the data compression function. The primitive shall indicate the values of the negotiated parameters. 5.3h  Connection establishment  On receipt of the CINIT confirm primitive from the data compression function, the control function shall indicate to the DTE that data transfer may commence.  Hdata  data compression function  On completion of connection establishment, the control function shall request encoding of the data received on the DTE/DCE interface.  To encode data, the control function shall issue a CDATA request primitive to the data compression function. This primitive shall indicate the data to be encoded.  On receipt of a CDATA indication primitive from the data compression function, the control function shall deliver the decoded data to the DTE/DCE interface.  H  Flow control procedures will be necessary in order to avoid potential loss of data due to buffer overflow. When the procedures defined in this Recommendation are used in conjunction with those defined in RecommendationV.42, the flow control procedures defined in RecommendationV.42, SS7.3.1 and 8.4.2, shall be applied.  H 5.5h  Coordination of the transfer of data between the data compression function and error control function  H  On receipt of a CTRANSFER indication primitive from the data compression function, the control function shall issue an LDATA request primitive to the error control function.  On receipt of an LDATA indication primitive from the error control function, the control function shall issue a CTRANSFER request primitive to the data compression function. 5.6h  Reinitialization of the data compression function  H  The control function shall issue a CINIT request to the data compression function on the following conditions:   a)pLESTABLISH indication or confirm;  H   b)pLSIGNAL indication or confirm, where the primitive indicates a destructive form.  H  It is the responsibility of the control functions to ensure that CINIT request primitives are issued only when no data is in transit between the data compression functions (e.g. in the error control functions) to ensure synchronization between the encoders and decoders. 5.7h  Expedited data transfer  H  Certain conditions, the specification of which is outside the scope of this Recommendation, may arise which require that any partially encoded data is transferred immediately, for example if the error control function is in an idle condition. If such a condition arises, the control function shall issue a CFLUSH request primitive to the data compression function, and shall then transfer remaining data in accordance with S5.5. 5.8h  Action on detection of CERROR  The CERROR indication is used to inform the control function that an error (for example, a procedural error or loss of synchronization) has been detected by the data compression function. The control function shall take appropriate recovery action, including reestablishment of the error corrected connection.  The following conditions recognized by the decoder result in the generation of a CERROR indication primitive:  H   a)preceipt of a STEPUP codeword when it would cause the value of C c4 P 2 c4 P  to exceed N c4 P 1 c4 P ;   b)preceipt of a codeword, at any time, equal to C c4 P 1 c4 P ;  H   c)preceipt of a codeword representing an empty dictionary entry;   d)preceipt of a reserved command code.  HH Ђ 6X Procedures for dictionary use and maintenance 6.1h  General  H  The data compression function employs an algorithm in which a string of characters read from the DTE is encoded as a fixed length codeword. The process employs dictionaries, in which the strings are stored, and which are dynamically updated during normal operation.  H  The data compression function contains two dictionaries, one maintained by the data compression encoder for use in compression of data received from the DTE, and one maintained by the data compression decoder for use in the decoding of data received from the error control function.  The dictionary functions are:  H   a)pstring matching, in which a sequence of characters is read from the DTE, and the dictionary searched for the resulting string (see S6.3);  H   b)pupdating, in which a new string is added to the dictionary (see S6.4);  H   c)pthe deletion of infrequently used strings in order that storage capacity may be reused (S6.5).  H  The dictionary used to store strings for use in the encoding and decoding process may be logically represented using an abstract data structure. The dictionary can be considered to contain a set of trees, as shown in Figure2/V.42 bis, each with a root corresponding to a character in the alphabet. With the 8bit character format there will be 256 trees.  H  A tree represents the set of known strings beginning with one specific character, and each node or point in the tree represents one of this set of strings. The trees in Figure 2/V.42 bis represent the strings A, B, BA, BAG, BAR, BAT, BI, BIN, C, D, DE, DO and DOG.  A node that has no dependant nodes, represented by the hierarchically lower level in the tree, is a leaf node. A leaf node represents the last character in a string.  H  A node that has no parent, represented by the hierarchically higher level in the tree, is a root node. A root node represents the first character in a string.  Associated with each node is a codeword used to uniquely identify the node. The assignment of codewords within the encoder dictionary of a data compression function, and the corresponding assignment of codewords within the decoder dictionary of the peer data compression function in the remote DCE are equivalent, and the codeword thus provides a reversible encoding of a string. 6.2h  Dictionary initialization procedure  H  On receipt of a CINIT request primitive from the control function, the data compression function shall reset the encoder and decoder dictionaries to the initial condition.  H  In the initial condition, each tree in the dictionary shall consist only of a root node. The codeword associated with each root node shall be N c4 P 6 c4 P   H (the number of control codewords) plus the ordinal value of the character represented by the node. The counter C c4 P 1 c4 P , used in the allocation of new nodes (see S6.5), shall be set to N c4 P 5 c4 P . 6.3h  String matching procedure  This procedure has the function of matching a sequence of characters (string) with a dictionary entry. The procedure shall commence with a single character representing the first character in the string. The following steps are then applied:   a)pa string shall be formed from the first character;  H   b)pif the string matches a dictionary entry, and the entry is not that entry created by the last invocation of the string matching procedure, then the next character shall be read and appended to the string and this step repeated;  H   c)pIf the string does not match a dictionary entry or matches the entry created by the last invocation of the string matching procedure, the last character appended to the string shall be removed. The string thus shortened represents the longest matched string and the last character represents the unmatched character.  H  This procedure will normally match the longest string of characters. However, there are two cases in which step b) shall be terminated before a longest match is found:  H   i)pif an exception condition occurs such as a CINIT request primitive or C-FLUSH request primitive (while in compressed mode only);  H   ii)pwhen a transition between transparent and compressed modes of operation occurs. HH Ђ 8J c4 P FIGURE 2/V.42 bis 8= Tree based representation of the dictionary  H Ё c4 P  When in transparent mode the encoder shall use only the criteria specified above for terminating the string matching procedure. When in compressed mode, however, the encoder may employ other criteria for terminating the procedure (e.g. a timeout).  H  If the string matching procedure is terminated before a longest match is found, the next character from the DTE shall be considered to be the "unmatched character" for the purposes of updating the dictionary and restarting the string matching procedure. 6.4h  Procedure for adding strings to the dictionary  H  In order to maintain efficient compression, the dictionary is adapted by the addition of new strings. A new string shall be formed by appending a single character to an existing string, thereby adding a new node onto a tree. The single character shall be the unmatched character resulting from the string matching operation, or the prefix character resulting from the string decoding operation. Following this procedure, the single character required to restart the string matching procedure will be the unmatched character.  There are two conditions under which a new string shall not be added:  H   a)pif this would result in the maximum string length, N c4 P 7 c4 P , being exceeded;   b)pif the string is already in the dictionary.  H  Immediately after the creation of a dictionary entry, the procedure for recovering a dictionary entry shall be applied. 6.5h  Procedure for recovering a dictionary entry  This section defines a systematic procedure for recovering dictionary entries for reuse when all available entries have been filled. When the  H last available dictionary entry has been assigned, this procedure recovers a single entry, maintaining the association between the empty entry and its codeword.  A counter C c4 P 1 c4 P  indicates the codeword associated with the next empty dictionary entry, and is maintained in the range N c4 P 5 c4 P  to N c4 P 2 c4 P  1. Counter C c4 P 1 c4 P  shall be set to N c4 P 5 c4 P  initially.  H  The procedure shall be applied only after the creation of a new dictionary entry, and shall consist of the following steps:   a)pcounter C c4 P 1 c4 P  shall be incremented;  H   b)pif the value of C c4 P 1 c4 P  exceeds N c4 P 2 c4 P  1 then C c4 P 1 c4 P  shall be set to N c4 P 5 c4 P ;  H   c)pif the node identified by the codeword with value C c4 P 1 c4 P  is in use and not a leaf node, then go to step a);  H   d)pif the node is a leaf node, then it shall be detached from its parent.  HH Ђ 7X Operation of the encoding function 7.1h  General  The encoding function has five principal operations:  H   a)pstring matching, in which a sequence of characters from the DTE is matched with a dictionary entry (see S7.3);  H   b)pencoding, in which the codeword of the matched dictionary entry is represented as a binary value of length C c4 P 2 c4 P  bits (see S7.4);  H   c)ptransfer, in which either the codeword(s) in compressed mode or the characters in transparent mode are passed to the control function (see S7.5);  H   d)pdictionary updating, in which a new dictionary entry is created, using the matched dictionary entry and the unmatched character (see S7.6);  H   e)pnod recovery, in which a dictionary entry is recovered for use in the next dictionary update (see S7.7).  H  The encoding function operates in one of two modes, transparent mode and compressed mode, switching between these modes on the basis of the test applied in f) below. The sequence of operations, and the cycling of the escape character (see S9) are identical in the two modes of operation.  H  The encoder shall support two further operations, which shall be applied only during the string matching procedure in accordance with S6.3:  H   f)pdata compressibility testing, in which the efficiency of the encoding process is estimated and transparent mode or compressed mode selected to maximize efficiency (see S7.8);  H   g)pflush, in which a CFLUSH request from the control function indicates that all outstanding data shall be sent (see S7.9).  HH 7.2h  Initial conditions  Hx  On receipt of a CINIT request the data compression function shall initialize the encoder to the following state:  H   a)pthe dictionary shall be set to the initial condition described in S6.2;   b)pthe codeword size C c4 P 2 c4 P  shall be set to N c4 P 3 c4 P  + 1;   c)pthe threshold C c4 P 3 c4 P  shall be set to N c4 P 4 c4 P  X 2;   d)pthe function shall be set to transparent mode;  H   e)pthe escape character shall be assigned the ordinal value 0.  HH 7.3h  String matching  H  On receipt of a CDATA request the data compression function shall apply the string matching procedure defined in S6.3. The initial character required shall be the unmatched character resulting from the most recent invocation of this procedure.  7.4pEncoding  H  This procedure is used when in the compressed mode of operation. Its purposes is to represent the codeword as a sequence of C c4 P 2 c4 P  bits; the order and numbering of the bits is shown in Figure 3/V.42 bis.  If the codeword corresponding to the matched dictionary entry is numerically equal to or greater than the threshold C c4 P 3 c4 P  then:  H   a)pthe STEPUP control codeword shall be encoded and transferred using the current codeword size (C c4 P 2 c4 P );   b)pthe codeword size C c4 P 2 c4 P , shall be increased by 1;   c)pmultiply C c4 P 3 c4 P  by 2;  H   d)pif the codeword is still numerically greater than or equal to C c4 P 3 c4 P , steps a) toc) shall be repeated.  H  The codeword is then transferred to the control function, in accordance with the procedures defined in S7.5. Q c4 P FIGURE 3/V.42 bis I Mapping of codewords into octets  c4 P 7.5h  Transfer  H  In transparent mode, characters shall be passed to the control function for transmission in octet aligned form, using a CTRANSFER indication. They may be transferred individually during the string matching procedure, or as a sequence following completion of the string matching procedure.  H  In compressed mode, the matched string shall be encoded according to the procedure defined in S7.4 and passed to the control function in packed form, with the least significant bit of a codeword immediately following the most significant bit of the preceding codeword.  H  When the encoder changes state from transparent to compressed mode, the least significant bit of the first codeword to be transferred shall be bit 1 of the next octet position.  Following transfer of a FLUSH control codeword, or when the encoder changes state from compressed to transparent mode following transfer of the ETM control codeword (see S9) in the sequence, sufficient 0 bits shall be transmitted to ensure that the next transmitted character is octet aligned.  H  Figure 3/V.42 bis provides an example of the data stream passed to the error control function during a transition from compressed to transparent mode. Two 11bit codewords A and B are transmitted in compressed form followed by a transition to transparent mode. In this example, the transition requires insertion of seven 0 bits in order that the first uncompressed character, C sent in transparent mode, is octet aligned. 7.6h  Dictionary updating  A new dictionary node shall be created from the match string and corresponding unmatched character returned by the string matching procedure, using the procedures defined in S6.4.  7.7pNode recovery  Hx  Following the creation of a new dictionary node, the node recovery procedure defined in S6.5 shall be applied. 7.8h  Data compressibility test  H  The data compression function shall periodically apply a test to determine the compressibility of the data. The nature of the test is not specified in this Recommendation; however it would consist of a comparison of the number of bits required to represent a segment of the data stream before and after compression.  H7.8.1 Transition to compressed mode  H  If the data compression function is in the transparent mode and determines that data compression would be effective, it shall:  H   a)pperform the dictionary update procedure using the current accumulated string and the next character to be processed by the string matching procedure (which will be the first character of the string represented by the first codeword transmitted in compressed mode);  H   b)pindicate to the peer data compression function that a transition to compressed mode is required, using the ECM transparent mode command sequence (see S9.1);   c)penter compressed mode.  HH  H7.8.2 Transition to transparent mode  H  If the data compression function is in the compressed mode and determines that the data stream is currently not compressible, it shall:  H   a)pensure that the codeword representing any partially encoded data has been transferred in accordance with the procedure given in SS7.4 and 7.5;  H   b)pperform the dictionary update procedure using the current accumulated string and the next character to be processed by the string matching procedure (which will be the first character transmitted in transparent mode);  H   c)pindicate to the peer data compression function by transferring the ETM control codeword (see S9) a transition to transparent mode;  H   d)ptransmit sufficient 0 bits to recover octet alignment (see S7.5);   e)pchange the state to transparent mode.  HH  H7.8.3 RESET function  H  In transparent mode the RESET command code may be used to indicate to the peer data compression function that the encoder dictionary is about to be re-initialized according to the procedures given in SS6.2 and 7.2. The RESET command code is sent using the escape character value before reinitialization takes place.  H  The circumstances under which the encoder requests a dictionary reset are not defined in this Recommendation, but would generally result from the encoder determining that some improvement in performance would result from resetting the dictionary. The procedures for requesting reinitialization of the dictionary on link establishment, or on detection by the control function of an error condition, are defined in SS5.2 and 5.6.  The RESET command code is not sent when a CINIT request primitive is received from the control function. 7.9h  Action on receipt of CFLUSH request  Upon receipt of a CFLUSH request from the control function, if the encoder is in compressed mode and there is a partiallymatched string being processed, the data compression function shall:  H  a) ensure that the codeword representing any partiallymatched string is transferred in accordance with the procedures defined in SS7.4 and 7.5;  H   b)pperform the dictionary update procedure using the current accumulated string and, when available, the next character to be processed by the string matching procedure;  H   c)pif step a) leaves extra bits pending for transmission (octet alignment not yet achieved), then:  hpi) transfer the FLUSH codeword (see S9);  H  hpii) if necessary, transfer sufficient 0 bits to recover octet alignment (see S7.5).  H  If the encoder is in transparent mode, on receipt of a CFLUSH request from the control function, the data compression function shall transfer all outstanding data; the string matching procedure is not terminated, and the dictionary update procedure is not performed. 8X Operation of the decoding function  H Ё The decoding function shall be capable of operation in both compressed and transparent modes, and shall operate in a manner consistent with that defined in SS6, 7 and 9.  On receipt of a CINIT request from the control function or a RESET command code from the peer data compression function, the data compression function shall initialize the decoding function in accordance with the procedures defined in SS6.2 and 7.2.  H  In transparent mode, the decoding function shall apply the string matching procedure given in S6.3, in order that the decoder dictionary may be maintained in a compatible state to the peer (remote) encoder dictionary. On receipt of the ECM or EID command code, the decoding function shall operate in a manner consistent with the encoder operations defined in SS7.8.1 and 9.2. New dictionary entries shall be created in a manner consistent with the procedures defined in SS6.4 and 7.3.  In compressed mode the decoding function shall recover the encoded strings. On receipt of the ETM or FLUSH codewords the decoder shall operate in  H a manner consistent with the encoder operations defined in SS7.8.2 and 7.9. New dictionary entries shall be created using the procedure defined in S6.4, with the first (prefix) character of the most recently decoded string being appended to the previous decoded string.  H  The decoder shall regard the STEPUP control codeword as an indication that the encoder has increased the codeword size in accordance with the procedures defined in S7.4. 9X Communications between peer data compression functions 9.1h  Control codewords and command codes  The control codewords and command codes allocated for communication between peer data compression functions are given in Table 2/V.42 bis. 9.2h  Procedures for use of the escape sequence  H  A transparent mode command sequence shall consist of the escape character followed by one of the command codes listed in S9.1 above.  To reduce data expansion resulting from the escape mechanism defined below, if the current escape character is detected within the data stream from the DTE, the data compression function shall:  H   a)pif in transparent mode, transfer the detected escape character, and transmit the EID code, and then  H   b)pin both transparent and compressed modes, modify the value of the escape character by adding to it the decimal value 51, the addition to be performed modulo 256. HH Ђ c4 P  8JTABLE 2/V.42 bis   c4 P Hp P X`h8< c4 P Control code words (used in compressed mode)  H  c4 P  H  c4 P HH҇Hp XG c4 P Code word XIName XFDescription  H p H c4 P ш H  c4 P HH҇'k c4 P 0 'k1 'k2 P XHETM FLUSH STEPUP Enter transparent mode Flush data Step up codeword size  H  c4 P ш H  c4 P  H p P XH`h'c c4 P Command codes (used in transparent mode)  H Hp P X`h c4 P  H  c4 P HH҇Hp XI c4 P Value XIName XFDescription  H p H c4 P ш H  c4 P HH҇'k c4 P 0 'k1 'k2 'g3 to 255 P XHECM EID RESET Reserved Enter compression mode Escape character in data Force reinitialization  H  c4 P ш HH Hp P X`h!(# c4 P   c4 P  10  Parameters  H Ё The following parameters are required by the data compression function. N c4 P 1 c4 P  to N c4 P 7 c4 P  and P c4 P 0 c4 P  to P c4 P 2 c4 P  apply to both directions of transmission, whilst a separate set of C c4 P 1 c4 P , C c4 P 2 c4 P , C c4 P 3 c4 P  variables must be provided in the encoder and decoder.   N c4 P 1 c4 P pMaximum codeword size (bits);   N c4 P 2 c4 P pTotal number of codewords;   N c4 P 3 c4 P pCharacter size (bits):  pN c4 P 3 c4 P  = 8;   N c4 P 4 c4 P pNumber of characters in the alphabet:  peq N\s\do5( c4 P 4 c4 P ) = 2\s\up5( c4 P N3 c4 P );  Hx   N c4 P 5 c4 P pindex number of first dictionary entry used to store a string:  pN c4 P 5 c4 P  = N c4 P 4 c4 P  + N c4 P 6 c4 P ;   N c4 P 6 c4 P pNumber of control codewords:  pN c4 P 6 c4 P  = 3;   N c4 P 7 c4 P pMaximum string length;   C c4 P 1 c4 P pNext empty dictionary entry;   C c4 P 2 c4 P pCurrent codeword size;   C c4 P 3 c4 P pThreshold for codeword size change;   P c4 P 0 c4 P pV.42 bis data compression request; Hp 0 X`h!(#  P c4 P 1 c4 P pNumber of codewords (negotiation parameter); Hp P X`h!(#  P c4 P 2 c4 P pMaximum string size (negotiation parameter). HH Ђ c4 P  8OANNEX A 8D c4 P (to Recommendation V.42 bis) 87 Procedures for negotiating  c4 P V.42  c4 P bis when used with  c4 P V.42  H Ё c4 P  When using this data compression Recommendation with V.42 error control, the XID negotiation procedure shall be used (see SS7.6, 8.10, 10 of Rec. V.42 and ISO 8885 1987 [6, 7].) A data link layer subfield in addition to those defined in Recommendation V.42 shall be used for this purpose. It shall appear in the XID frame immediately before the user data subfield and shall be encoded as in TableA1/V.42 bis.  H  During the protocol establishment phase, the presence of parameter P c4 P 0 c4 P  in the Private Parameter Set Data Link Layer Subfield of the XID frame shall indicate a request for data compression.  Note - The incorporation of the contents of this Annex into RecommendationàV.42 is under consideration by Study GroupàXVII. Q c4 P TABLE 1/V.42 bis  c4 P H XHh҇Hp P  c4 P  XBit U8 . . . 1  H p P H c4 P ш H  c4 P H XHh҇ c4 P Group ID Group Length Parameter ID Parameter length Parameter value Parameter ID Parameter length Parameter value Parameter ID Parameter length Parameter value Parameter ID Parameter length Parameter value 11110000 nnnnnnnn nnnnnnnn 00000000 00000011 01010110 00110100 00110010 00000001 00000001 000000nn 00000010 00000010 nnnnnnnn nnnnnnnn 00000011 00000001 nnnnnnnn Private parameter ser '((ISO 8885, Addendum 3)  H( (MSB) Length of parameter field (excludes group ID and length) (LSB) Parameter set identifier Length of string V 4 2 Rec. V.42 bis Data Compression request (P c4 P 0 c4 P ) Length of field Request for compression in: 00 neither direction  HH 01 negotiation initiatorresponder direction only 10 negotiation responderinitiator direction only 11 both directions Hp`PhRec.V.42 bis Number of codewords (P c4 P 1 c4 P ) 16bit integer (MSB) Value of parameter P c4 P 1 c4 P  (LSB)  H Hp`PhRec. V.42 bis Maximum string length (P c4 P 2 c4 P ) Hp`Ph8bit integer Value of parameter P c4 P 2 c4 P   H  c4 P ш H  c4 P MSB:+/Most significant bit  H p P X`h!(#LSB:pLeast significant bit HH Hp P X`h!(# 8MAPPENDIX I 8D c4 P (to Recommendation V.42 bis) 8; SDL description of encoder c4 P  (Z.100  c4 P to c4 P  Z.104) [8]  H Ё c4 P  Figure I1/V.42 bis shows the set of SDL symbols used in the diagrams of this Appendix.  H  The following diagrams provide an illustration of the operation of the encoder:  H   a)pFigure I2/V.42 bis: Encoder (see SS7.2, 7.3, 7.8, 7.9). This diagram illustrates the operation of the main elements of the encoder.  H   b)pFigure I3/V.42 bis: Process of character (see SS6.3, 6.4, 6.5). This diagram illustrates the operation of the string matching procedure, the conditions under which it is terminated and the action taken.  H   c)pFigure I4/V.42 bis: Check codeword size (see S7.4). This diagram illustrates the codeword size step up mechanism.  H   d)pFigure I5/V.42 bis: Test compression (see S7.8). This diagram illustrates the procedures for changing between transparent and compressed modes of operation and for use of RESET.  H   e)pFigure I6/V.42 bis: Flush (see S7.9). This diagram illustrates the action taken on receipt of a CFLUSH request.  H   f)pFigure I7/V.42 bis: Exception process next character (see SS7.8.1 a, 7.8.2 b, 7.9 b). This diagram illustrates the means by which the compressed mode character processing is performed following a transition to compressed mode or a flush operation.  Hh   g)pFigure I8/V.42 bis: Escape character procedure (see S9.2).   h)pFigure I9/V.42 bis: Signal reset procedure (S7.8.3).  H   i)pFigure I10/V.42 bis: Add string + character to dictionary procedure (SS6.4 and 6.5).  HH Ђ 8I c4 P FIGURE I1/V.42 bis 8J SDL Symbols used  c4 P  8I c4 P FIGURE I2/V.42 bis 8O Encoder  c4 P  8I c4 P FIGURE I3/V.42 bis 8E Process character procedure  c4 P  8I c4 P FIGURE I4/V.42 bis 8D Check codeword size procedure  c4 P  8I c4 P FIGURE I5/V.45 bis 8E Test compression procedure  c4 P  8I c4 P FIGURE I6/V.42 bis 8K Flush procedure  c4 P  8I c4 P FIGURE I7/V.42 bis 8= Exception process next character procedure  c4 P  8I c4 P FIGURE I8/V.42 bis 8E Escape character procedure  c4 P  8I c4 P FIGURE I9/V.42 bis 8F Signal "Reset" procedure  c4 P  8H c4 P FIGURE I10/V.42 bis 8: Add "string + character" to dictionary procedure 8MAPPENDIX II 8D c4 P (to Recommendation V.42 bis) 8F Guidance for implementors c4 P   H Ё c4 P  The following notes provide information on the implementation of the data compression scheme and on the selection of parameters. II.1  Selection of N c4 P 2 c4 P , the total number of codewords  H  The dictionary size is equal to N c4 P 2 c4 P  N c4 P 6 c4 P  (assuming that entries are not provided for the reserved codewords). The selection of a large value for N c4 P 2 c4 P  means that the number of strings available is large, but also that the value of N c4 P 1 c4 P  is larger. The gain in performance obtained from the selection of a larger dictionary may be offset by the larger codeword size needed, and for certain types of data, better performance may be obtained by using a smaller dictionary. If values of N c4 P 2 c4 P  in the range 2 c4 P n c4 P  + 1 (for integer n) to approximately 1.3 X 2 c4 P n c4 P  are selected, no performance improvement will be gained over the selection of the value 2 c4 P n c4 P . A value for N c4 P 2 c4 P  of 2048 provides good compression performance across a wide range of data types. II.2  Data structures  The data compression scheme described in this Recommendation is well suited to implementation using a tree based data structure. This type of  H data structure will provide good utilization of memory space and fast searching. II.3  Calculation of compression performance  H  The calculation of compression performance may be expressed as the number of characters received by an encoder divided by the number of octets transferred from the encoder (to the error control function). The count of characters and octets should be set to zero on receipt of a CINIT request. II.4  Examples of the operation of the encoder  H  The following three examples illustrate the operation of the encoder. It is assumed that the dictionary is in the state shown in Figure 2.V.42 bis.  HII.4.1 Simple case: "BAY", compressed mode  The first character "B" is read, and the dictionary searched for the string "B". As this string is present, the next character "A" is read and appended, forming the new string "BA". The dictionary is searched for the new string and when it is found, the next character "Y" is read and appended, forming the new string "BAY". The dictionary is searched for "BAY", which is not present. "Y" is removed, and the string matching procedure exits with "BA" as the matched string and "Y" as the unmatched character.  The codeword for "BA" is encoded in C c4 P 2 c4 P  bits, packed into octets, and passed to the control function for transmission. The new string "BAY" is created by appending "Y" to "BA", assigning the codeword with value C c4 P 1 c4 P  to this new string. C c4 P 1 c4 P  is incremented, and the node (string) currently assigned this value is tested to see if it is empty or is a leaf node. If the node is empty, it will be used in the next dictionary update. If the node is used and is not a leaf node, i.e. is part of a longer string, then C c4 P 1 c4 P  is incremented again and the test repeated. If the node is a leaf node, then it is detached from its parent and will be reused in the next dictionary update.  The character "Y" will be used to restart the string match.  HII.4.2 Simple case: "BAY", transparent mode  H  In transparent mode, the same sequence of operation described in SII.4.1 will occur, the only difference being that the characters "A", "Y" will be transmitted in place of the codeword for "BA".  H  II.4.3 Repeated characters or sequences: "CCCCC", compressed mode  H  The aim of this example is to illustrate a particular aspect of the algorithm. As the encoder is able to update its dictionary on the basis of lookahead, whilst the decoder is only able to update its dictionary on the basis of previously decoded data, it is necessary to ensure that the encoder does not use new dictionary entries before they are transmitted to the decoder.  H  The first "C" is read and will be matched with the dictionary entry for "C". The second "C" is read, appended to the first, and the dictionary searched for "CC". As "CC" is not in the dictionary, the string matching procedure exits with the matched string as "C" and the unmatched character as "C". "CC" is added to the dictionary, the codeword for "C" sent, and string matching restarts with the second "C".  H  The third "C" is read, appended to the second "C", forming "CC", and the dictionary searched for "CC". As this is in the dictionary but is, however, the entry created since the last string match, [see S6.3 b)], the string matching procedure exits with the matched string as "C" and the unmatched character as "C". "CC" is not added to the dictionary as it is already present, the codeword for "C" sent, and string matching starts with the third "C".  H  The fourth "C" is read, appended to the third "C", forming "CC", and the dictionary searched for "CC" As "CC" is found in the dictionary, and it does not match the entry created since the last string match (the update operation was inhibited), the fifth "C" is read and appended to the string. References [1]h  CCITT Recommendation Error Correcting Procedures for DCEs using AsynchronoustoSynchronous Conversion, Vol. VIII, Rec. V.42.  H [2]h  CCITT Recommendation Support by a ISDN of Data Terminal Equipment with V Series Type Interfaces with Provision for Statistical Multiplexing, Vol. VIII, Rec. V.120.  H [3]h  ISO 3309 Data Communication High Level Data Link Control Procedures Frame Structure.  H [4]h  CCITT Recommendation Definitions of terms concerning data communication over the telephone network, Vol. VIII, Rec. V.7. [5]h  CCITT Recommendation Transmission of Start Stop Characters over Synchronous Bearer Channels, Vol. VIII, Rec. V.14.  H [6]h  ISO 8885 1987 Information Processing Systems Data Communications High Level Data Link Control Procedures General Purpose XID Frame Information Field Content and Format.  H [7]h  ISO 8885 1987/ADD3 Information Processing Systems Data Communications High Level Data Link Control Procedures General Purpose XID Frame Information Field Content and Format Addendum 3: Definition of a private parameter data link layer subfield.  H [8]h  Serie Z.100 CCITT Recommendations Functional Specification and Description Language (SDL), Vol. X.