p1.py

# simple error correcting code
# assume that data is transmitted over a channel which
# sometimes corrupts the data stream
#
# for example, if we sent the bits 10110011
# we might receive 10110010 on the other side
#
# Consider a channel which has a 1% chance of incorrectly transmitting each bit
# that is sent.
# Additionally, assume messages we send contain 100 bits.
#
# What is probability that a message is corrupted?
# It will simply be the probability that any bit is corrupted (don't worry too
# much about this).
#
# P(bit one corrupted) + P(bit two corrupted) + P(bit three corrupted) ...
# = 0.01 + 0.01 + 0.01 + .... + 0.01 = 0.01 * 100 = 1
#
# So, there's a 100% chance that our 100 bit message will be corrupted going
# over this channel!
#
# One way to solve this problem is to send every bit more than once.
# For example, if we sent every bit 3 times, the message 10110011 would be sent
# as 111000111111000000111111
#
# If the receiver sees "111", it knows with high probility that the sender meant
# to sent "1", and, if we see 010, we can _probably_ guess that the sender meant
# to send "0".
#
# To detemine how many copies of each bit we need to send, we can use the "bit
# error rate" (1% in the example above) for the transmission channel as well as
# a bound for how tolerant we are to data corruption.
#
# So, assuming 1% bit error rate, 100 bit messages, and a requirment that our
# messages have a 90% chance of getting though the channel, how many bits do we
# need to send?
#
# 90% success rate means we have a 10% failure rate.
#
# Looking at a single bit first, assume we send three copies.
# - If all three copies are sent successfully (111), the decoder can decode
#   correctly.
# - If two copies are sent successfully (110, 101, 011), and one error, the
#   decoder decode correctly.
# - If no copies are sent successfully (000), the decoder will report the wrong
#   bit.
#
# So, the failure rate for a single bit is the chance that all three bits flip,
# which would be 0.01 * 0.01 * 0.01 = 0.001 %
#
# Then, the chance of any bit in the message getting flipped would be:
# P(all_three_copies_of_1_fail) + P(all_three_copies_of_bit_2_fail) + ...
#
# Which, for a 100 bit long message gives us:
# 0.00001 * 100 = 0.001 or 0.1 % chance of failure.
#
# This is obviously a great failure rate, but we're using a lot of extra
# resources to attain an error rate that we didn't need!
#
# In this excersize, please implement the following:

def number_of_repeated_bits_required(message_size, bit_error_rate_percent, success_rate_percent):
    """
    Returns the number of bits required to send a message of `message_size` over
    a channel with an error rate of `bit_error_rate_percent`, where the desired
    success rate is `success_rate_percent`
    """
    pass

def decode_message(message_as_list, repeated_bits):
    """
    Decode a message which has been coded using the coding scheme
    """