High-throughput home networking is partially driven by the arrival of DSL lines and cable modems to homes with multiple PCs. HomePlug is the result of a common industry desire to have a single transmission protocol for interconnecting PCs as well as entertainment electronics "wirelessly" over the in-home power lines. The formation of thirteen companies for the HomePlug Powerline Alliance was announced on April 10, 2000. Alphabetically, these founding companies were 3COM, AMD, CISCO, Compaq, Enikia, Intel, Intellon, Motorola, Panasonic, S3 (Diamond Multimedia), Tandy/RadioShack, and TI. The HomePlug group followed a development process for the proposal, the field test, and the selection of a transmission technology similar to the one that has been successfully practiced at HomePNA. Under the sponsorship of RadioShack and Compaq, five residences of different sizes in the Dallas, Texas, area were chosen to field test prototypes of different power line based transmission systems from Adaptive Network, Cogency, Enikia, Intellon, and Itran. Based on field-test performances of these prototypes, the system from Intellon was chosen as the basis for the HomePlug technology, and the decision was finalized on June 5, 2000. Intellon also immediately made the first draft of the HomePlug specification available to member companies. Technical working groups were formed to address issues such as field validation tests, radio emission limits, and coexistence with other power line based systems. Extensive field tests of prototypes conforming to the draft specification were conducted at more than 500 homes during the first quarter of 2001 by many participating member companies. Version 1.0 of the HomePlug specification was subsequently released on June 26, 2001. The HomePlug uses burst mode orthogonal frequency division multiplexing as its basic transmission technique. OFDM is also called Discrete MultiTone (DMT) for the modulation method used by ADSL. OFDM waveforms are generated by the inverse fast Fourier transform (IFFT) converting data bits allocated in many frequency subcarriers to time domain. Each complete cycle of IFFT produces one OFDM symbol. In time domain, each HomePlug OFDM symbol lasts 420 sampling points. With a sampling frequency of 50 MHz, HomePlug's symbol rate is about 119 kHz. HomePlug has an IFFT size of 256 real time points or 128 complex subcarriers in frequency domain. Adjacent subcarriers are therefore 50,000,000/256 = 195312.5 Hz apart. Extended OFDM symbols of 428 points are created by concatenating the last 172 time points in front of the original 256 IFFT time points. Extended symbols are sent over the power line with eight overlapping points between adjacent ones. Among these subcarriers, only 84 subcarriers are utilized creating a signal spectrum of from 4.4 to 20.8 MHz. Eight subcarriers are further turned off to create spectrum notches for avoiding interference to amateur radio bands. The transmission throughput is about 18 Mbps for 76 usable subcarriers each carrying a maximum of 2 bits at a symbol rate of 119 kHz. The net transmission throughput is reduced to about 12.7 Mbps for a Reed-Solomon coding efficiency of 238/254 and a convolution coding efficiency of 3/4. At the robust (ROBO) mode, where transmission conditions are most unfavorable, coding efficiencies become 43/51 and 1/2 while each coded bit occupies four subcarriers resulting in a transmission throughput of about 950 kbps. The HomePlug MAC is a variant of the Carrier Sense Multiple Access with Collision Avoidance protocol. The MAC uses a Virtual Carrier Sense (VCS) mechanism to minimize the number of collisions. Upon receipt of a preamble in the head, the receiver attempts to determine the duration of the packet and wait accordingly. The destination receiver responds with a short acknowledgment packet. If the source fails to receive the acknowledgment, it assumes that a collision has occurred. When packets collide, the HomePlug MAC uses a random back-off algorithm to resolve for the next transmitter. To interconnect entertainment electronics, four different priority levels are included in the HomePlug MAC. Higher priority levels can be assigned to timing-sensitive packets, such as those of music, as compared to PC-oriented data packets. 9.3.1 Highlights of HomePlug TechnologiesThe transmission technology can be explained by following the signal flow of a HomePlug transceiver [4]. Figure 9.15 shows a functional block diagram of a HomePlug transmitter. Data information bits pass through a scrambler, a Reed-Solomon encoder, a convolution encoder, a bit or ROBO interleaver to reach the bit mapper. The convolution encoding might also involve a puncturing process, as explained later, to produce a 3/4 convolution code instead of the 1/2 code. Data information bits can be mapped at either 1 or 2 bits per subcarrier using Differential BPSK (DBPSK) or Differential Quadrature Phase Shift Keying (DQPSK) modulation methods, respectively. After IFFT, cyclic prefixes are created for each extended symbol, and a preamble is inserted in the front of the packet. A shaping filter is also used to minimize out-of-band signal energy. Figure 9.15. Transmitter Block DiagramFor scrambling, data information bits are exclusive ORed with a pseudo-random sequence whose generator polynomial is described by Equation 9.1 This sequence generator is initialized with all ones. The scrambled data bits are then passed through a Reed-Solomon (255, 239, 8) or (255, 247, 4) encoder, where the first number represents the code word size, the second number the message size, and the third the number of correctable errors all in bytes. The generator polynomial is g(x) = (x + a)(x + a2)...(x + a16) for regular transmission modes and g(x) = (x + a)(x + a2)...(x + a8) for the ROBO mode. The convolution encoder thus has an efficiency of 1/2. A puncturing procedure is used to produce the 3/4 convolution encoding. Starting with the first pair of encoded bits, the puncturing procedure takes away an x output bit from the second pair and a y output bit from the third pair and repeats this process for every group of three pairs. To combat the effect of impulse noise, the bit interleaver redistributes data bits among 20 or 40 symbols. The ROBO interleaver introduces a redundancy of 4 in addition to the redistribution function. Data bits are modulated using either DBPSK or DQPSK. For DBPSK, a 0 bit is represented by the same phase as the previous symbol of the same subcarrier, and a 1 bit is represented by a 180° phase reversal of the previous symbol of the same subcarrier. 00, 01, 10, and 11 bit combinations are represented by 0°, 90°, 180°, and 270° phase shifts from the previous symbol of the same subcarrier respectively for DQPSK. Figure 9.16 shows a functional block diagram of a HomePlug receiver. The received signal from the power line is first normalized and digitized by the analog front end (AFE). Timing information is extracted from the preamble and used to drive the Fast Fourier Transform (FFT) and other receiver functions. Complex numbers from FFT are converted to magnitude and phase values for every subcarrier. Channel conditions can be estimated based on the magnitude information during preamble. Under certain bad transmission conditions, some nonusable subcarriers can be identified using corresponding pairs of HomePlug transceivers. Data bits are derived through deinterleaving, depuncturing, Viterbi decoding, Reed-Solomon decoding, and descrambling. Figure 9.16. Receiver Block DiagramFor rate 3/4 convolution-encoded data bits, a zero is inserted after the first pair of xy bits and another is inserted after the second pair of yx bits in the depuncturing process. Bits from a HomePlug convolution encoder depend on their input bit as well as the current state, which is a collection of six previous input bits. Instead of taking bits from each subcarrier as received data bits directly, the Viterbi decoding algorithm exclusive ORs these bits with ideal bit patterns from the current state to all possible next states. These results are accumulated and kept for a few potential paths of different passing states until a path with a significantly low sum of exclusive OR results can be identified. After a correct path is identified, the bit sequence along that path is released as correct received data bits. The Reed-Solomon decoding is carried out in several steps. Error syndromes are first calculated, an error locator polynomial is then formulated, roots of the error-located polynomial are searched, another z polynomial is formed based on error syndromes and coefficients of the error locator polynomial, and error values are calculated using the z polynomial and roots of the error locator polynomial. Errors can then be corrected based on error locations and corresponding error values. Descrambling of Reed-Solomon decoded bits is carried out by exclusive OR of these bits with a pseudo-random sequence whose generator polynomial is the same as that in the transmitter. 9.3.2 CSMA/CA and MIIThe CSMA/CA MAC protocol of HomePlug is similar to that of conventional Ethernet CSMA/CD except for the difference of collision avoidance and collision detection. Because power line attenuation can be severe from time to time, the detection of collisions is not guaranteed. Therefore, the correct reception of each packet needs to be confirmed via a short acknowledgment packet from the destination transceiver. A normal HomePlug packet consists of a delimiter, a frame header, a frame body, and an FCS. Depending on the transmission mode (ROBO or normal), modulation method (DBPSK or DQPSK), coding efficiency (1/2 or 3/4), and the number of available subcarriers, the total number of data bytes within a packet of maximum size varies. When the size of an original data packet exceeds that available within a HomePlug packet, a segmentation process is carried out in the source transceiver to use multiple HomePlug packets to carry the data packet and a reassembly process is carried out in the destination transceiver to put the data packet together based on multiple received HomePlug packets. All segmentation information such as segment length, segment count, and last segment flag are contained in the segment control field of frame header. With the segmentation information, a destination transceiver can reassemble the data packet. Each correct reception of a normal packet is acknowledged by the destination transceiver responding with a short packet. HomePlug transceivers at different neighboring houses can still receive unintended packets if these houses share the same transformer and, therefore, their power lines are physically connected. HomePlug MAC can provide logic separations between different home networks through encryption using 56-bit DES (Data Encryption Standard). Details of this encryption algorithm are defined by the Federal Information Processing Standards (FIPS) Publication 46-3, "Data Encryption Standard," using Cipher Block Chaining (CBC) mode. To participate in a logical home network defined by encryption, a transceiver needs to have a particular network encryption key for that network. A transceiver can obtain a network encryption key by either password or network entry. In other words, a network encryption key can be obtained from a user who knows the local password or by receiving a message encrypted using a previously known key from another transceiver. The use of the standard Ethernet MII is recommended by the HomePlug standards. Transmit Clock (TXCLK) and Receive Clock (RXCLK) rate of 2.5 MHz is recommended in conjunction with the 10-Mbps operation mode. The MII is used as a data channel that transfers data back and forth in units of packets with flow controlled by the carrier sense (CRS) signal. Ethernet-mandated management data registers and extended registers for HomePlug power line transceivers are all accessible via the MDIO/MDCLK. Initially, packets are exchanged between two transceivers using the default ROBO mode. Channel estimation, tone masking, FEC coding rate, and modulation methods are then negotiated between MAC management entities of these two transceivers by setting up right values of proper registers. A specific EtherType has been reserved that allows MAC entities on HomePlug network to exchange this information. MAC management also supports the encryption procedure for establishing a logic home network. 9.3.3 Components of a Simulation ModelAssuming that correct timing information can be recovered from the preamble, the construction of a HomePlug simulation model for performance studies mainly involves putting together functional blocks of Reed-Solomon as well as convolution coding/decoding and FFT/IFFT. These functions, at a command or block level (such as RSENCODE, RSDECODE, CONVENC, VITDEC, FFT, IFFT) can all be found in Communications and Signal Processing tool boxes of MATLAB and Simulink, respectively. To understand them for the purpose of implementation, detailed realization procedures and steps of these functions with HomePlug parameters are discussed in this section. Related MATLAB files are also included at the end of this chapter. Reed-Solomon code is based on nonbinary, 2m, (m = 2, 3, ...) representation of symbols and associated finite field arithmetic operations. For the Reed-Solomon code used in HomePlug, m = 8 and 2m = 256. That means each data symbol is represented by 8 bits and can have digital equivalent values of from 0 to 255. The encoding of Reed-Solomon code is carried out by Galois field multiplication and addition of data symbols and coefficients of the generator polynomial. The multiplication is performed by adding power indexes of two numbers in their power representations, while the addition is executed by bit-wise exclusive OR operation of two numbers in their binary representations. Assuming that the least significant bit is at the rightmost position 1 and the most significant bit is at the most leftmost position 8, power representations with indices of 7, 6, 5, 4, 3, 2, 1, and 0 have only one 1-bit at positions 8 through 1, respectively. For example, a7 and 10000000 are power and binary representations of 128 in a 28 Galois field (GF). The power representation with the highest index in the 28 Galois field is a254. The finite field nature brings a255 back to a0 = 1 (i.e., a255 = a0 = 1). Because each bit in the binary representation of the 28 Galois field carries a weight of ai for i less than 8, the binary presentation can also be expressed in the polynomial format. For example, the binary representation of a8 is 00011101 and the corresponding polynomial format is a4 + a3 + a2 + 1. The binary and polynomial equivalents of any power representations in the 28 Galois field with an index larger than 7 can be found using its primitive polynomial and the fact that the polynomial becomes zero when the variable x is substituted by a. The primitive polynomial for the 28 Galois field is Equation 9.2 Primitive polynomials of other 2m Galois fields can be found in coding reference books [5] and by the MATLAB function GFPRIMFD. Since p(a) = a8 + a4 + a3 + a2 + 1 = 0, we find a8 = a8 + a8 + a4 + a3 + a2 + 1 = a4 + a3 + a2 + 1. Using an = an-1 · a, we can find polynomials for a9 through a11 as a9 = a8 · a = a5 + a4 + a3 + a, a10 = a9 · a = a6 + a5 + a4 + a2, and a11 = a10 · a = a7 + a6 + a5 + a3. For a12 and a13, we again use the primitive polynomial to obtain a12 = a11 · a = a8 + a7 + a6 + a4 = a4 + a3 + a2 + 1 + a7 + a6 + a4 = a7 + a6 + a3 + a2 + 1, and a13 = a12 · a = a8 + a7 + a4 + a3 + a = a4 + a3 + a2 + 1 + a7 + a4 + a3 + a = a7 + a2 + a + 1. A lookup table can thus be established to relate the power index to binary and polynomial representations as partially demonstrated in Table 9.3. Analogous to the conventional log function, this can also be called the inverse log table of the 28 Galois field since it takes the power index as inputs and produces binary as outputs. A log table of the 28 Galois field can also be configured by taking binary as inputs and producing power index as outputs. These tables are necessary for Reed-Solomon encoding and decoding because conversions between different representations happen frequently during alternating multiplication and addition operations. The MATLAB program to generate these tables appears at the end of this chapter. The MATLAB function GFTPLE can also be used to generate these tables. The GF (28) Reed-Solomon code used in HomePlug has a block or code word size of 28 1 = 255 symbols or bytes, or equivalently, 255 x 8 = 2040 bits. For regular operation, a code word consists of 239 message bytes and 16 parity bytes, and the number of correctable error bytes is 8. Parity bytes, c(x), are the remainder of the message polynomial divided by the generator polynomial: Equation 9.3
These 239 coefficients of the message polynomial carry data information at 8 bits each: Equation 9.4 Equation 9.5 The generator polynomial of the Reed-Solomon (255, 239, 8) code has the following product format: Equation 9.6 The generator polynomial can also be represented in the conventional polynomial format as Equation 9.7 This conventional format can be obtained using the MATLAB function RSPOLY. The remainder is obtained by dividing the message polynomial by the generator polynomial. To cancel the first term, m1x254, of the time-shifted message polynomial, we multiply the generator polynomial g(x) with the first message m1 and perform bit-wise exclusive OR operation against the first 17 terms of the message polynomial. Next, we multiply the g(x) by m2 + m1 x g1 to cancel the second term, m2x253, after the first exclusive OR operation. The multiplication and addition process is repeated until the last term, m239x16, is canceled and the remainder is obtained. This repetitive operation can be carried out using the shift register structure as shown in Figure 9.17 where multiplications are carried out by additions of power indices and additions are executed by exclusive OR operations of binary representations of 8 bits. Figure 9.17. A Reed-Solomon Encoder ImplementationCode words are formed by combining message bytes with parity bytes. Equation 9.8 The MATLAB program of this Reed-Solomon encoding process is listed at the end of this chapter [6]. The encoding process can also be accomplished using MATLAB function RSENCODE. The differences are that the RSENCODE command takes in the last element of the input polynomial message vector as the first input and subsequently combines these parity bytes at the beginning of the codeword vector. The Reed-Solomon decoding is carried out in the following steps. Error syndromes are first calculated, an error locator polynomial is then formulated, roots of the error-located polynomial are searched, another z polynomial is formed based on error syndromes and coefficients of the error locator polynomial, and error values are calculated using the z polynomial and roots of the error locator polynomial. Error can then be corrected based on error locations and corresponding error values. Denoting the received message of 255 bytes as r(x) = r1x254 + r2x253 + ... + r254x+ r255, error syndromes are calculated by substituting x with a, a2, ... a16 in the received polynomial to obtain S1 = r(a), S2 = r(a2), ..., S16 = r(a16), respectively. Error syndromes can be represented in either power index or 8-bit binary format. The error locator polynomial, L(x) = 1 + s1 x + ... + svxv, can then be formed using Berlekamp's iterative algorithm as described in the following eight steps, where and 2t = 16 for this application.
These v roots of the error locator polynomial can be found using Chien's search algorithm by substituting x with a, a2, ..., into L(x) to find L(bi) = 0 for i = 1, …, v. The z(x) polynomial is then formed using error syndromes and coefficients of the error locator polynomial as Equation 9.10 These v error values can be found by replacing x in the z(x) polynomial with roots of the error locator polynomial as Equation 9.11 Errors are then corrected based on error locations and corresponding error values. The MATLAB program of this Reed-Solomon decoding process is listed at the end of this chapter [7]. The decoding process can also be accomplished using MATLAB function RSDECODE. Generating x and y bits using the convolution encoder can be based on the current and previous 6 input data bits. These previous 6 input bits also determine the current state and, similarly, the next state is determined by the current and previous 5 input bits. Relationships between input bit, output bits, current state, and the next state are summarized in Table 9.4. This lookup table can be used for encoding to produce x and y outputs based on current state and input bits, but it is more useful for Viterbi decoding [8].
Starting from a known state, either at the beginning of a packet or after a successful determination of a correct path, the Viterbi decoder calculates the total number of different bits compared between the received bits and those leading to next possible states. For HomePlug, the number of received bits as well as those leading to the next states is 2 and the number of next states is also 2 from a current state. After the first comparison, the number of possible current states becomes 2 and each additional comparison of received bits can double the number of possible states. To avoid unnecessary calculations, it is sufficient to maintain only four possible states of lowest accumulated bit difference numbers after multiple comparisons for a HomePlug Viterbi decoder. After a sufficient number of comparisons, the Viterbi decoder selects the state with a significantly lower number of accumulated bit differences as the correct one and releases the bits associated with the path connecting the previous known state to the correct state as the received bit stream. The Viterbi decoding procedure can be described in following steps:
MATLAB programs for HomePlug convolution encoding and Viterbi decoding are listed at the end of this chapter. They are equivalent to MATLAB functions of CONVENC and VITDEC in the Communication toolbox. FFT and IFFT are usually carried out with either a decimation-in-time or decimation-in-frequency algorithm [9]. The decimation-in-time algorithm starts with two-point operations and finishes with an operation of the full FFT size. The decimation-in-frequency algorithm starts with an operation of the full IFFT size and finishes with two-point operations. Either algorithm can be used for FFT or IFFT with the proper definition of the base complex exponent, Each algorithm takes about log2 N stages of operations. To take advantage of zero subcarriers, the decimation-in-time algorithm can be used for IFFT, and the decimation-in-frequency algorithm can be used for FFT for HomePlug. Using the decimation-in-time algorithm, these eight stages of 256-point operations for IFFT can be simplified to four stages of six 32-point operations plus four stages of 256-point operations. Similarly, these eight stages of 256-point operations for FFT can be simplified to four stages of 256-point operations plus four stages of six 32-point operations using the decimation-in-frequency algorithm. |