Method for selecting frame encoding parameters to improve transmission performance in a frame-based communications network

[0001] This patent application claims the benefit of the filing date of U.S. Provisional Patent Application No. 60/197,224 filed Apr. 14, 2000; and U.S. Provisional Patent Application No. 60/196,002 filed Apr. 7, 2000; the entire contents of both of which are hereby expressly incorporated by reference.

[0002] This patent application is further related to the following U.S. Patent Applications filed concurrently herewith and commonly assigned, entitled “A Method of Sharing Information among a Plurality of Stations in a Frame-based Communications Network”, “A Method of Enhancing Network Transmission on a Priority-enabled Frame-based Communications Network”, “A Method of Determining a Start of a Transmitted Frame in a Frame-based Communications Network”, “A Method of Determining an End of a Transmitted Frame in a Frame-based Communications Network”, “A Method for Providing Dynamic Adjustment of Frame Encoding Parameters in a Frame-based Communications Network”, “A Method for Selecting Frame Encoding Parameters in a Frame-based Communications Network”, “A Method of Determining a Collision Between a Plurality of Transmitting Stations in a Frame-based Communications Network”, “A Method of Providing Synchronous Transport of Packets Asynchronous Network Nodes in a Frame-based Communications Network”, “A Method of Controlling Data Sampling Clocking of Asynchronous Network Nodes in a Frame-based Communications Network”, “A Method for Distributing Sets of Collision Resolution Parameters in a Frame-based Communications Network”, “A Method and Apparatus for Optimizing Signal Transformation in a Frame-based Communications Network”, “A Method and Apparatus for Transceiver Noise Reduction in a Frame-based Communications Network”, “A Method for Selecting an Operating Mode for a Frame-based Communications Network”, and “A Transceiver Method and Signal Therefor Embodied in a Carrier Wave for a Frame-based Communications Network”.

[0003] The present invention relates to the field of communications, and, in particular, to a frame-based communications network.

[0004] As computers become more and more cost effective for the everyday consumer and for small businesses, such computers become more plentiful for use within local area environments such as homes, office buildings and the like. For example, within a home a person with a computer in the bedroom, and another in the living room, may want to share common files, utilize a common digital subscriber line (DSL), or otherwise transfer information between the computers. Accordingly, various technologies are being developed for computer interconnection of multiple computers located within such environments. One example of such technologies are the Home Phoneline Network Alliance (HPNA) specifications for local area network (LAN) computer interconnection which utilize existing telephone lines within the local environment for the transmission of data packets between the computers.

[0005] FIG. 1a shows in block diagram form a general home networking environment within which the present invention can be implemented. Home network 10 includes existing (installed) plain old telephone service (POTS) wiring 12, network clients 14, the computer port side of modem 16 and fax 18. POTS wiring 12 provides wiring infrastructure used to network multiple clients at a customer premises (e.g., home) 20. POTS wiring 12 can be conventional unshielded twisted pair (UTP) wiring that is generally routed internally in the walls of the customer premises 20 to various locations (e.g., rooms) within the customer premises. Subscriber loop 22 (also called a “local loop”) is a physical wiring link that directly connects an individual customer premises 20 to the Central Office through telephone network interface 24, a demarcation point between the inside and outside of customer premises 20. Of particular importance for residential networks are systems that provide communication between computers as reliably and with as high a data rate as possible. Communication over residential telephone wiring is provided through inventive frame-oriented link, media access and physical layer protocols and implementation techniques associated therewith described herein.

[0006] Referring now to FIG. 1b, those skilled in the art can appreciate that home phone-line network configuration 10 can also utilize interface 6010 to provide signals outside customer premises 20. For example, interface 6010 can include a V.90 modem as described above, connected through the central office to an internet service provider. Interface 6010 can include an ADSL modem, a VDSL modem or the like transport interface.

[0007] Another desired solution for high speed data communications appears to be cable modem systems. Cable modems are capable of providing data rates as high as 56 Mbps, and is thus suitable for high speed file transfer. In a cable modem system, a headend or cable modem termination system (CMTS) is typically located at a cable company facility and functions as a modem which services a large number subscribers. Each subscriber has a cable modem (CM). Thus, the CMTS facilitates bidirectional communication with any desired one of the plurality of CMs. Referring to FIG. 1c, a hybrid fiber coaxial (HFC) network 1010 facilitates the transmission of data between a headend 1012, which includes at least one CMTS, and a plurality of homes 1014, each of which contains a CM. Such HFC networks are commonly utilized by cable providers to provide Internet access, cable television, pay-per-view and the like to subscribers. Approximately 500 homes 1014 are in electrical communication with each node 1016, 1034 of the HFC network 1010, typically via coaxial cable 1029, 1030, 1031. Amplifiers 1015 facilitate the electrical connection of the more distant homes 1014 to the nodes 1016, 1034 by boosting the electrical signals so as to desirably enhance the signal-to-noise ratio of such communications and by then transmitting the electrical signals over coaxial conductors 1030, 1031. Coaxial conductors 1029 electrically interconnect the homes 1014 with the coaxial conductors 1030, 1031, which extend between amplifiers 1015 and nodes 1016, 1034. Each node 1016, 1034 is electrically connected to a hub 1022, 1024, typically via an optical fiber 1028, 1032. The hubs 1022, 1024 are in communication with the headend 1012, via optical fiber 1020, 1026. Each hub is typically capable of facilitating communication with approximately 20,000 homes 1014. The optical fiber 1020, 1026 extending intermediate the headend 1012 and each hub 1022, 1024 defines a fiber ring which is typically capable of facilitating communication between approximately 100,000 homes 1014 and the headend 1012. The headend 1012 may include video servers, =satellite receivers, video modulators, telephone switches and/or Internet routers 1018, as well as the CMTS. The headend 1012 communicates via transmission line 1013, which may be a T1 or T2 line, with the Internet, other headends and/or any other desired device(s) or network.

[0008] Given the HPNA environment and the Cable Modem System environment, an opportunity exists for a system provider to integrate each respective environment with voice services. FIG. 1d depicts such an integrated environment. As can be seen in FIG. 1d, a connection point in the home to the telephony world (e.g., the world of video, voice, high speed data network traffic), could be provided to a home user through cable modem 1046 which would include an HPNA transceiver. The cable modem system provider may also wish to accomodate providing telephone service along with high speed data service. A home computer user, rather than using a traditional modem to connect to an internet service provider, would find it convenient to utilize cable modem 1046, taking advantage of the very high speed data service provided by the cable modem. Having a cable modem customer, the cable modem provider may also find it commercially beneficial to offer video feeds, and telephone service over the same cable modem network.

[0009] A cable modem having an HPNA V2 transceiver included therein, can readily interface into the home phone line network through the telephone jack within the home. Computers coupled to the home network then communicate through the cable modem to the outside telephony world as described above. Telephone service coming from outside the customer premises over the cable modem system would be in a digitized packetized format. It would then proceed over the HPNA network in the same digitized packeting format. If the user, in addition to having computers and the like attached to the HPNA network, wished to have an analog telephone(s) connected to the HPNA, the telephone'(s) analog signal would go through a digital conversion and put the digital information into packets for passing the packets back and forth over the network. The analog telephone signal is sampled and packetized at the appropriate clock rate creating the packet after a certain number of samples.

[0010] Therefore, to effectively operate in such communications network environments a need exists for a method for selecting frame encoding parameters to improve transmission performance in a frame-based communications network. The present invention as described and claimed in this application provides a solution to meet such need.

[0011] In accordance with the present invention a method is provided for selecting frame encoding parameters to improve transmission performance for a transmitting frame being transmitted from a transmitting station to a receiving station over a transmission medium of a frame-based communications network, the transmitting frame having a header segment and a payload segment, the header segment being transmitted using a fixed set of encoding parameters such that the header segment can be received and decoded by all stations on the network, the payload segment being transmitted using a variable set of payload encoding parameters, the transmitting station sending the transmitting frame using one set of the variable set of payload encoding parameters at a time. The receiving station receives and decodes the header and payload segments of each transmitting frame. The decoding includes computing frame statistics. A plurality of sets are selected from the variable set of payload encoding parameters to form a possible set of payload encoding parameters. For each set of payload encoding parameters in the possible set of payload encoding parameters, an estimate of network performance characteristics expected if the transmitting station were to transmit the transmitting frame using that set of payload encoding parameters is generated based upon the frame statistics. A set of payload encoding parameters having optimized network performance characteristics is selected based upon estimates of expected network performance for each set of payload encoding parameters in the possible set of payload encoding parameters. The frame statistics include a slicer maximum squared error for the header segment and a slicer maximum squared error for the payload segment.

[0012] Also in accordance with the present invention the expected network performance characteristic estimates can include expected time of the transmitting frame on the transmission medium. The optimized network performance characteristics can include minimum time of the transmitting frame on the transmission medium. The expected time of the transmitting frame on the transmission medium is calculated as a function of an average number of payload bytes, a payload symbol rate, a payload bits per symbol, a header segment time on the transmission medium, a collision resolution overhead time, and an expected number of retransmissions. The expected number of retransmissions is calculated as a function of an estimated packet error rate.

[0103] Before addressing the Voice aspects of the present invention, the Homenetworking implementation aspects will be first addressed.

Homenetworking Implementation Aspects

[0104] A communications network typically includes a group of nodes interconnected by a transmission medium. The term “node” relates to any device that shares frames of data with other nodes in the network. Devices that may make up a node are computers, printers, scanners, etc. A node may also be a telephone, a television, a set-top box for televisions, a camera or other electronic sensing or communication device. Any device that can send and/or receive frames of data with other devices via a communication medium may be a node for purposes of the present invention.

[0105] The transmission medium that links each node in a network is equally one of a diverse family of media. Common media used include unshielded twisted pair (e.g. phone wire, CAT-5 cabling), power lines, optical fiber, coaxial cable and wireless transmission media. The operations that each individual node performs in order to access data from, and transmit data to, the rest of the network may be logically broken down into seven layers according to the ISO Open Systems Interconnection (OSI) seven-layer network model, which is also referred to as the “network stack”. The seven layers, from the bottom to the top are: 1) the PHYSICAL layer, 2) the DATA LINK layer, 3) the NETWORK layer, 4) the TRANSPORT layer, 5) the SESSION layer, 6) the PRESENTATION layer, and 7) the APPLICATION layer. FIG. 2 illustrates the ISO seven-layer reference model.

[0106] The PHYSICAL layer, or physical link layer, or PHY, is concerned with transmission of unstructured bit stream traffic over physical media, and relates to the mechanical, electrical, functional, and procedural characteristics to access and receive data from the physical medium. The DATA layer, sometimes referred to as the data link layer, provides for the reliable transfer of information across the physical link. It is concerned with sending frames, or blocks of data, with the necessary synchronization, error control, and flow control. The NETWORK layer separates the uppermost layers from the transmission and switching technologies used to connect nodes. It relates to establishing, maintaining, or terminating connection between nodes.

[0107] The TRANSPORT layer relates to reliability and transparency in data transfers between nodes, and provides end-to-end error recovery and flow control. The SESSION layer provides control to communications between applications, and establishes, manages, and terminates connections between cooperating applications. The PRESENTATION layer provides independence to the application processes from differences in data syntax or protocols. Finally, the highest layer, the APPLICATION layer, provides access to the OSI environment for users. Much more has been written about the benefits and distributed functionality of such an arrangement of layers and need not be recounted here.

[0108] In frame-based networks, there are two fundamental models or topologies: 1) broadcast/multipoint networks, where all nodes are physically attached to the same network medium, and use a single, shared channel and frames transmitted on the network are visible to all nodes; and 2) point-to-point networks, where pairs of nodes are connected to each other with communication channels which are not connected to any other nodes on the network. Frames transmitted on one channel are not visible to nodes on other channels unless the frames are retransmitted onto the other channels by a node that is connected to multiple channels. Each channel may use a separate segment of the network medium, or multiple channels may share a single segment using e.g., Frequency Division Multiplexing or Time Division Multiplexing techniques. One common example of such a point-to-point network topology is that used for IEEE 10BaseT 802.3 networks, with network nodes connected via point-to-point Category 5 unshielded twisted pair cable, using multi-port devices called hubs to retransmit frames received from one network segment to all other segments.

[0109] FIGS. 3a and 3b show a broadcast/multipoint network and a point-to-point network, respectively, for use with the present invention. In FIG. 3a, representative nodes 140a, 140b, 140c are communicatively coupled with a common transmission medium 250 through individual segments 240a, 240b, 240c respectively. Thus, a message containing a broadcast destination address sent from one node is sent to all other nodes coupled with transmission medium 250. In FIG. 3b, nodes 140d, 140e, 140f are communicatively coupled to each other by individual segments 260d, 260e, 260f respectively of transmission media and hub 255. Messages sent from one node to another node on one segment are not visible to nodes on other segments unless they are retransmitted by a node that is connected to multiple segments, such as hub 255 in a network. Segments 240a, 240b, 240c and common transmission medium 250 may be (but are not restricted to) a phone line, a power line, a wireless medium, coaxial cable, or a fiber optic medium. Reference to FIGS. 3a and 3b should be made with respect to the description of the embodiments of the invention as set forth below.

[0110] Each node in either type of network has within it a device that permits the node to send and receive data frames in the form of electrical, electromagnetic, or optical signals. The device is conventionally a semiconductor device implementing the PHYSICAL layer of the network connectivity, and the medium access control (MAC) portion of the DATA layer of network connectivity.

[0111] Returning to FIG. 2, there is shown a basic network illustrating a network communication protocol between first node 102 that runs an application (“APP X”) and another node 104 that runs the same or different application (“APP Y”). Nodes 102 and 104 communicate message 108 via transmission medium 106. In the example shown in FIG. 2, when node 102 has message 108 to send to node 104, it transfers the message down through its network stack on the left, from layer to layer. Application header (AH) 103 is appended to message 108 in the APPLICATION layer, to identify the application being executed by node 102. Original message 108, plus the application header AH, is passed to the PRESENTATION layer, where it is again appended with a presentation layer header (PH) 105. Such process continues, accordingly adding session header (SH) 107, transport header (TH) 109 and network header (NH) 111 down to the DATA layer, where the message and appended headers is encapsulated with data layer header (DH) 112 and start of frame (SOF) indicator 113. The DATA layer also may add data trailer (DT)114 and end of frame (EOF) indicator 115. Data layer header 112 may include a source address (SA) to identify node 102 sending the message, and may also include a destination address (DA) to identify the intended recipient or group of recipients.

[0112] The message with appended headers, trailers and indicators is then passed to the PHYSICAL layer where it is passed on to network transmission medium 106. When received by node 104, the reverse process occurs in the network stack of node 104. At each layer, the header and/or trailer information is stripped off as message 108 ascends the network stack.

[0113] The details of the network stack in FIG. 2 are provided for reference only, and the present invention is not limited to functioning with network stack implementations that exactly match FIG. 2.

[0114] Referring still to FIG. 2, the lower two layers are described in further detail. It should be understood that these layers are typically implemented as a combination of logic and memory storage that is configured to carry out the task of the layer. The logic can be in the form of hardware, software, firmware, or a combination of those. Each layer may also be implemented using programmable gate array (PGA) technology, such as system programmable gate arrays (SPGA) and field programmable gate arrays (FPGA). Also, each layer, or a combination of the layers, may be implemented as an integrated circuit or software program. Therefore, it should be apparent to those skilled in the art, that there are many ways in which to implement the inventions described herein.

[0115] FIG. 2 shows DATA layers 120a, 120b and PHYSICAL layers 220a, 220b for a representative pair of nodes 140a, 140b according to the invention. Each node has within it semiconductor device(s) that implement the PHYSICAL layer as well as the medium access control (MAC) and Link Layer portions of the DATA layer, such as that implemented by the Broadcom Corporation Model BCM 4210 Controller. As discussed above, the PHYSICAL layer is concerned with transmission and reception of bit stream traffic to and from the transmission medium. Transmitters and receivers, described in more detail below, form a transmission medium interface, and may be implemented as a single device or separate devices.

[0116] Referring now to FIGS. 4a and 4b, an embodiment implementing the inventive concepts is depicted wherein, for example, a device such as computer 14 can be interconnected therethough to premises UTP wiring as set forth in FIG. 1a, and through which the protocol set forth in FIG. 2 is processed. FIG. 4a shows in block diagram form the controller aspects of the embodiment, while FIG. 4b show typical network interface device (NID) analog front end aspects of the embodiment.

[0117] Referring to FIG. 4a, controller 300 is a fully integrated MAC/PHY device that transmits and receives data (e.g., 10 Mbps and above as implemented by the aforementioned Broadcom Corporation Model BCM 4210, 4211, 4413 controllers). Controller 300 includes bus interface 310, such as a PCI or MSI bus interface for communication in accordance with well-known PC-based and/or peripheral/internet appliance architectures. Controller 300 also includes digital PHY 320 having a FDQAM/QAM transmitter and receiver interfacing with the analog front end and MAC 330, coupling to bus interface 310 through transmit (TX) FIFO 340 and receive (RX) FIFO 350. Bus interface 310 also has the capability of similarly communicating with other devices 360, such as a v.90 modem through v.90 modem interface or a 10/100 Fast Ethernet bus through a 10/100 Fast Ethernet interface, and their respective transmit (TX) FIFO 370 and receive (RX) FIFO 380. The operations of such bus interfaces and TX/RX FIFOs are well known in the art and are not described in more detail. The operation of the MAC/PHY aspects of the embodiment are described in more detail herein below.

[0118] Referring to FIG. 4b, NID analog front end 400 connects controller 300 depicted in FIG. 4a to a transmission medium 106 such as a premises UTP wiring as depicted in FIGS. 1a, 1b and 1c. Analog front end 400 includes digital input/output (I/O) circuit 410 for transferring samples and is coupled to a transmit path and a receive path. Digital I/O 410 includes clock 412 for driving controller 300 with a 64 MHz+/−100 ppm clock generated by 64 Mhz crystal 414. The transmit path includes digital-to-analog converter 420 for converting 10 bit sample data to an analog signal, automatic gain controller 425 for setting gains based upon input received by digital I/O 410, filter 430, transmit-off switch 435, and is coupled to phoneline connector 450, such as a UTP wiring RJ11 connector, through electronic hybrid 440 for buffering signals and filter/transformer/electronic protection circuit 445. The receive path includes analog-to-digital converter 460 for sending valid sample data, variable gain amplifier (VGA) 470, filter 480 for low-pass anti-aliasing, VGA 490, and is similarly coupled to phoneline connector 450 through electronic hybrid 440 and filter/transformer/electronic protection circuit 445. Electronic hybrid 440 and filter/transformer/electronic protection circuit 445 are connected therebetween by a plurality of transmit and receive lines (e.g., TX, RX1, RX2) 495. The operations of the analog front end are well known in the art.

Homenetworking PHY Layer Overview

[0119] In accordance with a preferred embodiment of the present invention PHY 320 uses 4 MBaud QAM modulation and 2 MBaud Frequency Diverse QAM (FDQAM), with 2 to 8 bits-per-Baud constellation encoding, resulting in a PHY-layer payload modulation rate that ranges from 4 Mb/s to 32 Mb/s. The modulation techniques are set forth in U.S. patent application Ser. No. 09/169,552 entitled “Frequency Diverse Single Carrier Modulation For Robust Communication Over In-Premises Wiring”, which is incorporated herein by reference. Information is transmitted on the transmission medium/channel in bursts. Each burst or physical layer frame consists of PHY-layer payload information encapsulated with a PHY preamble, header and postamble. The PHY-layer payload in each physical frame is that part of the Ethernet Link Level frame that follows the Ethertype field through the Frame Check Sequence (FCS), plus a CRC-16 and a pad field for the 4 Mbaud rate. Hereafter, “payload” refers to the PHY-layer payload unless otherwise specified.

[0120] Referring to FIG. 5, a transmitter aspect of PHY 320 is shown in functional block diagram form. Transmitter 500 includes frame processor 510, data scrambler 520, bit-to-symbol mapper (constellation encoder) 530, and QAM/FDQAM modulator 540. The frame format transmitted by transmitter 500 is shown in FIG. 6. Frame format 600 consists of low-rate header section 610, a variable-rate payload section 620, and a low-rate trailer 630. Some parts of the frame are not scrambled, as described below. Except where otherwise stated, all fields are encoded most significant octet first, least significant bit first within each octet. Bit number 0 is the lsb within a field. Diagrams in the figures herewith show MSB bits or octets to the left. Header 610 includes a preamble (PREAMBLE64) 612 and is defined as a repetition of four 16 symbol sequences (TRN16) that result from encoding 0xfc483084 in the order described above at 2 MBaud, 2 bits-per-Baud, with the scrambler disabled. The TRN16 is a white, constant amplitude QPSK sequence. The preamble facilitates power estimation and gain control, Baud Frequency Offset Estimation, Equalizer Training, Carrier Sense, and Collision Detection as is described in more detail below. Header 610 also includes frame control field 614. Frame control field 614 is a 32-bit field defined in the table set forth in FIG. 7, and with the bit-ordering defined above, the frame control fields are transmitted in the order shown in FIG. 8. Frame Type (FT) 616 is an eight bit field that is intended to provide flexibility for defining other frame formats in future versions of the embodiment. Present devices transmit 0 in this field, and discard any frames with FT other than zero. All other values are reserved. The field definitions in the present embodiment are for FT=0.

[0121] The FT field is intended to provide a mechanism for Forward Compatibility, allowing extensions to use frame formats differing from the present embodiment. A next field is scrambler initialization (SI) field 618. A 4-bit field is set to the value used to initialize scrambler 520, as described below. A next field is the priority (PRI) field 620 which refers to a media access priority mechanism as described below. The 3 bit PHY priority value (PRI) refers to the absolute priority that a given frame will be given when determining media access, and is the value used in the MAC embodiment described below. Priority 7 has preferential access over Priority 0. PRI field 620 is a field carried in the PHY-level frame transmission and is intended to indicate a 3-bit PHY-level priority or class-of-service indication to the receiver link level processor for managing priority and class of service of the received frame. The PRI value is not used by the receiver PHY processor. For stations that do not implement class-of-service the PRI field is ignored on receive, and is transmitted set to 1. The next field 622 is reserved (RSVD) for future use and is ignored by the receiver. Adjacent to field 622 is payload encoding (PE) field 624 which determines the constellation encoding of the payload bits. The PE values are defined as forth in FIG. 9. Certain PE values are reserved. Reserved PE values are intended to code for higher Baud rates and carrier frequencies that will be introduced in later versions of the embodiment. The next field is a header check sequence (HCS) 626. HCS 626 is an 8-bit cyclic redundancy check (CRC) computed as a function of the 128-bit sequence in transmission order starting with the FT bits and ending with the Ethernet source address (SA) bits, with zeros substituted for the as-of-yet uncomputed HCS field. The encoding is defined by the following generating polynomial.
G(x)=x⁸+x⁷+x⁶+x⁴+x²+1
Mathematically, the CRC value corresponding to a given frame is defined by the following procedure.

