Method and system for constructing and decoding rateless codes with partial information

Simple SummaryContent extracted from patent full text and abstract with AI.

This invention relates to improving data transmission and storage using forward error correction (FEC) based on rateless codes, particularly when the receiving host already knows part of the data being sent. The proposed method allows efficient transmission of only the unknown (or changed) portions of the data by modifying standard rateless codes, optimizing both the number of symbols sent and the computational effort required for encoding and decoding. Specialized pre-encoding and pre-decoding devices adapt the transmission and recovery process by leveraging partial information already available at the receiver, thus minimizing redundant data transfer.

Use CasesContent extracted from patent full text and abstract with AI.

• Efficient synchronization of distributed databases where receivers may already hold some records
• Incremental software or firmware updates to devices without re-sending the full dataset
• Broadcasting updates to multiple mobile devices with differing versions of a dataset, such as app content, maps, or large files
• Error-resilient data backup and restoration, where only changed data need to be transmitted
• Content delivery networks (CDNs) updating cache nodes with only changed or missing data segments
• Updating blockchain or distributed ledger nodes that may have partial data sets
• Cloud storage solutions sending only differential content during file sync

BenefitsContent extracted from patent full text and abstract with AI.

• Reduces the amount of data that needs to be transmitted, saving bandwidth and time
• Lower computational cost for both encoding at the sender and decoding at the receiver
• Efficient incremental updates—only changed or missing data is sent
• Enables simultaneous broadcast to multiple receivers with differing data subsets, without customizing each transmission
• Lower transmission redundancy, reducing network load
• Applicable to a wide range of symbol sizes, making it versatile for both small and large data blocks
• Compatible with existing rateless codes (e.g., LT, Raptor codes) with minimal modifications
• Enhances robustness and efficiency for lossy networks and variable storage environments

Technical Classifications (CPCs)

Inventors & Applicants

Patent Abstract

In order to improve data transmission using forward error correction based on rateless codes, the invention proposes a method for data transmission from a transmitting host (100) to at least one receiving host (201-20H), wherein the transmitted data is coded for forward error correction, and wherein a pre-defined set X k of symbols, comprising k symbols, is provided at the transmitting host, an individual subset X n h of said pre-defined set X k , comprising n h symbols is provided at each receiving host, said method comprising the steps of a) calculating an encoded symbol by the transmitting host (100) by means of an encoding algorithm based on a pre-defined rateless code depending on the pre-defined set of symbols X k , wherein the encoded symbol is associated with at least one randomly selected symbol of the set X k , and wherein the number of symbols of set X k which are associated with the encoded signal is determined by means of a discrete probability density P* k having k components with a sum of 1, b) transmitting the calculated encoded symbol and the information with which symbols of set X k it is associated to each of the receiving hosts (201-20H), c) decoding the encoded symbol by each receiving host (201-20H) by means of a decoding algorithm based on a pre-defined rateless code and corresponding to said encoding algorithm, and d) repeating steps a) through c) until each receiving host (201-20H) has retrieved from the received encoded symbols the respective difference set of symbols X k - X n h . The invention further proposes a pre-encoding device (110), a pre-decoding device (210) and a transmission system for performing the method.