Error correction code (ECC) decoding architecture design using synthesis-time design parameters

Error correction code (ECC) decoding architecture design using synthesis-time design parameters. An approach is presented herein by which an ECC decoding architecture can be designed using synthesis-time design parameters. The manner presented herein allows for a designer to arrive at an ECC decoding architecture in a more direct, straightforward manner that using prior art means. A number of considerations (e.g., architecture parameters, semi-soft design constraints, parallel implementation, etc.) are initially provided; certain or all of these considerations can be predetermined, determined adaptively, and/or modified during the design process. A designer is provided a means by which a most desirable ECC decoding architecture can be arrived at relatively quickly.

BACKGROUND OF THE INVENTION

1. Technical Field of the Invention

The invention relates generally to devices that include a hard disk drive (HDD); and, more particularly, it relates to management of the various functions that are performed within such devices that include a HDD.

2. Description of Related Art

As is known, many varieties of memory storage devices (e.g., disk drives/HDDs), such as magnetic disk drives are used to provide data storage for a host device, either directly, or through a network such as a storage area network (SAN) or network attached storage (NAS). Typical host devices include stand alone computer systems such as a desktop or laptop computer, enterprise storage devices such as servers, storage arrays such as a redundant array of independent disks (RAID) arrays, storage routers, storage switches and storage directors, and other consumer devices such as video game systems and digital video recorders. These devices provide high storage capacity in a cost effective manner.

When designing devices that include a HDD, there are many considerations to make and oftentimes many cost/benefit/trade-offs that are made to arrive at a final solution. The prior art approaches to making and designing such systems that may include an HDD are typically performed in an ad hoc way, in that, a designer generally considers the overall design and attempts to come up with (ideally) a best overall design. These systems oftentimes include some form of error correction code (ECC) decoding functionality as well, and the design of such ECC decoding functionality can oftentimes be one of the more challenging portions of overall design. In the prior art, there is no general means by which the design of such ECC decoding architectures can be made, including those implemented within devices and systems that include one or more HDDs.

BRIEF SUMMARY OF THE INVENTION

DETAILED DESCRIPTION OF THE INVENTION

A novel approach is presented herein by which an ECC decoding architecture can be designed using synthesis-time design parameters. These synthesis-time design parameters include parameters employed to design the ECC decoding architecture, and they are parameters which are adjusted and modified during the designing of the ECC decoding architecture. Once a final ECC decoding architecture has been converged upon (or decided upon), then these synthesis-time design parameters can then be viewed as ‘hard’ parameters which govern the actual size or area, number of gates, processing, speed, power consumption, etc. of the final ECC decoding architecture that can be implemented in hardware within a device and/or communication device.

The manner presented herein allows for a designer to arrive at an ECC decoding architecture in a more direct, straightforward manner that using prior art means. A number of considerations (e.g., architecture parameters, semi-soft design constraints, parallel implementation, etc.) are initially provided; certain or all of these considerations can be predetermined, determined adaptively, and/or modified during the design process. A designer is provided a means by which a most desirable ECC decoding architecture can be arrived at relatively quickly.

Generally speaking, it is very difficult to determine the best architectural tradeoffs for a set of ECC design constraints prior to starting a design. Even when this task can be accomplished to a sufficient degree (which is not oftentimes possible), the overall design cannot otherwise be fine tuned at the last minute without. Moreover, there is an inherent amount of risk in making architectural design changes later on in the overall design process. For example, state machines and other logic must be changed when doing so, and mistakes can easily be made then. There is substantial effort (e.g., design time, effort, cost, etc.) required to perform any architectural changes in order to meet changing ECC requirements. A substantial amount of time (schedule) is also required to perform architectural changes in order to meet changing ECC requirements.

This novel design approach introduces the use of a variety of ECC architectural design parameters that are elaborated during design synthesis to accomplish a finely tuned ECC architecture. In addition, in some embodiments, a spreadsheet or computer program can be used as analysis tool (e.g., which can be a method, processing module, and/or combo thereof in certain embodiments) to help make tradeoff decisions on design parameter settings. For certain desired embodiments, some of the design requirements for each are listed below:

ECC Design Requirements

The ECC decoder clock should be independent and run at a higher frequency than the channel's symbol read transfer clock.

The design should be made parametric with various synthesis-time parameters in the design to select Galois field ALU parallelism, Chien search parallelism, value computer (divider) parallelism, maximum FCC correction power, etc.

The ECC Galois field math should be made dependant on ECC parameters that include the ECC symbol width, and the primitive polynomial of the Galois field.

Analysis Tool Requirements

The analysis tool must compute the worst-case minimum time between adjacent sectors based on disk drive format overhead variables and a channel data rate variable.

The analysis tool must compute the worst-case maximum ECC on-the-fly correction time based on the above mentioned design parameter settings.

The analysis tool should be able to estimate silicon area consumption (in gates) based on the above mentioned design parameter settings and the ASIC technology being used.