• • [0122] a) The first 8 bits of the input bit sequence in transmission order are complemented.
  • [0123] b) The 128 bits of the sequence in transmission order are then considered to be the coefficients of a polynomial M(x) of degree 127. (The first bit of the FT field corresponds to the x¹²⁷ term and the last bit of the SA field corresponds to the x⁰ term.)
  • [0124] c) M(x) is multiplied by x⁸ and divided by G(x), producing a remainder R(x) of degree<=7.
  • [0125] d) R(x) is multiplied by H(x) to produce N(x), where H(x) is defined as H(x)=x⁷+x⁶+x⁵+x⁴+x²+x+1
  • [0126] e) N(x) is divided by G(x), producing a remainder R′(x) of degree<=7.
  • [0127] f) The coefficients of R′(x) are considered to be an 8-bit sequence.
  • [0128] g) The bit sequence is complemented and the result is the CRC′.

[0129] The 8 bits of the CRC′ are placed in the HCS field so that x⁷ is the least-significant bit of the octet and x⁰ term is the most-significant bit of the octet. (The bits of the CRC′ are thus transmitted in the order x⁷, x⁶, . . . x¹, x⁰.) Although HCS 626 is embedded within the protected bit-stream, it is calculated in such a way that the resulting 128-bit stream provides error-detection capabilities identical to those of a 120-bit stream with an 8-bit CRC appended. The resulting 128-bit sequence, considered as the coefficients of a polynomial of degree 127, when divided by G(x), will always produce a remainder equal to x⁷+x⁶+x+1. The input bits are unscrambled. Because all fields covered by the HCS are transmitted at 2 MBaud and 2 bits per Baud, as described below, these fields should be received correctly in many cases where the payload is received in error. The HCS may be used in conjunction with soft-decision error statistics to determine with high probability whether the header was received correctly. This knowledge may be useful for optimizing the performance of ARQ and/or rate negotiation algorithms described below.

[0130] Returning to FIG. 6, it can be seen that the bit fields starting with the destination address (DA) field 628 and ending with the FCS field 630 are identical to the corresponding fields described in IEEE Std 802.3 as depicted in FIG. 10 and are referred to as Link-level Ethernet Frame (packet) 632. The bits of a PHY-level Ethernet frame have an Ethernet preamble 634 and start-frame-delimiter (SFD) 636 bits prepended to the Link-level frame, these bits are not present in the frames of the present embodiment. It is intended that IEEE assigned Ethernet MAC addresses are used for Destination Address (DA) 628 and Source Address (SA) 638. The Ethernet frame consists of an integer number of octets. Following Ether-type field 640 is Ethernet data field 642, FCS field 630 and cyclic redundancy check (CRC) field 644. CRC field 644 is a 16-bit cyclic redundancy check computed as a function of the contents of the (unscrambled) Ethernet frame in transmission order, starting with the first bit of the DA field and ending with the last bit of the FCS field. The encoding is defined by the following generating polynomial.
G(x)=x¹⁶+x¹²+x⁵+1
Mathematically, the CRC value corresponding to a given frame is defined by the following procedure:

• • [0131] h) The first 16 bits of the frame in transmission order are complemented.
  • [0132] i) The n bits of the frame in transmission order are then considered to be the coefficients of a polynomial M(x) of degree n−1. (The first bit of the Destination Address field corresponds to the x⁽ⁿ⁻¹⁾ term and the last bit of the FCS field corresponds to the x⁰ term.)
  • [0133] j) M(x) is multiplied by x¹⁶ and divided by G(x), producing a remainder R(x) of degree<=15.
  • [0134] k) The coefficients of R(x) are considered to be a 16-bit sequence.
  • [0135] l) The bit sequence is complemented and the result is the CRC.
    The 16 bits of the CRC are placed in the CRC-16 field so that x¹⁵ is the least significant bit of the first octet, and the x⁰ term is the most-significant bit of the last octet. (The bits of the CRC are thus transmitted in the order x¹⁵, x¹⁴, . . . x¹, x⁰.)
    The CRC-16, in conjunction with Ethernet's FCS, provides for more protection from undetected errors than the FCS alone. This is motivated by environmental factors that will often result in a frame error rate (FER) several orders of magnitude higher than that of Ethernet, making the FCS insufficient by itself. For 4 MBaud payloads, a variable-length PAD field 646 follows CRC field 644 and consists of an integer number of octets. The last octet of the pad field (PAD_LENGTH) specifies the number of zero octets (0x00) preceding PAD_LENGTH. The value of PAD_LENGTH must equal or exceed the number of zero octets required to ensure that the minimum length of the transmission, from the first symbol of the PREAMBLE64 through the last symbol of the end of frame delimiter, is 92.5 microseconds. For 2 MBaud payloads, there is no PAD field. The PAD field is not present in a Compatibility Mode Frame, as described below. An example of a compliant formula for generating PAD_LENGTH is max (102-N, 0), where N is the number of octets from DA to FCS, inclusive. This ensures that a collision fragment can be discriminated from a valid frame by the transmission length detected by the carrier sense function, as described below. The next field is End of Frame (EOF) Delimiter field 648. The End-of-Frame sequence consists of the first 4 symbols of the TRN sequence, or 0xfc encoded as 2 bits-per-Baud at 2 Mbaud. This field is provided to facilitate accurate end-of-carrier-sensing in low-SNR conditions. A station demodulating a frame can use this field to determine exactly where the last payload symbol occurred.

[0136] Turning now back to FIG. 5 and to FIG. 11, scrambler 520 is described in more detail. Two difficult problems in CSMA/CD networks that use uncontrolled wiring (e.g. phoneline or powerline networks) are addressed. The first problem is premature end-of-carrier detection and the second problem is radio-frequency egress. With regard to premature end-of-carrier detection, in powerline and phoneline CSMA/CD networks, there is a need to reliably detect the end of a frame in the presence of severe channel distortion. There also is a trade-off between the mean time required to detect the end of frame (from the actual end of frame) and the reliability of detection (probability of false alarm and probability of missed detection). Two effects make end-of-frame detection difficult, particularly when the frame boundary detector is decoupled from the demodulator: (1) the possibility of a long run of innermost constellation points, particularly for large constellations (e.g. high-order QAM or PAM); and (2) the possibility of a long run of constant or near-constant (nearest neighbors in a large constellation) symbols. A long run of innermost points can clearly be a problem if an energy or matched filter detector is used to detect frame boundaries, and constant/near-constant symbol sequences (which produce tonal transmitted sequences) are problematic because they may be highly attenuated by the channel over which they travel. Large constellations are used in the system to achieve high spectral efficiency, and, hence, high data rates. Scrambling generally is an effective tool in combating these problems. However, there is still a non-zero probability of either a sufficiently long run of innermost points or a sufficiently long run of constant/near-constant symbols to cause frame loss. Ordinarily, one would not be concerned about these low-probability events. However, frame loss due to end-of-frame detection failure is deterministic: provided that the channel does not change between transmissions and the SNR is high, every transmission will fall victim to the same premature end-of-carrier detection problem. With regard to radio frequency (RF) egress, in wired networks, there is always energy radiated from the wires that convey information. This egress can interfere with other services, some (e.g. amateur radio) which are specifically protected by government agencies. In the “high-frequency” range, interference into amateur radio receivers is a particular concern. These receivers typically have a channel bandwidth of less than 3 kHz. While scrambling is also an effective tool for spreading packet energy over a wide band, thereby reducing the probability of harmful interference, many network packets (e.g. TCP acknowledgments) contain identical or nearly-identical data. Also, collisions between different stations' transmissions on the wire may result in the transmission of exactly the same data many times within a short time window. Using the same scrambler seed (delay line initialization) for every transmitted frame may result in bursts of narrowband energy that are more likely to interfere with services such as amateur radio. Therefore, in accordance with the present invention a common solution to both problems is provided by two very simple circuits for mitigating this problem, one at the transmitter and another at the receiver. Either an N-bit counter is implemented at the transmitter for every active path (source+destination address combination) over which a frame may be sent on the network, or an N-bit pseudo-random number generator is implemented. A simple linear-feedback shift register may be used to generate the pseudo-random number, if that approach is chosen. On every transmitted frame, the scrambler initialization circuit either generates a pseudo-random N-bit number, or it increments the counter for the path over which the frame will travel, modulo-2^N. Either technique is sufficient. The scrambler initialization circuit inserts the N bits into any of the M (>=N) bits of a scrambler delay line. Note that the N bits need not be contiguous in the M-bit delay line. For a sufficient implementation, N>=2. The scrambler initialization circuit inserts same N-bit value into an unscramble part of the header of the transmitted frame, so that the receiver may correctly recover the transmitted bit sequence by initializing the descrambler with the chosen value. In one embodiment, the scrambler is the frame-synchronized scrambler shown in FIG. 11, which uses the following generating polynomial: G(x)=x²³+x¹⁸+1. Bits 15 through 18 of a shift register are initialized with a 4-bit pseudo-random number (or per-path counter value). All other values are initialized to 1. The same value is placed in the unscrambled “SI” field of the Frame Control part of the header so that the receiver may recover the chosen scrambler initialization. FIG. 6 described above shows an example frame format which may convey the “SI” (scrambler initialization) bits to the receiver. FIG. 8 described above shows the components of the “Frame Control” field of the previous diagram in this example. All bits up to and including “SI” in the are unscrambled in accordance with the present invention. Any bits following the SI field are scrambled using this technique.

[0137] Now to further describe the scrambler initialization aspects shown in FIG. 11, scrambler 520 is a frame-synchronized scrambler which uses the generating polynomial G(x)=x²³+x¹⁸+1. Bits 15 through 18 of shift register 650 are initialized with a 4-bit pseudo-random number. This value is placed in SI field 618 defined above in the order such that register position 15 is the MSB (bit 19 of frame control) and bit 18 is the LSB (bit 16 of frame control). Scrambler 520 is bypassed during the preamble bit field and the first 16 bits of Frame Control. Scrambler 520 is initialized and enabled starting with the 17^th bit of Frame Control field 614. Scrambler 520 is bypassed after the last bit of the CRC-16644, or the last bit of the PAD field 646, if present. The EOF sequence is not scrambled. The use of a pseudo-random initial scrambler state results in a more uniform power-spectral density (PSD) measured over multiple similar frames. This eliminates the problem of tones in the PSD from highly correlated successive packets.

[0138] As can be seen in FIG. 11, input frame 5010 is the output of framing 510 as seen in FIG. 5 which also generates SI value 618 as seen in FIG. 8. Bit values of 15002 are inserted into register bit locations 1-145004. Further bit values of 15006 are inserted into register bit locations 19-235008. SI value 618 is inserted into bit locations 15, 16, 17, 185009 of register 650. Each of the additions are modulo 2, i.e., a bit, exclusive or, another bit, and so on. Input bits 5010 are exclusive or'd with the output bits of register 650. Output bits 5012 are provided to constellation encoder 530 as seen in FIG. 5., bit 1 being the most recent bit.

[0139] As to the descrambler initialization circuit, at the receiver, the descrambler initialization circuit extracts the N bits of the “SI” field from the received frame. It then inserts the N bits into the same positions of the descrambler delay line that were initialized in the scrambler, in the same order. (Note that the descrambler and scrambler delay lines have exactly the same length, in bits.) In the example embodiment, all other bits in the descrambler delay line are set to “1”. The first bit inserted into the descrambler is exactly the first bit inserted into the scrambler in the transmitter.

[0140] Turning again to FIG. 5, following scramber 520 is constellation encoder 530. All bits up to and including the Ethertype field are encoded at 2 MBaud, 2 bits per Baud. Starting with the 1^st bit following the Ethertype field, the bits are encoded according to the PE field 624, up to the last bit of the CRC-16644, or the last bit of PAD 646 if it is present. The EOF sequence 648 is encoded at 2 MBaud, 2 bits per Baud. Constellation encoder 530 performs bit to symbol mapping. The incoming bits are grouped into N-bit symbols, where N is the number of bits per baud specified in PE field 624. The bit to symbol mapping is shown in FIGS. 12a through 12g. The symbol values are shown with bits ordered such that the right-most bit is the first bit received from scrambler 520 and the left-most bit is the last bit received from scrambler 520. All constellations except for 3 bits-per-Baud lie on a uniform square grid, and all constellations are symmetric about the real and imaginary axes. The relative scaling of different constellations at a single baud rate is shown in FIG. 13. The constellation points are scaled such that the reference points have the values shown, with a minimum-distance tolerance of plus or minus 4%. The constellation points are scaled such that the outermost points have approximately equal magnitude. Symbols at 4 MBaud are transmitted at 0.707 the amplitude of symbols at 2 MBaud. On a transition from 2 MBaud to 4 MBaud, the first 4 MBaud symbol occur 0.5 microseconds after the last 2 MBaud symbol. On a transition from 4 MBaud to 2 MBaud, the first 2 MBaud symbol occur 0.5 microseconds after the last 4 MBaud symbol. This is illustrated in FIG. 14. If the number of bits in a sequence at a given encoding rate (i.e. Baud rate and bits per Baud) is not an integer multiple of the number of bits per Baud, then enough zero bits are inserted at the end of the bit-stream to complete the last symbol. The number of zero bits inserted is the minimum number such that the length of the appended bit stream is an integer multiple of the number of bits per Baud. The number of octets in the original input bit stream can be determined unambiguously from the number of symbols transmitted. This is true because the maximum encoding size is 8 bits per baud, which implies that the number of zero-bits appended must always be less than eight.

[0141] Referring again back to FIG. 5, complex symbols from constellation encoder 540 are input to QAM/FDQAM Modulator 540. QAM/FDQAM modulator implements Quadrature Amplitude Modulation (QAM). FIG. 15 shows an example QAM implementation. The carrier frequency and transmit filters are the same for Baud rates of 2 MHz and 4 MHz. Thus, a 2 MBaud signal is equivalent to an appropriately scaled 4 MBaud signal in which every other symbol is zero. The QAM/FDQAM Modulator used in conjunction with the present invention is described in more detail in the pending application referenced above.

[0142] In addition to the frame formatting described above, the present invention provides for a Compatibility Frame format which is defined for use by HPNA V2 nodes when they are sharing the phoneline with HPNA V1 nodes. In this case, it is important that the V2 transmissions can masquerade as valid V1 frames for correct carrier sense and collision detection behavior, even though the V1 nodes will not be able to recover the data from the frame. In this format, referring to FIG. 16, frame 700 starts with a modified V1 AID field 710, followed by a V2 symbol sequence modified to have periodic gaps 720 so that a V1 receiver will detect this signal as a series of pulses. The frame ends with trailer 730 that includes 4-symbol V2 EOF 740 and a single pulse, EOP 750, generated by passing a QPSK symbol through the transmit path.

[0143] Referring to FIG. 17, transmitter aspect of PHY 320 operating in Compatibility mode is shown in functional block diagram form. Transmitter 800 includes framing 810 implementing the compatibility mode framing described above. Scrambler 820 is responsive to framing 810 and is identical to scrambler 520 described above in conjunction FIG. 5. Scrambler 820 is initialized at the same point in the frame control field. Coupled to scrambler 820 is Constellation Encoder 830 Constellation encoder 830 is identical to the constellation encoder 530 described above in conjunction with FIG. 5.

[0144] Referring back to FIG. 16, Preamble48760 is defined as a repetition of three contiguous 16 symbol sequences (TRN16) that result from encoding 0xfc483084 at 2 MBaud, 2 bits-per-baud, with scrambler 820 disabled. The 72-symbol header, including frame control field (as defined in FIG. 7) and Ethernet DA, SA, and Ethertype fields, is contained within four contiguous subframes. It is scrambled and mapped to constellation points, prior to gapping, as previously described above. In the header, a subframe consists of: one non-information-bearing symbol (the lead symbol), produced by Gap Insertion block 840, and 18 data symbols (header). A gap of 6 2-Mbaud zero symbols (silence) follows each subframe of 19 non-zero symbols. The format of each subframe and gap for the 2-Mbaud header is depicted in FIG. 18. On subframes 0 and 2 of the header, the lead symbol is defined as the first symbol of PREAMBLE48 (bit sequence 00, encoded as QPSK). On subframes 1 and 3 of the header, the lead symbol is defined as the negation of the first symbol of PREAMBLE48 (bit sequence 11, encoded as QPSK). The peak symbol amplitude shown in FIG. 18 is defined hereinbefore in conjunction with constellation scaling. The sign of the lead symbol alternates such that the output of the QAM/FDQAM modulator is the same at the beginning of every subframe. Negating the lead symbol of every other subframe accounts for the 180-degree rotation introduced by the (7-MHz=carrier frequency) modulator and the odd number of symbols between the first symbols of two adjacent subframes. The special relationship between the carrier phase of the first symbol of the preamble and of every lead symbol is specific to the V2 compatibility mode. There are no such requirements in the V2 native mode.

[0145] Now turning to the 2-Mbaud and 4-Mbaud payloads in conjunction with compatibility mode, the 2-Mbaud payload is encapsulated in subframes, consisting of: one non-information-bearing symbol (the lead symbol), produced by Gap Insertion block 840, between 1 and 18 data symbols (payload). A gap of 6 2-Mbaud zero symbols (silence) follows each subframe. On subframes 2*k, k>1, the lead symbol is defined as the first symbol of PREAMBLE48. On subframes 2*k+1, k>1, the lead symbol is defined as the negation of the first symbol of PREAMBLE48. The first floor [N*8/(r*18)] subframes of the payload, where N is the number of payload bytes and r is the number of bits per baud, contain exactly 18 information-bearing symbols. The last subframe of the payload contains the remaining payload symbols, between 1 and 18. The last subframe is also followed by a gap of 6 zero symbols. The format for all but the last of the 2-Mbaud payload subframes and gaps is identical to the header subframe and gap depicted in FIG. 18. For 3, 5, and 7 bits per baud, the lead symbol is not a valid point in the constellation encoder. The 4-Mbaud payload is encapsulated in subframes, consisting of: one non-information-bearing symbol (the lead symbol), produced by Gap Insertion block 840, one zero symbol, and between 1 and 35 data symbols (payload). A gap of 13 4-Mbaud zero symbols (silence) follows each subframe. On subframes 2*k, k>1, the lead symbol is defined as the first symbol of PREAMBLE48. On subframes 2*k+1, k>1, the lead symbol is defined as the negation of the first symbol of PREAMBLE48. The first floor[N*8/(r*35)] subframes of the payload, where N is the number of payload bytes and r is the number of bits per baud, contain exactly 35 information-bearing symbols. The last subframe of the payload contains the remaining payload symbols, between 1 and 35. The last subframe is also followed by a gap of 13 4-Mbaud zero symbols. The format for all but the last of the 4-Mbaud payload subframes and gaps is depicted in FIG. 19. The peak symbol amplitude and the amplitude of the other symbols shown in the figure are defined above in conjunction with 4-Mbaud constellation scaling. For 3, 5, and 7 bits per baud, the lead symbol is not a valid point in the constellation encoder.

[0146] There are also two possible EOF/EOP sequences following a 2-Mbaud payload and four possible EOF/EOP sequences following a 4-Mbaud payload. The EOF/EOP symbol sequence for the 2-Mbaud payload case is defined in the table set forth in FIG. 20. P is the number of information-bearing symbols in the last payload subframe and M is the number of payload subframes in the frame. The entire EOF/EOP sequence is encoded as QPSK at 2 Mbaud with the scrambler bypassed. The last symbol (similar to an V1 EOP) is used for accurate end-of-carrier timing in all V1 receivers. The EOF/EOP symbol sequence for the 4-Mbaud payload case is defined in the table set forth in FIG. 21. P is the number of information-bearing symbols in the last payload subframe and M is the number of payload subframes in the frame. The entire EOF/EOP sequence is encoded as QPSK at 2 M-baud with the scrambler bypassed. The last symbol (similar to an V1 EOP) is used for accurate end-of-carrier timing in all V1 receivers.

[0147] Referring back to FIG. 17, Modified AID Generator 850 is provided. A modified V1 AID is prepended to every frame. The modified AID is defined as a V1 AID in which each pulse in the AID is replaced by a pulse defined below. The AID number is one chosen by the sending station and conflicts are resolved by selecting a new AID number. The control word always indicates high-speed and low-power transmission. The use of the AID mechanism for collision detection implies that V2 has the same limitation on the maximum number of nodes as V1 when in compatibility mode. FIG. 22 shows the first part of a compatibility mode frame. The modified AID pulse is generated by passing the first symbol of the PREAMBLE48 through the QAM/FDQAM modulator with the same initial modulator phase as the first symbol of the PREAMBLE48. The modified AID pulse is also used for the JAM sequence.

[0148] Referring back to FIG. 17 QAM/FDQAM Modulator operates continuously from the first symbol of PREAMBLE48, as described for QAM/FDQAM Modulator 540 of FIG. 5.

[0149] Now turning to transmitter electrical characteristics, stations at a minimum are capable of transmitting and receiving 2 MBaud modulated frames in native V2 frame format. In a preferred embodiment stations are capable of transmitting and receiving 2 Mbaud Compatibility V2 frame format. Stations at a minimum are capable of transmitting all constellations from 2 bits-per-Baud to 8 bits-per Baud (PE values 1-7) and receiving all constellations from 2 bits per Baud to 6 bits per Baud (PE values 1-5). The R.M.S. differential transmit voltage does not exceed −15 dBVrms in any 2-msec window between 0 and 30 MHz, measured across a 135-Ohm load between tip and ring for any payload encoding. The peak differential transmit voltage does not exceed 580 mVpeak for any payload encoding at either 2 Mbaud or 4 M baud. Stations that are not transmitting emit less than −65 dBVrms measured across a 100-Ohm load between tip and ring. The electrical characteristics described below as to spectral mask apply to both the V2 native mode and the V2 compatibility mode. The V2 metallic power spectral density (PSD) is constrained by the upper bound depicted in the FIGS. 23a and 23b with the measurement made across a 100-Ohm load across tip and ring at the transmitter wire interface. The mask applies to all payload encodings at both 2 and 4 Mbaud. The resolution bandwidth used to make this measurement is 10 kHz for frequencies between 2.0 and 30.0 MHz and 3 kHz for frequencies between 0.015 and 2.0 MHz. An averaging window of 213 seconds used, and 1500-octet MTUs separated by an IFG duration of silence is assumed. A total of 50 kHz of possibly non-contiguous bands may exceed the limit line under 2.0 MHz, with no sub-band greater than 20 dB above the limit line. A total of 100 kHz of possibly non-contiguous bands may exceed the limit line between 13.0 and 30.0 MHz, with no sub-band greater than 20 dB above the limit line. The 10 dB notches at 4.0, 7.0 and 10.0 MHz are designed to reduce RFI egress in the radio amateur bands. The mask is tested at PE values of 1 and 2 (2 and 3 bits/symbol), as these payload encodings result in the maximum transmitted power. The absolute power accuracy is +0/−2.5 dB relative to −7 dBm, integrated from 0 to 30 MHz. The passband ripple between 4.75 and 6.25 MHz and between 8.0 and 9.25 MHz is less than 2.0 dB. The magnitude of the V2 transmitter output is upper-bounded by the temporal mask shown in FIG. 24 for a compatibility mode pulse (the symbol response of the 2.0 transmitter). The response is measured across a 100-Ohm load between tip and ring at the transmitter's WIRE interface. Output before t=0 and after t=5.0 microseconds is <0.032% of the peak amplitude. The first compatibility mode pulse in the modified AID is exactly the transmitter symbol response. The transmitter C-weighted output in the band extending from 200 Hz to 3000 Hz does not exceed 10 dBrnC when terminated with a 600-Ohm resistive load. The transmitter emits no more than −55 dBVrms across a 50-Ohm load between the center tap of a balun with CMRR >60 dB and the transceiver ground in the band extending from 0.1 MHz to 50 MHz. The transmitter clock frequency is accurate to within +/−100 ppm over all operating temperatures for the device. The minimum operating temperature range for this characteristic is 0 to 70 degrees C. In general, a +/−50 ppm crystal meets this characteristic. The R.M.S. jitter of the transmitter clock is less than 70 psec, averaged over a sliding 10-microsecond window. The differential noise output does not exceed −65 dBVrms across a 100-Ohm load, measured from 4 to 10 MHz with the transmitter idle. There is no gain or phase imbalance in the transmitter, except with respect to constellation scaling as described above.

