Generalized near optimal packet encoding
A communication system includes: a transmitter including: an arithmetic decoder configured to generate an output symbol based on input bits and a symbol frequency table that sets frequencies of excluded symbols to 0 and frequencies of allowed symbols to non-zero values, the transmitter being configured to iteratively generate a sequence of restricted packets and an ending state, the sequence of restricted packets excluding instances of the one or more excluded symbols and to transmit the sequence of restricted packets and the ending state on a channel; and a receiver including: an arithmetic encoder configured to compute an output state based on an input state, an input symbol, and the symbol frequency table, the receiver being configured to: supply an ending state received from the channel and the restricted packets to the arithmetic encoder to iteratively generate a final state, and recover a bit sequence from the final state.
1. A transmitter comprising:
a memory configured to store an initial state computed from a bit sequence of an input data packet; and
an arithmetic decoder configured to generate a symbol based on input bits and a symbol frequency table, wherein the symbol frequency table sets frequencies of one or more excluded symbols to 0 and frequencies of one or more allowed symbols to non-zero values,
the transmitter being configured to supply the initial state to the arithmetic decoder as the input bits to iteratively generate a sequence of restricted packets and an ending state, the sequence of restricted packets excluding instances of the one or more excluded symbols, and
the transmitter being configured to transmit the sequence of restricted packets and the ending state on a channel.
2. The transmitter of claim 1 , further comprising:
a packet buffer configured to store the input data packet in reversed sequence.
3. The transmitter of claim 1 , further comprising:
a pseudorandom number generator configured to generate a pseudorandom sequence,
wherein the initial state is computed based on a pseudorandomized data packet computed from the bit sequence of the input data packet and the pseudorandom sequence.
4. The transmitter of claim 3 , further comprising an exclusive-or circuit configured to generate the pseudorandomized data packet by computing an exclusive-or of the pseudorandom sequence and the bit sequence of the input data packet.
5. The transmitter of claim 1 , further configured to update the symbol frequency table to set a frequency of an additional symbol to 0.
6. The transmitter of claim 1 , further configured to update the symbol frequency table to set a frequency of one the one or more excluded symbols to a non-zero value.
7. The transmitter of claim 1 , wherein the arithmetic decoder is an asymmetric numeral systems (ANS) decoder.
8. The transmitter of claim 7 , wherein the ANS decoder is a table ANS decoder.
9. A receiver comprising:
an arithmetic encoder configured to compute a state based on an input state, a symbol, and a symbol frequency table, wherein the symbol frequency table sets frequencies of one or more excluded symbols to 0 and frequencies of one or more allowed symbols to non-zero values,
the receiver being configured to:
supply an ending state received from a channel and a plurality of restricted packets received from the channel to the arithmetic encoder to iteratively generate a final state, the restricted packets excluding instances of the one or more excluded symbols, and
recover a bit sequence from the final state; and
a memory configured to store a recovered data packet computed based on the bit sequence.
10. The receiver of claim 9 , further comprising:
a symbol buffer configured to store the restricted packets in reversed sequence.
11. The receiver of claim 9 , further comprising:
a pseudorandom number generator configured to generate a pseudorandom sequence
wherein the receiver is configured to compute the recovered data packet based on the pseudorandom sequence and the bit sequence.
12. The receiver of claim 11 , further comprising an exclusive-or circuit configured to generate the recovered data packet by computing an exclusive-or of the pseudorandom sequence and the bit sequence.
13. The receiver of claim 9 , further configured to update the symbol frequency table to set a frequency of an additional symbol to 0.
14. The receiver of claim 9 , further configured to update the symbol frequency table to set a frequency of one the one or more excluded symbols to a non-zero value.
15. The receiver of claim 9 , wherein the arithmetic encoder is an asymmetric numeral systems (ANS) encoder.
16. The receiver of claim 15 , wherein the ANS encoder is a table ANS encoder.
17. A communication system comprising:
a transmitter comprising:
a memory configured to store an initial state computed based on a bit sequence of an input data packet; and
an arithmetic decoder configured to generate an output symbol based on input bits and a symbol frequency table, wherein the symbol frequency table sets frequencies of one or more excluded symbols to 0 and frequencies of one or more allowed symbols to non-zero values,
the transmitter being configured to supply the initial state to the arithmetic decoder as the input bits to iteratively generate a sequence of restricted packets and an ending state, the sequence of restricted packets excluding instances of the one or more excluded symbols, and
the transmitter being configured to transmit the sequence of restricted packets and the ending state on a channel;
a symbol buffer configured to store the restricted packets; and
a receiver comprising:
an arithmetic encoder configured to compute an output state based on an input state, an input symbol, and the symbol frequency table,
the receiver being configured to:
supply an ending state received from the channel and the restricted packets to the arithmetic encoder to iteratively generate a final state, the sequence of restricted packets excluding instances of the one or more excluded symbols, and
recover a bit sequence from the final state; and
a memory configured to store a recovered data packet computed based on the bit sequence.
18. The communications system of claim 17 ,
wherein the transmitter further comprises:
a transmitter pseudorandom number generator configured based on a seed value to generate a pseudorandom sequence; and
a transmitter exclusive-or circuit configured to compute an exclusive-or of the pseudorandom sequence and the bit sequence of the input data packet to compute a pseudorandomized data packet, wherein the initial state is computed based on the pseudorandomized data packet and
wherein the receiver further comprises:
a receiver pseudorandom number generator configured based on the seed value to generate the pseudorandom sequence; and
a receiver exclusive-or circuit configured to compute an exclusive-or of the pseudorandom sequence and the bit sequence to compute the recovered data packet.
19. The communications system of claim 17 ,
wherein the transmitter further comprises:
a packet buffer configured to store a bit sequence; and
the symbol buffer, and
wherein the receiver is free of buffers.
20. The communications system of claim 17 ,
wherein the receiver further comprises:
a packet buffer configured to store a bit sequence; and
the symbol buffer, and
wherein the transmitter is free of buffers.
21. The communications system of claim 17 , wherein:
the arithmetic decoder is an asymmetric numeral systems (ANS) decoder, and
the arithmetic encoder is an asymmetric numeral systems (ANS) encoder.
22. The communications system of claim 17 , further configured to update the symbol frequency table at the arithmetic decoder and the arithmetic encoder to set a frequency of an additional symbol to 0.