The novel design means presented herein allows the designer to make last-minute tradeoffs between silicon area consumption, FCC performance requirements, maximum system clock frequencies, power consumption, etc. Many benefits are provided by this novel design approach. Though this list is not exhaustive, some of the benefits include (1) ASIC cost and power savings due to efficient silicon area consumption, (2) risk mitigation for design modifications (e.g., the design doesn't change only the parameters) and (3) there is minimal schedule impact due to quick turn-around time for parameterized design modifications, etc.

FIG. 1illustrates an embodiment of a disk drive unit100. In particular, disk drive unit100includes a disk102that is rotated by a servo motor (not specifically shown) at a velocity such as 3600 revolutions per minute (RPM), 4200 RPM, 4800 RPM, 5,400 RPM, 7,200 RPM, 10,000 RPM, 15,000 RPM; however, other velocities including greater or lesser velocities may likewise be used, depending on the particular application and implementation in a host device. In one possible embodiment, disk102can be a magnetic disk that stores information as magnetic field changes on some type of magnetic medium. The medium can be a rigid or non-rigid, removable or non-removable, that consists of or is coated with magnetic material.

Disk drive unit100further includes one or more read/write heads104that are coupled to arm106that is moved by actuator108over the surface of the disk102either by translation, rotation or both. A disk controller130is included for controlling the read and write operations to and from the drive, for controlling the speed of the servo motor and the motion of actuator108, and for providing an interface to and from the host device.

FIG. 2illustrates an embodiment of an apparatus200that includes a disk controller130. In particular, disk controller130includes a read/write channel140for reading and writing data to and from disk102through read/write heads104. Disk formatter125is included for controlling the formatting of data and provides clock signals and other timing signals that control the flow of the data written to, and data read from disk102. Servo formatter120provides clock signals and other timing signals based on servo control data read from disk102. Device controllers105control the operation of drive devices109such as actuator108and the servo motor, etc. Host interface150receives read and write commands from host device50and transmits data read from disk102along with other control information in accordance with a host interface protocol. In one embodiment, the host interface protocol can include, SCSI, SATA, enhanced integrated drive electronics (EIDE), or any number of other host interface protocols, either open or proprietary that can be used for this purpose.

Disk controller130further includes a processing module132and memory module134. Processing module132can be implemented using one or more microprocessors, micro-controllers, digital signal processors, microcomputers, central processing units, field programmable gate arrays, programmable logic devices, state machines, logic circuits, analog circuits, digital circuits, and/or any devices that manipulates signal (analog and/or digital) based on operational instructions that are stored in memory module134. When processing module132is implemented with two or more devices, each device can perform the same steps, processes or functions in order to provide fault tolerance or redundancy. Alternatively, the function, steps and processes performed by processing module132can be split between different devices to provide greater computational speed and/or efficiency.

Memory module134may be a single memory device or a plurality of memory devices. Such a memory device may be a read-only memory, random access memory, volatile memory, non-volatile memory, static random access memory (SRAM), dynamic random access memory (DRAM), flash memory, cache memory, and/or any device that stores digital information. Note that when the processing module132implements one or more of its functions via a state machine, analog circuitry, digital circuitry, and/or logic circuitry, the memory module134storing the corresponding operational instructions may be embedded within, or external to, the circuitry comprising the state machine, analog circuitry, digital circuitry, and/or logic circuitry. Further note that, the memory module134stores, and the processing module132executes, operational instructions that can correspond to one or more of the steps or a process, method and/or function illustrated herein.

Disk controller130includes a plurality of modules, in particular, device controllers105, processing module132, memory module134, read/write channel140, disk formatter125, and servo formatter120that are interconnected via bus136and bus137. The host interface150can be connected to only the bus137and communicates with the host device50. Each of these modules can be implemented in hardware, firmware, software or a combination thereof, in accordance with the broad scope of the present invention. While a particular bus architecture is shown inFIG. 2with buses136and137, alternative bus architectures that include either a single bus configuration or additional data buses, further connectivity, such as direct connectivity between the various modules, are likewise possible to implement the features and functions included in various embodiments.

In one possible embodiment, one or more modules of disk controller130are implemented as part of a system on a chip (SoC) integrated circuit. In an embodiment, this SoC integrated circuit includes a digital portion that can include additional modules such as protocol converters, linear block code encoding and decoding modules, etc., and an analog portion that includes device controllers105and optionally additional modules, such as a power supply, etc. In a further embodiment, the various functions and features of disk controller130are implemented in a plurality of integrated circuit devices that communicate and combine to perform the functionality of disk controller130.

When the drive unit100is manufactured, disk formatter125writes a plurality of servo wedges along with a corresponding plurality of servo address marks at equal radial distance along the disk102. The servo address marks are used by the timing generator for triggering the “start time” for various events employed when accessing the media of the disk102through read/write heads104.

FIG. 3Aillustrates an embodiment of a handheld audio unit51. In particular, disk drive unit100can be implemented in the handheld audio unit51. In one possible embodiment, the disk drive unit100can include a small form factor magnetic hard disk whose disk102has a diameter 1.8″ or smaller that is incorporated into or otherwise used by handheld audio unit51to provide general storage or storage of audio content such as motion picture expert group (MPEG) audio layer 3 (MP3) files or Windows Media Architecture (WMA) files, video content such as MPEG4 files for playback to a user, and/or any other type of information that may be stored in a digital format.

FIG. 3Billustrates an embodiment of a computer52. In particular, disk drive unit100can be implemented in the computer52. In one possible embodiment, disk drive unit100can include a small form factor magnetic hard disk whose disk102has a diameter 1.8″ or smaller, a 2.5″ or 3.5″ drive or larger drive for applications such as enterprise storage applications. Disk drive100is incorporated into or otherwise used by computer52to provide general purpose storage for any type of information in digital format. Computer52can be a desktop computer, or an enterprise storage devices such a server, of a host computer that is attached to a storage array such as a redundant array of independent disks (RAID) array, storage router, edge router, storage switch and/or storage director.

FIG. 3Cillustrates an embodiment of a wireless communication device53. In particular, disk drive unit100can be implemented in the wireless communication device53. In one possible embodiment, disk drive unit100can include a small form factor magnetic hard disk whose disk102has a diameter 1.8″ or smaller that is incorporated into or otherwise used by wireless communication device53to provide general storage or storage of audio content such as motion picture expert group (MPEG) audio layer 3 (MP3) files or Windows Media Architecture (WMA) files, video content such as MPEG4 files, JPEG (joint photographic expert group) files, bitmap files and files stored in other graphics formats that may be captured by an integrated camera or downloaded to the wireless communication device53, emails, webpage information and other information downloaded from the Internet, address book information, and/or any other type of information that may be stored in a digital format.

In a possible embodiment, wireless communication device53is capable of communicating via a wireless telephone network such as a cellular, personal communications service (PCS), general packet radio service (GPRS), global system for mobile communications (GSM), and integrated digital enhanced network (iDEN) or other wireless communications network capable of sending and receiving telephone calls. Further, wireless communication device53is capable of communicating via the Internet to access email, download content, access websites, and provide steaming audio and/or video programming. In this fashion, wireless communication device53can place and receive telephone calls, text messages such as emails, short message service (SMS) messages, pages and other data messages that can include attachments such as documents, audio files, video files, images and other graphics.

FIG. 3Dillustrates an embodiment of a personal digital assistant (PDA)54. In particular, disk drive unit100can be implemented in the personal digital assistant (PDA)54. In one possible embodiment, disk drive unit100can include a small form factor magnetic hard disk whose disk102has a diameter 1.8″ or smaller that is incorporated into or otherwise used by personal digital assistant54to provide general storage or storage of audio content such as motion picture expert group (MPEG) audio layer 3 (MP3) files or Windows Media Architecture (WMA) files, video content such as MPEG4 files, JPEG (joint photographic expert group) files, bitmap files and files stored in other graphics formats, emails, webpage information and other information downloaded from the Internet, address book information, and/or any other type of information that may be stored in a digital format.

FIG. 3Eillustrates an embodiment of a laptop computer55. In particular, disk drive unit100can be implemented in the laptop computer55. In one possible embodiment, disk drive unit100can include a small form factor magnetic hard disk whose disk102has a diameter 1.8″ or smaller, or a 2.5″ drive. Disk drive100is incorporated into or otherwise used by laptop computer52to provide general purpose storage for any type of information in digital format.

FIG. 4is a diagram illustrating an embodiment of a communication system400.

Referring toFIG. 4, this embodiment of a communication system400is a communication channel499that communicatively couples a communication device410(including a transmitter412having an encoder414and including a receiver416having a decoder418) situated at one end of the communication channel499to another communication device420(including a transmitter426having an encoder428and including a receiver422having a decoder424) at the other end of the communication channel499. In some embodiments, either of the communication devices410and420may only include a transmitter or a receiver. There are several different types of media by which the communication channel499may be implemented (e.g., a satellite communication channel430using satellite dishes432and434, a wireless communication channel440using towers442and444and/or local antennae452and454, a wired communication channel450, and/or a fiber-optic communication channel460using electrical to optical (E/O) interface462and optical to electrical (O/E) interface464)). In addition, more than one type of media may be implemented and interfaced together thereby forming the communication channel499.