[0150] Now turning to a comparable receiver's electrical characteristics, the receiver detects frames with peak voltage up to −6 dBV across tip and ring at a frame error rate of no greater than 10⁻⁴ with additive white Gaussian noise at a PSD of less than −140 dBm/Hz, measured at the receiver. The receiver detects 1518-octet frames frames encoded as 2 bits/symbol and 2 Mbaud with R.M.S. voltage as low as 2.5 mV at no greater than 10⁻⁴ frame error rate. The R.M.S. voltage is computed only over time during which the transmitter is active. The receiver detects no more than 1 in 10⁴ 1518-octet, 2 bits/symbol, 2 Msymbol/sec frames with R.M.S voltage less than 1.0 mV. Both criteria assume additive white Gaussian noise at a PSD of less than −140 dBm/Hz, measured at the receiver, and assume a flat channel. The receiver demodulates frames with payload encoded at 6 bits/symbol, 2 or 4 Mbaud (if implemented), and differential R.M.S voltage as low as 20 mV (measured over the header) at a frame error rate less than 10−4 under the following conditions: (1) White Gaussian noise with PSD less than −130 dBm/Hz is added at the receiver, and (2) A single tone interferer with any of the frequency band and input voltage combinations set forth in FIG. 25. The applied voltage is measured across tip and ring at the input to the transceiver. The receiver demodulates frames with payload encoded at 6 bits/symbol, 2 or 4 Mbaud (if implemented), and differential R.M.S voltage as low as 20 mV (measured over the header) at a frame error rate less than 10−4 under the following conditions: (1) White Gaussian noise with PSD less than −130 dBm/Hz is added at the receiver, differential mode, and (2) A single-tone interferer, measured between the center tap of a test transformer and ground at the input to the transceiver, with any of the following frequency band and input voltage combinations set forth in FIG. 26. The common mode rejection of the test transformer used to insert the signal should exceed 60 dB to 100 MHz.

[0151] The average return loss of the transceiver with respect to a 100-Ohm resistive load exceeds 12 dB between 4.75 and 9.25 MHz. This characteristic applies to the transceiver powered on or in low-power mode (transmitter powered off). The average return loss with respect to a 100-Ohm resistive load exceeds 6 dB between 4.75 and 9.25 MHz with the transceiver removed from a source of power. The magnitude of the input impedance is >10 Ohms from 0-30 MHz and conforms to the lower-bound mask set forth in FIG. 27. This characteristic applies to the transceiver powered on, in low-power mode (transmitter powered off), or removed from a source of power. FIG. 28 shows an example of the input impedance of a compliant device with a lower bound mask.

[0152] With regard to the receiver aspects in accordance with the PHY layer protocol, reference in made to FIG. 30, wherein receiver functionality 900 is shown in block diagram form. Receiver functionality 900 performs the reverse of that described above for transmitter 500, namely, upon receiving a signal from 2-4 wire hybrid and performing front end processing as described in conjunction with FIG. 4b, the following occurs: QAM/FDQAM Demodulator Gap Removal, Consellation Decoding, De-scrambling and De-framing, as is well-known in the art given the above-defined transmitter functionality.

Homenetworking MAC Layer Overview

[0153] Now turning to the MAC Layer, the station media access control (MAC) function, as seen at the wire interface is described in more detail. The HPNA V2 MAC is modeled after the carrier-sense multiple-access with collision detection (CSMA/CD) MAC function of Ethernet (IEEE Std 802.3, 1998 Edition), adapted to the V2 PHY and enhanced with quality-of-service (QoS) features. The MAC functions described hereinbelow should not be confused with host interface and other layer functions typically implemented in a “MAC chip”. Also the MAC control function should not be confused with IEEE 802.3 Clause 31 MAC Control.

[0154] Referring to FIG. 29, the MAC logical layers and functions are depicted. Although the MAC function is an essential part of the wire interface characteristics, the system partitioning of PHY and MAC functions is implementation dependent. In particular, it is intended that the present embodiment can be implemented in an integrated PHY+MAC chip as well as a PHY-only chip that can be interfaced with a standard “MAC chip” using the Media Independent Interface (MII) described in IEEE Std 802.3—1998, clause 22.

[0155] When in Compatibility Mode V2 devices transmit either V1 Format frames or V2 Compatibility Format frames depending on the destination station type. The MAC operation in this mode is IEEE Std 802.3—1998 CSMA/CD MAC with BEB collision resolution and no access priority. When in compatibility mode the MAC operation is as specified in IEEE Std. 802.3—1998, clause 4, for a MAC sublayer operating in half duplex mode at speeds of 100 Mb/s and below. The timing parameters to be used in Compatibility Mode are in accordance with the V1 PHY Specification, Version 1.1. In compatibility mode the MAC times the inter-frame gap from the de-assertion of the carrier sense signal, CAR_SENS. The timing of CAR_SENS relative to the wire interface adheres to the timing specified in HPNA V1 PHY Specification rev 1.1, clause 3.3.

[0156] An implementation may have different individual CAR_SENS/MAC timing parameters provided the overall timing at the wire interface is the same as CAR_SENS/MAC with the parameters specified. Further, In compatibility mode the detection of collisions is as specified in HPNA V1 PHY Specification rev 1.1, clause 2.5.3, with a JAM signal emitted as specified in clause 2.5.4. ACCESS ID values are maintained as specified in clause 2.5.5.

[0157] Now turning to V2 Mode MAC Operation, each station on an V2 network segment, when not in Compatibility Mode, executes the V2 MAC function to coordinate access to the shared media. Switching between Compatibility Mode and V2 native mode is described hereinbelow. The MAC timing parameters for V2 Mode are also defined below.

[0158] The Carrier Sense Multiple Access/Collision Detect (CSMA/CD) media access method is the means by which two or more stations share a common transmission channel. To transmit, a station waits (defers) for a quiet period on the channel (that is, no other station is transmitting) and then sends the intended message modulated as per the PHY characteristics. The transmission deferral is ordered by up to eight priority levels, implementing absolute priority among stations contending for access. If, after initiating a transmission, the message collides with that of another station, then each transmitting station ceases transmission and resolves the collision by choosing a Backoff Level and defers to other stations that have chosen a lower Backoff Level. The distributed algorithm for choosing Backoff Level guarantees that the access latency is tightly bounded. Each aspect of this access method process is set forth in detail hereinbelow.

[0159] Referring again to FIG. 30, a transceiver functional block diagram of an embodiment of the present invention is shown which includes transmit functionality portion 500, counterpart receive functionality portion 900, V1 compatability transmit and receive functionality portions 910, 920, MAC functionality portion 1000 for both V1 and V2 modes, and 2-4 wire hybrid portion 930. Included in MAC 1000 is carrier sense functionality portion 1100, collision detection functionality portion 1200, and CSMA/CD collision resolution/rx frame synchronization functionality portion 1300. Carrier Sense 1100 detects the starting and ending times of a valid frame transmission on the wire. This is used to determine when frames are present on the channel/transmission medium, as well as being used to determine the presence of a Backoff Signal in a Signal Slot. Collision Detection 1200 detects the presence of a valid frame transmission from some other station during an active transmission, and for all stations, including non-transmitting stations, detects the received fragment that represents a transmission truncated by a collision. Collision Resolution 1300 implements the distributed algorithm that controls backoff. Although the performance of the blocks in the MAC function are implementation dependent, certain minimum performance requirements are needed to ensure interoperability and compatible sharing of the channel and are now described in more detail.

[0160] Referring to FIG. 31 a frame transmission that is valid with respect to the specified Carrier Sense (CS) function (Valid CS Frame) is shown. A transmitted Valid CS Frame will be affected by various signal impairments when seen by any receiver. A Valid CS Frame at the transmitter wire interface consists of: (1) A sequence of symbols whose duration is equal to or greater than 92.5 microseconds (TX_FRAME minimum) duration, but less than the maximum described below; (2) the first (64+16+24+24+8) symbols of which modulated at the Base Rate (2 MBaud QPSK, 2 bits per symbol), where the initial 64 symbols consist of the preamble sequence 1110, where the next 64 symbol sequence (other) 1120 is unique to the transmitting station, and where the next 8 symbols are the (likely non-unique) bits of the Ethertype field; (3) an arbitrary Minimum Signal 1140, defined as a sequence of symbols whose R.M.S. value over any 8-microsecond window shall never be more than 9 dB less than 100 mVrms across 100 Ohms (NOMINAL_RMS_VOLTAGE); (4) 4 symbols of the EOF sequence 1150; (5) a trailing transient, whose peak voltage does not exceed 0.1% of the absolute peak transmitted voltage across a 100-Ohm load at the WIRE interface at any point >5 microseconds after the last transmitted symbol of the EOF; and (6) a gap before the next transmission of this station of CS_IFG microseconds from the last symbol of the EOF to the first symbol of PREAMBLE of the next transmission, measured at the transmitter's wire interface. When a station detects what may be a collision it terminates transmission early, as described below.

[0161] A Valid Collision Fragment at the transmitter wire interface consists of: (1) a sequence of symbols of 70.0 microseconds (CD_FRAG) duration; (2) consisting of (64+16+24+24+8) symbols modulated at the Base Rate (2 MBaud QPSK, 2 bits per symbol), where the initial 64 symbols consist of the preamble sequence, and where the next 64 symbol sequence is unique to the transmitting station, followed by 8 more symbols; (3) 4 symbols of the EOF sequence; (4) a trailing transient, whose peak voltage does not exceed 0.1% of the absolute peak transmitted voltage across a 100-Ohm load at the WIRE interface at any point >5 microseconds after the last transmitted symbol of the EOF; and (5) a gap of at least CS_IFG+CD_FRAG microseconds from the first symbol of the PREAMBLE64 of the Valid Collision Fragment to the first symbol of the BACKOFF20 signal in the first Backoff Signal Slot (if present), measured at the transmitter's wire interface. Receivers are only required to correctly detect Valid CS Frames, Valid Collision Fragments, and the Backoff Signal described below. The Inter-frame Gap is 29.0 microseconds (CS_IFG), where the gap is defined at the points at which the previous frame drops below 50% of its peak and the current frame rises above 50% of its peak. Timing of subsequent transmissions following a Valid CS Frame or Valid Collision Fragment are based on a MAC timing reference, established by the receiver.

[0162] Referring to FIGS. 32 and 33, time following a transmission TX is divided into slots: (1) an Interframe Gap (IFG) 1400; (2) three Backoff Signal Slots 1500 (following collisions 1600); and (3) 8 priority slots 1700. During these time periods the MAC is synchronized and the slot timing is defined by the rules for valid transmissions as set forth above. After priority slot 0 there may be an arbitrarily long period with no transmissions followed by one or more stations attempting transmission. In this latter case the MAC is unsynchronized. When MAC timing is synchronized stations commence any transmission no earlier than 0 and no later than 4 microseconds (TX_ON) after a slot origin, measured at the transmitter wire interface. Receiver Carrier Sense function 1100 as seen in FIG. 30 detects a maximum-amplitude Valid CS Frame over a range of 0 to at least 38 dB (CS_RANGE) flat-channel insertion loss and additive noise with a flat PSD of −140 dBm/Hz at the receiver with a missed frame rate of less than 10⁻⁴ and a premature end-of-frame declaration rate less than 10⁻⁴. With additive white Gaussian noise applied at the input with a PSD of −110 dBm/Hz, the false carrier detection rate is no greater than 1 per second. When the MAC is unsynchronized, the latest a station may commence transmission after a possible Valid CS Frame has appeared at the wire interface is 12 microseconds (CS_DEFER) from the first symbol of the PREAMBLE64 of the detected frame, as measured at the station's wire interface. CS_DEFER is the maximum allowed carrier sense delay.

[0163] The V2 embodiment can be used for carrying media streams, such as video and audio (as described in more detail below). To reduce the latency variation in these streams, a priority mechanism is implemented to allow higher layers to label outgoing frames with priority, and guarantee that those frames will have preferential access to the channel over lower priority frames. The access priority method implemented is to delay transmissions to a slot beyond the minimum inter-frame gap, based on the priority level of the frame waiting to be transmitted. Referring back to FIG. 32, slots are numbered in decreasing priority, starting at priority 7. Higher priority transmissions commence transmission in earlier slots and acquire the channel without contending with the lower priority traffic. A station's Priority Slot is based on the PHY priority number associated with the frame ready for transmission (TX_PRI), as determined by the network stack and communicated to the MAC. The station uses any slot with a number less than or equal to TX_PRI, normally the slot numbered exactly TX_PRI. FIG. 32 shows the relative timing of priority slots. After priority slot 0 there are no more priority slots, and any station with traffic at any priority level can contend on a first-come, first-served basis. All collisions after priority slot 0 are considered to happen at PRI=0.) The Priority Slot width is 21 μmicroseconds (PRI_SLOT). No station transmits in a Priority Slot numbered higher than the TX_PRI assigned to the frame being transmitted. Stations not implementing priority default TX_PRI to a value of 1 when transmitting. Stations waiting for transmission monitor Carrier Sense, and defer if CS was true prior to the start of the station's Priority Slot, or if beyond Priority Slot 0 the station defers if CS was true prior to the start of transmission. Any station ready to transmit at the start of its Priority Slot transmits if CS was false prior to the start of it's Priority Slot, without deferring if CS was asserted prior to the start of transmission. See FIGS. 34a and 34b, depicting transmission aspects, without and with priority access, respectively. With priority access video traffic at priority level 7 gains access ahead of best effort traffic scheduled at level 1. The slot timer is restarted if there is some other transmission that acquires the channel while a station is waiting at a lower priority.

[0164] The TX_PRI value is the priority the MAC uses to schedule transmission and is the value present in the PRI field of the frame header. This value is determined by a higher layer in the network stack. The PRI field is used to transport the priority label from source to destination, to assist the destination in managing the receive queue. The 3 bit priority values referred to are “PHY priorities”. PRI=7 has the highest priority, PRI=0 has the lowest. There may be a mapping between PHY priorities and the Link Layer (LL) priority values as delivered to the Link Layer by the NETWORK Layer. This mapping is described herein below with regard to the Link Layer Protocols for V2. In general, the NETWORK layer or APPLICATION layer will determine what policy is used to map traffic onto LL priorities. For instance, IETF Integrated Services currently defines priority 0 as the default “best effort” priority, and priority 1 as the penalty “worse than best effort” priority—and most implementations will map best effort to PHY PRI=1 and worse-than-best-effort to PHY PRI=0. The PHY priority mechanism is strict priority (as opposed to schemes which allocate lower priorities some minimum percentage of network capacity)—higher priority traffic always defers lower priority traffic. Higher priority traffic will be limited by admission control or other Link Layer policy mechanism to prevent over-subscription.

[0165] Two or more stations may begin transmitting in the same Priority Slot following the IFG period. All stations monitor the channel to detect the colliding transmissions of other stations. Colliding frame(s) will be received over a channel with impairments. FIG. 35, shows length of collisions and non-collisions. Passive stations can detect collisions by observing the length of transmission fragment and the validity of the received PREAMBLE64. A Valid CS Frame is guaranteed to have a unique symbol sequence within the first 128 symbols (which are transmitted at Base Rate). The Ethernet MAC Source Address (SA) is used to guarantee uniqueness. That field is scrambled, but the [scrambled SA, SI] tuple will be unique. SI is the 4-bit scrambler initialization field, as described above. After detecting a collision a station continues to transmit through the Ethertype field followed by an EOF sequence (symbol 139) and then cease transmission. Thus, a station detecting a collision will cease transmission no later than 70.0 microseconds (CD_FRAG) after the beginning of the frame as measured at the wire interface. The minimum size of a Valid CS Frame is 92.5 microseconds (TX_MIN). No jam signal is transmitted on collisions. Passive stations, that are not transmitting, monitor the length of Carrier Sense events and generate a Collision Fragment indication to the Collision Resolution function if the duration of carrier is less than 92 microseconds (CD_THRESHOLD). Stations do not recognize carrier events shorter than 32.0 microseconds (CD_MIN) as collisions. All transmitting and passive stations are capable of detecting the collision of any maximum-amplitude Valid CS Frame transmission received over a range of 0 to 36 dB (CD_RANGE) flat-channel channel insertion loss and additive noise with a flat PSD of −140 dBm/Hz at the receiver with a missed-collision error rate of less than 10−4 and a false collision error rate of less than 10⁻³, where the origin of the colliding frame is offset relative to the first symbol of the transmitted frame anywhere from earlier by up to 12 microseconds (CD_OFFSET_EARLY) to later by up to 15 microseconds (CD_OFFSET_LATE). Where there is a missed collision, the probability of detected and undetected errors in the payload data is enhanced, so Collision Detection implementations are biased towards false collision errors, which are more innocuous.

[0166] A collision occurs when two or more stations are active with ready frames and are contending for access to the channel at approximately the same time. Generally, collisions are between frames at the same priority level. A distributed collision resolution (CR) algorithm is run which results in stations becoming ordered into Backoff Levels where only one station is at Backoff Level 0 and can therefore acquire the channel. After the winning station completes its transmission, all stations reduce their Backoff Level by one if it is greater than zero, and the new station(s) at Backoff Level 0 attempt transmission. All stations, even those with no frame to transmit, monitor the activity on the medium. Also, the collision resolution cycle is closed, so that stations that did not collide are not allowed to contend for access to the medium until all stations that collided have transmitted one frame successfully or have forgone the right to transmit their waiting frame. Ultimately all stations that were contending for access in the initial collision gain access to the wire and the collision resolution cycle is ended. This results in access latency being tightly bounded. This mechanism differs from Binary Exponential Backoff (BEB) used in other versions of Ethernet in that the Backoff Level does not determine he contention slot chosen by a station—all stations at a given priority always contend in the slot corresponding to the access priority. Instead stations at non-zero Backoff Levels defer contending until stations that are at zero Backoff Level transmit. The method used is called Distributed Fair Priority Queuing (DFPQ) as described in co-pending application Ser. No. 09/0267,884, the content of which are expressly incorporated by reference herein. Each station maintains eight Backoff Level (BL) counters, one for each priority. The Backoff Level counters are initialized to 0. The priority level of a collision can be inferred from the priority slot where the collision occurs. Consider the case where stations are only contending on one priority. After a collision and an IFG, three special Backoff Signal slots (S0 . . . S2) are present before the normal sequence of priority contention slots occurs. Signal slots only occur after collisions, they do not follow successful transmissions. Each active station pseudo-randomly chooses one of the slots, and transmits a Backoff Signal. More than one station can transmit a Backoff Signal in the same slot. The active stations transmit Backoff Signals to indicate ordering information that determines the new Backoff Levels to be used. All stations (even those without a frame ready to transmit) monitor collision events and the Backoff Signal slots to compute the Backoff Level. If an active station sees a Backoff Signal in a slot prior to the one it chose, it increases its Backoff Level. Those stations at Backoff Level 0 (ones that are actively contending) that saw no Backoff Signals prior to the one they chose, remain at Backoff Level 0 and contend for transmission in the priority slot equal to TX_PRI that immediately follows the Backoff Signal sequence. Eventually, only one station remains at Backoff Level 0 and successfully gains access to the channel. Stations with higher priority waiting frames may pre-empt the collision resolution by transmitting in a higher-priority slot. All stations, even those not contending for access to the wire, also maintain a Maximum Backoff Level (MBL) counter per priority, which is incremented for each Backoff Signal seen and decremented when a successful transmission occurs. The MBL is non-zero whenever a collision resolution cycle is in progress. When a station first becomes active, if MBL is non-zero, BL is initialized to contents [MBL], otherwise BL is initialized to 0. This ensures that all currently active stations gain access to the channel before stations can re-enter the waiting queue. The BACKOFF20 signal is a symbol sequence consisting of 16 symbols of the preamble sequence (TRN16) transmitted, followed by the 4 symbol EOF sequence. Detection of the BACKOFF20 signal(s) in a Backoff Signal slot must be possible even if more than one station selects the same slot. Stations implement saturating 4-bit BL and MBL counters. The width of the Signal Slot is 32 microseconds (SIG_SLOT). Stations implement the MAC function with collision resolution whose behavior matches the procedural model described below.

[0167] The procedural model uses a pseudo-code modeled after Concurrent Pascal. IEEE Std 802.3 1998 Clause 4.2.2 provides an overview of this pseudo-code. The code set forth below models three independent concurrent processes (Deference, Transmitter, Receiver), which interact through shared variables. The Deference process is driven by the detection of transmissions on the channel, and times the boundaries for Signal Slots and Priority Slots. The shared variable current Priority signals the Transmitter process when a transmission slot exists.

[0168]