The signals employed within this embodiment of a communication system400can be Reed-Solomon (RS) coded signals, LDPC (Low Density Parity Check) coded signal, turbo coded signals, turbo trellis coded modulation (TTCM), or coded signal generated using some other error correction code (ECC). Any of a very wide variety of applications that employ ECC coding can benefit from various aspects of the invention, including any of those types of communication systems depicted inFIG. 4. Moreover, other types of devices and applications that employ ECC coding (e.g., including those employing some type of HDD or other memory storage means) can also benefit from various aspects of the invention.

FIG. 5illustrates an embodiment of an apparatus500that is operable to design an error correction code (ECC) decoding architecture using synthesis-time design parameters. The apparatus500includes a processing module520, and a memory510. The memory510is coupled to the processing module, and the memory510is operable to store operational instructions that enable the processing module520to perform a variety of functions. The processing module520is operable to perform the appropriate processing to arrive at and/or assist in the design of an ECC decoding architecture based on one or more architecture parameters using any of the approaches presented herein.

If desired in some embodiments, the ECC decoding architecture can be provided from the apparatus500to a communication system540that is operable to employ and perform error correcting coding using that ECC decoding architecture. The parity check matrix of the LDPC code can also be provided from the apparatus500to any of a variety of devices or communication devices530implemented within the communication system540as well. The device or communication device530can include a HDD532in certain embodiments. This way, a completely integrated means is provided by which the FCC decoding architecture can be constructed and provided to and implemented as part of a device or communication device that employs that ECC decoding architecture. If desired, the apparatus520can be designed to generate multiple FCC decoding architectures corresponding to multiple needs and/or desired as well. In some embodiments, the apparatus520can selectively provide different information (corresponding to different FCC decoding architecture) to different communication devices and/or communication systems. That way, different communication links between different communication devices can employ different error correcting coding. Clearly, the apparatus520can also provide the same information (corresponding to a singular FCC decoding architecture) to each of different communication devices and/or communication systems as well without departing from the scope and spirit of the invention.

FIG. 6illustrates an alternative embodiment of an apparatus600that is operable to design an error correction code (FCC) decoding architecture using synthesis-time design parameters. The apparatus600includes a processing module620, and a memory610. The memory610is coupled to the processing module, and the memory610is operable to store operational instructions that enable the processing module620to perform a variety of functions. The processing module620(serviced by the memory610) can be implemented as an apparatus capable to perform any of the functionality of any of the various modules and/or functional blocks described herein. For example, the processing module620(serviced by the memory620) can be implemented as an apparatus capable to perform LDPC code construction and processing of an LDPC coded signal using any of the various embodiments described herein. The processing module620is operable to perform the appropriate processing to generate at least one LDPC matrix corresponding to at least one LDPC code using any of the approach presented herein.

If desired in some embodiments, the apparatus600can be any of a variety of devices or communication devices630, or any part or portion of any such device or communication device630. The device or communication device630can include a HDD632in certain embodiments. Any such communication device that includes the apparatus600can be implemented within any of a variety of communication systems640as well. It is also noted that various embodiments of design of ECC decoding architecture presented herein, and equivalents thereof, may be applied to many types of communication systems and/or communication devices.

FIG. 7illustrates an embodiment of a method700for designing an error correction code (ECC) decoding architecture using synthesis-time design parameters.

The method700begins by receiving a plurality of architecture parameters as shown in a block710. This plurality of architecture parameters can be predetermined, adaptively determined, and/or provided using some other means). The method700then continues by selecting a first plurality of semi-soft design constraints based (at least in part) on the plurality of predetermined architecture parameters as shown in a block720. It is noted that some examples of semi-soft design constraints can be found with reference toFIG. 13. In other words, based on the plurality of architecture parameters, the first plurality of semi-soft design constraints is then determined; some of the plurality of architecture parameters direct the vales of the plurality of semi-soft design constraints; others of the plurality of semi-soft design constraints may be determined independent of the plurality of architecture parameters in some embodiments.

The method700then continues by selecting a first parallel implementation of a plurality of processing modules employed within the ECC decoding architecture as shown in a block730. In some embodiments, this first parallel implementation of the plurality of processing modules is a least parallel implementation of the plurality of processing modules. The plurality of processing modules can include a number of different processing modules including one or more arithmetic logic units (ALUs) which can be implemented (if desired) as Galois field ALUs, specifically designed mathematical processing modules such as dividers, and/or Chien search modules, etc.

The method700then continues by generating a first version of the ECC decoding architecture based on the first plurality of semi-soft design constraints and the first parallel implementation of a plurality of processing modules as shown in a block740. The method700(or other methods performed in accordance with certain aspects of the invention) can involve generating multiple versions of the ECC decoding architecture, and one or more of the plurality of architecture parameters and/or the plurality of semi-soft design constraints can be modified during the design process to generate the multiple versions of the ECC decoding architecture.

The method700then continues by determining whether the first ECC decoding architecture meets a time constraint as shown in a decision block750. This time constraint can be a time required by the ECC decoding architecture to perform correction of a maximum number of errors within a coded signal that is being decoded or to be decoded. Along the lines, some of the limiting factors to determine whether or not the ECC decoding architecture can perform correction of the maximum number of errors within the period of time include sector transfer time (e.g., the time needed to transfer a sector of data to or from the media of an HDD), a maximum transfer data rate (e.g., the maximum speed at which bits can transferred to or from the media of an HDD), the format of data (e.g., the size of preambles within the data), the relationships between various sub-system clocks (e.g., the relationships between the channel sub-clock which governs the rate at which data is transferred through the channel of an HDD, the sub-clock employed by the ECC sub-system within the device, and/or other sub-clocks within the device).

If it is determined that the first ECC decoding architecture meets the time constraint in the decision block750, then the method700operates by employing the first version of the ECC decoding architecture to design at least a portion of a device that is operable to decode the coded signal. In some embodiments, the device is a communication device that is operable to communicate with other communication devices and/or communication networks. In other embodiments, the device is a device is a stand-alone device that does not perform communication with other devices.

Alternatively, if it is determined that the first ECC decoding architecture does not meet the time constraint in the decision block750, then the method700operates by selecting a second plurality of semi-soft design constraints based on the plurality of predetermined architecture parameters as shown in a block760. In this situation, the method700then continues by selecting a second parallel implementation of the plurality of processing modules employed within the ECC decoding architecture as shown in a block770. The method700then continues by generating a second version of the ECC decoding architecture based on the second plurality of semi-soft design constraints and the second parallel implementation of the plurality of processing modules as shown in a block780. The method700then continues by employing the second version of the ECC decoding architecture to design at least a portion of the device that is operable to decode the coded signal as shown in a block790.

FIG. 8illustrates an alternative embodiment of a method800for designing an ECC decoding architecture using synthesis-time design parameters.

The method800begins by receiving architecture parameters as shown in a block810. Analogous to the previous embodiment, these architecture parameters can be predetermined, adaptively determined, and/or provided using some other means). The method800then continues by selecting current semi-soft design constraints based (at least in part) on the architecture parameters as shown in a block820. In other words, based on the architecture parameters, the current semi-soft design constraints is then determined; some of the architecture parameters direct the current values of the semi-soft design constraints; others of the current values of the semi-soft design constraints may be determined independent of the architecture parameters in some embodiments.