(Deference:
Loop, looking for carrier sense, and when found determine whether the
transmission was a collision or valid frame.
If it was a collision, process the signal slots and run the
collision resolution algorithm.
In any case, then process the priority slots, looking for carrier.
Note that the “current” priority level is sticky from the slot
the last collision occurred in.
Note that the Backoff Level (BL) and Maximum Backoff Level (MBL)
counters are saturating at 0 and 15.)
Const
nPriorities = 8; (Number of priority levels)
nSignals = 3; (Number of signal slots)
nLevels= 16; (Number of Backoff Levels)
process Deference;
begin
currentPriority := 0; (Priority of the slot we are in)
cycle (deference loop)
sawFrame := false;
sawCollision := false;
while not carrierSense( ) do nothing; (watch for carrier to appear)
deferring := true;
startTime := time( );
stopTime := startTime;
while carrierSense( ) do
stopTime := time( );
if ((stopTime − startTime > CD_MIN) and
(stopTime − startTime < CD_THRESHOLD)) or collisionSense( )
then sawCollision := true
else sawFrame := true;
(After a collision, process the three signal slots)
if sawCollision then
begin
(wait until the end of the IFG, timing from start of fragment
reduces skew, since start-of-carrier uncertainty is less than
end-of-carrier uncertainty )
while (time( ) − startTime < CS_IFG + CD_FRAG) do
nothing( );
computeSignals( );
for (i := 0; i < nSignals; i++)
begin
startTime := time( );
signal[i] := 0;
if signalSlot = i then sendSignal( );
while (time( ) −startTime < SIG_SLOT) do
if carrierSense( ) then signal[i] := 1;
end;
processSignals ( );
end;
if (not sawCollision) then
begin
(wait until the end of the IFG)
while (time( ) − stopTime < CS_IFG) do nothing( );
(If last transmission was successful, drop Backoff Levels)
BL[currentPriority] := saturate(0,nLevels−1,BL(currentPriority)−
MBL[currentPriority] := saturate (0,nlevels−
1,MBL[currentPriority]−1);
end;
(avoid timing hazard with transmitter, currentPriority must be
setup
before deferring is cleared)
currentPriority ;= nPriorities−1;
deferring := false;
(Now time out the Priority (contention) slots)
for (i := nPriorities−1; i>=0; i−−)
begin
slotTime := time( );
currentPriority := i;
while (time( ) −slotTime < PRI_SLOT) do
if carrierSense( ) then endcycle; (restart deference loop)
(if priority slot passed with no contenders, then that priority
level must be idle, good practice says make sure the backoff
counters are reset)
BL[currentPriority] := 0;
MBL[currentPriority] := 0;
end;
end; (cycle)
end; (Deference)
(computeSignals: Determine which signals to send)
function computeSignals( );
begin
signalSlot := 1; (−1 means no signal to send, initialization)
if (txReady and (txPriority = currentPriority) and BL[txPriority]=0) then
signalSlot = integerRandom(nSignals); (select Backoff Signal slot)
end; (computeSignals)
(processSignals: Process the received signals, adjusting the Backoff
Levels)
function processSignals( );
begin
psignals := 0;
for (i=0; i < nSignals; i++)
if signal[i] then psignals++;
if (txReady and (txPriority = currentPriority)) then
begin
backoffLevel := BL[currentPriority];
if backoffLevel = 0 then
begin
tem := 0;
for (i=0; i < signalSlot; i++)
if signal[i] then tem++;
BL [currentPriority] := saturate (0,nLevels−1, tem);
end;
if backoffLevel > 0 then
if psignals > 0 then
BL[currentPriority] :=
saturate(0,nLevels−1,backoffLevel + psignals−1);
end;
if psignals > 0 then
begin
if MBL[currentPriority] = 0 then MBL[currentPriority] := psignals;
else MBL[currentPriority] = saturate (0,nLevels−1,
MBL[currentPriority]  + psignals−1);
end;
end; (processSignals)
(Transmitter: Wait for txReady and txPriority from the link level process.
send txFinished when frame has been sent.)
process Transmitter;
begin
cycle
while (not txReady) do nothing( );
BL[txPriority] := MBL[txPriority];
while (not (txPriority >= currentPriority and BL[txPriority]=0)
or deferring)
do nothing( );
ttime := time( );
xmtDataOn( ); (start data transmitting)
while xmtBusy( ) and (time( ) − ttime < CD_FRAG) do
begin
if collisionSense( ) then
begin
xmtDataOff( ); (turn off, after sending minimum collision
fragment)
Ncollisions++; (timeout on excessive collision limit)
if Ncollisions = attemptLimit−1 then txFinished( );
endcycle;
end;
end;
while xmtBusy( ) do nothing( );
txReady := false;
txFinished( );  (signal link level that frame has been
transmitted)
end; ( cycle )
end; ( Transmitter )
(collisionSense: )
function collisionSense( );
begin
( When transmitting, detect the presence of a second transmission.
When receiving, detect overlapped transmissions)
end; ( collisionSense )
(Receiver: )
process Receiver;
begin
( Wait for carrier sense. Demodulate received signals into frames.
Reject collision fragments. Determine frame boundaries. Check FCS.
Filter based on destination address. Perform optional Link Layer
signaling and other controller functions.)
end; ( Receiver )

[0169] Referring to FIG. 36, certain Mac parameters are set forth. Where a tolerance is indicated, Δ=63 nanoseconds. The Link-level frame consists of the DA through FCS fields, prior to the PHY-level frame encapsulation. All V2 stations transmit link-level frames with a minimum of 64 octets. The payload field of link-level frames smaller than minFrameSize is padded with any value octets appended after the supplied payload to make the frame minFrameSize long. The maximum standard Ethernet frame is 1518 octets, but some V2 link-layer encapsulations may add additional octets. All V2 stations are able to transmit and receive link-level frames with up to 1526 octets. No V2 station transmits link level-frames with more than (PE+1)*1024 octets for 2 MBaud and not more than (PE−7)*2048 octets for 4 MBaud. The number of octets specified counts DA through FCS, and does not count preamble, header, CRC-16 or PAD or EOF. This will result in a maximum frame duration of 4166 microseconds for a frame with PE=15. A V2 station defaults the maximum length frame it will send to a given DA to 1526 octets until it can determine that the receiver can support larger transmission units (e.g. by use of the CSA announcement of CSA_MTU as described below with regard to Link protocols. These maximums establish an upper bound on the duration of a given transmission and an upper bound on the maximum frame size that receivers must accommodate.

Homenetworking Link Layer Overview

[0170] In accordance with the present invention the following link control functions are implemented: (1) Rate Negotiation; (2) Link Integrity; (3) Capability Announcement; (4) Limited Automatic Repeat reQuest (LARQ). These link functions use control frames to carry protocol messages between stations. V2 includes a standardized mechanism for Link Layer network control and encapsulation. Control frames are data link layer frames that are identified by IEEE assigned Ethertype value (0x886c designated for the Assignee of the present application) in the Type/Length field of the frame, and further distinguished by individual sub-types. The link control entities may be implemented in hardware or driver software. Link Control frames are not seen by layer 3 (IP) of the network stack, and are not bridged between network segments.

[0171] It should be noted that the Minimal Link Protocol Support Profile for HPNA V2 Link Protocols embodiments of the present invention allow less complex implementations of the HPNA V2 characteristics. While each of the four control protocols serves an important function in the operation of the network, it is possible to implement minimal support for CSA and LARQ that is compatible with fully functional implementations and does not detract from the overall performance of other stations. The shorter name, Minimal Profile, will be used hereinbelow. Full support of all the link protocols, called the Full Link Protocol Support Profile or Full Profile for short, is assumed unless Minimal Profile is explicitly mentioned.

[0172] Referring to FIGS. 37 and 38, there are two basic formats for a Link Control Frame, a long subtype and a short subtype. The long subtype format is provided for future specified control frames where the amount of control information exceeds 256 octets. The control and encapsulation frames described herein use the short subtype format. In the frame formats defined below, note that before transmission the Link Control Frame is converted into a physical layer frame by adding Preamble, Frame Control, CRC-16, PAD and EOF as described above.

[0173] Describing first the short format as shown in FIG. 37, the SSVersion field is recommended for all protocols using the Short Form Link Control Frame header, and specifies which format version of the control information is used. This allows future extension of each SSType. SSLength is checked only to ensure that enough control information is present. New, backwards compatible, frame formats may contain additional fixed data fields, but will always contain the fixed fields specified in earlier formats, so protocol implementations simply use the latest version that is less than or equal to SSVersion. The Next Ethertype field is implemented for all SS headers. Among other things, it supports backward compatibility by enabling receivers to always strip short format link layer headers. If the Next Ethertype field is zero, then the frame is a basic control frame and is dropped after processing the control information it contains. The Next Ethertype is always the last two octets of the control header. The position of Next Ethertype in the frame is determined using the SSLength field in order to ensure forward compatibility. V2 receivers are able to remove at least one encapsulating header with an unknown subtype from any received data frame. Future embodiment versions may require the processing of multiple headers, such as might occur if a Rate Request Control Frame were inserted into (piggybacked on) a regular data frame with a LARQ header. The header and trailer for standard Ethernet frames are cross-hatched in FIG. 37, in order to highlight the formats of the control information frames.

[0174] Describing now the long format as shown in FIG. 38, an LSVersion, similar to SSVersion, is recommended for all Long Format subtypes. A Next_Ethertype field is implemented for all Long Format subtypes. In general, if Long Format subtypes are not understood by the receiver (a fact possibly announced via future CSA options) then they are dropped. Processing requirements with respect to forward compatibility, dropping of unknown frame types with Next_Ethertype=0, and removal of Long Format headers with Next_Ethertype !=0, are identical to those for Short Format Control Frame headers. Network transmission order of frame fields is from the top to the bottom of each figure. Within a field, the MSByte of the field is the first octet of the field to be transmitted, with the LSBit of each octet transmitted first. Subsequent bytes within a field are transmitted in decreasing order of significance. When subfields are pictured in the figures, the ordering shown is decreasing significance from the top to the bottom of the figure.

[0175] The payload encoding (PE) that can be achieved is a function of the channel quality between source and destination, and the channel quality generally differs between each pair of stations depending on the wiring topology and specific channel impairments. Therefore the Rate Negotiation function in a destination station uses Rate Request Control Frames (RRCF), as shown and defined in FIG. 39, to provide information to a source station as to the payload encoding that the source station use to encode future frames sent to this destination, and to generate test frames to assist a receiver in selecting the most appropriate band to use. The policy which the destination station uses to select the desired payload encoding and the policy it uses to decide when to transmit Rate Request Control Frames are implementation dependent. Algorithms for selection of payload encoding and time to transmit RRCF for a preferred embodiment are set forth in more detail below. Stations avoid transmission policies that can result in excessive RRCF traffic. The PHY payload modulation can use 2 to 8 bits-per-Baud constellations and one of several defined bands which are combinations of Baud rates, modulation type (QAM vs. FDQAM) and carrier frequency, as described above. The RRCF specifies a maximum constellation (bits per Baud) that the receiver (ReqDA) wishes to be used in a given band, or indicates that a given band is not supported. Additional bands may exist in future versions, and can be described with band descriptors {PE, rank} added after Band 2. If additional bands are present, their descriptors will appear between Band2_Rank and RefAddr1, and HPNA V2 stations take their presence into account when determining the location of the RefAddr list. In FIG. 39, the cross-hatched fields will not always be present. V2 stations ignore band characteristics beyond Numbands=2. If a receiver does not specify a band in an RRCF, or specifies a PE of 0 for a band, then transmitters do not use that band. The NumBands and NumAddr fields are placed next to each other so that all the fixed fields can be referenced at known offsets in the frame. FIG. 40 shows the assigned values that may appear in the band description entries in the Rate Request Control Frame. FIG. 41 shows the values that may appear in the OpCode entry in the Rate Request Control Frame. FIG. 42 describes further terms and definitions. Rate Negotiation is defined over simplex logical channels. A separate channel is defined for each combination of Ethernet DA and SA. There is no explicit channel setup procedure. A new channel is implicitly defined when a packet is received from a new SA or sent to a new DA. Each channel has a single sender but can have multiple receivers. Receivers operate independently. Rate control frames (all OpCodes) are sent with a priority corresponding to Link Layer priority7. RRCF are not sent with a Link Layer priority of 6. RRCFs may be sent with a lower Link Layer priority, from the set [5,4,3,0]. However, the Link Layer priority of an RRCF is not lower than the highest Link Layer priority received in the last 2 seconds from the station to which the RRCF is being sent. Rate Change Requests (OpCode=0) is sent with an encoding of 2 Mbaud FDQAM at 2 bits per baud (PE=1) when the network is operating in V2 mode, and with V1 encoding when the network is operating in Compatibility mode. Selection of the encoding for Rate Test Request frames and Rate Test Reply frames is described below. Each station maintains a timer with a period of 128 seconds. There is no attempt to synchronize this timer between stations. The timer is not modified by receipt or transmission of any frames. The timer interval is used when determining which nodes have been actively sending to multicast and broadcast addresses and when sending reminder RRCFs in reference to multicast and broadcast addresses.

[0176] Turning now to the sender operation, the logical channel state information is accessed to determine the sender PE to use for transmission. The channel is created if necessary, and the sender PE defaults to PE=1 (2 bits-per-baud, 2 Mbaud FDQAM) if the network is in V2 mode, or to PE=8 if the network is operating in Compatibility mode. Logical channel state information includes the node type (if known), the sender PE and the receiver PE for each band for which this information has been specified. When first entering Compatibility mode, all transmissions to all nodes are sent with V1 encoding for a period of 60 seconds, regardless of the sender PE associated with the logical channel state information. While in Compatibility mode, if the logical channel state information for any active V2 node includes a value of sender PE=8, then all transmissions to all nodes are sent with V1 encoding. When no active V2 node's logical channel state information includes a value of sender PE=8, transmissions revert to the rate specified by the sender PE associated with each channel. While in Compatibility mode, all multicast and broadcast frames are always transmitted with V1 encoding. While in V1 mode, all frames are always transmitted with V1 encoding. For each of the RefAddrs in the RRCF (starting with RefAddr0, the SA of the RRCF frame), the logical channel state information is accessed, if any exists, corresponding to the RefAddr, and the sender PE is updated according to the band characteristics in the RRCF. If no logical channel state information exists for RefAddr0, the station creates a new logical channel state entry and initializes the sender PE according to the band characteristics in the RRCF. If no logical channel state information exists for additional RefAddrs, the station may either ignore those addresses or create new logical channel state entries and initialize the sender PE according to the band characteristics in the RRCF. For multicast addresses and the broadcast address, senders use a rate that is receivable by all nodes actively listening to that address. Sender stations may enforce a minimum PE which they will use to transmit to a given multicast channel, based on application-level information about Quality of Service (QoS). It is desirable to send at the highest rate supported by the channel. Hence, if a RefAddr is a multicast address or the broadcast address, the sender uses the PE value which yields the highest raw bit-rate, but which is not greater than any of the band characteristicss provided by the nodes actively listening to that address. Active multicast listeners are defined as any stations which have, in either of the last two 128-second intervals, either (1) sent any frame to the multicast address or (2) sent a RRCF to this station with the multicast address listed in the RefAddr list. Active broadcast listeners are defined as any stations which have, in either of the last two 128-second intervals, either (1) sent any frame (with the optional exception of Link Integrity frames using PE=1) to the broadcast address or (2) sent a RRCF to this station with the broadcast address listed in the RefAddr list. For each supported band encoding a Rate Test Reply frame (RRCF OpCode 2) is generated to the requester encoded using the specified payload encoding. The contents of the RRCF is the current logical channel state info. Support for Rate Test Request frames is only required in stations that implement additional bands beyond Band1. Stations that only implement Band1 silently discard received Rate Test Request frames. An active V2 node is any station from which a frame has been received in either of the last two 128-second intervals. Whenever a transition to Compatibility mode occurs, sender PE is reset to a value of 8 for all channels. Whenever a transition to V2 mode occurs, sender PE is reset to a value of 1 for all channels. A station which is not capable of transmiting or decoding compatibility mode frames (hereafter referred to as a non-compat station), adheres to the following additional rules. Whenever a non-compat station transitions from V2 to Compatibility mode, it transmits a broadcast RRCF (i.e. an RRCF with DA=“FFFFFFFFFFFF”) requesting PE=8 for all applicable refAddr values, within the first 30 seconds after the mode transition. As long as the non-compat station remains in Compatibility mode, it continues to transmit broadcast RRCFs requesting PE=8 for all applicable refAddr values, at a rate of one RRCF every 128 seconds. These RRCF transmission rules replace all other RRCF transmission rules for a non-compat station during Compatibility mode.

[0177] Now turning to receiver operation, the following baseline algorithm for limiting the number of RRCFs is a preferred embodiment. Alternative implementations do not generate more RRCFs than the suggested implementation. Nodes that are interested in participating in a multicast or broadcast channel provide a mechanism to ensure that all sources of frames sent to the multicast address of the channel are reminded of this node's participation in that channel at least once every 128 seconds. For each channel, a Rate Control Backoff Limit (RCBL) is maintained that ranges in value from 1 to 1024, and a Rate Control Backoff Frame Count (RCBFC). RCBL is initialized to 1, and RCBFC is initialized to 0. For each received frame, the new desired PE is computed. A sample algorithm for selection of desired PE is described below. If the new desired PE is different from the previous value of the desired PE, then RCBL is reset to 1, and RCBFC is reset to 0. The new value is saved for desired PE. If the PE of the received frame is different from the new desired PE, then RCBFC is incremented by 1. If RCBFC is now greater than or equal to RCBL, then an RRCF is sent to the source of the frame, RCBFC is reset to 0, and RCBL is doubled up to a maximum of 1024. If a multicast channel is active (based on receiving frames other than RRCFs within the last two 128-second intervals), and more than 128 seconds have passed since the receiver has sent a frame to this multicast address, an RRCF is transmitted with the current receiver PE to any nodes that have sent frames to that multicast address, with a RefAddr set to the multicast address in question. Multiple multicast addresses may be aggregated into a single RRCF being sent to a node that has been active on multiple multicast addresses. However, only addresses for which the intended recipient of the RRCF has been active are included. In RRCF messages, requesting stations attempt to specify the maximum payload encoding that they believe will have an acceptable error rate, in order to maximize the aggregate throughput of the network. At a minimum, the 2 MBaud band is specified in an RRCF. An example algorithm suitable for use by devices implementing a single band (Band1) on networks with additive white noise and impulse noise is now described. Other algorithms are possible which may better optimize the selected payload encoding based on the measured channel conditions. For each implementation, a table of average slicer mean squared error (ASMSE) required for each payload encoding (except PE=8) to achieve a packet error rate (PER) of 1e-3 is compiled. This table is defined as DOWN_LARQ. A second table is defined with a target PER of 1e-6. This table is defined as DOWN_NOLARQ. UP_LARQ is defined as DOWN_LARQ with all ASMSE values decreased by 2 dB and UP_NOLARQ is defined as DOWN_NOLARQ with all ASMSE values decreased by 2 dB.

[0178] The following steps describe how to select the new payload encoding desired for a particular channel, (new_pe), given the current payload encoding desired on that channel, (curr_pe), and a new frame is received on that channel.

• [0179] 1. Keep a history window of 16 HPNA V2 frames per channel. For each channel, compute the ASMSE over all frames in the history window that did not have a CRC error.
• [0180] 2. If in Compatibility mode, assess whether or not enough margin exists in the system to allow proper detection of compatibility frames on a per channel basis. If, for any given channel, such margin is determined not to exist, then set new_pe=8 for that channel. If such margin is determined to exist and curr_pe=8, set new_pe=1. If such margin is determined to exist and curr_pe 8, set new_pe=curr_pe. If new_pe=8 or curr_pe=8, then exit. Else:
• [0181] 3. If all the frames in the history window were received with a CRC error, set new_pe=1 and exit. Else:
• [0182] 4. If LARQ is in use on a channel, find the greatest payload encoding in the UP_LARQ table with an ASMSE greater than or equal to the ASMSE computed in step 1. If LARQ is not in use, use the UP_NOLARQ table. Define this payload encoding as new_up_pe
• [0183] 5. If LARQ is in use on a channel, find the greatest payload encoding in the DOWN_LARQ table with an ASMSE greater than or equal to the ASMSE computed in step 1. If LARQ is not in use, use the DOWN_NOLARQ table. Define this payload encoding as new_down_pe
• [0184] 6. If new_up_pe>curr_pe, set new_pe=new_up_pe and exit. Else:
• [0185] 7. If new_down_pe<curr_pe, set new_pe=new_down_pe and exit. Else:
• [0186] 8. If neither 6 nor 7 is satisfied, set new_pe=curr_pe.
  The offset between the up and down rate selection tables provides the algorithm with hysteresis to provide stability in selection of a payload encoding in the presence of minor variations in ASME. Due to this offset, conditions 6 and 7 cannot both be satisfied simultaneously. The combination of the 16 frame history window with the selection hysteresis prevents the rate selection algorithm from generating an excessive number of rate changes while remaining responsive to significant changes in the channel conditions. The selection algorithm for the value PE=8 in step 2 should also include hysteresis to avoid generating an excessive number of rate changes while remaining responsive to significant changes in the channel conditions. Periodically, but at a rate not to exceed once every 128 seconds (except as described below), a receiver may send a Rate Test Request frame to a sender to test if the channel can support a different band. The band encodings represent the encodings for which the receiver would like the sender to generate test frames. NumAddr is set to 0 in Rate Test Request frames. Rate Test Request frames are sent encoded at the current negotiated rate for the channel from the receiver to the sender. Support for Rate Test Request frames is only required in stations that implement additional bands beyond Band1. Stations that only implement Band1 need not provide a mechanism for generating Rate Test Request frames. Upon receipt of a Rate Test Reply frame, the receiver uses the demodulation statistics for this frame, and any previously received Rate Test Reply frames using this encoding, to make a decision as to the channel's capability to support the tested band encoding. If the decision is that the channel is not capable of supporting the tested band encoding, the receiver does not generate another Rate Test Request frame for at least 128 seconds. If the decision is that the channel is capable of supporting the tested band encoding, the receiver may repeat the test to collect more data, at a maximum rate of one RateTest Request frame every second, with a maximum of 16 additional tests. At this point, the receiver generates a Rate Change Request to the sender specifying the new band encoding. Support for Rate Test Reply frames is only required in stations that implement additional bands beyond Band1. Stations that only implement Band1 silently discard received Rate Test Reply frames. Whenever a transition to Compatibility mode occurs, the receiver PE is set to a value of 8 for all channels for a period of 60 seconds, to match the Sender nodes' behavior. Whenever a transition to V2 mode occurs, the receiver PE is set to a value of 1 for all channels.

[0187] The Link Integrity Function is now more fully described. In addition to the implementation aspects set forth hereinbelow, the concepts set forth in related U.S. patent application Ser. No. 09/619,553 entitled “A Method And Apparatus For Verifying Connectivity Among Nodes In A Communication Network”, which is incorporated herein by reference. The purpose of the Link Integrity Function is to provide a means for hardware and/or software to determine whether or not this station is able to receive frames from at least one other station on the network. In the absence of other traffic, a station periodically transmits a Link Integrity Control Frame (LICF) to the Broadcast MAC address, with the interval between such transmissions governed by the method described below.

[0188] When in Compatibility Mode, a V2 station transmits LICF's once per second as HPNA V1 frames. The standard frame format defined below is used (including the use of Broadcast (0xFFFFFFFFFFFF) for the destination MAC address). When in native V2 mode, all stations implement the following function to ensure that, with high probability, within any 1 second interval there is either (1) at least one LICF sent to the Broadcast MAC address from this station, or (2) at least one packet addressed to the Broadcast MAC address received from each of at least two other stations. Additionally, all stations send at least one LICF every 64 seconds. In V2 mode, a Link Packet is any frame received with a valid header FCS. In compatibility mode, a Link Packet is any V2 compatibility frame with valid header FCS or any V1 frame fragment with a valid AID header and a PCOM field. Each station maintains a free-running timer with a period of 1 second. There is no attempt to synchronize this timer between stations. The timer is not modified by any link state transitions or by the reception of any frames. This timer is the source of the timeout event used in the link integrity state table described below. Each station maintains a 6 bit FORCE SEND counter which is initialized to a random value between 30 and 63. This initialization value may be selected once at node startup and used for each re-initialization of the FORCE_SEND counter, or a new random value may be selected for each re-initialization of the FORCE_SEND counter. Each station has a register (SA1) that can be set from the SA of a received Link Packet. When in native V2 node, an LICF is sent with a priority corresponding to Link Layer priority 7. The PE for an LICF is determined by accessing the RRCF logical channel information for the broadcast channel. Each station sends a Link Integrity Control Frame (LICF) according to the state diagrams shown in FIGS. 43a and 43b. The state diagram depicted in FIG. 43a gives a pictorial view of the state transitions, with some minor loss of detail, including omission of events that do not cause state transitions (and have no associated actions), and the collapsing of multiple events into a single transition with a more complex description of the action. FIG. 43b provides a complete state table, with associated actions. The timeout event is the periodic expiration of a one second free-running timer. Initial State: DOWN, Force_Send initialized: 30<=Force_Send<=63. The FSM is a unified implementation which provides the required behavior in both native V2 and Compatibility compatibility modes. Link Integrity Status is indicated when in any state but DOWN. In a preferred embodiment all stations include a visible Link Status Indicator (LSI) (e.g. an LED) for indicating Link Integrity Status. FIG. 44 shows a Link Integrity Short Frame.

[0189] The Capability and Status Announcement aspect in accordance with the present invention is now described more fully. A mechanism is defined for network-wide negotiation, capability discovery and status announcement. It is based on periodic broadcast announcements, called Capabilities and Status Announcements (CSA) sent in CSA Control Frames (CSACFs). The defined status flags allow determination of the station's HPNA version, optional feature support, and link-layer priority usage, as well as communication of network configuration commands. The purpose of the protocol is to distribute to all stations the complete set of status flags in use on the network, so that stations can make operational decisions based on those flags with no further interaction. Stations use the CSA Control Frame as shown in FIG. 45 and the CSA Flag definitions as shown in FIG. 46. Stations send a CSA Control Frame once per minute or when a change in the station's current status requires the announcement of new (or deleted) flags. A station sending a CSA Control Frame announcing a status change sends a second copy of the most recent CSACF a short interval after the first, since it is always possible to lose a frame due to temporary changes in the channel, impulse noise, etc. The interval is randomly selected (not simply fixed), and chosen from the range 1 to 1000 milliseconds, inclusive. CSA Control Frames are sent with a priority corresponding to Link Layer priority 7. CSA Control Frames are always sent to the Broadcast address (0xFFFFFFFFFFFF). The PE for a CSA control frame is determined by accessing the RRCF logical channel information for the broadcast channel. A Request op-code is defined to allow a station to quickly gather complete information about all stations. Upon receiving a CSA control frame with the Request opcode, a station transmits a current CSA message after a delay of a short interval, using the same mechanism (and parameters) that delays the second copy of CSA announcements, described above. Referring to FIG. 45, the first three fields beyond the Ethernet header comprise the standard header for short format control frames. Referring to FIG. 46, flags are used for CSA_CurrentTxSet, CSA_OldestTxSet, and CSA_CurrentRXSet in Capabilities and Status Announcement control frames. Thirty-two bit-flags are supported for announcing status and configuration information. The flags are divided into three basic groups: mode selection flags including HPNA version information, supported options, and in-use TX link layer priority announcements. These flags are added to the global state as soon as announced, and removed when no longer announced by any station, either through explicit deletion or by timing them out. An in-use TX link layer priority will be announced for a period of one to two minutes after the last frame actually sent with the priority, until the aging mechanism causes it to be deleted from CurrentTxSet. The default set of status flags, used to initialize the NewTxSet (defined below), is defined to be the priorities 0 and 7, the station's HPNA version, and any supported options. The basic time interval used to age out non-persistent status information is one minute. Each station has a repeating timer set to this interval. The timers in different stations are not synchronized, and synchronization is avoided. The description below refers to the time between one expiration of this timer and the next as a “period”. The “current” period refers to the time since the most recent expiration of the timer. A CSA frame is sent at the end of each interval. FIGS. 47 and 48 depict variables and timers respectively. Each station maintains five basic sets of status and priority information, as shown in FIG. 49. In addition, three more composite sets are defined as the union of two or more of the basic sets, as shown in FIG. 50. The composite sets are kept in sync with their component basic sets.

[0190] Now turning to the Capabilities and Status Announcement Protocol operation, the CSA Protocol does not directly process transmit frames. When the LARQ protocol as discussed below is in use (Full Profile stations), CSA looks at the LL priority of the frame as it would normally be sent to the driver: 1. If the LL priority is not already in NewTxSet, it is added to NewTxSet. 2. If the LL priority was not already in NewTxSet and it is not in PreviousTxSet, then a new CSA control frame with the CSA_Opcode set to 0 (Announce) is sent, and the RetransmitTimer is started. If the timer was already running, it is then canceled and restarted. The current PHY priority mapping function for the driver is updated. The receiver may want to save a copy of some or all of the most recent CSA from each other station as a simple way of tracking other station's capabilities and status:

• [0191] 1. The status and options flags from the CSA_CurrentTxSet are recorded (optionally) in a table indexed by the SourceMacAddress. The options flags are used to select use of optional functions between pairs of stations that implement the same options.
• [0192] 2. If the CSA_Opcode in the frame is 1 (Request), then the RetransmitTimer is started. If the timer is already running it is recommended that it be left running, although this is not required and cancellation followed by restart is allowed.
• [0193] 3. If CSA_CurrentTxSet has a flag not already in NewRxSet, then the flag is added to NewRxSet, and it is determined whether this flag is not present in the PreviousRxSet. The corresponding boolean expressions are as follows:
  NewRxFlags=(CSA_CurrentTxSet & ˜NewRxSet
  NewRxSet|=NewRxFlags
  ReallyNewFlags=NewRxFlags & ˜(PreviousRxSet | CurrentRxSet)
• [0194] 4. CSA_OldestTxSet is compared with CSA_CurrentTxSet. If a flag has been deleted, and if that flag is also missing from CSA_CurrentRxSet, the flag is then deleted from NewRxSet, and PreviousRxSet. The corresponding boolean expressions are as follows:
  DeleteSet=(CSA_OldestTxSet & ˜CSA_CurrentTxSet) & ˜CSA_CurrentRxSet
  NewRxSet=NewRxSet & ˜DeleteSet
  PreviousRxSet=PreviousRxSet & ˜DeleteSet
• [0195] 5. If either ReallyNewFlags or DeleteSet are non-zero, then the network mode and priority mapping are updated, as necessary. When a CSP Timer timeout occurs, the various status sets are rolled over, the composite sets are re-computed, and a CSA is sent. The RetransmitTimer, if needed, is set.
  • [0196] 1. Move NewRxSet to PreviousRxSet.
  • [0197] 2. Set NewRxSet to 0 (empty set).
  • [0198] 3. Move PreviousTxSet to OldestTxSet.
  • [0199] 4. Move NewTxSet to PreviousTxSet.
  • [0200] 5. Set NewTxSet to the default set, consisting of this station's highest supported version, current configuration flags if any (normally none), currently supported options, and the default priority set {0,7}.
  • [0201] 6. Update CurrentTxSet, CurrentRxSet, and InuseSet (at least logically, an implementation need not keep separate copies of these values).
  • [0202] 7. Send a CSA frame with the CSA_Opcode set to 0 (Announce), including the updated flags.
  • [0203] 8. If CSA_CurrentTxSet and CSA_OldestTxSet in the CSA frame just sent were different, start the RetransmitTimer. If the timer was previously running, then cancel it and restart it.
  • [0204] 9. If one or more status flags have been deleted, then recompute the network operating mode and/or priority mapping function due to changed status flags. The mode/mapping recomputation is performed if DeleteSet, as computed below, is not empty(0):
    DeleteSet=OldestTxSet & ˜(PrevTxSet | CurrentRxSet)
    If the RetransmitTimer expires, a current CSA frame is sent for this station with the CSA_Opcode set to 0 (Announce). The timer is not restarted. The CSA protocol does not itself perform network mode selection, but simply provides a distribution mechanism for configuration flags.

[0205] There is a cost of slightly lower maximum attainable bandwidth associated with lower PHY priorities in the HPNA V2 MAC protocol if a default mapping scheme of link layer to PHY layer priorities is employed. This cost becomes especially burdensome when only lower-priority traffic is being carried on the network. Therefore, the CSA protocol includes procedures for remapping lower LL priorities to higher PHY layer priorities when no station on the network is sending traffic marked for those higher priorities. The choice of Physical Layer (PHY) priority for a given frame is based on its assigned Link Layer (LL) priority. The default mapping from LL priority to PHY priority is specified below. The LL priority of a frame at the sender is conveyed to the receiving station in order to allow proper recovery of link layer protocol at the receiver. This requires either a fixed, one-to-one, mapping of LL to PHY priorities, or some mechanism for carrying the LL priority within each frame. The LARQ protocol, defined below, carries the assigned LL priority from a sending station to a receiving station, providing the required mechanism, and thereby creating the opportunity to apply non-default LL to PHY priority mappings, which in turn, allows for higher maximum attainable bandwidth. A station may optionally use an 802.1q header to convey the LL priority. However, since support for 802.1q headers is optional, a station employing this method attempt to determine that all receivers of the frame support the use of 802.1q headers. Stations that do not support 802.1q headers are unlikely to properly receive frames that include an 802.1q header. When the assignment of a Physical layer priority to the frame occurs, any changes to the PHY priority remapping function due to the use of a new priority should already have been made. The driver uses the remapped PHY priority to transmit the frame (including placing this value in the Frame Control Header) unless the frame has no LARQ header, in which case the default LL-to-PHY mapping is used. The LL priority of received frames indicated up the protocol stack by the driver (before any reassignment due to a LARQ or 802.1q header) is determined using the default PHY-to-LL priority map, except that Minimal Profile stations indicate the priority of all frames as LL 0. The mechanism that guarantees correct LL priority for received frames is the restoration of LL priority from the LARQ (or optionally, 802.1q) header. LARQ header processing is always performed after the default LL priority has been assigned in the receive path. The IEEE 802.1p characteristics places the default (unassigned/best-effort) priority above both priorities 1 and 2, when an 8-level priority system is in use. Therefore, Link Layer priority 0 will be mapped above both LL 1 and LL 2 for default Physical Layer priority assignment. IEEE 802.1p designates priority level 7 for Network Control and priority level 6 for traffic requiring latency of <10 msec (typically characterized as voice-like traffic). However, on HPNA V2 networks, PHY priority level 7 is reserved for traffic requiring latency of <10 msec, and Network Control traffic is redirected to HPNA PHY priority level 6. So the default mapping for LL to PHY priorities includes the swapping of priorities 6 and 7. For transmitted frames, the set of LL priorities [0, 1, 2, 3, 4, 5, 6, 7] are by default mapped in order to the following set of PHY priorities [2, 0, 1, 3, 4, 5, 7, 6]. For received frames, PHY priorities [0,1,2,3,4,5,6,7] are, by default, mapped to LL priorities [1,2,0,3,4,5,7,6]. The PHY priority remapping is performed below LARQ in the protocol stack, and is not applied to the priority field in the LARQ (or optionally, 802.1q) header. PHY priority remapping is not performed on data frames (those that are not link control frames) unless a LARQ (or optionally, 802.1q) header has been added with the original LL priority. PHY priority remapping is performed on Link Control Frames. Without priority mapping, a station would pass the original LL priority into the driver, where that value would be used to select the associated PHY priority from the default map. With priority remapping, the default-assigned PHY priorities are increased to make use of higher PHY priorities that would otherwise be unused. The remapping function is simple. For each PHY priority P that corresponds to an in-use LL priority, the new priority P′ to use is that priority increased by the number of higher unused priorities. For example, if [1,3,4,7] are in use, then priority 4 will be increased by 2 to 6, since there are two higher unused priorities (5,6). The tables shown in FIGS. 51a and 51b contain a few more examples, including the default LL-to-PHY translation. The columns in the tables represent LL priorities before mapping. The left hand section shows some sets of in-use priorities, with the right-hand section showing the new PHY priority that the driver should use in each case. The cross-hatched entries show mappings that no sender is using. However, if there is any possibility of an implementation sending with an out-of-date mapping, or sending a priority that hasn't been included in the mapping, then it always uses the priority of the next lower valid mapping. Consider the following example. If the CurrentInuse, are [0,1,4,7], then the corresponding set of in-use PHY priorities is [2,0,4,6]. Then increase each by the number of missing higher priorities: 2->5, 0->4, 4->6 and 6->7. Just to be safe, the any unused PHY priorities are also remapped to the new value of the next lower in-use priority, giving: 1->4, 3->5, 5->6, 7->7. So the in-use LL priorities [0,1,4,7] result in transmitting PHY priorities [5,4,6,7]. A complete map for all the LL priorities adds the remaining remapped values for the default priorities corresponding to the unused LL priorities: LL[0,1,2,3,4,5,6,7] gives PHY[5,4,4,5,6,7,7].

[0206] Now turning to the Limited Automatic Repeat reQuest (LARQ) in more detail, the operation of which is set forth in pending U.S. patent application Ser. No. 09/316,541 entitled “Limited Automatic Repeat Request Protocol For Frame-Based Communications Channels” which is incorporated herein by reference. This is a protocol that reduces the effective error rate when frame errors occur. Its primary distinction from similar, sequence number-based protocols is that it does not guarantee reliable delivery of every frame, but instead conceals errors in the physical layer through fast retransmission of frames. The goal is to significantly enhance the usability of networks that may, at least occasionally, have frame error rates (FER) of 1 in 10⁻² or worse. Protocols such as TCP are known to perform poorly when FER gets high enough, and other applications, such as multi-media over streaming transport layers, are also susceptible to poor performance due to high FER conditions. The protocol provides a negative acknowledgment (NACK) mechanism for receivers to request the retransmission of frames that were missed or received with errors. There is no positive acknowledgment mechanism. There is no explicit connection setup or tear-down mechanism. A reminder mechanism gives receivers a second chance to detect missing frames when relatively long gaps (in time) occur between frames. LARQ functions as an adaptation layer between the Ethernet link layer (layer 2) and the IP network layer (layer 3). It is commonly implemented in the device driver. Stations implement LARQ per “LARQ channel”, where a LARQ Channel is identified by the tuple {source address, destination address, priority}. Stations may enable or disable LARQ processing on a channel dynamically, based on information about network frame error rates. However, in a preferred embodiment it is recommended that LARQ be left enabled at all times, since the per-packet processing overhead is quite low, and the complexity associated with enabling and disabling the protocol (including determination of appropriate parameters) probably outweighs any likely performance gains. Stations should implement LARQ, and if they do so, they use the specified control frame formats and use the recommended procedures defined below. Stations not adding LARQ (or optionally, 802.1q) headers do not remap PHY priorities, and treat all received traffic as “best effort”, that is, all traffic is assigned to Link Layer Priority 0. Stations may choose to add LARQ headers on transmitted frames with the LARQ_NORtx flag set to 1. This flag indicates that the station does not retransmit frames for this channel, but adding the LARQ header allows the station to use PHY priority remapping since the LL priority of successfully received frames will be restored from the LARQ header. All stations are capable of removing LARQ headers from received frames (de-encapsulating the original payloads). Furthermore, if the implementation supports multiple LL priorities in its receive protocol processing, then it restores the LL priority from the LARQ header, if one is present. If a station does not implement LARQ, then it drops LARQ control frames and it discards frames marked as retransmissions in the LARQ header. The text below uses the terms “insert” and “remove” when discussing LARQ headers. The formal definition of the LARQ frame format provides a Next Ethertype field that contains the original frame's Ethertype value. In practice, it will generally be the case that LARQ frames will be created by inserting the 8 octets starting with the Ethertype 0x886c into the original frame between the Ethernet header's source address and the original frame's Ethertype. The original frame's Ethertype becomes relabeled as the Next Ethertype field of the final frame. The LARQ header carries LLC priority across the network. The use of 802.1q headers is not required for this function, and V2 drivers are not required to support the use of 802.1q headers for conveying priority. FIGS. 52a, 52b, 52c, 52d, 52e and 52f.1-52f.2, depict the LARQ Reminder Control Frame, the LARQ NACK Control Frame, the LARQ Encapsulation Frame, the LARQ_Encapsulation Header Data, the LAEQ Control Header Data, and various terms and definitions, respectively. LARQ is defined for operation on simplex logical channels. A separate logical channel is defined for each combination of Ethernet destination address, Ethernet source address and link layer priority. There is no explicit channel setup procedure. A new channel is implicitly defined when a station chooses to send LARQ encapsulated frames for a new combination of DA, SA and link layer priority. The station that sends such frames (usually the owner of the SA, except in the case of a bridge masquerading as SA) is the sender for the channel. Each channel has a single sender. Any station that receives the frames and processes the LARQ headers is a receiver. There may be any number of receivers. Receivers operate independently. Variables and Parameters of the sender operation are set forth in FIG. 53. For a sender (new channel) implementation-dependent parameters are selected, if necessary, and an initial value for Send Sequence Number is selected. The link layer priority for the frame is determined in an implementation-dependent manner, for instance, by examining the 802.1p priority passed along with packets in newer NDIS implementations. The logical channel state information is accessed for the DA, SA and link layer priority of the frame. The Send Sequence Number, modulo 4096 (the size of the sequence number space) is incremented. The LARQ header is built with the new value of Send Sequence Number, and the Multiple Retransmission flag set to 0. The Priority field in the LARQ header is set to the Link Layer priority value specified for the frame. If no priority is specified, then the priority is set to 0. A LARQ header (short form control frame format with LARQ_hdr data) is inserted between the SA and the Ethertype/Length field of the original frame. The new frame is eight bytes longer than the original. A copy of the frame is saved and the frame is then sent. The reminder timer for the channel is restarted. A save timer is started for the sequence number. When no other resource limitations apply, a sending station normally saves a frame for Maximum Save Interval, which corresponds to Maximum Hold Interval used by LARQ receivers. For the send to process a NACK Control Frame the priority and Original Destination Address (NACK_DA) are read from the LARQ NACK header. The logical channel state information for the Sender channel is accessed, where the channel DA is the NACK_DA and the channel SA is the Ethernet DA from the Nack control frame. The NACK Count in the LARQ header indicates the number of sequence numbers requested for retransmission. The first indicated sequence number is the value Sequence Number in the NACK header, followed by the next (NACK Count−1) sequence numbers. For each indicated sequence number starting with the first:

• • [0207] If a copy of the original frame is no longer available, go to the next sequence number.
  • [0208] If the most recent retransmission of the frame is within Minimum Retransmission Interval of the current time, go to the next sequence number.
  • [0209] Prepare a copy of the original frame with its original LARQ header for retransmission.
  • [0210] Copy the value of the Multiple Retransmission Flag from the NACK header into the LARQ header of the frame to be retransmitted.
  • [0211] Set the LARQ_Rtx flag to 1.
  • [0212] Send the retransmitted frame.
    A retransmission is not sent if a received Nack control frame has an error. If the reminder timer expires, a Reminder control frame is created, with the Sequence Number set to the current value of Send Sequence Number for the channel. The priority for the Reminder control frame is the same as the priority for the channel. The frame is then sent and the reminder timer is not restarted for the channel. The save timer sets an upper bound on how long frames will be saved by a sender for possible retransmission. If set too long, host resources may be wasted saving frames that will never be retransmitted. This timer is conceptually implemented per sequence number. Any resources associated with the saved frame are released. A LARQ implementation requires careful attention to resource management. The resources include the buffers used for saving copies of data for retransmission, the buffers and other resources used to manage the re-ordering of frames to incorporate retransmissions, and the various timers used to govern proper behavior and efficient protocol operation. Saved copies of frames are kept for Maximum Save Interval (default is 150 ms), other considerations notwithstanding. The maximum number of saved frames for any channel, are a function of the maximum rate that new frames may be generated. Very slow devices might usefully save only a couple of frames for retransmission. A high-speed device serving video streams might save 100 or more frames for a single channel. Senders that save relatively few frames are more likely to receive NACK control frames for sequence numbers that can no longer be retransmitted. Such behavior is inefficient, but causes no other problems. The description of correct protocol for receiver operation channel variables and parameters are set forth in FIG. 54. The actual implementation may vary so long as the behavior remains unchanged. When a data frame with a LARQ header or a LARQ Reminder control frame is received with a new combination of DA, SA and link layer priority, the receiver initializes state information for a new channel. The primary piece of state information is the Current Sequence Number for the channel. Current Sequence Number is initialized to the sequence number immediately preceding that found in the LARQ header of the received frame. This assignment takes place prior to processing the received frame and results in the frame either appearing to be the next expected data frame, or the reminder for the next expected data frame. With regard to receiver LARQ data or reminder frame, the channel state information is looked up based on the Ethernet DA and SA in the received frame plus the Link Layer priority from the LARQ header. A new channel is setup if necessary. If the received sequence number of the received frame is out of sequence, the channel state may be reset. If the sequence number (before resetting) is old, and the Forget timer has expired, then the sequence space may be reset to the value of the received frame's sequence number. If the received sequence number is newer than the Current Sequence Number (after any reset of the sequence number space) then new sequence number processing steps are performed as set forth below, otherwise the old sequence number processing steps is performed. With regard to receiver LARQ frames with CRC or other errors, for best performance, implementations allow the LARQ protocol module to process errored frames, such as those with payload CRC errors. This will, in many cases, allow Nack indications to be sent more quickly since the receiver will not have to wait for the next frame to detect the loss. At the same time, it provides a second opportunity for detecting lost frames at the end of a sequence, when a later Reminder would be the only protection. If errored frames are used, they are used only to detect a very small of missing sequence numbers for an existing channel (one missed frame is recommended). In particular, if the frame appears to have a valid LARQ header, and the frame's source MAC address, destination MAC address, and LARQ header priority match an existing logical channel, and if the sequence number is (Current Sequence Number+1), then this frame is treated as a Reminder control frame for the purposes of processing. Note that Reminder control frames are always dropped after processing. In all other cases, the errored frame is dropped with no further processing. A new channel is not set up if the frame has an error. A retransmission is not sent if a Nack control frame has an error. A channel is not reset (for sequence numbering purposes) for an errored frame.

[0213] With regard to the receiver involving a new sequence number, if the frame has an error indicated by a lower layer driver, such as a CRC error, and the sequence number of the frame is anything other than (Current Sequence Number+1), then the frame is dropped with no further processing. Otherwise, the frame is processed as a Reminder control frame. If the difference between the new sequence number of the received frame and the oldest missing sequence number is greater than (Maximum Receive Limit−1), the following steps are repeated until the acceptable limit is reached.

• • [0214] Cancel the Nack retransmission timer and the lost frame timer for the oldest missing sequence number.
  • [0215] If there is a saved frame for the next sequence number, then deliver in-sequence frames to the next layer above until the next sequence number with a missing frame is reached (which may be the next expected sequence number for the channel, (Current Sequence Number+1)). The value from the Priority field from the LARQ header for each frame is delivered to the next layer along with each associated frame.
    If the sequence number is the next expected sequence number (Current Sequence Number+1) and the frame is a good data frame and there are no older missing sequence numbers, then the frame is sent up to the next layer. If the sequence number is newer than (Current Sequence Number+1), or is a reminder for (Current Sequence Number+1), then one or more Nack control frames is sent requesting retransmission of the missing frame (s). The destination address for the Nack is the source address of the received frame. The source address is this station's MAC address. The destination address of the received frame is placed in the original destination address field (NACK_DA) in the LARQ Nack control frame header. The Multiple Retransmission flag is set to 0. The [first] missing sequence number is placed in the sequence number field. The priority for the Reminder control frame is the same as the priority for the channel. If multiple Nack control frames are sent, the earliest sequence number is sent first. For each missing sequence number a Nack retransmission timer is started, set to expire at the current time plus Nack Retransmission Interval. For each missing sequence number, a lost frame timer is started, set to expire at the current time plus Maximum Hold Interval. If the frame is a good data frame and was not delivered to the next layer it is saved. If the frame is a reminder frame (or an errored data frame) it is dropped. The Current Sequence Number is then advanced to the sequence number in the received frame.

[0216] With regard to the receiver regarding an old sequence number, if the sequence number is the same or older than Current Sequence Number, then it will generate no control frames, although it may itself be dropped, held, or sent up to the next higher layer, possibly causing other held frames to be sent up as well. It may cause the cancellation of a Nack retransmission timer or lost frame timer associated with that sequence number. If the frame is not a good (e.g. bad CRC) data frame, or it's sequence number is older than the oldest missing frame, or it has already been received (this is a duplicate retransmission), or it is a Reminder frame, then the frame is dropped and further processing is skipped for this frame. The Nack retransmission timer and the lost frame timer is cancelled for the sequence number. If the sequence is not the oldest missing sequence number, then the frame is saved. If the sequence number is the oldest missing sequence number, then the frame is delivered up to the next higher layer. If there is a saved frame for the next sequence number, then in-sequence frames are delivered to the layer above until the next sequence number with a missing frame is reached (which may be the next expected sequence number for the channel). The value from the Priority field from the LARQ header for each frame is delivered to the next layer along with each associated frame.

[0217] With regard to the Receiver and Nack retransmission timer expiration, if a Nack retransmission timer expires, then another Nack control frame is sent for the associated sequence number. The priority for the Nack control frame is the same as the priority for the channel. Multiple sequence numbers may be nacked at the same time, if their timers expire at similar times. The Multiple Retransmission flag is set to 1 for Nack control frames sent as a result of retransmission timer expiration. While there is no explicit limit on the number of Nack control frames sent for a particular sequence number, it should be noted that the Nack timer is canceled if the frame is received or if the sequence number is declared lost.

[0218] With regard to the Receiver and lost frame timer expiration, the lost frame timer is implementation dependent. Its purpose is to set an upper bound on how long frames will be held before they are sent up when a frame is really lost. If set too long, network resources may be wasted on NACK control frames sent for frames that the sender on the channel will never retransmit. Further, higher layer transport timers may also become involved. The default value of 150 ms is strongly suggested as an upper bound. Upon expiration, the sequence number is declared lost, resulting in the cancellation of the Nack retransmission timer and the lost frame timer for the sequence number. If there is a saved frame for the next sequence number, then send up in-sequence frames until the next sequence number with a missing frame is reached (which may be the next expected sequence number for the channel). If the lost frame timers for multiple sequence numbers expire at the same time, then the timers are processed in sequence from oldest to newest. With regard to the Receiver, a forget timer is provided. The forget timer is an implementation dependent mechanism to allow a receiver to reset the sequence number space of a channel when a received sequence number is not the next expected (Current Sequence Number+1) and a relatively long interval has expired since the last frame received on the channel. Once expired, a receiver will accept any unusual sequence number as the next expected sequence number, allowing for undetected resets of other stations, disconnection from the network, etc. The definition of “unusual sequence number” is implementation dependent, but generally means any old sequence number or any new sequence number that is not close to the current sequence number, where “close” is 1 or some other small integer. A one second default is suggested.

[0219] With regard to Receiver resource management, in general, the receiver will want to set upper bounds on the number held frames per channel and the number of held frames across channels. The bounds may vary based on the priority of the channel. Timer intervals may vary based on factors such as the priority of the channel, or measured intervals for successful retransmissions. The description above suggests per-sequence number timers. This is for descriptive purposes only, and does not imply any implementation mechanism.

[0220] It should be noted that with regard to the Link Layer Protocol, there are certain vendor specific formats. Referring to FIGS. 55a and 55b respectively, two types allow vendor-specific extensions which may be reasonably handled by implementations that do not otherwise support them. The vendor specific short frame format set forth in FIG. 55a allows short control messages and encapsulation headers, while the vendor specific long frame format set forth in FIG. 55b allows other extensions that require longer messages.

[0221] With regard to Minimal Link Protocol Support Profile for HPNA V2 Link Protocols, the Minimal Link Protocol Support Profile for HPNA V2 Link Protocols allows less complex implementations of the HPNA V2 characteristics. While each of the component protocols serves an important function in the operation of the network, it is possible to implement minimal support for some of the more complex protocols that is compatible with fully functional implementations and does not detract from the overall performance of other stations. The shorter name, Minimal Profile, will be used in the following description. The alternative is full support of all the link protocols, called the Full Link Protocol Support Profile, or Full Profile for short. A Minimal Profile station can send only best effort data traffic, and treats all received traffic as best effort. A Minimal Profile station cannot advertise or use optional features that may be defined in the future. Due to the lack of support for LARQ, a Minimal Profile station may see dramatically reduced network throughput. A Minimal Profile station is able to handle all HPNA V2 Link Protocol frames, which are those marked the HPNA Ethertype 0x886c in the Ethernet header of the received frame. This includes dropping control frames with unknown subtypes and de-encapsulating data frames with unknown subtypes. The length field is used to locate the Next_Ethertype field in order to determine whether frames are control or data (encapsulated) frames. A Minimal Profile station implements the standard HPNA V2 Link Integrity function, including suppression of LICFs in native V2 mode. A Minimal Profile station implements the full set of rate-selection functions required for operation in both 1m2 mode and V2 mode using the 2 MBaud band. A Minimal Profile station properly handles frames with LARQ headers. It drops received control frames. It properly removes LARQ headers from data frames. In addition, if the LARQ header on a data frame has the retransmission flag set, then the frame is dropped in order to prevent duplicate and out-of-order frames. A Minimal Profile station adds LARQ headers to data frames being transmitted, setting the priority to 0 and the LARQ_NORTX flag to 1 in the LARQ headers. If LARQ headers are added, then the minimal station may use priority remapping based on priority status information received in CSA messages. Alternatively, if LARQ headers are added, the minimal station may use default priority mapping. A Minimal Profile station listens to CSA Control Frames and performs mode selection based on the configuration flags received (ConfigV1, ConfigCompatibility, ConfigV2). In particular, it uses the union of the CSA_CurrentTxSet and CSA_CurrentRxSet as the set of in-use flags. A Minimal Profile station does not send CSA Control Frames, and can therefore never advertise optional features, or use non-default priorities. In addition to control frames, a Minimal Profile station only sends normal data frames using the default priority assigned to best-effort/unspecified QOS. The Link Layer priority value for this QOS is 0. If the station is not adding LARQ headers, then data frames is sent using the default physical layer priority for link layer priority 0. (i.e. it uses physical layer priority 2.) If LARQ headers are being added as specified above, then the LARQ header priority field is set to 0, and the station again uses the default remapping function for link layer priorities to determine the actual Physical layer priority to use for Link Layer priority 0. (i.e. it uses physical layer priority 2.) A Minimal Profile station only indicates LL priority 0, if any priority is indicated, for received frames, regardless of the physical layer priority or priority value in a LARQ header. In support of Minimal Profile stations, a minor addition is also needed for the CSA characteristics for Full Profile stations. Any station that is not sending CSA frames, but which is determined to be a V2 station as a result of traffic received from that station, is treated as if it advertised a default set of status flags, including no supported options, only LL priority 0 in use, and highest supported station type V2.

Homenetworking Further Implementation Details

[0222] Certain further aspects of the embodiments of the present invention as described in more detail below. These aspects include: carrier sense for severely distorted networks, collision detector for severly distorted networks, scrambler and descrambler initialization circuits, gain estimation circuit for burst modem, rate negotiation and rate selection algorithms, Split Winding Transformer for Modem Transceiver S/N Optimization, and Transmit Off Switch for Modem Receiver Noise Reduction

[0223] Carrier Sense for Severely Distorted Networks

[0224] Now turning to the carrier sense function in more detail, a preferred carrier sensing embodiment which is particularly useful for severely-distorted networks is described. On a typical Ethernet bus, all taps are terminated in the characteristic impedance of the line to minimize reflected signal power. Because reflections are insignificant and the signal-to-noise ratio (SNR) at each receiver is very high, a simple carrier sense technique (e.g. level detector with a fixed threshold) may be used to determine when the medium is busy. In residential networking over pre-installed wiring (e.g. phone wiring, power wiring), attenuation may be high due to wall jacks and unused wire segments that are not terminated with the characteristic impedance of the wire. There will also be severe reflections for the same reason. The receiver SNRs may be low (10 dB or lower in some cases). In addition, the problem is complicated by the fact that every path between two stations on the network has a different channel impulse response. On one path, two stations may communicate at a high rate (e.g. 8 bits/symbol), while all other paths only support 2 bits/symbol. The implication of this example is that the demodulator may not be used as the method of carrier sense in such a network, as all stations on the network are able to delineate frames, even those whose payloads may not be demodulated due to insufficient SNR. Beyond even these complications, there is impulse noise, which may result in false carrier detection with certain types of detectors. In accordance with the present invention a detector is provided for precisely determining the start of a frame (within 1 microsecond) in a severely-impaired CSMA/CD network. In addition, this detector determines the start of a frame with sufficient precision to generate a channel model with a small number of adjustable coefficients for generating decision-feedback equalizer weights. In accordnace with the present invention, a preamble format is provided in which M identical copies of the same k*n-symbol quadrature phase-shift keying (QPSK) sequence are transmitted sequentially. This k*n-symbol sequence is spectrally white over an k*n-symbol span (has a single non-zero circular autocorrelation value). Further, the k*n-symbol QPSK sequence consists of k sequentially-transmitted copies of an n-symbol subsequence that is spectrally white over an n-symbol span. Further, a detector for precisely determining the end of a frame (within a 4-microsecond window) in a severely-impaired CSMA/CD network is provided. In accordance with the present invention an n-symbol sequence that is spectrally white over an n-symbol span that delimits the end of a burst and enables this detector is provided. By keeping the end-of-frame detection uncertainty low, the efficiency of the network is increased.

[0225] The carrier sensor, for example carrier sense 1100 of FIG. 30, consists of two components: one which detects the start of frame and one which detects the end of frame. The carrier sense circuit takes an input from the medium access controller (MAC), which forces reset. The decision logic depends on the state information, per the table set forth in FIG. 56.

[0226] With regard to the start-of-preamble detector, which is described below in conjunction with FIG. 59, complex samples at L times the nominal transmitted symbol rate are the input to this detector. Typically, L will be 2, 4, 8, or 16. The complex samples are generated by a filter which performs nearly a Hilbert transform on its input. In addition, the input samples are band-pass and notch filtered to attenuate noise and interference while minimally reducing the channel capacity. The circuit embodiment in accordance with the present invention consists of a special filter whose coefficients are matched to the preamble symbol sequence and a detector which performs near-optimal detection of the preamble in the presence of additive white Gaussian noise. The filter/detector is not a true matched filter detector in the textbook sense, because: (1) the filter is not matched to the input sample sequence but, rather, the input symbol sequence, and (2) the filter includes additional delay elements to minimize the probability of a false trigger immediately before the correct start of burst position. There are two possibilities for start of preamble detectors: a simple, low-delay detector and a more complex, robust detector. Both are included in the description of the embodiments below. The circuit in accordance with the present invention is designed to operate in networks in which the insertion loss between any two points is less than 38 dB. Since the carrier sense function must operate before the gain can be adjusted, the minimum SNR at which the system must operate is calculated as:
SNR>PSNR(10-bit ADC)−PAR(4-QAM preamble)−L_insert
PSNR is the peak signal to noise+distortion for the analog-to-digital converter (ADC), which is about 60 dB. The worst-case PAR for the preamble is about 10 dB. Note that if the line noise floor is greater than the ADC noise+distortion floor, the maximum tolerated insertion loss will be less than 38 dB. So, the start of preamble detection function must operate reliably down to about 12 dB SNR. Reliable operation is defined as no more than one missed detection in 10⁵ actual frames and no more than one false alarm in 10 seconds in additive white Gaussian noise (no valid frames). Missed detection performance should improve with increasing SNR. Reliable detection tends to require longer filters and more averaging. Unfortunately, increasing reliability has the side-effect of increasing the medium access slot times. Because of the need to minimize the slot time, the start of preamble detector may consist of two matched filter detectors. One is a “first-pass”, short matched filter detector which is used for determining slot boundaries (to minimize the slot duration). The second uses a matched filter which spans one entire copy of the training preamble, for reliable detection. The first-pass detector produces a “transmit hold-off” signal, which is used only to inhibit transmission until the second-pass (longer filter) detector makes a more reliable determination of medium state. The second-pass start of preamble detector uses a matched filter with averaging and an average power estimate to determine the start of frame within +/−1-microsecond intervals. Therefore, in accordance with the present invention, both a circuit in which the low-delay and robust detectors are used in conjunction and also a circuit in which only the robust detector is used is provided.

[0227] With regard to the low-delay detector, it uses a filter matched to the first n symbols of the preamble. The filter coefficients are the first n symbols of the preamble in reverse order, complex-conjugated, then interspersed with L zeros per symbol. If the first n symbols are [s₀, s₁, . . . s_(n−1|] then the filter coefficients are [s_(n−1)*, 0, 0, 0, s_(n−2)*, 0, 0, 0, . . . s₀*, 0, 0, 0], when L=4. “*” indicates complex conjugation of the symbol value. The bit widths, shown in FIG. 57 as r, r+1, q, etc., are merely examples in one particular embodiment, and the invention is not limited to any particular datapath widths. “j” is the sample (time) index in FIG. 57. Note that, because the preamble consists of only QPSK symbols, no multiplications (only additions and subtractions) are required. The output of the MA block is computed as max (x_i, x_q)+½*min(x_i, x_q), where x_i is the in-phase component of the complex sample and x_q is the quadrature component, with rounding. The output of the matched filter in this one embodiment saturates at r+1 bits twos-complement, but other outputs are possible within the scope of this invention. AVG may be either a simple L*n-sample moving average or a one-pole smoothing filter with alpha=1/(L*n).

[0228] Referring briefly to FIG. 58, which is described in more detail below, a circuit block diagram is shown giving an example of an averaging circuit for L*n=16 samples. The (roughly) equivalent moving average would sum the 16 samples, then shift the result right by 4 bits with rounding. Therefore, in accordance with the present invention a circuit is provided that enables rapid detection of the start of a burst using the first n symbols of the preamble and no multiplication operations. This allows delineation of medium access slot boundaries.

[0229] With regard to the robust detector, it uses a filter matched to the first k*n symbols of the preamble, described above. The filter coefficients are the first k*n symbols of the preamble in reverse order, complex-conjugated, then interspersed with L zeros per symbol. If the first k*n symbols are [s₀, s₁, . . . s_(k*n−1)], then the filter coefficients are [s_(k*n−1)*, 0, 0, 0, s_(k*n−2)*, 0, 0, 0, . . . s₀*, 0, 0, 0], when L=4. “*” indicates complex conjugation of the symbol value. The bit widths, shown in the FIG. 59 as r, r+1, q, etc., are merely examples in one particular embodiment, and the invention is not limited to any particular datapath widths. Similarly, the thresholds depicted in the figure are considered “good values”, but are not a requirement of the invention. The thresholds are adjustable. The delays between the delays between the h_match path and the power estimation path, D^v1 and D^v2, are used to account for the differences in group delay between the paths. If these delays are not included, the probability of a false trigger slightly before the beginning of a frame may be increased. Note that, because the preamble consists of only QPSK symbols, no multiplications (only additions and subtractions) are required. The output of the MA block is computed as max(x_i, x_q)+½*min(x_i, x_q), where x_i is the in-phase component of the complex sample and x_q is the quadrature component, with rounding. The output of the matched filter in this one embodiment saturates at r−1 bits twos-complement, but other outputs are possible within the scope of this invention. AVG1 may be either a simple L*k*n-sample moving average or a one-pole smoothing filter with alpha=1/(L*k*n) and a variable output scaler. AVG2 may either be a L*n-sample moving average or a one-pole smoothing filter with alpha=1/(L*n) and a variable output scaler. Note again that the “matched filter” in this detector is not a true “matched filter”, since it is not matched to the expected input sample sequence: there is no a priori knowledge of the wire network's impulse response. Therefore, in accordance with the present invention a circuit is provided that enables very robust detection of the start of a burst using the first k*n symbols of the preamble and no multiplication operations. This enables efficient channel estimation (fewer coefficients), reliable detection of the start of a burst in SNRs as low as 3 dB, and accurate automatic gain control.

[0230] Referring back to FIG. 59, specific operational aspects of the start of frame detection are described in more detail. One aspect is the start of frame detection. In upper portion 3010 the first stages of carrier sense/start of preamble detection is shown. In lower portion 3012 the remaining stages are shown. Accordingly, the carrier sense processing starts at the upper left portion of FIG. 59 and ends at the lower right portion of FIG. 59. Input 3014 has r bits, which in a preferred embodiment is at 8 Msamples/sec. Matching filter/correlator 3016 receives the r bits, and filters the input using filter coefficients which are a time-reversed sequence copy of the preamble sequence. The output of filter 3016 is provided to magnitude approximator 3018 and squaring function 3020. Magnitude approximator 3018 provides a real output for which on one squaring operation is needeed, avoiding the need for a multiplier function. The output of squaring function 3020 is input to low-pass filter 3022. Low pass filter 3022 smoothes the input thereto and provides output Z_j. At input 3014 r is also fed into an energy detection computation where magnitude approximation 3024 is performed, then a squaring operation 3026, then a longer duration low-pass filtering 3028, and then performing a low-pass filtering operation 3030 comparable to that of low-pass filter 3022, providing an output zh₃. Z₃ is then put through logarithm function 3032 to allow measuring of ratios avoiding division operations. Z_hj is similarly put through logarithm function 3034. The output from logarithm function 3032. Two tests are performed during the carrier sense computation at compare functions 3036 and 3038. Where inputs A and B respectively are compared based upon a threshold, e.g., 9 dB threshold input into compare function 3036 and 3 dB threshold input into compare function 3038. In other words a calculation is performed to determine if A−B is >than the threshold. Delays 3040, 3042, 3044 are provided between the logarithm functions and the compare functions. In essence, with regard to the Z_j processing of portion 3012, the smoothed low-pass filtered output of the matched filter is compared with a delayed copy of itself, as provided by delay 3040. In addition delay function 3044 is applied to the output of logarithm function 3032 providing a slightly delayed input to compare function 3038. With regard to the zhj processing, delay function 3042 and maximizing function 3046 is applied to the output of logarithm function 3034 to provide a sampled maximum to avoid getting a false trigger. Therefore compare function 3038 compares that smoothed low-pass filtered output is greater than the Z_hj output of the energy detector. The output of comparator functions 3036 and 3038 is then provided to AND function 3040, a match if both inputs are true and a no match if one is not true.

[0231] Referring now to FIG. 58 in more detail, low-pass filtering function 3022 (and its counterparter function 3030) is depicted in more detail and is considered an implementation of an Infinite Impulse Response (IIR) filter. Left by 4 bit shift 3042 is applied to input signals N, the output of which is applied to adder 3044. The output of adder 3044 is provided to round to the nearest integer function 3046 which provides a signal which is sent to right by 4 bit shift 3048, then to one clock delay 3050. The output of one clock delay 3050 is provided to left by 4 bit shift 3052, the output of which is applied to subtractor 3054 along with an output of delay 3050. The value of the recursive path is then set thereby. Rounder 3056 takes the N+8 signal from adder 3044 and provides its output to Right by 8 bit shift 3058 to provide N bits output. On the other hand filter 3028 is a moving average filter which takes N inputs sums them together and divides the sum by N.

[0232] With regard to the end-of-frame detector, end of frame detection is complicated by the need to avoid prematurely detecting the end of a burst and the possibibility that there can be: (1) a long run of innermost constellation points in a large transmitted constellation—in this case, the receiver attempting to determine the end of frame may be unable to demodulate the signal because the SNR is not sufficient (the innermost points are lost in noise); and (2) a long run of the same, or nearly the same, constellation point—in this case, a channel with a null in exactly the wrong place can substantially attenuate this symbol sequence. The, end of frame detector uses a short filter matched to the last n symbols of the frame (the end-of-frame delimiter), above. Again, the input is complex at L times the nominal transmitted symbol rate. The matched filter in this case consists of L*n coefficients, which are the n “end-of-frame” marker symbols, complex-conjugated, time-reversed, and upsampled by L with zero-filling. The input is applied to the matched filter, and the output of the filter is passed into a magnitude approximation circuit. The output of the magnitude approximation circuit is squared and applied to the same one-pole low-pass filter or moving average filter described in the sections above. The averaged output is then applied to the same approximate 10*log10(.) function. This output can be called z(j), where j is the sample index. The first criterion for detecting the end of a frame is:
z(j)−z(j−L*p)<thd_off
A reasonable value for thd_off in one embodiment is 8 dB. A reasonable value for L*p in microseconds is 12. Therefore, in accordance with the present invention other values of thd_off and L*p within scope the scope of the present invention. If this test passes, the z(j−L*p) value is stored, and the-same test is applied on the L*k*n subsequent samples, replacing z(j−L*p) with this stored value. If k1 of these tests pass, the end of frame is declared. The end-of-carrier detector described herein is capable of determining the end of a received frame within a +/−2 microseconds interval, and can be considered as a circuit that performs two tests in order. Therefore, in accordance with the present invention a circuit is provided that enables rapid detection of the end of carrier using the last n symbols of the burst and no multiplication operations. This enables efficient use of the medium by keeping medium access slots short.

[0233] Referring to FIG. 60, with regard to the first test of the end-of-carrier detector, it uses an n-symbol matched filter, almost exactly as the first-pass carrier sense. However, note that, while the coefficients are identical, the delay between compared matched filter outputs is not 2*n−1 symbols, but p>(2*n−1) symbols. This is required, as the channel postcursor ISI typically far exceeds the duration of the precursor ISI on phoneline, powerline, or wireless networks. Again, as before, the datapath widths are given strictly to show one particular embodiment. The exact values in the diagram do not limit the scope of the current invention. AVG is either an L*n-sample moving average or a one-pole filter with alpha =1/(L*n) and a variable output scaler.

[0234] With regard to the second test, when the output of the first test goes active, the delayed value r_j−L*p is stored. On the L*k*n subsequent samples, the stored value is compared with the the non-delayed r₃ value. If the thd_off threshold is exceeded on k1 of these samples, the end of the frame is declared. One particular embodiment requires that the thd_off threshold be exceeded on all L*k*n samples. The state diagram shown in FIG. 61 depicts such a case.

[0235] In accordance with the present invention, a frame may not be terminated until a specified point after the start of the frame. In one embodiment, this point is the end of the Ethertype field of an encapsulated Ethernet frame. The present invention includes a timer to ensure that the device does not remain in the BUSY state indefinitely. The present invention further includes the ability to detect a third-party collision any time the time between the second-pass start-of-preamble detection and the end-of-frame detection is less than a specified duration threshold. A “third-party collision” is one in which the detecting station was not a transmitter. An embodiment of the invention optionally can include a dB function implemented with two 1-entry look-up tables, a coarse 10*log10(.) table and a fine 10*log10(.) table. The tables include unsigned values with m0 fractional bits. An example embodiment could be described by the tables set forth in FIGS. 62a and 62b, showing coarse dB table values and fine dB table values, respectively. The algorithm is:

• [0236] 1. x=max(x, 2)
• [0237] 2. Find the most significant non-zero bit in the input, x. Call the position of this bit (0 . . . 31) b.
• [0238] 3. d₁=coarse_tbl[b]
• [0239] 4. if b>3, k=(x−2^b)<<(b−5), else k=(x−2^b)>(5−b).
• [0240] 5. d₂=fine_tbl[k]
• [0241] 6. output=d₁+d₂
  The output in the example embodiment yields 96 dB of dynamic range with up to 0.25 dB resolution.

[0242] With regard-to the end of carrier detector, there are two aspects which will be described in more detail referring again to FIGS. 60 and 61. In FIG. 60 it should be noted that the path from r input to match/no match output is similar to the correlator path in FIG. 59 without the energy detection path. Since at the end of the preamble there are four contiguous symbols of the training preamble. Therefore, the matched filter is run against the entire frame looking for peaks. Towards the end of the frame there will be a small spike and dropoff. The flow in FIG. 60 provides a tentative match/no match decision, similar to that of the correlator path of FIG. 59. The decision is tentative to avoid premature truncation of the frame. A state machine, as depicted in FIG. 61, is provided taking in the tentative match/no match decision as shown in FIG. 60. As described above, Test 1 is match/no match. If out of Test 1 the decision is yes, the state proceeds to Test 2, 0. When going from Test 1 to Test 2, 0 the last value of peak detected is latched. Then every subsequent sample is compared against the latched value. If after a number of comparisons it is determined that the signal is greater than the threshold value, the end of frame is determined to be detected.

[0243] Referring again to FIGS. 62a and 62b, the logarithm functions 3032 and 3034 as described above can be implemented using the index and values set forth in FIGS. 62a and 62b.

[0244] Collision Detector for Severely-Distorted Networks

[0245] The collision detector design for networking on phone lines is complicated by the need to detect collisions even when the line input impedance changes on the time scale of a transmitted frame. Line input impedance changes occur with telephone hook-switch transitions, keying, and addition/deletion of devices from the network. In addition, since the hybrid will not exactly match the line input impedance, a substantial amount of hybrid leakage (echo) will be present; so, it is not possible to simply use carrier detection as a criterion for a collision when transmitting. Because the noise floor may vary substantially over time, due to crosstalk and impulse noise, and because a colliding signal may be attenuated by as much as 38 dB more than the echo signal, an estimate of the noise floor is needed for optimal detection of colliding signals. This noise estimate is made either directly before the transmitted frame or during the preamble. The claimed invention makes this estimate during the preamble. The collision detector circuit in accordance with the present invention includes three functional aspects: (1) a channel estimator, the concepts of which are described in co-pending application Ser. No. 09/585,774, entitled “Method and Apparatus for Efficient Determination of Channel Estimate and Baud Frequency Offset Estimate” and which is incorporated by reference herein; (2) a noise floor estimator; and (3) a unique field match (either SRC or SI+SRC or SRC+DST or SI+SRC+DST).

[0246] In accordance with the present invention a method and apparatus is provided for generating a preamble sequence to facilitate channel estimation and noise floor estimation. A sequence b is defined as the 16 symbols set forth below. $b=\left[\begin{array}{c}{b}_0\\ b_1\\ ⋮\\ b_{15}\end{array}\right]=\left[\begin{array}{c}1+i\\ -1-i\\ -1-i\\ -1-i\\ 1+i\\ 1-i\\ 1+i\\ -1+i\\ 1+i\\ 1+i\\ -1-i\\ 1+i\\ 1+i\\ -1+i\\ 1+i\\ 1-i\end{array}\right]$
This sequence has an important property that $\frac{1}{32}\sum _{k=0}^{15}{b}_k{b}_{\mathrm{mod}\left(k+n,16\right)}^{*}=\{\begin{array}{c}1,n=0\\ 0,n\ne 0\end{array}$
All symbols in this sequence belong to a 4-QAM (or QPSK) constellation. The preamble sequence is generated as four sequential copies of the 16-symbol sequence b defined above. Channel estimation for the purpose of detecting collisions is performed on either the first, second and third copies of the preamble and/or on the second, third, and fourth copies of the preamble. Throughout the following section on channel estimation, the copies used in one estimate are referred to as the first, second, and third copies, respectively. The characterization signal is the part of the received signal used for channel estimation. This signal is defined as the second and third or third and fourth copies of preamble in the received signal. The start of this signal at the receiver input interface is found by simply waiting a fixed time interval after the start of transmission (to account for fixed propagation delays). Referring to FIGS. 63a-63c, the quantities described above are shown, assuming that the characterization signal is the third and fourth copies of the preamble sequence.

[0247] Further, in accordance with the present invention, a method for computing a complex channel estimate sampled at four times the symbol frequency of the preamble signal is provided. The complex input signal is also sampled at four times the symbol frequency of the preamble signal. Let B represent the matrix of preamble symbol values, upsampled by four and zero-filled: $B^H=\left[\begin{array}{ccccccccccccc}{b}_0^{*}& 0& 0& 0& b_1^{*}& 0& 0& 0& \cdots & b_{15}^{*}& 0& 0& 0\\ 0& b_0^{*}& 0& 0& 0& b_1^{*}& 0& 0& \cdots & 0& b_{15}^{*}& 0& 0\\ 0& 0& b_0^{*}& 0& 0& 0& b_1^{*}& 0& \cdots & 0& 0& b_{15}^{*}& 0\\ 0& 0& 0& b_0^{*}& 0& 0& 0& b_1^{*}& \cdots & 0& 0& 0& b_{15}^{*}\\ b_{15}^{*}& 0& 0& 0& b_0^{*}& 0& 0& 0& \cdots & b_{14}^{*}& 0& 0& 0\\ 0& b_{15}^{*}& 0& 0& 0& b_0^{*}& 0& 0& \cdots & 0& b_{14}^{*}& 0& 0\\ 0& 0& b_{15}^{*}& 0& 0& 0& b_0^{*}& 0& \cdots & 0& 0& b_{14}^{*}& 0\\ 0& 0& 0& b_{15}^{*}& 0& 0& 0& b_0^{*}& \cdots & 0& 0& 0& b_{14}^{*}\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋰& ⋮& ⋮& ⋮& ⋮\\ b_1^{*}& 0& 0& 0& b_2^{*}& 0& 0& 0& \cdots & b_0^{*}& 0& 0& 0\\ 0& b_1^{*}& 0& 0& 0& b_2^{*}& 0& 0& \cdots & 0& b_0^{*}& 0& 0\\ 0& 0& b_1^{*}& 0& 0& 0& b_2^{*}& 0& \cdots & 0& 0& b_0^{*}& 0\\ 0& 0& 0& b_1^{*}& 0& 0& 0& b_2^{*}& \cdots & 0& 0& 0& b_0^{*}\end{array}\right]$
here ( )^H represents the Hermitian transpose or conjugate transpose and where “*” indicates complex conjugation of a scalar element. Let y₁, y₂, and y be column vectors of received samples in the characterization signal: $\begin{array}{ccc}{y}_1=\left[\begin{array}{c}{y}_o\\ y_1\\ ⋮\\ y_{62}\\ y_{63}\end{array}\right]& y_2=\left[\begin{array}{c}{y}_{64}\\ y_{65}\\ ⋮\\ y_{126}\\ y_{127}\end{array}\right]& y=\left[\begin{array}{c}{y}_1\\ y_2\end{array}\right]\end{array}$
Let h be a complex 64-sample channel, sampled at 4 times the symbol rate. $h=\left[\begin{array}{c}{h}_o\\ h_1\\ ⋮\\ h_{62}\\ h_{63}\end{array}\right]$
Let A be a matrix defined as $A=\left[\begin{array}{c}B\\ B\end{array}\right]$
The received signal y is given by y=Ah+n, where n is a vector of random noise values. The goal is to find a channel estimate h which minimizes
e²=∥Aĥ−y∥²¹
It can be shown (reference Haykin) that the optimal channel estimate is given by
ĥ=(A^HA)⁻¹A^Hy
The preamble sequence defined above was designed to have the important property
A^HA=64I₆₄
where I_N represents an N by N identity matrix. Hence, $\begin{array}{c}\hat{h}=\frac{1}{64}{A}^{H}y\\ =\frac{1}{64}[\begin{array}{cc}{B}^H& B^H]\end{array}\\ =\frac{1}{64}\begin{array}{cc}[B^H& B^H]\end{array}\left[\begin{array}{c}{y}_1\\ y_2\end{array}\right]\\ =\frac{1}{64}{B}^H\left(y_1+y_2\right)\end{array}$ $[\begin{array}{c}{h}_0\\ h_1\\ h_2\\ h_3\\ h_4\\ h_5\\ h_6\\ h_7\\ ⋮\\ h_{60}\\ h_{61}\\ h_{62}\\ h_{63}\end{array}]=\frac{1}{32}[\begin{array}{ccccccccccccc}{b}_0^{*}& 0& 0& 0& b_1^{*}& 0& 0& 0& \cdots & b_{15}^{*}& 0& 0& 0\\ 0& b_0^{*}& 0& 0& 0& b_1^{*}& 0& 0& \cdots & 0& b_{15}^{*}& 0& 0\\ 0& 0& b_0^{*}& 0& 0& 0& b_1^{*}& 0& \cdots & 0& 0& b_{15}^{*}& 0\\ 0& 0& 0& b_0^{*}& 0& 0& 0& b_1^{*}& \cdots & 0& 0& 0& b_{15}^{*}\\ b_{15}^{*}& 0& 0& 0& b_0^{*}& 0& 0& 0& \cdots & b_{14}^{*}& 0& 0& 0\\ 0& b_{15}^{*}& 0& 0& 0& b_0^{*}& 0& 0& \cdots & 0& b_{14}^{*}& 0& 0\\ 0& 0& b_{15}^{*}& 0& 0& 0& b_0^{*}& 0& \cdots & 0& 0& b_{14}^{*}& 0\\ 0& 0& 0& b_{15}^{*}& 0& 0& 0& b_0^{*}& \cdots & 0& 0& 0& b_{14}^{*}\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋰& ⋮& ⋮& ⋮& ⋮\\ b_1^{*}& 0& 0& 0& b_2^{*}& 0& 0& 0& \cdots & b_0^{*}& 0& 0& 0\\ 0& b_1^{*}& 0& 0& 0& b_2^{*}& 0& 0& \cdots & 0& b_0^{*}& 0& 0\\ 0& 0& b_1^{*}& 0& 0& 0& b_2^{*}& 0& \cdots & 0& 0& b_0^{*}& 0\\ 0& 0& 0& b_1^{*}& 0& 0& 0& b_2^{*}& \cdots & 0& 0& 0& b_0^{*}\end{array}]·[\begin{array}{c}{y}_0+y_{64}\\ y_1+y_{65}\\ y_2+y_{66}\\ y_3+y_{67}\\ y_4+y_{68}\\ y_5+y_{69}\\ y_6+y_{70}\\ y_7+y_{71}\\ ⋮\\ y_{60}+y_{124}\\ y_{61}+y_{125}\\ y_{62}+y_{126}\\ y_{63}+y_{127}\end{array}]$

[0248] The noise floor estimate is computed over the 2^nd and 3^rd copies of the training preamble and, also, over the 3^rd and 4^th copies of the training preamble. Two noise estimates are computed because a colliding signal that is received more than 16 symbols before or after the start of transmission will corrupt either the second or the last copy of the training preamble. If, for example, only the 3^rd and 4^th copies of the training preamble were used, a colliding signal received more than 16 symbols after the start of a transmission could result in an over-estimated noise floor and a possible failure to detect the collision. The noise vector is simply the difference between the received sample sequence (over some part of the training preamble) minus the estimate of what should be received: $\begin{array}{c}{e}_1=\left(2·L_{\mathrm{trn}}\right)·\left(y_1-{\hat{y}}_1\right)\\ =\left(2·L_{\mathrm{trn}}\right)·\left(y_1-A·{\hat{h}}_1\right)\\ =\left(2·L_{\mathrm{trn}}\right)·\left(y_1-A·{\left(A^H·A\right)}^{-1}·A^H·y_1\right)\\ =\left(\left(2·L_{\mathrm{trn}}\right)·I_{128}-A·A^H\right)·y_1\\ e_2=\left(2·L_{\mathrm{trn}}\right)·\left(y_2-{\hat{y}}_2\right)\\ =\left(2·L_{\mathrm{trn}}\right)·\left(y_2-A·{\hat{h}}_2\right)\\ =\left(2·L_{\mathrm{trn}}\right)·\left(y_2-A·{\left(A^H·A\right)}^{-1}·A^H·y_2\right)\\ =\left(\left(2·L_{\mathrm{trn}}\right)·I_{128}-A·A^H\right)·y_2\end{array}$ $\mathrm{where}\text{:}$ $A=\left[\begin{array}{ccccccccccccc}{s}_0^{*}& 0& 0& 0& s_{15}^{*}& 0& 0& 0& \cdots & s_1^{*}& 0& 0& 0\\ 0& s_0^{*}& 0& 0& 0& s_{14}^{*}& 0& 0& \cdots & 0& s_1^{*}& 0& 0\\ 0& 0& s_0^{*}& 0& 0& 0& s_{14}^{*}& 0& \cdots & 0& 0& s_1^{*}& 0\\ 0& 0& 0& s_0^{*}& 0& 0& 0& s_{14}^{*}& \cdots & 0& 0& 0& s_1^{*}\\ s_1^{*}& 0& 0& 0& s_0^{*}& 0& 0& 0& \cdots & s_2^{*}& 0& 0& 0\\ 0& s_1^{*}& 0& 0& 0& s_0^{*}& 0& 0& \cdots & 0& s_2^{*}& 0& 0\\ 0& 0& s_1^{*}& 0& 0& 0& s_0^{*}& 0& \cdots & 0& 0& s_2^{*}& 0\\ 0& 0& 0& s_1^{*}& 0& 0& 0& s_0^{*}& \cdots & 0& 0& 0& s_2^{*}\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋰& ⋮& ⋮& ⋮& ⋮\\ s_{15}^{*}& 0& 0& 0& s_{14}^{*}& 0& 0& 0& \cdots & s_0^{*}& 0& 0& 0\\ 0& s_{15}^{*}& 0& 0& 0& s_{14}^{*}& 0& 0& \cdots & 0& s_0^{*}& 0& 0\\ 0& 0& s_{15}^{*}& 0& 0& 0& s_{14}^{*}& 0& \cdots & 0& 0& s_0^{*}& 0\\ 0& 0& 0& s_{15}^{*}& 0& 0& 0& s_{14}^{*}& \cdots & 0& 0& 0& s_0^{*}\end{array}\right]$ $\mathrm{and}$ $A^H=\left[\begin{array}{ccccccccccccc}{s}_0& 0& 0& 0& s_1& 0& 0& 0& \cdots & s_{15}& 0& 0& 0\\ 0& s_0& 0& 0& 0& s_1& 0& 0& \cdots & 0& s_{15}& 0& 0\\ 0& 0& s_0& 0& 0& 0& s_1& 0& \cdots & 0& 0& s_{15}& 0\\ 0& 0& 0& s_0& 0& 0& 0& s_1& \cdots & 0& 0& 0& s_{15}\\ s_{15}& 0& 0& 0& s_0& 0& 0& 0& \cdots & s_{14}& 0& 0& 0\\ 0& s_{15}& 0& 0& 0& s_0& 0& 0& \cdots & 0& s_{14}& 0& 0\\ 0& 0& s_{15}& 0& 0& 0& s_0& 0& \cdots & 0& 0& s_{14}& 0\\ 0& 0& 0& s_{15}& 0& 0& 0& s_0& \cdots & 0& 0& 0& s_{14}\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋰& ⋮& ⋮& ⋮& ⋮\\ s_1& 0& 0& 0& s_2& 0& 0& 0& \cdots & s_0& 0& 0& 0\\ 0& s_1& 0& 0& 0& s_2& 0& 0& \cdots & 0& s_0& 0& 0\\ 0& 0& s_1& 0& 0& 0& s_2& 0& \cdots & 0& 0& s_0& 0\\ 0& 0& 0& s_1& 0& 0& 0& s_2& \cdots & 0& 0& 0& s_0\end{array}\right]$
A is a 128×64 matrix; and A^H is the Hermitian (complex-conjugate) transpose of the A matrix. S₀ . . . S₁₅ are the symbols of the training white training preamble subsequence (in order), and “*” denotes complex conjugation. Note that (A^H.A)^−I is the 64×64 identity matrix (I₆₄) multiplied by the constant 1/(2*L_trn). In the invention, L_trn is 16 (symbol intervals). Writing out y₁ and y₂ explicitly in terms of the received sample vector y (k_offset is the relative sample index from the start of transmission): $\begin{array}{c}{e}_1=\left[\left(2·L_{\mathrm{trn}}\right)·I_{128}-A·A^H\right]·\left[\begin{array}{c}y\left[k_{\mathrm{offset}}+N*L_{\mathrm{trn}}\right]\\ y\left[k_{\mathrm{offset}}+N*L_{\mathrm{trn}}+1\right]\\ ⋮\\ y\left[k_{\mathrm{offset}}+3*N*L_{\mathrm{trn}}-1\right]\end{array}\right]\\ e_2=\left[\left(2·L_{\mathrm{trn}}\right)·I_{128}-A·A^H\right]·\left[\begin{array}{c}y\left[k_{\mathrm{offset}}+2*N*L_{\mathrm{trn}}\right]\\ y\left[k_{\mathrm{offset}}+2*N*L_{\mathrm{trn}}+1\right]\\ ⋮\\ y\left[k_{\mathrm{offset}}+4*N*L_{\mathrm{trn}}-1\right]\end{array}\right]\end{array}$
It turns out the matrix ((2−L_trn)−I₁₂₈−A−A^H) is simply the tri-diagonal matrix: $\left(2·L_{\mathrm{trn}}\right)·\left[\begin{array}{ccccccccccccc}1& 0& 0& 0& \cdots & 0& -1& 0& \cdots & 0& 0& 0& 0\\ 0& 1& 0& 0& \cdots & 0& 0& -1& \cdots & 0& 0& 0& 0\\ 0& 0& 1& 0& \cdots & 0& 0& 0& ⋰& ⋮& 0& 0& 0\\ 0& 0& 0& 1& \cdots & 0& 0& 0& \cdots & -1& ⋮& 0& 0\\ 0& 0& 0& 0& ⋰& ⋮& 0& 0& \cdots & 0& -1& ⋮& 0\\ 0& 0& 0& 0& \cdots & 1& ⋮& 0& \cdots & 0& 0& -1& ⋮\\ ⋮& 0& 0& 0& \cdots & 0& 1& ⋮& \cdots & 0& 0& 0& -1\\ -1& ⋮& 0& 0& \cdots & 0& 0& 1& \cdots & 0& 0& 0& 0\\ 0& -1& ⋮& 0& \cdots & 0& 0& 0& ⋰& ⋮& 0& 0& 0\\ 0& 0& -1& ⋮& \cdots & 0& 0& 0& \cdots & 1& ⋮& 0& 0\\ 0& 0& 0& -1& \cdots & 0& 0& 0& \cdots & 0& 1& ⋮& 0\\ 0& 0& 0& 0& ⋰& ⋮& ⋮& ⋮& \cdots & 0& 0& 1& ⋮\\ 0& 0& 0& 0& \cdots & -1& 0& 0& \cdots & 0& 0& 0& 1\end{array}\right]$
So, the noise estimates can be reduced to the following simple calculations:
e₁(k)=y(k+k_offset+N·L_trn)−y(k+k_offset+2·N·L_trn), k=0 . . . N·L_trn−1
e₂(k₁=y(k+k_offset+2·N·L_trn)−y(k+k_offset+3·N·L_trn), k=0 . . . N·L_trn−1
In a proposed embodiment, the error vectors are S0.9 values. If overflow of any intermediate computation occurs, a collision is declared.

[0249] In accordance with the present invention, a method and apparatus is provided for the computation of the variance of each noise estimate. ${\eta }_1=\frac{1}{\left(N·2·L_{\mathrm{trn}}\right)}·\sum _{k=0}^{N·L_{\mathrm{trn}}}\mathrm{mag\_approx}{\left(e_1\left(k\right)\right)}^2$ ${\eta }_2=\frac{1}{\left(N·2·L_{\mathrm{trn}}\right)}·\sum _{k=0}^{N·L_{\mathrm{trn}}}\mathrm{mag\_approx}{\left(e_2\left(k\right)\right)}^2$
For the fixed-point calculations in one proposed embodiment, rounding is used in the right shift (of 7 bits); the output is a 19-bit quantity. However, any datapath width may be used. If η₁<η₂, the η=η₁ and the channel estimate is computed using the 2^nd and 3^rd copies of the training preamble; otherwise η=η₂ and the channel estimate is computed using the 3^rd and 4^th copies of the training preamble. The resulting value q is then clipped to be within η_low and η_high (the low and high noise points). In a proposed embodiment, both of these values are 9-bit “dB” values that are used to control the range of allowable noise variance estimates, i.e.:
η>η_high→η=η_high
η<η_low→η=η_low
If |10*log₁₀(η₁)−10*log₁₀(η₂)|>cd_threshold_—1, then a collision is declared. This test will very rarely pass when a collision has not occurred and catches the case of a colliding signal received more than 16 symbols before or after the start of transmission.

[0250] The last aspect of the collision detection is a unique field match. In accordance with the present invention, a transmitter sends bursts which have a unique source (“SRC”) address. In addition, there are other header fields which may be useful in a unique symbol template. In the following sections, a preferred embodiment, using the “SRC” field as the unique symbol template, is described. However, combinations of other fields, for example, SRC and destination address (“DST”), the “scrambler initialization” (SI) field and the SRC and DST fields, and the SI and SRC fields, may be used. In accordance with the present invention, the SRC field is included in the template. Referring back to FIGS. 6 and 8, the transmitted burst (frame) format is illustrated. “DA” and “SA” correspond to “DST” and “SRC” in the remaining text. The SRC sample template (as distinguished from the SRC symbol template) is a sequence of sample values at four times the symbol rate (T/4) which spans the 24 symbols (12 bytes) of the source address and 4 additional symbols of “guard” following the SRC field. The “guard” portion accounts for the precursor of the channel impulse response. If only the SRC field is considered unique (as in the preferred embodiment), the SRC sample template is computed as the linear convolution of the 9^th symbol of the DST field through the four symbols following the SRC field with the channel estimate. Other sample templates are possible, including any which are generated as the linear convolution of a unique symbol template and the channel estimate. The channel estimate is computed either from the 2^nd and 3^rd or from the 3^rd and 4^th copies of the preamble, as described above. In the preferred embodiment, the linear convolution is computed in three pieces, and the three components of the template are summed to produce the result. The first component, the destination symbol component, is computed as follows (63×63 matrix by 63×1 column vector): $y_{\mathrm{DST}}=\left[\begin{array}{ccccccccccccc}{h}_{63}& h_{62}& h_{61}& h_{60}& h_{59}& h_{58}& h_{57}& h_{56}& \cdots & h_3& h_2& h_1& h_0\\ 0& h_{63}& h_{62}& h_{61}& h_{60}& h_{59}& h_{58}& h_{57}& \cdots & h_4& h_3& h_2& h_1\\ 0& 0& h_{63}& h_{62}& h_{61}& h_{60}& h_{59}& h_{58}& \cdots & h_5& h_4& h_3& h_2\\ 0& 0& 0& h_{63}& h_{62}& h_{61}& h_{60}& h_{59}& \cdots & h_6& h_5& h_4& h_3\\ 0& 0& 0& 0& h_{63}& h_{62}& h_{61}& h_{60}& \cdots & h_7& h_6& h_5& h_4\\ 0& 0& 0& 0& 0& h_{63}& h_{62}& h_{61}& \cdots & h_8& h_7& h_6& h_5\\ 0& 0& 0& 0& 0& 0& h_{63}& h_{62}& \cdots & h_9& h_8& h_7& h_6\\ 0& 0& 0& 0& 0& 0& 0& h_{63}& \cdots & h_{10}& h_9& h_8& h_7\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋰& ⋮& ⋮& ⋮& ⋮\\ 0& 0& 0& 0& 0& 0& 0& 0& \cdots & h_{63}& h_{62}& h_{61}& h_{60}\\ 0& 0& 0& 0& 0& 0& 0& 0& \cdots & 0& h_{63}& h_{62}& h_{61}\\ 0& 0& 0& 0& 0& 0& 0& 0& \cdots & 0& 0& h_{63}& h_{62}\\ 0& 0& 0& 0& 0& 0& 0& 0& \cdots & 0& 0& 0& h_{63}\end{array}\right]·\left[\begin{array}{c}0\\ 0\\ 0\\ s_{\mathrm{dst}}\left(9\right)\\ 0\\ 0\\ 0\\ ⋮\\ s_{\mathrm{dst}}\left(23\right)\\ 0\\ 0\\ 0\end{array}\right]$
The “guard” symbol component is computed as follows (16×16 matrix by 16×1 column vector): $y_{\mathrm{GRD}}=\left[\begin{array}{cccccc}{h}_0& 0& 0& 0& \cdots & 0\\ h_1& h_0& 0& 0& \cdots & 0\\ h_2& h_1& h_0& 0& \cdots & 0\\ h_3& h_2& h_1& h_0& \cdots & 0\\ ⋮& ⋮& ⋮& ⋮& ⋰& ⋮\\ h_{15}& h_{14}& h_{13}& h_{12}& \cdots & h_0\end{array}\right]·\left[\begin{array}{c}{s}_{\mathrm{rsv}}\left(0\right)\\ 0\\ 0\\ 0\\ ⋮\\ s_{\mathrm{rsv}}\left(3\right)\\ 0\\ 0\\ 0\end{array}\right]$
The source symbol component is computed as follows (112×96 matrix by 96×1 column vector): $y_{\mathrm{SRC}}=\left[\begin{array}{cccccccccccc}{h}_0& 0& 0& 0& 0& 0& 0& \cdots & 0& 0& 0& 0\\ h_1& h_0& 0& 0& 0& 0& 0& \cdots & 0& 0& 0& 0\\ h_2& h_1& h_0& 0& 0& 0& 0& \cdots & 0& 0& 0& 0\\ h_3& h_2& h_1& h_0& 0& 0& 0& \cdots & 0& 0& 0& 0\\ h_4& h_3& h_2& h_1& h_0& 0& 0& \cdots & 0& 0& 0& 0\\ h_5& h_4& h_3& h_2& h_1& h_0& \cdots & \cdots & 0& 0& 0& 0\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋰& ⋮& ⋮& ⋮& ⋮& ⋮\\ h_{63}& h_{62}& h_{61}& h_{60}& h_{59}& h_{58}& \cdots & h_0& 0& 0& 0& 0\\ 0& h_{63}& h_{62}& h_{61}& h_{60}& h_{59}& \cdots & h_1& h_0& 0& 0& 0\\ 0& 0& h_{63}& h_{62}& h_{61}& h_{60}& \cdots & h_2& h_1& h_0& 0& 0\\ ⋮& ⋮& ⋮& ⋰& ⋰& ⋰& ⋰& ⋰& ⋰& ⋰& ⋰& 0\\ 0& 0& 0& \cdots & h_{63}& h_{62}& h_{61}& h_{60}& \cdots & h_2& h_1& h_0\\ 0& 0& 0& \cdots & 0& h_{63}& h_{62}& h_{61}& \cdots & h_3& h_2& h_1\\ 0& 0& 0& \cdots & ⋮& ⋮& ⋰& ⋮& ⋮& ⋮& ⋮& ⋮\\ 0& 0& 0& \cdots & 0& 0& \cdots & h_{63}& \cdots & h_{18}& h_{17}& h_{16}\end{array}\right]·\left[\begin{array}{c}{s}_{\mathrm{src}}\left(0\right)\\ 0\\ 0\\ 0\\ s_{\mathrm{src}}\left(1\right)\\ 0\\ 0\\ 0\\ ⋮\\ s_{\mathrm{src}}\left(23\right)\\ 0\\ 0\\ 0\end{array}\right]$
The template signal is computed as: $\hat{y}\left(k\right)=\{\begin{array}{c}{y}_{\mathrm{SRC}}\left(k\right)+y_{\mathrm{DST}}\left(k\right),k=0\dots N·L_{\mathrm{trn}}-2\\ y_{\mathrm{SRC}}\left(k\right),k=N·L_{\mathrm{trn}}-1\dots N·L_{\mathrm{src}}-1\\ y_{\mathrm{SRC}}\left(k\right)+y_{\mathrm{GRD}}\left(k-N·L_{\mathrm{trn}}\right),k=N·L_{\mathrm{src}}\dots N·\left(L_{\mathrm{src}}+L_{\mathrm{grd}}\right)-1\end{array}$
Graphically, the template is constructed as set forth in FIG. 64. The SRC match error sequence is then just the 112-point sequence defined by:
e(k)={circumflex over (y)}(k)−(2·L_trn)·y(k+k_offset+N·(4·_—L_trn+L_dst)),
k=0 . . . N·(L_src+L_grd)−1
The template is built in the following order:

• [0251] 1. initialize the template to the negation of the input sample sequence (shifted left by 6 bits)
• [0252] 2. add the y_DST term
• [0253] 3. add the y_GRD term
• [0254] 4. add the y_SRC term
  If overflow of the template accumulator occurs at any point in these calculations, then a collision is declared. The size of the accumulator may vary in this invention, but the preferred embodiment uses r+5 bits, where r is the number of analog-to-digital converter output bits. The signed SRC match error is the input to a magnitude approximation, computed as max(x_j, x_q)+½*min(x_{j, xq}), where x_i is the in-phase component of the complex sample and x_q is the quadrature component, with rounding. Referring to FIG. 65 the maximum over the magnitude of all N*(L_trn+L_grd)=112 error output samples is found; this is called |e_max|. The maximum error between the received SRC field samples and the estimated SRC field samples is compared against a threshold which varies with the noise floor estimate. The datapath widths are those used in the preferred embodiment, but other datapath widths can be implemented in accordance with the present invention. If a “no match” result is returned, a collision occurred. In one embodiment, k_offset is an 8-bit signed value (in units of T/4 samples) that indicates where the hybrid leakage is received relative to the start of transmission. k_offset+76 samples would be the index on which the “start” signal would be asserted if the carrier sense were running. It must be writable from the external interface. In one embodiment, the 20*log10(.) function is implemented with two 16-entry look-up tables, a coarse 20*log10(.) table and a fine 20*log10(.) table. Referring to FIGS. 66a and 66b, the table set forth in FIG. 66a contains unsigned 7.2 values and the table set forth in FIG. 66b contains unsigned 3.2 values. The algorithm is:
• [0255] 1. x=max(x, 2)
• [0256] 2. Find the most significant non-zero bit in the input, x. Call the position of this bit (0 . . . 15) b.
• [0257] 3. d₁=coarse_tbl[b]
• [0258] 4. if b>3, k=(x−2^b)<<(b−4), else k=(x−2^b)>>(4−b).
• [0259] 5. d₂=fine tbl[k]
• [0260] 6. output=d₁+d₂
  The output is in 7.2 format, representing up to 96 dB of dynamic range with up to 0.25 dB resolution.

[0261] Gain Estimation Circuit for Burst Modem

[0262] Now turning to the gain estimation circuit aspect of the present invention, in digital burst modem receiver designs, either an analog-to-digital converter (ADC) sufficient to meet the dynamic range requirements of the signal propagation path is used, or a lower-precision ADC may often be used in conjunction with a variable-gain amplifier. For many applications, e.g. phoneline, powerline, or wireless networking, the dynamic range requirements are large (often greater than 60 dB), because the path propagation loss can vary between 0 dB and 40 to 70 dB. To meet system requirements with the former approach, a very large and expensive ADC would be required. Therefore, designers often choose a lower-precision ADC with a variable-gain amplifier and some control circuit. In accordance with the present invention, a circuit is provided which estimates the required gain from a carefully-designed preamble at the start of a burst (packet). A preamble of M*N symbol duration is presupposed. The preamble is structured so that M identical copies of an N-symbol subsequence are transmitted sequentially. Each N-symbol subsequence has the property of being spectrally white (i.e. nonzero cyclic autocorrelation at only one of the N possible lag values). In accordance with the invention, the start of a burst (packet) is detected at the receiver. This function is usually referred to as “carrier sense”. The circuit set forth herein takes a binary start-of-frame/no-start-of-frame indication from the carrier sense. The circuit in accordance with the present invention has two subcircuits. The first estimates the received signal power over an N-symbol window. This subcircuit runs continuously. The second estimates the required gain to maximize signal-to-noise ratio, given the power estimate, and the binary indication from carrier sense. It runs only after carrier sense has indicated the start of burst, and it ceases operation after it computes a gain code, until the next start of burst indication. The input to the power estimation circuit is a k-bit received signal magnitude value. This value is the output the ADC with little or no frequency-selective (e.g. low-pass or band-pass) filtering. The power accumulator, which is 2*k+log2(L*N) unsigned bits, is initialized to zero. N is the number of symbols in one copy of the preamble, and L is the ADC oversampling factor (sampling frequency divided by symbol frequency). The oversampling factor L is chosen to be sufficiently-large to avoid aliasing. For the first L*N samples after initialization, the square of each new k-bit magnitude value (nk) is added to the accumulator. No values are subtracted from the power accumulator. On and following the (N*L−1)^th sample after initialization, the power accumulator calculation becomes:
pwr_—acc=pwr_—acc+Z_k²−Z_{k−nk−(N*L)}².
A block diagram of a possible embodiment, in which k=7 bits, is shown in FIG. 67. The gain code update is triggered by the start of burst indication from carrier sense. At this point, the upper 2*k bits of the power accumulator (rounded up) are passed to the gain code calculation. The combination of the preamble structure and the power estimation circuit yields a nearly-constant power estimate for any less-than-N-symbol shift of the start of burst indication. This property allows the start of burst indication to be somewhat inaccurate (because of channel characteristics, etc.). The gain control block operates once on every start of burst transition and takes the power estimator output sample (2*k bits) as its input. One commercially-available embodiment provides a control range of 22.5 dB for the variable second-stage amplifier with a step size of roughly 0.75 dB, but many other control ranges and step sizes are possible. There are two programmable tables and a programmable back_off value. The programmable back-off value allows fixed gain variations due to particular implementations and also allows variations in the peak-to-average ratio of the received signal to be tolerated by this circuit without unacceptable saturation of the receiver. The first programmable table, rough_gain_table, is a r0-entry by 10-bit array of codes mapping to very coarse gain values. In one embodiment, it is an 8-entry table with 8-bit values corresponding to gain values of {0, 3, 6, 9, 12, 15, 18, 21, 24} dB. The second table, fine_gain_table, is r1-entry by I1-bit array of codes mapping to a refinement of those coarse values. One embodiment might use a 4-entry by 8-bit array of codes mapping to gain values 0.75 dB, 1.5 dB, 2.25, and 3 dB. The 10-bit back-off value allows for fixed gain variations during system bring-up and peak-to-average ratio variations. There is also a r2-entry by 12-bit sparse fixed table, called the fine_log_map, which maps integers 0 . . . (r2−1) to the corresponding fine_gain_table bin. In one embodiment, this may be a 32-entry by 4-bit sparse fixed table, which maps integers 0 . . . 31 to a corresponding fine_gain_table bin. It could contain the values {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3,3} in ascending order, as an example. The gain control calculation can be summarized in the following steps: Set b to the minimum of 2^(k−1)−1 and the 2*k-bit averaged power input value; Determine the highest nonzero bit position in b; i.e. r=max[floor(log2(b)), log2(r2)]; If r>log2(r2)−1, bin_index=2*k−1−r,b′=bit and (floor(b>>(r−log2(r2))), 31); else bin_index=2*k−1−log₂(r2), b′=1; bin_gain=rough gain table [bin index, step_gain=fine_gain_table[fine_log_map[b′]]; G=max (bin_gain−step_gain−back_off, O). The G output is guaranteed to be an r0-bit quantity. When the carrier sense does not indicate a start-of-burst condition (no signal present at the receiver), G is always set to the nominal gain setting (0 dB). The computed gain code value is used to set the analog front-end variable gain value.

[0263] As seen in FIG. 67, a power estimate is provided. Delay line 4010 is 64 samples deep. 10 bits in phase and quadrature components 4012 go into delay buffer 4010 and into multiplexer 4014. Magnitude approximator 4106 provides a 10 bit output which is provided to bit selector 4018 which takes out 7 bits with rounding. Squaring operation 4020 is then performed to provide a power estimate as output. The power estimate output is provided to demultiplexer 4022. Accumulator 4024 takes the output from the demultiplexer 4024 and provides it to bit selector 4026 which in turn provides an averaged power estimate 4028.

[0264] Rate Negotiation and Rate Selection

[0265] As described above, in accordance with the present invention the dynamically selecting of the encoding of data frames on a network where nodes can transmit frames with various encodings is provided. The encodings may vary several parameters including but not limited to the numbers of bits per symbol, the number of symbols per second, or the frequency band(s) used. A node receiving data frames makes a determination about which encodings are appropriate for use on the channel between the sender and the receiver. Multiple encodings may be selected. The data frame receiver then notifies the data frame sender of the encoding selections, with an indication of the relative usability of the selected encodings, via a control frame. The sender is free to use any of the specified encodings, or may use one not included in the list according to additional selection criteria. The protocol tolerates loss of control frames, and provides a mechanism for retransmission of lost control frames without excessively loading the network. The protocol also provides a mechanism for adaptive selection of the encoding to use for transmission to a group of nodes (a “multicast group”). In particular, a node receiving data frames first gathers statistics from frames sent at any encoding, and extrapolates these statistics to estimate the expected frame error rate of all possible encodings. Using the estimated frame error rates, the data receiving node computes a performance metric for all possible encodings. Using the performance metrics, the data receiving node selects an encoding for use on the channel between the sender and the receiver to maximize network throughput subject to frame error rate constraints.

[0266] With regard to the Rate Negotiation and Selection Algorithms, consider the packet data network, as described hereinabove, where a series of packets P_i, each composed of a fixed length header and a variable length payload, are transmitted from a data sender station, A, to a data receiver station, B. The headers are transmitted using FDQAM modulation at symbol rate S_min, and constellation size bi bits per symbol. The payloads are transmitted using QAM or FDQAM modulation at symbol rate S_i, and constellation size b_i from the sets S, and R, respectively, to maximize network throughput subject to additional constraints, in the presence of time-varying impairments. We assume that there is a mechanism for error detection, but not for error correction. We also assume that there is a mechanism for B to notify A of packet errors, and for A to retransmit such errored packets upon receiving notification from B. The Rate Negotiation and Selection algorithms must operate in dynamic environments, with time varying impairments. Several of these impairments are defined to develop the algorithms in accordance with the present invention:

• • [0267] Channel Frequency Selectivity: Spectral nulls or severe attenuation in isolated portions of the band of interest lead to packet error rate (PER) performance that varies with symbol rate. While we assume that the channel is quasi-static, (fixed for the duration of several transmitted packets), it may change between packets, P_i.
  • [0268] Time Invariant White Noise: Noise at the input to B which has flat Power Spectral Density (PSD) over the band of interest. This impairment is also quasi-static.
  • [0269] Time Varying White Noise: Noise at the input to B, which has flat PSD over the band of interest, but with level changing between packets, P_i, on a time scale similar to the packet duration.
  • [0270] Periodic Impulse Noise: Periodic high amplitude impulses at the input to B.
  • [0271] Colored Noise: Noise at the input to B, which has frequency-dependent PSD over the band of interest. This impairment may be either quasi-static, or vary on a time scale similar to the packet duration.
    The process of selecting (s_i, b_i) is separated into functions performed by the data sender, A, and the data receiver B. B collects statistics on packets received from A, performing a Rate Selection Algorithm, to choose (S_i,desired, b_i,desired). B transmits Rate Request Control Frames (RRCFs) to A, typically using (s_min, b_min), to signal changes in (s_i,desired, b_i,desired). A honors B's requests, changing (s_i, b_i) to (s_i,desired, b_i,desired) in response to RRCFs from B. RRCFs are full, legal frames which are treated the same as data frames by the MAC layer. They may be sent at a different priority than best-effort data frames to provide faster adaptation. RRCFs are sent when node B selects a desired rate which differs from the current rate, with some backoff algorithm to prevent flooding the network with rate change requests and to allow time for rate info to arrive and get processed at A.

[0272] Various backoff algorithms may be employed including: (1) truncated binary exponential backoff (BEB) with backoff based on received frame count, (2) truncated BEB with backoff based on time weighted truncated backoff (based on received frame count or time) where the backoff function is dependent on the desired and current payload encoding rates, and need not be a binary exponential function.

[0273] Rate Selection refers to the algorithm by which B chooses (S_i,desired, b_i,desired). Each of the algorithms presented use some or all of the following input statistics upon receiving packet P_i, (squared error refers to squared error refers to squared decision point error): Header rate, (s_min,b_min);Header error indicator, X_hdr,i,ε(0,1), O indicates error-free header, 1 indicates header error; Header sum of squared error, ε_hdr,i; Header maximum squared error, E_hdr,1; Header length symbols), n_hdr; Payload rates, (S₁, b₁); Payload error indicator, X_hdr,iε{0,1}, 0 indicates error-free payload, 1 indicates payload error; Payload sum of squared error, ε_pld,i; Payload maximum squared error, E_pdl,i; Payload length (symbols), n_pld,i; FSE power for each symbol rate in S, P_FSE,s,i, and Normalized, per-symbol ISI power estimate for each symbol rate in S, P_ISI,s,i. Given these input statistics, each algorithm maintains state variables, performing computations based on the input statistics and state variables, first to select the new desired constellation size from R_s for each symbol rate in S, then to select the new desired symbol rate from all those in S. Two algorithms are presented, requiting different amounts of state storage and computation: (1) Mean Squared Error Algorithm and (2) Maximum Squared Error Algorithm. For the purpose of constellation size selection, we initially assume that only a single symbol rate, s, is under consideration, and that s_i=x for all i.

[0274] With regard to the Mean Squared Error Algorithm, error rates of candidate constellations are estimated, selecting constellation to maximize throughput subject to maximum length packet, maximum PER constraint. If we assume that: probability of symbol error is independent from symbol to symbol, hence:
Noise is additive, white, and Gaussian, hence: $\mathrm{SER}\left(\mathrm{SNR},b\right)\equiv \{\begin{array}{cc}2·Q\left(\sqrt{2·\mathrm{SNR}/b}\right)·\left(1-\frac{1}{2}Q\left(\sqrt{2·\mathrm{SNR}/b}\right)\right)& b=2,\mathrm{QAM}\\ 2·Q\left(\sqrt{2·\mathrm{SNR}}·\sin \left(\pi /2^b\right)\right)& b=3,\mathrm{PSK}\\ 1-{\left(1-2·Q\left(\sqrt{3·1/2^{b-1}·\mathrm{SNR}}\right)\right)}^2& b>3,\mathrm{odd},\mathrm{QAM}\\ 1-{\left(1-2·\left(1-1/\sqrt{2^b}\right)·Q\left(\sqrt{3·1/2^{b-1}·\mathrm{SNR}}\right)\right)}^2& b>3,\mathrm{even},\mathrm{QAM}\end{array}\mathrm{where}:Q\left(x\right)=\frac{1}{2\pi }{\int }_x^{\infty }{e}^{-\frac{x^2}{2}}dx$
(see J. G. Proakis, Communications Systems Engineering, section 9.2-9.3, 1994). Then we can precompute SNR thresholds, SNR_min,b for each constellation size b in R, such that: PER(SNR_min,b)=PER_max. Hence, PER<PER_max for SNR>SNR_min,b is monotonically increasing with b. However, in the event that either the independent SER assumption or the white noise assumption are invalid, SNR_min,b is computed by different means, such that PER<PER_max is still satisfied for SNR>SNR_min,b. Following each received packet p_i, with error-free header, X_hdr,i=0, and error free payload, X_pld,i=0, an SNR estimate, {overscore (SNR)}_i is computed. A sliding-window average of length N is used to bound maximum response time to N received packets, so state is needed to store the last N−1 values of ε_hdr, ε_pld, and n_pld: ${\stackrel{\_}{\mathrm{SNR}}}_i\equiv E_{s,b_{\min }}·\left(\frac{N·n_{\mathrm{hdr}}+\sum _{j=i-\left(N-1\right)}^i{n}_{\mathrm{pld},j}}{\sum _{j=i-\left(N-1\right)}^i\left({\varepsilon }_{\mathrm{hdr},j}+{\varepsilon }_{\mathrm{pld},j}\right)}\right)$

• • [0275] where E_s,bmin is the mean energy per symbol for constellation size b_min.
    If the implementation is memory constrained, a single-pole average is used and state is only needed to store the last value of the error average, {overscore (ε)}_i−1: $\begin{array}{c}{\stackrel{\_}{\varepsilon }}_{i,\mathrm{hdr}}\equiv {\stackrel{\_}{\varepsilon }}_{i-1}·{\left(1-\frac{1}{\tau }\right)}^{n_{\mathrm{hdr},i}}+\left(\frac{{\varepsilon }_{\mathrm{hdr},i}}{n_{\mathrm{hdr},i}}\right)·\left(1-{\left(1-\frac{1}{\tau }\right)}^{n_{\mathrm{hdr},i}}\right)\\ {\stackrel{\_}{\varepsilon }}_i\equiv {\stackrel{\_}{\varepsilon }}_{i,\mathrm{hdr}}·{\left(1-\frac{1}{\tau }\right)}^{n_{\mathrm{pld},i}}+\left(\frac{{\varepsilon }_{\mathrm{pld},i}}{n_{\mathrm{pld},i}}\right)·\left(1-{\left(1-\frac{1}{\tau }\right)}^{n_{\mathrm{pld},i}}\right)\\ {\stackrel{\_}{\mathrm{SNR}}}_i\equiv E_{s,b_{\min }}·{\stackrel{\_}{\varepsilon }}_i^{-1}\end{array}$
    where τ is a time constant describing the weighting of new measurements in the average. Note that the implementation above inherently weights payload measurements more strongly that header measurements. In cases where it is desirable to place stronger weight on header measurements, the following substitutions are made for n_hdr and n_pld,i: n′_hdr>n_hdr and n′_pld,i<n_pld,i. Note that the power and multiply operations above can be implemented with a lower accuracy fixed precision approach, without significant performance impact. Following each received packet P_i, {overscore (SNR)}_i is compared to the threshold set SNR_min,b to choose the new constellation size, b_i+1,desired: $\begin{array}{c}{b}_{i+1,\mathrm{up}}=\underset{\mathrm{b\epsilon B}}{\max }\left(b\right),\mathrm{subject}\mathrm{to}\stackrel{\_}{{\mathrm{SNR}}_i}>{\mathrm{SNR}}_{\min ,b}+\Delta \\ b_{i+1,\mathrm{down}}=\underset{\mathrm{b\epsilon B}}{\max }\left(b\right),\mathrm{subject}\mathrm{to}\stackrel{\_}{{\mathrm{SNR}}_i}>{\mathrm{SNR}}_{\min ,b}\\ b_{i+1,\mathrm{desired}}=\max \left(b_{i+1,\mathrm{up}},\min \left(b_{i,\mathrm{desired}},b_{i+1,\mathrm{down}}\right)\right)\end{array}$
    The offset, Δ, provides decision stability when {overscore (SNR)}_i has value near a threshold SNR_min,b.