The method800then continues by selecting a current parallel implementation of processing modules employed within the ECC decoding architecture as shown in a block830. In some embodiments, this current implementation of the processing modules is a least parallel implementation of the processing modules. The processing modules can include a number of different processing modules including one or more arithmetic logic units (ALUs), specifically designed mathematical processing modules such as dividers, and/or Chien search modules, etc.

The method800then continues by generating a current version of the ECC decoding architecture based on the current semi-soft design constraints and the current parallel implementation of a processing modules as shown in a block840. The method800(or other methods performed in accordance with certain aspects of the invention) can involves generating multiple versions of the ECC decoding architecture, and one or more of the architecture parameters, the semi-soft design constraints, and/or the parallel implementation of the processing modules can be modified during the design process to generate the multiple versions of the ECC decoding architecture. In other words, the current values of each of the one or more of the architecture parameters and/or the semi-soft design constraints can be modified during the design process. In some embodiments, the modification of the parallel implementation of the processing modules involves initially employing a least parallel implementation of the processing modules, then subsequently employing a second least parallel implementation of the processing modules, and so on until a sufficiently desired trade-off is found.

The method800then continues by determining whether the current version of the ECC decoding architecture meets a time constraint as shown in a decision block850. As with a previous embodiment, this time constraint can be a time required by the ECC decoding architecture to perform correction of a maximum number of errors within a coded signal that is being or to be decoded.

If it is determined that the current version of the ECC decoding architecture meets the time constraint in the decision block850, then the method800operates by determining of the current version of the ECC decoding architecture meets a hardware constraint as shown in a decision block860. In some embodiments, this hardware constraint is power consumed by the device, a number of gates employed to implement the device in hardware, or some other hardware constraint.

If it is determined that the current version of the ECC decoding architecture meets a hardware constraint in the decision block860, then the method800operates by employing the current version of the ECC decoding architecture to design at least a portion of a device that is operable to decode the coded signal as shown in a block870. In some embodiments, as mentioned with respect to a previous embodiment, the device is a communication device that is operable to communicate with other communication devices and/or communication networks. In other embodiments, the device is a device is a stand-alone device that does not perform communication with other devices.

However, if it is determined that the current version of the ECC decoding architecture does not meet the time constraint in the decision block850, then the method800operates by then determining whether to modify one, all or some combination thereof of the parallel implementation, the semi-soft design constraints, and/or the originally received architecture parameters as shown in a block855. Based on which of these different considerations are modified, then the method800modifies them ultimately to generate a next version of the ECC decoding architecture.

Similarly, if it is determined that the current version of the ECC decoding architecture does not meet the hardware constraint in the decision block860, then the method800operates by then determining whether to modify one, all or some combination thereof of the parallel implementation, the semi-soft design constraints, and/or the originally received architecture parameters. Based on which of these different considerations are modified, then the method800modifies them ultimately to generate a next version of the ECC decoding architecture. The method800then continues by performing this iterative design processing until the current version of the ECC decoding architecture meets both one or more time constraints and one or more hardware constraints. Then these are met, then the method800operates by employing the current version (e.g., the latest version) of the ECC decoding architecture to design at least a portion of a device that is operable to decode the coded signal as shown in a block870.

FIG. 9illustrates an embodiment of a Reed-Solomon (RS) decoder900. The signals employed within some embodiments of ECC decoding architectures designed in accordance with certain aspects of the invention can be Reed-Solomon (RS) coded signals. Any of a very wide variety of applications that employ RS coding can benefit from various aspects of the invention, including any of those types of communication systems depicted inFIG. 4. Moreover, other types of devices and applications (e.g., including those employ some type of HDD) that employ RS coding can also benefit from various aspects of the invention.

Referring again to the RS decoder900ofFIG. 9, this is a general depiction of an architecture of a RS decoder900, and it is noted that variations and/or modifications thereof may be performed without departing from the scope and spirit of the invention. At a minimum, the RS decoder includes an error locator polynomial generation module920and an error location search module930.

A corresponding RS encoder (not shown in this particular embodiment) takes data (e.g., a block of digital data) and adds redundancy or parity bits thereto thereby generating a codeword (e.g., a codeword to be written, transmitted, and/or launched into a communication channel). This redundancy is generated as a function of the particular RS code employed. Therefore, when the data (after undergoing RS encoding) is provided to some storage media (and/or transmitted via a communication channel and/or launched into a communication channel), and after it is read there from (or received there from), in the undesirable event that any errors occurred during either of these processes (write and/or read or transmit and/or receive), hopefully the number of errors incurred is less than the error correcting capability of the RS code. The number and types of errors that can be corrected depends on the particular characteristics of the RS code employed.

Looking atFIG. 9, a received codeword991can be viewed as being the originally transmitted (or written) codeword plus any errors that have been incurred during the write and/or read processes to the media or during the transmission and/or receipt of a RS coded signal. In addition, such as in the context of HDD applications, perhaps some defects occurred to the actual physical surface of the storage media after the codeword has been written. This received codeword would then also include those incurred errors as well. Generally speaking, the RS decoder900attempts to identify the locations and magnitudes of any errors within the received codeword991(up to the error correcting capability of the RS code) and to correct those errors.

A syndrome calculation module910then processes the received codeword991to generate syndromes992. The operation of the syndrome calculation module910is analogous and similar to the calculation of the redundancy or parity bits within the RS encoding processing. As a function of the RS code employed, a RS codeword has a predetermined number of syndromes that depend only on errors (i.e., not on the actually written or transmitted codeword). The syndromes can be calculated by substituting a predetermined number of roots (as determined by the RS code) of the generator polynomial (employed within RS encoding) into the received codeword991.

An error locator polynomial generation module920then receives these calculated syndromes992. The syndromes992are also passed to an error magnitude calculation module940. The error locator polynomial generation module920can generate the error locator polynomial993using various means, two of which can include the Berlekamp-Massey method922or Euclid method924.

The error locator polynomial993is provided to an error correction module950. The error locator polynomial993is also provided to an error location search module930that is operable to solve for the roots of the error locator polynomial993. One approach is to employ the Chien search function932.

Once the error locations994have been found within the error location search module930(i.e., using the Chien search function932), then the error locations994are provided to the error magnitude calculation module940as well as to the error correction module950. The error magnitude calculation module940finds the symbol error values, and it can employ a known approach such as the Forney method942. Once the error locations994and the error magnitudes995are known, then the error correction module950corrects for them and outputs an estimated codeword996.

With respect to the various processing modules depicted in this diagram as well as others, it is noted that any such processing module may be a single processing device or a plurality of processing devices. Such a processing device may be a microprocessor, micro-controller, digital signal processor, microcomputer, central processing unit, field programmable gate array, programmable logic device, state machine, logic circuitry, analog circuitry, digital circuitry, and/or any device that manipulates signals (analog and/or digital) based on operational instructions. Any such processing module can also be coupled to a memory. Such a memory may be a single memory device or a plurality of memory devices. Such a memory device may be a read-only memory, random access memory, volatile memory, non-volatile memory, static memory, dynamic memory, flash memory, and/or any device that stores digital information. Note that when such a processing module implements one or more of its functions via a state machine, analog circuitry, digital circuitry, and/or logic circuitry, the memory storing the corresponding operational instructions is embedded with the circuitry comprising the state machine, analog circuitry, digital circuitry, and/or logic circuitry. The memory stores, and the processing module executes, operational instructions corresponding to at least some of the steps and/or functions illustrated herein. Alternatively, it is noted that such a processing module may include an embedded memory (or memories) that is operable to assist in the operations analogous to an external memory as described above.

FIG. 10illustrates an embodiment of a decoding architecture1000that employs Berlekamp-Massey decoding processing1000when decoding a RS coded signal. With an architecture designed in accordance with this embodiment, the source (SRC) and destination (DEST) register banks may be reused during error value polynomial (EVP) computation and error location search operation (e.g., during the Chien search operation in accordance with RS decoding processing). As can also be seen, a first plurality of registers1040includes a number of registers as depicted by SRC(1), SRC(2), . . . , and a SRC(n). Polynomial multiplications by Xc-pare accomplished by shifting the source (SRC) register bank as required. Similarly, a second plurality of registers1050includes a number of registers as depicted by DEST(1), DEST(2), and DEST(n). The first plurality of registers1040is operable to store the previous plurality of error location polynomial coefficients (σp(x)), and the second plurality of registers1050is operable to store the current plurality of error location polynomial coefficients (σc(x)). It is also noted that the error location polynomial is based the computed discrepancy which is based, in part, on the syndromes that correspond to a received codeword of the RS coded signal. These syndromes can be stored in a plurality of syndrome registers1010as depicted by SYN(0), SYN(1), . . . , SYN(2n−2), and SYN(2n−1). As can be seen in the diagram, selections of syndromes for discrepancy computations from the plurality of syndrome registers1010is performed by modifying the plurality of syndrome registers1010by wrap-around shifting; this obviates the need to perform multiplexing (e.g., resulting in the saving of gates) or some other form of modification of the plurality of syndrome registers1010to perform the appropriate selection of syndromes.

A plurality of arithmetic logic units (ALUs)1060as depicted by ALU(1), ALU(2), . . . , ALU(n) is operable to perform certain of the calculations required in performing both the error location polynomial generation and error value computation. One of the operations the plurality of ALUs1060performs is the calculation of the values of sigma (σ) (which is based on the values in the first plurality of registers1040, the second plurality of registers1050, and the discrepancy ratio); another one of the operations the plurality of ALUs1060performs is calculation of the discrepancy (which is based on the current sigma iteration and a selected set of syndromes). The discrepancy is generated using a summation of selected syndromes multiplied by corresponding sigma (σ) coefficients. It is noted that in the context of RS decoding, sigma (σ) corresponds to the error location polynomial.

While a plurality of ALUs1060is depicted here, it is noted that as few as a single ALU could be employed sequentially to perform the calculations for each of the corresponding registers. Alternatively, as many as one ALU could be employed for each to perform the calculations for each of the corresponding registers in a fully parallel implementation. Moreover, other number of ALUs can also be employed thereby giving a designer the ability to consider various cost performance trade-offs (e.g., various degrees of parallelism). The degree of parallelism of the ALUs1060is one of the many parameters that can be modified in designing an ECC decoding architecture in accordance with certain aspects of the invention.

When performing the division operations in accordance with generating the error location polynomial in accordance with RS decoding processing, a divider1030employs an inverter and a multiplier. This implementation of division is much cheaper than a single-cycle implemented divider in hardware. One of the reasons that such a divider1030(inverter and multiplier) can be employed herein because of the pipelined arrangement of the decoding processing. For example, the division processing can be afforded slightly more time herein when compared to prior art approaches. This allows for the use of multiple clock cycles to perform the inversion processing, and inversion is much cheaper to implement than a single-cycle implemented divider in hardware. A state machine1020is also employed to coordinate and govern the operations within the decoding processing.

As can be seen, the total number of registers required is slightly more than 4n, where n is the hardware correction power and n≦t; it is noted that t is the ECC software correction power. It is noted that this diagram corresponds to the ECC decoder and does not include the symbol/syndrome computer module. When also including the symbol/syndrome computer module, then total number of registers required would be slightly more than 6n.

In accordance with certain embodiments of decoding of a RS coded signal, it may be required to compute the error value polynomial, which is also referred to as the error magnitude polynomial. If this is a requirement, the value in the DEST register bank (reference numeral1050) may be moved into the SRC register bank (reference numeral1040) so that the error value polynomial can be computed and stored in the DEST register bank. However, some implementations may not require generation of the error value polynomial at all.

The next step is to evaluate the error location polynomial in order to determine the locations of all errors (i.e., perform the error location search operations). This can be performed using a Chien search operation in some embodiments. As mentioned above, the error location search operations (e.g., the Chien search) can be performed using the existing SRC (first plurality of registers1040) and DEST (second plurality of registers1050) register banks. In one embodiment of a HDD application, it is noted that this re-using of the same register banks can be performed provided that an entire ECC correction can be completed within the worst-case sector transfer time.

FIG. 11illustrates an embodiment of error location searching and error magnitude (value) calculation1100in accordance with decoding of a RS coded signal. This embodiment depicts one embodiment of a configuration of the hardware required for performing the error location search operations (e.g., the Chien search) as well as the error magnitude calculation operations (i.e., computing the error values). Analogous to the previous embodiment, it is noted that the division operations in accordance with performing the error value calculation can also employ a divider1130employs an inverter and a multiplier. It is noted that the divider1130can be the same divider1030of the previous embodiment; in other words, the divider1030can be reused for error value computation, if desired.

Again, such an implementation of division is much cheaper than a single-cycle implemented divider in hardware, and the pipelined arrangement of the decoding processing allows for the use of such a divider1130(inverter and multiplier, which can be implemented using a parallel embodiment that includes multiple divider modules that each include inverters and multipliers). In this embodiment, Chien searching is performed, and a Chien search state machine1120(which itself can be implemented using a degree of parallelism that includes more than one Chien search modules as depicted by Chien search module1121, . . . , and Chien search module1122) is employed to coordinate and govern the operations of the error location search operation within the decoding processing.

The error location search operations employ a first plurality of registers1140and a second plurality of registers1150that are employed within the error location polynomial generation operations. The first plurality of registers1140is operable to store a first plurality of evaluated coefficients (e.g., a previous group) corresponding to each error location when processing the error location polynomial (σp(x)), shown as σp(1), σp(2), . . . , σp(n−1) and σp(n). The second plurality of registers1150is operable to store a second plurality of evaluated coefficients corresponding to each error location when processing the error location polynomial (e.g., a current group) (σc(x)), shown as σc(1), σc(2), . . . , σc(n−1), and σc(n).

The additional hardware required to perform a Chien search and compute error values (reference numeral1131) includes constant (α) multipliers (shown as ×α), XOR trees and control logic. The divider and registers can be shared with the error location polynomial generation operations (e.g., the compute ELP function).

It is also noted with respect to this diagram that while (σp(x)) is shown within the first plurality of registers1140, the actual values in these registers are the coefficients of some polynomial that is employed to compute error values at each error location.

It is noted that various degrees of parallelism can be employed when doing error location searching (e.g., when doing Chien searching) in order to reduce evaluation time. Alternative to the embodiment shown in this diagram, multiple alpha (a) multipliers can be employed between the output of the registers and the input of the registers (e.g., multiple “×α” blocks could be employed instead of a singular “×α” block for each register). If this multiple alpha (α) multipliers are employed, then access to each intermediate result (i.e., each result after each alpha (α) multiplier) must be accessible for Chien searching evaluation. For example, multiple XOR trees would then operate on each intermediate result point (which shows 2 alpha (α) multipliers implemented) to allow that point's evaluation in Chien searching as depicted inFIG. 12. Clearly, more than 2 alpha (α) multipliers could also be employed without departing from the scope and spirit of the invention.

FIG. 12illustrates an alternative embodiment of error location searching and error magnitude (value) calculation1200in accordance with decoding of a RS coded signal. This embodiment is analogous to the previous embodiment ofFIG. 11, in that, a divider1230(which can be parallel implemented) and a Chien search state machine1220(which itself can be implemented using a degree of parallelism that includes more than one Chien search modules as depicted by Chien search module1221, . . . , and Chien search module1222) is employed to coordinate and govern the operations of the error location search operation within the decoding processing. However, this embodiment also includes two “×α” blocks (e.g., 2 alpha (α) multipliers) instead of a singular “×α” block for each register and different XOR trees that access the results from each of the “×α” blocks (e.g., alpha (α) multipliers). Clearly, this degree of operating using multiple “×α” blocks (e.g., multiple alpha (α) multipliers) can also be extended which would then necessitate more XOR trees. There may be a point where the trade-off of requiring more XOR trees is undesirable, and the current combination of the number of “×α” blocks (e.g., alpha (a) multipliers) and the number of XOR trees hits a sweet spot in the overall ECC decoding architecture.

Similarly, the trade-offs between various of the other design parameters may also arrive at a sweet spot, in that, the combination of those design parameters may be optimal for a particular design. The novel design approach presented herein allows a designer to arrive at such a sweet spot much quicker and much easier than using prior art design approaches.

FIG. 13illustrates an embodiment of some of the possible design considerations1300employed when designing an FCC decoding architecture using synthesis-time design parameters.

Some of the architecture parameters1310that can be employed include, but are not limited to, a symbol size of a coded signal to be decoded using the FCC decoding architecture as shown in a block1311, a primitive polynomial1312(e.g., as employed within RS coding), a maximum t level (e.g., a number of errors a RS code can correct) as shown in a block1313, a channel data rate1314(e.g., of a read channel as in a HDD application or a communication channel that couples a device that includes the FCC decoding architecture to at least one other device or communication network), a maximum sector size1315(e.g., as in a HDD application), format variables1316(e.g., as in a HDD application), correction time (e.g., the time required by the ECC decoding architecture to correct the maximum number of errors), and/or another architecture parameter as shown in a block1319. It is noted that the maximum sector size1315is oftentimes related to the symbol size in HDD application.

Some of the semi-soft design constraints1320that can be employed include, but are not limited to, a system clock as shown in a block1321and the programmed t level (e.g., a number of errors a RS code can correct) as shown in the block1322; the t level can be considered as either an architecture parameter or a semi-soft design constraint. Other semi-soft design constraints can also be employed as shown in a block1329.

Some of the parallel implementation parameters1330that can be employed include, but are not limited to, the degree of parallelism employed by the ALUs as shown in a block1331, the degree of parallelism employed by the Chien search modules (e.g., in a RS decoding architecture) as shown in a block1332, the degree of parallelism employed by multiple dividers as shown in a block1333, and/or parallel implementation parameter as shown in a block1339. It is noted that the maximum sector size1315is oftentimes related to the symbol size in HDD application.

As stated above, many benefits are provided by this novel design approach. Though this list is not exhaustive, some of the benefits include area and power savings, a means that enables last-minute architectural modifications, as well as the ability to enable better ECC architectural decision making. In addition, it is noted that various end-result parameters (e.g., size or area, and power consumption) can be determined based on the various synthesis runs that have been performed. Moreover, a high degree of granularity can be provided with respect to how individual elements of the ECC decoding architecture affect these end-result parameters (e.g., size or area, and power consumption). Considering area, it can be determined how the number of registers employed correlates to the overall size or area of a device that includes the ECC decoding architecture. Also, depending on the parameters to be employed in various ECC decoding architecture designs, there may be instances where certain embodiments have larger area portions of certain components (e.g., combinatorial logic circuitry such as XOR decision trees). This high degree of granularity also can provide the relationship of how certain design parameters affect the size of the combinatorial logic circuitry, and how this in turn affects the area of the ECC decoding architecture.

Considering power consumption, some of the main contributors to this end-result parameter include the area of the ECC decoding architecture, the number of flops in the ECC decoding architecture, and the clock frequencies of each of the various sub-systems.

If only a few synthesis runs are performed, then modeling (e.g., curve fitting, extrapolation, interpolation, etc.) can be employed to model the correlation between how these individual elements of the ECC decoding architecture affect these end-result parameters. Clearly, the more synthesis runs that are performed, then the modeling can be even more accurate based on empirical data thereby modeling the correlation between how these individual elements of the ECC decoding architecture affect these end-result parameters.

This ability to correlate each of the design parameters (or a selected subset of the design parameters) to the end-result parameters (e.g., size or area, and power consumption) of the ECC decoding architecture allow a designer the ability to perform trade-offs between these various end-result parameters when arriving at a final ECC decoding architecture for a particular application.

It is also noted that there are many variations that can be employed in the design scaling parameters used herein. Also, while some of the embodiments presented herein correspond to RS coding, the principles presented herein can also be extended to designing other types of ECC coding architectures as well. When considering RS codes, other variations besides the RS decoding approach presented herein can also be employed without departing from the scope and spirit of the invention. Along those lines, there are possible variations in the ECC RS encoder/syndrome generator architecture that can also be employed as well. Moreover, there are variations in the analysis tool implementation which can also be employed.

The present invention has been described above with the aid of functional building blocks illustrating the performance of certain significant functions. The boundaries of these functional building blocks have been arbitrarily defined for convenience of description. Alternate boundaries could be defined as long as the certain significant functions are appropriately performed. Similarly, flow diagram blocks may also have been arbitrarily defined herein to illustrate certain significant functionality. To the extent used, the flow diagram block boundaries and sequence could have been defined otherwise and still perform the certain significant functionality. Such alternate definitions of both functional building blocks and flow diagram blocks and sequences are thus within the scope and spirit of the claimed invention.

One of average skill in the art will also recognize that the functional building blocks, and other illustrative blocks, modules and components herein, can be implemented as illustrated or by discrete components, application specific integrated circuits, processors executing appropriate software and the like or any combination thereof.